Explorar Circle STARKs

Nos últimos anos, o design do protocolo STARKs tem tendido a usar campos menores. As primeiras implementações do STARKs usavam campos de 256 bits, compatíveis com assinaturas baseadas em curvas elípticas. No entanto, esse design tem eficiência relativamente baixa, e o processamento de números grandes desperdiça poder computacional. Para resolver esse problema, os STARKs começaram a mudar para o uso de campos menores: primeiro o Goldilocks, depois o Mersenne31 e o BabyBear.

Esta transição aumentou a velocidade das provas. Por exemplo, a Starkware consegue provar 620.000 hashes Poseidon2 por segundo em um notebook M3. Desde que confiemos no Poseidon2 como uma função hash, podemos resolver o desafio de desenvolver um ZK-EVM eficiente. Como funcionam essas tecnologias? Como essas provas são estabelecidas em campos menores? Este artigo irá explorar esses detalhes, com foco especial na solução Circle STARKs.

Problemas comuns ao usar campos matemáticos menores

Ao criar provas baseadas em hash, uma técnica importante é provar indiretamente as propriedades do polinômio através dos resultados da avaliação do polinômio em pontos aleatórios. Isso pode simplificar significativamente o processo de prova.

Por exemplo, suponha que seja necessário gerar o commitment do polinômio A, que deve satisfazer 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. Em seguida, deduz-se que A(r) = c, provando que Q = (A - c)/(X - r) é um polinômio.

Para evitar ataques, é necessário escolher r somente após o atacante fornecer A. Nos protocolos baseados em curvas elípticas, pode-se escolher um número aleatório de 256 bits. Mas em STARKs com campos menores, há apenas cerca de 2 bilhões de valores de r disponíveis, e o atacante pode quebrar por exaustão.

Existem duas soluções:

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

Várias verificações aleatórias são simples e eficazes, mas apresentam problemas de eficiência. O domínio estendido é semelhante aos números complexos, mas é baseado em um domínio finito. Introduzimos um novo valor α, declarando que α^2= um certo valor. Assim, é possível realizar cálculos mais complexos em um domínio finito. O domínio estendido é utilizado apenas em cenários como o protocolo FRI, enquanto a maior parte das operações matemáticas ainda ocorre no campo básico.

FRI Comum

Ao construir SNARK ou STARK, o primeiro passo é a aritmética, transformando o problema computacional em uma equação polinomial. Para provar que há uma solução, é necessário demonstrar que os valores apresentados são polinômios razoáveis e têm o grau máximo. Para isso, utiliza-se a técnica de combinação linear aleatória aplicada passo a passo:

1. Suponha que haja um valor de avaliação do polinómio A, é necessário provar que o grau é <2^20
2. Considerar B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D é uma combinação linear aleatória de B e C: D = B + rC

Essencialmente, B isola coeficientes pares, e C isola coeficientes ímpares. Dados B e C, A pode ser recuperado. 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 combinação linear aleatória, deve ter um grau igual ao grau de A.

O FRI simplifica o processo de verificação ao reduzir o problema de provar um polinómio de grau d para um problema de grau d/2. Este processo pode ser repetido várias vezes, cada vez simplificando o problema pela metade.

Para realizar a redução gradual do domínio, utiliza-se um mapeamento de dois para um. Este mapeamento permite reduzir o tamanho do conjunto de dados pela metade e é repetível. Começando com o subgrupo multiplicativo, aplica-se uma operação de quadrado ao conjunto S, e o novo conjunto S^2 mantém a mesma propriedade. Isso permite uma redução contínua do tamanho do conjunto de dados, até que, finalmente, reste apenas um valor.

O módulo BabyBear faz com que seu maior subgrupo multiplicativo contenha todos os valores não nulos, com um tamanho de subgrupo de 2k-1. Um subgrupo de tamanho 2^k pode ser escolhido e, em seguida, o método FRI é aplicado para reduzir gradualmente o grau do polinômio a 15. O módulo Mersenne31 faz com que o tamanho do subgrupo multiplicativo seja 2^31-1, que só pode ser dividido por 2 uma vez, após o que as técnicas acima não podem ser usadas.

O domínio Mersenne31 é adequado para cálculos em CPU/GPU de 32 bits. Suas propriedades de módulo permitem que muitas operações sejam realizadas utilizando operações de bits eficientes. No domínio Mersenne31, as operações aritméticas são aproximadamente 1,3 vezes mais rápidas do que no domínio BabyBear. Se for possível implementar FRI no domínio Mersenne31, isso aumentará significativamente a eficiência computacional.

Circle FRI

A astúcia dos STARKs circulares reside no fato de que, dada uma prime 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 certas condições, 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 ao longo do círculo. Primeiro, convergem 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 o polinômio unidimensional P(x).

A partir da segunda rodada, o mapeamento torna-se: f0(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 do dobro dos pontos.

FFTs Circulares

O grupo Circle também suporta FFT, com uma construção semelhante à do FRI. O objeto processado pelo Circle FFT é o espaço de Riemann-Roch: polinômio módulo círculo (x^2 + y^2 - 1 = 0).

Os coeficientes de saída do FFT circular são bases específicas: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Os desenvolvedores podem praticamente ignorar este ponto. STARKs apenas precisam armazenar os polinômios como um conjunto de valores de avaliação. FFT é usado para expansão de baixo grau: dado N valores, gera-se k*N valores sobre o mesmo polinômio.

Cálculo Comercial

No protocolo STARK, uma operação comum é realizar multiplicações em pontos específicos. Por exemplo, provar P(x)=y:

1. Calcular o quociente Q = (P - y)/(X - x)
2. Provar que Q é um polinómio e não uma fração

No grupo STARK da circle, devido à falta de uma função linear em um único ponto, é necessário usar técnicas diferentes para substituir os métodos tradicionais de operações comerciais. Através da avaliação em dois pontos, é demonstrado que é possível adicionar um ponto virtual que não precisa ser considerado.

Se o polinómio P é igual a y1 em x1 e igual a y2 em x2, escolha a função de interpolação L que é igual a y1 em x1 e igual a y2 em x2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

Em seguida, prove que P - L é zero nesses dois pontos, provando que o quociente Q é um polinómio dividindo L por L.

Polinômio desaparecido

Em STARK, as equações polinomiais geralmente têm a forma C(P(x), P(next(x))) = Z(x) · H(x), Z(x) é zero em todo o domínio de avaliação.

Na STARK circular, a função correspondente é: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Os polinómios que desaparecem podem ser derivados de funções de dobra: o STARK convencional reutiliza x → x^2, enquanto o STARK circular reutiliza x → 2x^2 - 1.

Ordem Inversa

Em STARKs, a avaliação de polinômios geralmente é ordenada em ordem inversa de bits. Por exemplo, quando n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Esta ordenação faz com que os valores dos grupos iniciais no processo de avaliação FRI fiquem adjacentes na ordenação, economizando espaço.

Na STARKs do circle, a estrutura de empilhamento é ligeiramente diferente. Para ajustar a ordem reversa para refletir essa estrutura, é necessário inverter cada posição, exceto a última, utilizando a última posição para decidir se as outras posições devem ser invertidas.

Ordem reversa dobrável 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. O cálculo geralmente envolve:

1. Aritmética nativa: usada para lógica de negócios
2. Aritmética nativa: usada em criptografia
3. Encontrar parâmetros: Método de cálculo geral e eficiente

A chave para a eficiência está em aproveitar ao máximo o espaço de rastreamento computacional. O tamanho do campo Circle STARKs é 2^31, desperdiçando pouco espaço.

Binius é melhor do que Circle STARKs, permitindo a mistura de campos de tamanhos diferentes, resultando em um empacotamento de bits mais eficiente. Mas o custo é que o conceito é mais complexo, enquanto o conceito de Circle STARKs é relativamente simples.

Conclusão

Os STARKs do Circle não são mais complexos para os desenvolvedores do que os STARKs. Compreender o Circle FRI e os Circle FFTs pode servir como um caminho para entender outros FFTs especiais.

Combinando as tecnologias Mersenne31, BabyBear e Binius, estamos próximos do limite de eficiência da camada base dos STARKs. As futuras direções de otimização dos STARK podem incluir:

1. Maximizar a eficiência aritmética de funções hash e assinaturas, etc.
2. Construção recursiva para permitir mais paralelização
3. Máquina virtual aritmética para melhorar a experiência do desenvolvedor