Explorar Circle STARKs

Nos últimos anos, a tendência do 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 era menos eficiente. Para resolver esse problema, o STARKs começou a usar campos menores, como Goldilocks, Mersenne31 e BabyBear.

Esta transformação aumentou significativamente a velocidade da prova. Por exemplo, a Starkware consegue provar 620.000 hashes Poseidon2 por segundo em um notebook M3. Isso significa que, desde que se confie no Poseidon2 como função hash, é possível resolver o problema do ZK-EVM eficiente.

Este artigo irá explorar como essas tecnologias funcionam, com foco especial na solução Circle STARKs, que é compatível com o campo Mersenne31.

Perguntas frequentes sobre o uso de pequenos campos

Ao criar uma prova baseada 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 bastante o processo de prova.

No entanto, realizar essa amostragem aleatória em pequenos campos apresenta problemas de segurança. Por exemplo, o campo Mersenne31 tem apenas cerca de 2 bilhões de pontos de amostragem possíveis, o que é viável para um atacante determinado.

Existem duas soluções:

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

Várias verificações são simples e eficazes, mas apresentam problemas de eficiência. Campos expandidos podem oferecer mais opções de pontos de amostragem, aumentando assim a segurança.

FRI Regular

O primeiro passo do protocolo FRI é transformar o problema computacional em uma equação polinomial. Em seguida, prova-se que a solução polinomial proposta é de fato um polinômio razoável e tem um certo grau máximo.

O FRI consegue isso simplificando progressivamente o problema de provar um polinômio de grau d em um problema de provar um polinômio de grau d/2. Este processo pode ser repetido várias vezes, reduzindo a escala do problema pela metade a cada iteração.

Cada passo do FRI reduz a ordem do polinómio e o tamanho do conjunto de pontos pela metade. O primeiro é a chave para o funcionamento do FRI, enquanto o segundo torna o algoritmo extremamente rápido.

Circle FRI

A genialidade dos STARKs em círculo reside no fato de que ele encontrou um grupo de tamanho p, com uma propriedade semelhante de par-a-um. Este grupo é composto por pontos que satisfazem condições específicas.

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

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

Este mapeamento reduz o tamanho do conjunto de pontos pela metade a cada vez.

FFTs de Círculo

O grupo Circle também suporta FFT, e a forma de construção é semelhante à do FRI. No entanto, os objetos tratados pelo Circle FFT não são polinómios estritamente, mas sim o que se denomina espaço de Riemann-Roch.

Como desenvolvedor, você pode praticamente ignorar isso. Os STARKs só precisam que você armazene polinômios como um conjunto de valores de avaliação. O único lugar onde o FFT é necessário é para realizar a expansão de baixo grau.

Cálculo Comercial

Nos STARKs da Circle, como não há uma função linear que possa ser aplicada em um ponto único, é necessário usar técnicas diferentes para substituir os métodos tradicionais de aritmética.

Temos de avaliar em dois pontos para provar, adicionando assim um ponto virtual que não precisa de atenção.

Polinómio desaparecido

Na Circle STARKs, a forma do polinômio desaparecido é:

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

Inverso

A ordem inversa nos STARKs circulares precisa ser ajustada para refletir sua estrutura de dobragem especial. Especificamente, cada posição deve ser invertida, exceto a última, e a última posição deve determinar se as outras posições serão invertidas.

Eficiência

Os STARKs circulares são muito eficientes. Em comparação com os SNARKs de grandes campos, eles podem aproveitar melhor o espaço no rastreamento computacional.

A Binius é melhor que a Circle STARKs em certos aspectos, mas isso vem com um custo, pois o conceito é mais complexo. Em comparação, a Circle STARKs é relativamente simples em termos de conceito.

Conclusão

Os STARKs em círculo não são mais complexos para os desenvolvedores do que os STARKs convencionais. Embora a matemática por trás seja complexa, essa complexidade está bem oculta.

Combinando tecnologias como Mersenne31, BabyBear e Binius, parece que estamos nos aproximando do limite de eficiência da camada básica dos STARKs. As direções de otimização futuras podem incluir:

1. Maximizar a eficiência da função hash e da assinatura
2. Construção recursiva para aumentar a paralelismo
3. Otimizar a máquina virtual para melhorar a experiência de desenvolvimento