Explorar Circle STARKs

Nos últimos anos, a tendência de design do protocolo STARKs tem se voltado para o uso de campos menores. As implementações iniciais do STARKs usavam campos de 256 bits, compatíveis com assinaturas de curva elíptica, mas com eficiência mais baixa. Para aumentar a eficiência, o STARKs começou a usar campos menores, como Goldilocks, Mersenne31 e BabyBear.

Esta transformação aumentou significativamente a velocidade de prova. Por exemplo, a Starkware consegue provar 620.000 hashes Poseidon2 por segundo em um laptop M3. Isso significa que, desde que se confie no Poseidon2 como uma função hash, é possível resolver o problema da ZK-EVM eficiente. Este artigo explorará como essas tecnologias funcionam, com um foco especial na solução Circle STARKs.

Perguntas frequentes sobre o uso de pequenos campos

Em 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 muito o processo de prova.

Por exemplo, o sistema de prova pode exigir a geração de um compromisso do polinômio A, que satisfaça A^3(x) + x - A(ωx) = x^N. O protocolo pode exigir a escolha de coordenadas aleatórias r e provar que A(r) + r - A(ωr) = r^N.

Para prevenir ataques, deve-se escolher r somente após o atacante fornecer A. Isso é simples em campos de 256 bits, mas em campos pequenos há apenas cerca de 2 bilhões de opções para r, o que pode ser quebrado pelo atacante.

Existem duas soluções:

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

Vários testes simples e eficazes, mas pode ser necessário aumentar o número de rondas para melhorar a segurança. O domínio expandido é semelhante ao plural, mas baseado em um domínio finito. Ao introduzir um novo valor α, cria-se uma estrutura matemática mais complexa, oferecendo mais opções.

Regular FRI

O primeiro passo do protocolo FRI é transformar o problema de cálculo em uma equação polinomial P(X,Y,Z)=0. Depois, prova-se que o valor proposto é um polinômio razoável e de grau limitado.

O FRI simplifica a verificação ao reduzir o problema de provar que um polinómio tem grau d para o problema de provar que tem grau d/2. Este processo pode ser repetido várias vezes, reduzindo o problema à metade a cada vez.

Circle FRI

A genialidade dos STARKs em círculo reside no fato de que, para um primo p, é possível encontrar um grupo de tamanho p, com uma característica semelhante à de dois para um. 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 da adição: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

A forma dupla é: 2*(x,y) = (2x^2 - 1, 2xy)

A mapeamento do Circle FRI começa a partir da segunda rodada: f0(2x^2-1) = (F(x) + F(-x))/2

Este mapeamento reduz o tamanho do conjunto pela metade a cada vez, x representa dois pontos: (x, y) e (x, -y). (x → 2x^2 - 1) é a regra de duplicação de pontos.

FFTs de Círculo

O grupo Circle também suporta FFT, e a forma de construção é semelhante à do FRI. No entanto, o objeto tratado pelo Circle FFT é o espaço de Riemann-Roch, e não polinômios estritos.

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

Os desenvolvedores podem praticamente ignorar isso, apenas armazenando o polinômio como um conjunto de valores de avaliação. FFT é principalmente usado para baixa expansão.

Quotienting

No STARK do grupo circle, devido à ausência de funções lineares de ponto único, é necessário utilizar técnicas diferentes para substituir a operação comercial tradicional. Normalmente, é necessário avaliar em dois pontos para provar, adicionando um ponto virtual.

Polinômios desaparecendo

O polinómio de desaparecimento em Circle STARK é: Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Inverter a ordem dos bits

No Circle STARKs, é necessário ajustar a ordem reversa para refletir a estrutura de dobra, ou seja, inverter cada bit, exceto o último, e usar o último bit para decidir se os outros bits devem ser revertidos.

Eficiência

Circle STARKs são muito eficientes, os cálculos geralmente envolvem:

1. Aritmética nativa da lógica de negócios
2. A aritmética nativa da criptografia ( como o hash Poseidon )
3. Encontrar parâmetros

O campo de tamanho 2^31 reduziu o desperdício de espaço. O Binius é superior em termos de tamanhos de campo mistos, mas o conceito é mais complexo.

Conclusão

Os STARKs em círculo não são mais complexos para os desenvolvedores do que os STARKs. Compreender a sua matemática leva tempo, mas a complexidade está bem escondida.

Combinando Mersenne31, BabyBear e tecnologia de campos binários, a eficiência da camada base dos STARKs está próxima do limite. As direções futuras de otimização podem incluir:

• Maximizar a eficiência aritmética de funções hash, etc.
• Construção recursiva para aumentar a paralelização
• Máquina virtual aritmética para melhorar a experiência de desenvolvimento