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 tem uma eficiência mais baixa. Para resolver esse problema, o STARKs começou a usar campos menores, como Goldilocks, Mersenne31 e BabyBear.

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

Este artigo irá explorar como estas tecnologias funcionam, com atenção especial para a solução Circle STARKs, que é compatível 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 bastante o processo de prova.

Para prevenir ataques, precisamos escolher pontos aleatórios após o atacante fornecer o polinómio. Em campos grandes, pode-se simplesmente escolher um número aleatório de 256 bits. Mas em campos pequenos, o número de valores possíveis é muito reduzido, tornando-se fácil para o atacante esgotar todas as opções.

Há 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 têm eficiência relativamente baixa. Campos de extensão são semelhantes a plurais, permitindo operações mais complexas em domínios limitados. Isso aumentou a segurança, mantendo a eficiência dos pequenos campos.

Circle FRI

A genialidade dos STARKs circulares reside no fato de que, dado um primo p, é possível encontrar um grupo de tamanho p que possui uma propriedade semelhante de um-para-dois. Este grupo é composto por um conjunto de pontos que satisfazem condições específicas, como o conjunto de pontos onde x^2 mod p é igual a um certo valor.

Estes pontos seguem uma regra de adição: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

A forma dupla é: 2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRI converte todos os pontos em uma única linha reta, e em seguida realiza uma combinação linear aleatória, resultando no polinômio unidimensional P(x).

A partir da segunda rodada, a mapeação torna-se: f0(2x^2-1) = (F(x) + F(-x)) / 2

Este mapeamento reduz o tamanho do conjunto pela metade a cada vez, convertendo a coordenada x de dois pontos opostos no círculo na coordenada x do ponto após a duplicação.

FFTs de Círculo

O grupo Circle também suporta FFT, com um método de construção semelhante ao FRI. Uma diferença chave é que o Circle FFT não lida com polinómios em sentido estrito, mas sim com o espaço de Riemann-Roch.

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

Cálculo Comercial

No STARK, uma operação comum é realizar operações de divisão em pontos específicos. No grupo circular, devido à ausência de uma função linear em um único ponto, são necessárias técnicas diferentes.

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

Polinômio Desaparecido

Na STARK do circle, a função polinomial correspondente que desaparece é:

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

Ordem inversa

Os STARKs em círculo precisam ajustar a ordem reversa dos bits para refletir sua estrutura de dobra. Precisamos inverter todos os bits, exceto o último, usando o último bit para decidir se os outros bits devem ser invertidos.

Eficiência

Circle STARKs são muito eficientes. Um cálculo comprovado normalmente envolve:

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

A chave para a eficiência é tirar pleno partido do espaço no rastreamento computacional. Os Circle STARKs desperdiçam menos espaço em campos de tamanho 2^31.

Conclusão

Circle STARKs 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, estamos nos aproximando do limite de eficiência da camada base STARKs. As direções de otimização futuras podem incluir:

• Maximizar a eficiência de primitivas como funções hash
• Construção recursiva para aumentar a paralelismo
• Máquina virtual aritmética para melhorar a experiência de desenvolvimento