Explorar Circle STARKs

Nos últimos anos, a tendência do design do protocolo STARKs é a de usar campos menores. As primeiras implementações de produção de STARKs usavam campos de 256 bits, mas esse design tinha eficiência reduzida. Para resolver esse problema, os STARKs começaram a usar campos menores, como Goldilocks, Mersenne31 e BabyBear.

Essa mudança aumentou a velocidade de prova. Por exemplo, a Starkware consegue provar 620.000 valores de hash Poseidon2 por segundo em um laptop M3. Isso significa que, desde que estejamos dispostos a confiar no Poseidon2 como função de hash, podemos resolver o problema de desenvolver um ZK-EVM eficiente.

Este artigo irá explorar o funcionamento dessas tecnologias, com foco especial na solução Circle STARKs. O Circle STARKs possui propriedades únicas que são compatíveis com o campo Mersenne31.

Perguntas frequentes sobre o uso de campos matemáticos menores

Ao criar uma prova baseada em hash, uma técnica importante é validar indiretamente as propriedades do polinómio através da prova dos resultados da avaliação do polinómio em pontos aleatórios. Este método pode simplificar significativamente o processo de prova.

Para prevenir ataques, precisamos escolher pontos aleatórios somente após o atacante fornecer o polinômio. Em STARKs de campos menores, o número de valores aleatórios disponíveis é limitado, o que representa um desafio para a segurança.

Existem duas soluções:

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

Os campos expandidos são semelhantes aos múltiplos, mas baseados em campos finitos. Ao introduzir um novo valor α, criamos uma nova estrutura matemática que permite operações mais complexas em campos finitos. Esta expansão permite-nos ter mais opções de valores, aumentando assim a segurança.

Circle FRI

A genialidade dos STARKs circulares está em que, dado um primo p, é possível encontrar um grupo de tamanho p, com características semelhantes a uma relação de dois para um. Este grupo é composto por pontos que satisfazem condições específicas e seguem uma regra de adição.

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

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

Esta mapeação 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 de Círculo

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

Como desenvolvedor, você pode quase ignorar isso completamente. STARKs nunca exigem que você entenda os coeficientes. Você só precisa armazenar o polinômio como um conjunto de valores avaliados em um domínio específico.

Quotienting

No protocolo STARK do grupo circle, devido à ausência de uma função linear que possa ser resolvida por um único ponto, é necessário utilizar técnicas diferentes para substituir o método tradicional de divisão. Somos obrigados a provar por meio da avaliação em dois pontos, adicionando assim um ponto virtual que não precisa ser considerado.

Polinómios que desaparecem

Na STARK circular, a função polinomial desaparecida é:

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

Para ajustar a ordem inversa para refletir a estrutura de dobra do Circle STARKs, precisamos inverter cada dígito, exceto o último, e usar o último dígito para decidir se os outros dígitos devem ser invertidos.

Eficiência

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

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

A chave para a eficiência é aproveitar ao máximo todo o espaço no rastreamento computacional para trabalho útil. Os Circle STARKs têm um bom desempenho nesse aspecto.

Conclusão

Os STARKs de Circle não são mais complexos para os desenvolvedores do que os STARKs. Embora a matemática por trás seja complexa, essa complexidade está, na verdade, bem ocultada.

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

1. Maximizar a eficiência da aritmética em funções de hash e assinaturas.
2. Realizar a construção recursiva para habilitar mais paralelismo
3. Máquina virtual aritmética para melhorar a experiência dos desenvolvedores