Explorar Circle STARKs

Nos últimos anos, o design do protocolo STARKs tende a utilizar campos menores. As primeiras implementações do STARKs usavam campos de 256 bits, realizando operações de módulo em grandes números, compatíveis com assinaturas baseadas em curvas elípticas. No entanto, esse design tem baixa eficiência, desperdiçando poder de computação ao processar grandes números. Para resolver esse problema, o STARKs começou a usar campos menores: Goldilocks, Mersenne31 e BabyBear.

Esta transformação aumentou a velocidade de prova. Por exemplo, a Starkware consegue provar 620.000 valores de hash Poseidon2 por segundo em laptops M3. Desde que se confie no Poseidon2 como função de hash, é possível resolver o desafio do desenvolvimento eficiente de ZK-EVM. Como funcionam essas tecnologias? Como se estabelecem as provas em pequenos campos? Este artigo explorará esses detalhes, com especial foco na solução Circle STARKs.

Perguntas frequentes sobre o uso de pequenos campos

Ao criar provas baseadas em hash, uma técnica importante é validar indiretamente as propriedades do polinómio através da avaliação do polinómio em pontos aleatórios. Isso simplifica significativamente o processo de prova.

Por exemplo, suponha que se deseja provar que o polinómio A satisfaz A^3(x) + x - A(ωx) = x^N. O protocolo pode exigir a seleção de coordenadas aleatórias r e provar que A(r) + r - A(ωr) = r^N. Então, retroceda A(r) = c, provando que Q = (A - c)/(X - r) é um polinómio.

Para prevenir ataques, é necessário escolher r após o atacante fornecer A. No campo de 256 bits, isso é muito simples: basta escolher um número aleatório de 256 bits. Mas no campo pequeno, o número de valores r disponíveis é de apenas cerca de 2 bilhões, e embora o trabalho do atacante seja grande, ele ainda pode tentar todas as possibilidades.

Existem duas soluções:

1. Realizar várias verificações aleatórias
2. Campos de extensão

Várias verificações são simples e eficazes, mas apresentam problemas de eficiência. O campo de extensão é semelhante a um plural, mas baseado em um domínio finito. Um novo valor α é introduzido para satisfazer uma certa relação, como α^2 = certo valor. Isso cria uma nova estrutura matemática, que permite operações mais complexas sobre um domínio finito. O domínio de extensão é utilizado apenas quando combinações lineares aleatórias são necessárias; a maior parte das operações ainda é realizada no campo base.

FRI Comum

O primeiro passo para construir um SNARK ou STARK é transformar o problema computacional em uma equação polinomial P(X,Y,Z)=0. A solução deve provar que os valores propostos são polinômios razoáveis e de grau finito. Isso é realizado através da aplicação gradual de combinações lineares aleatórias:

1. Suponha que haja o valor de avaliação do polinômio A, é necessário provar que o grau é < 2^20
2. Considerar B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D é uma combinação linear aleatória de B e C: D=B+rC

B isola os coeficientes pares de A, C isola os coeficientes ímpares. Dado B e C, A pode ser recuperado: A(x) = B(x^2) + xC(x^2). Se o grau de A < 2^20, os graus de B e C são, respetivamente, o grau de A e o grau de A - 1. D, como uma combinação aleatória, deve ter o grau do grau de A.

FRI simplifica a verificação reduzindo a prova do grau do polinômio de d para uma prova de grau d/2. Este processo pode ser repetido várias vezes, cada vez simplificando o problema pela metade. Se a saída de uma fase não corresponder ao grau esperado, essa rodada de verificação falhará.

FRI reduz a ordem do polinómio e o tamanho do conjunto de pontos à metade a cada passo. O primeiro é a chave para o funcionamento do FRI, enquanto o segundo torna o algoritmo extremamente rápido: o custo total de cálculo é O(N) em vez de O(N*log(N)).

Para reduzir gradualmente o domínio, utiliza-se um mapeamento um-para-dois. Esse mapeamento permite reduzir pela metade o tamanho do conjunto de dados e é repetível. Começando com o subgrupo multiplicativo, cada elemento x tem seu múltiplo 2x também no conjunto. Ao elevar o conjunto S ao quadrado, o novo conjunto S^2 mantém a mesma propriedade. Isso permite a redução contínua do tamanho do conjunto de dados até restar apenas um valor.

O módulo do BabyBear faz com que seu maior grupo multiplicativo contenha todos os valores não nulos, com tamanho 2^k-1. Isso é muito adequado para a técnica mencionada, pois pode efetivamente reduzir o grau polinomial através de mapeamentos repetidos. O tamanho do grupo multiplicativo do Mersenne31 é 2^31-1, podendo ser dividido por 2 apenas uma vez, após o que essa técnica não pode ser utilizada.

O domínio Mersenne31 é muito adequado para cálculos em CPU/GPU de 32 bits. Suas características de módulo (, como 2^31-1), permitem que muitas operações utilizem operações de bits eficientes: os resultados acima do módulo podem ser reduzidos por deslocamento. A multiplicação pode ser processada de forma eficiente com instruções específicas da CPU. As operações aritméticas de Mersenne31 são cerca de 1,3 vezes mais rápidas do que as do BabyBear. Se o FRI puder ser implementado no Mersenne31, a eficiência será significativamente aumentada.

Circle FRI

A genialidade dos STARKs em círculo reside no fato de que, dado um número primo p, pode-se encontrar um grupo de tamanho p com uma propriedade semelhante à de um par. Este grupo é composto por pontos que satisfazem condições específicas, como o conjunto de pontos onde x^2 mod p é igual a um determinado valor.

Estes pontos seguem a regra de adição:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Forma dupla: 2*(x,y) = (2x^2 - 1, 2xy)

Estamos focados nos pontos em posições ímpares na circunferência. Primeiro, convergimos todos os pontos para uma linha reta: f0(x) = (F(x,y) + F(x,-y))/2

Em seguida, faça uma combinação linear aleatória para obter o polinômio unidimensional P(x).

A partir da segunda ronda, o mapeamento torna-se: f0(2x^2-1) = (F(x) + F(-x))/2

Esta mapeação reduz o tamanho do conjunto pela metade a cada vez. Cada x representa dois pontos: (x,y) e (x,-y). (x → 2x^2 - 1) é a lei de duplicação de pontos. Vamos converter as coordenadas x dos dois pontos opostos no círculo nas coordenadas x do ponto após a duplicação.

FFTs de Círculo

O grupo Circle também suporta FFT, com uma construção semelhante à do FRI. A principal diferença é que o Circle FFT não processa polinómios estritos, mas sim o espaço de Riemann-Roch: polinómios módulo círculo (x^2 + y^2 - 1 = 0).

Os coeficientes de saída do FFT Circular são uma base específica: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Os desenvolvedores podem praticamente ignorar este ponto. STARKs apenas precisam armazenar os polinómios como um conjunto de valores de avaliação. FFT é utilizado apenas para extensões de baixo grau: dado N valores, gera-se k*N valores do mesmo polinómio.

Cálculo Comercial

Uma operação comum do STARK é realizar operações de divisão em pontos específicos. Por exemplo, a prova de P(x)=y pode ser feita através dos seguintes passos:

1. Cálculo do quociente: Q = (P - y)/(X - x)
2. Provar que Q é um polinómio e não uma fração

No grupo circle STARK, devido à falta de uma função linear de ponto único, são necessárias diferentes técnicas. Pode-se construir uma função tangente, mas ela tem multiplicidade 2 no ponto. Portanto, é necessário avaliar em dois pontos para provar.

Se P for igual a y1 em x1 e igual a y2 em x2, escolhemos a função de interpolação L que é igual nessas duas pontos. Depois, provamos que P-L é zero nesses dois pontos, demonstrando que o quociente Q, obtido ao dividir L por L, é um polinómio.

Polinômio Desaparecido

As equações polinomiais que o STARK tenta provar geralmente têm a forma C(P(x), P(next(x))) = Z(x) · H(x), Z(x) é identicamente zero no domínio de avaliação original.

Na STARK circular, a função correspondente é: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Ordem inversa

A avaliação de polinômios em STARKs geralmente é feita na ordem de bits reversa. Na circle STARKs, a estrutura de dobra é ligeiramente diferente:

• Primeiro passo: (x,y) e (x,-y) emparelhar
• Segundo passo: emparelhar x com -x
• Passos seguintes: emparelhar p e q, de modo que Q^i(p) = -Q^i(q)

Para ajustar a ordem inversa, é necessário inverter cada dígito, exceto o último, usando o último dígito para decidir se os outros devem ser invertidos.

Eficiência

Circle STARKs são muito eficientes. Os cálculos geralmente envolvem:

1. Aritmética nativa: utilizada para lógica de negócios
2. Aritmética nativa: utilizada em criptografia ( como o hash Poseidon )
3. Encontrar parâmetros: método de cálculo geral e eficiente

A chave para a eficiência está em aproveitar ao máximo o espaço de rastreamento computacional. Aqui, o tamanho do campo é 2^31, o desperdício de espaço não é grande. Hashes como Poseidon aproveitam cada bit de cada número em qualquer campo.

Binius alcança uma embalagem de bits mais eficiente ao misturar campos de tamanhos diferentes, mas o custo é uma complexidade conceitual maior. O conceito de Circle STARKs é relativamente simples.

Conclusão

Circle STARKs não é mais complexo para os desenvolvedores do que STARKs. A principal diferença na implementação em relação ao FRI convencional está nas três questões mencionadas acima. Embora a matemática por trás seja complexa, essa complexidade está bem oculta.

Compreender o Circle FRI e os FFTs pode ser uma forma de entender outros FFTs especiais, como os FFTs de domínio binário e os FFTs de curvas elípticas.

Combinando tecnologias como Mersenne31, BabyBear e Binius, estamos nos aproximando do limite de eficiência da camada base dos STARKs. A otimização futura pode se concentrar em:

1. Maximizar a eficiência aritmética de funções de hash e assinaturas, entre outras.
2. Construção recursiva para habilitar mais paralelismo
3. Máquina virtual aritmética para melhorar a experiência do desenvolvedor