Explorar Circle STARKs

Nos últimos anos, a tendência do design do protocolo STARKs tem sido a de utilizar campos menores. As primeiras implementações de STARKs usavam campos de 256 bits, mas esse design tinha uma eficiência inferior. Para melhorar a eficiência, os STARKs começaram a usar campos menores, como Goldilocks, Mersenne31 e BabyBear.

O uso de pequenos campos pode aumentar significativamente a velocidade da prova. Por exemplo, a Starkware consegue provar 620 mil hashes Poseidon2 por segundo em um notebook M3. No entanto, pequenos campos também trazem novos desafios, como garantir a segurança em um espaço de escolha limitado.

Este artigo irá explorar os Circle STARKs, que são uma nova solução compatível com o campo Mersenne31. Os Circle STARKs resolvem os problemas de segurança trazidos por campos pequenos, operando sobre grupos de pontos em um círculo.

Circle FRI

A ideia central do Circle FRI é definir um grupo de pontos de tamanho p em um círculo, onde este grupo possui a propriedade de mapeamento dois-para-um. Os pontos no grupo satisfazem x^2 + y^2 = 1 (mod p).

O processo de mapeamento do Circle FRI é o seguinte:

1. Primeiro, converta todos os pontos para a linha do eixo x.
2. Realizar combinações lineares aleatórias para obter um polinómio unidimensional P(x)
3. A partir da segunda ronda, utilizar o mapeamento f_0(2x^2-1) = (F(x) + F(-x))/2

Este processo reduz o tamanho do conjunto de pontos pela metade a cada vez, semelhante ao FRI convencional.

FFTs Circulares

O grupo Circle também suporta FFT, cuja construção é semelhante à Circle FRI. A diferença é que o Circle FFT não processa polinômios em sentido estrito, mas sim espaços de Riemann-Roch.

Os coeficientes de saída do Circle FFT são específicos da base do Circle FFT: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, ...}

Como desenvolvedor, você pode ignorar esses detalhes matemáticos e simplesmente armazenar o polinômio como um conjunto de valores de avaliação.

Outros detalhes técnicos

• A operação comercial em STARKs do Circle precisa ser avaliada em dois pontos.
• A forma de construção de polinómios desaparecidos é diferente
• Usar a ordem de bits reversa modificada para se adaptar à estrutura de colapso do Circle STARKs

Eficiência

Circle STARKs é muito eficiente em campos de números primos de 31 bits:

• Aproveitou ao máximo o espaço de computação
• Adequado para lógica de negócios e cálculo criptográfico
• Suporta operações eficientes de tabela de procura

Em comparação, a solução Binius tem ligeira vantagem em eficiência, mas o conceito é mais complexo.

Resumo

Os STARKs circulares não são mais complexos para os desenvolvedores do que os STARKs convencionais. Eles oferecem uma solução elegante para os STARKs de pequenos campos, com a esperança de impulsionar a tecnologia STARKs em direção a uma maior eficiência.

As direções de otimização futuras para os STARKs podem incluir:

• Otimizar funções hash e outras primitivas criptográficas
• Utilizar a construção recursiva para aumentar a paralelização
• Melhorar a aritmética da máquina virtual para aprimorar a experiência de desenvolvimento