Explorar Circle STARKs

Circle STARKs é um novo tipo de sistema de prova STARK que utiliza as propriedades especiais dos grupos circulares para construir provas eficientes. Este artigo irá explorar o funcionamento do Circle STARKs e suas vantagens.

Contexto

Nos últimos anos, o design do protocolo STARKs tem tendido a usar campos matemáticos menores, como Goldilocks, Mersenne31 e BabyBear. Essa mudança aumentou significativamente a velocidade de prova; por exemplo, a Starkware consegue provar 620.000 hashes Poseidon2 por segundo em um notebook M3.

Mas o uso de pequenos campos também traz alguns desafios, como garantir a segurança dentro de um espaço de aleatoriedade limitado. O Circle STARKs resolveu esse problema através de um design inteligente.

O princípio fundamental do Circle STARKs

A ideia central dos STARKs de círculo é utilizar a propriedade de mapeamento de dois para um dos grupos circulares. Dado um primo p, podemos encontrar um grupo de tamanho p, que possui características de dois para um semelhantes. Este grupo é composto por todos os pontos que satisfazem x^2 + y^2 = 1 mod p, ou seja, (x,y).

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)

Usando esta mapeamento, podemos construir um sistema de prova semelhante ao FRI, mas a trabalhar em campos menores.

FFTs Circulares

O grupo Circle também suporta operações FFT, mas os objetos tratados não são polinómios no sentido estrito, mas sim o chamado espaço de Riemann-Roch. Isso significa que consideramos qualquer múltiplo de x^2 + y^2 - 1 como zero.

Isto faz com que os coeficientes de saída do Circle FFT sejam diferentes dos do FFT convencional, sendo baseados em uma base específica {1, y, x, xy, 2x^2 - 1, ...}. Mas como desenvolvedores, podemos quase ignorar isso, tratando simplesmente os polinómios como um conjunto de valores de avaliação.

Técnicas especiais do Circle STARKs

comércio de operações

Devido ao fato de o grupo circular não ter funções lineares que possam ser obtidas através de um único ponto, o Circle STARKs utiliza técnicas de operações de quociente diferentes. Provamos isso avaliando em dois pontos, adicionando assim um ponto virtual que não precisa de atenção.

polinômio desaparecido

A forma do polinômio de desaparecimento em STARKs de círculo é:

Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

ordem inversa

Para se adaptar à estrutura de dobra especial do Circle STARKs, precisamos ajustar a ordem reversa dos bits. O método específico é inverter todos os bits, exceto o último, e usar o último bit para determinar se os outros bits devem ser invertidos.

A eficiência do Circle STARKs

Circle STARKs trabalha em campos素 de 31 bits, sendo mais eficiente do que os STARKs de campos grandes. Ele aproveita ao máximo o espaço do campo, reduzindo o desperdício de espaço livre. Embora soluções como a Binius sejam superiores em alguns aspectos, o conceito de Circle STARKs é mais simples.

Conclusão

Circle STARKs oferece aos desenvolvedores uma variante de STARK que é simples em conceito, mas eficiente. Ela equilibra bem eficiência e facilidade de uso, sendo um passo importante no desenvolvimento da tecnologia STARK. No futuro, a otimização do STARK pode se concentrar nas seguintes direções:

1. Maximizar a eficiência aritmética de funções de hash e outros primitivos criptográficos básicos
2. Melhorar a paralelização através da construção recursiva
3. Melhorar a aritmética da máquina virtual para otimizar a experiência do desenvolvedor

A chegada dos STARKs em Círculo nos oferece uma janela para entender e explorar mais tecnologias FFT especiais, impulsionando a tecnologia STARK em direção a uma evolução mais eficiente e prática.