Explorar Circle STARKs

Nos últimos anos, a tendência no design do protocolo STARKs tem sido a de usar campos menores. As primeiras implementações do STARKs usavam campos de 256 bits, mas esse design tinha uma eficiência mais baixa. Para resolver esse problema, o STARKs começou a usar campos 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. Isso significa que, contanto que se confie no Poseidon2 como função hash, o problema do ZK-EVM eficiente pode ser resolvido.

Este artigo irá explorar como estas tecnologias funcionam, com especial atenção para a solução Circle STARKs. A Circle STARKs possui propriedades únicas compatíveis com o campo Mersenne31.

Perguntas Frequentes sobre o Uso de Campos Pequenos

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

Para prevenir ataques, precisamos escolher pontos aleatórios após o atacante fornecer o polinômio. Nos STARKs de campos menores, há apenas cerca de 2 bilhões de pontos aleatórios disponíveis, o que não é seguro para um atacante determinado.

Existem duas soluções:

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

Várias verificações são simples e eficazes, mas apresentam problemas de eficiência. Os campos de extensão são semelhantes aos múltiplos, mas baseados em um campo finito. Isso nos permite operar em um campo maior, aumentando a segurança.

FRI Regular

O protocolo FRI verifica através da simplificação do problema de provar um polinómio de grau d para um problema de provar um polinómio de grau d/2. Este processo pode ser repetido várias vezes, simplificando o problema pela metade a cada vez.

FRI usa uma mapeamento de dois para um para reduzir o tamanho do conjunto de dados pela metade. Este mapeamento é repetível, permitindo-nos continuar a reduzir o tamanho do conjunto de dados.

Circle FRI

A genialidade dos Circle STARKs reside no fato de que, dado um primo p, é possível encontrar um grupo de tamanho p que possui uma característica semelhante de um-para-dois. Este grupo é composto por pontos que satisfazem condições específicas.

A partir da segunda ronda, a mapeação muda:

f_0(2x^2-1) = (F(x) + F(-x))/2

Este mapeamento 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 regra de duplicação de pontos.

FFTs Circulares

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

Como desenvolvedor, você pode praticamente ignorar esse ponto. STARKs exigem apenas que os polinômios sejam armazenados como valores de avaliação. O único lugar onde a FFT é necessária é para realizar a expansão de baixo grau.

Quotienting

No STARK do grupo circle, como não há uma função linear que possa ser usada em um único ponto, é necessário empregar técnicas diferentes para substituir a multiplicação comercial tradicional. Normalmente, é necessário avaliar em dois pontos para provar.

Polinômios desaparecendo

No STARK circular, o polinômio de desaparecimento é:

Z_1(x,y) = y Z_2(x,y) = x Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

Inverter a ordem dos bits

Os STARKs em círculo precisam ajustar a ordem inversa dos bits para refletir sua estrutura de dobra especial. Cada bit, exceto o último, deve ser invertido, e o último bit é usado para decidir se os outros bits devem ser invertidos.

Eficiência

Circle STARKs é muito eficiente. O cálculo geralmente envolve:

1. Aritmética nativa para lógica de negócios
2. Aritmética nativa para criptografia
3. Encontrar parâmetros

A chave é aproveitar ao máximo o espaço no rastreamento computacional. Um campo de tamanho 2^31 reduz o espaço desperdiçado.

Conclusão

Os STARKs circulares não são mais complexos para os desenvolvedores do que os STARKs convencionais. A matemática por trás deles é complexa, mas está basicamente oculta para os desenvolvedores.

Compreender o Circle FRI e os FFTs pode ser uma forma de entender outros FFTs especiais.

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

• Maximização da eficiência da aritmética em funções de hash, entre outras.
• Realizar construção recursiva para permitir mais paralelismo
• Máquina virtual aritmética para melhorar a experiência do desenvolvedor