Exploração Profunda dos STARKs da Circle

Nos últimos anos, a tendência do design do protocolo STARKs é mudar para o uso de campos menores. As implementações mais antigas do STARKs usavam campos de 256 bits, o que tornava esses protocolos compatíveis com assinaturas baseadas em curvas elípticas. No entanto, esse design é menos eficiente e processar números grandes consome muita potência computacional. Para resolver esse problema, os STARKs começaram a mudar para o uso de campos menores: primeiro Goldilocks, depois Mersenne31 e BabyBear.

Esta transformação aumentou significativamente a velocidade da 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 do ZK-EVM eficiente. Como funcionam essas tecnologias? Como estabelecer provas em campos pequenos? Este artigo explorará esses detalhes, com foco especial na solução Circle STARKs.

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 dos resultados da avaliação do polinómio em pontos aleatórios. Isso simplifica consideravelmente o processo de prova.

Por exemplo, suponha que seja necessário gerar um compromisso para um polinômio A, que satisfaça A^3(x) + x - A(ωx) = x^N. O protocolo pode exigir a escolha de coordenadas aleatórias r e provar que A(r) + r - A(ωr) = r^N. Então, retrocedendo, A(r) = c, prova que Q = (A - c)/(X - r) é um polinômio.

Para evitar ataques, é necessário escolher r após o atacante fornecer A. No protocolo de campo grande, pode-se escolher um número aleatório de 256 bits como r. Mas nos STARKs de campo pequeno, apenas cerca de 2 bilhões de valores de r estão disponíveis, e o atacante pode tentar todos os possíveis.

Este problema tem duas soluções:

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

Várias verificações aleatórias simples são eficazes, mas existem problemas de eficiência. Campos de extensão são semelhantes a plurais, mas baseados em um domínio finito. Introduzimos um novo valor α que satisfaz α^2 = um determinado valor, criando uma nova estrutura matemática. Isso nos permite ter mais opções de valores, aumentando a segurança.

Regular FRI

O primeiro passo do protocolo FRI é normalmente a aritmética, transformando o problema computacional na equação P(X,Y,Z)=0, onde P é um polinómio, X, Y, Z são parâmetros. Resolver a equação corresponde a resolver o problema original.

Para provar a correção da solução, é necessário demonstrar que os valores propostos são polinômios razoáveis e de grau máximo. Usando a técnica de combinações lineares aleatórias:

• Suponha que existem valores de avaliação do polinómio A, deve-se provar que o seu grau é <2^20
• Considerar B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D é uma combinação linear aleatória de B e C: D = B + rC

Essencialmente, B isola coeficientes pares, e C isola coeficientes ímpares. B e C podem recuperar A. Se o grau de A < 2^20, os graus de B e C são, respetivamente, o grau de A e o grau de A - 1. D, como uma combinação aleatória, deve ter o grau de A.

FRI repete este processo de simplificação, reduzindo a questão pela metade a cada vez. Este design detecta eficazmente entradas que não cumprem os requisitos.

Circle FRI

Esta é a genialidade dos STARKs da Circle. Dado um primo p, pode-se 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, como o conjunto de pontos onde x^2 mod p é igual a um determinado valor.

Estes pontos seguem a regra da adição: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) A forma dupla é: 2 * (x,y) = (2x^2 - 1, 2xy)

Focamos nos pontos nas posições ímpares do círculo, convergindo todos os pontos para uma linha reta: f0(x) = (F(x,y) + F(x,-y))/2

Em seguida, faça uma combinação linear aleatória para obter um polinómio unidimensional P(x).

A partir da segunda rodada, o mapeamento torna-se: f0(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, com um método de construção semelhante ao FRI. No entanto, o objeto tratado pelo Circle FFT é o espaço de Riemann-Roch, e não polinômios estritos.

Como desenvolvedor, você pode basicamente ignorar esse ponto. STARKs apenas precisam armazenar polinômios como um conjunto de valores de avaliação. FFT é usado principalmente para baixa expansão: dado N valores, gera k*N valores no mesmo polinômio.

Quotienting

Nos STARKs da Circle, devido à ausência de funções lineares de ponto único, é necessário usar técnicas diferentes para substituir a operação comercial tradicional. Através da avaliação em dois pontos para demonstrar, adicionando um ponto virtual.

Se o polinómio P for igual a y1 em x1 e igual a y2 em x2, escolha a função de interpolação L que é igual em ambos os pontos. Depois, prove que P-L é zero nos dois pontos, e que o quociente Q obtido ao dividir L é um polinómio.

Polinômios desaparecendo

O polinómio de desaparecimento em STARKs de Circle é: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Isso pode ser derivado da função de dobra: reutilizando x → 2x^2 - 1.

Inverter a ordem dos bits

A ordem inversa em STARKs de círculo deve ser ajustada: inverter cada bit exceto o último, usando o último bit para decidir se os outros bits devem ser invertidos.

A sequência reversa de dobra de tamanho 16 é: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Eficiência

Circle STARKs é muito eficiente. Os cálculos geralmente envolvem:

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

A chave para a eficiência está em aproveitar ao máximo o espaço de rastreamento computacional. O campo de 31 bits reduz o desperdício. A Binius mistura campos de diferentes tamanhos com mais eficiência, mas o conceito é mais complexo.

Conclusão

Os STARKs de círculo não são complexos para os desenvolvedores. Compreender a matemática por trás leva tempo, mas a complexidade está bem oculta. É também uma forma de entender outras FFTs especiais.

Atualmente, a eficiência da camada básica STARKs está próxima do limite. As direções de otimização futuras podem incluir:

• Maximizar a eficiência das funções hash e de outros primitivos criptográficos básicos
• Construção recursiva para aumentar a paralelização
• Máquina virtual aritmética para melhorar a experiência de desenvolvimento