Nos últimos anos, a tendência no design do protocolo STARKs tem sido a de utilizar campos menores. As primeiras implementações de produção do STARKs usavam campos de 256 bits, ou seja, realizavam operações de módulo em grandes números. No entanto, esse design tem eficiência inferior, e processar grandes números consome muita capacidade computacional. Para resolver esse problema, os STARKs começaram a usar campos menores: primeiro o Goldilocks, depois o Mersenne31 e o BabyBear.
Esta mudança melhorou significativamente a velocidade de prova. Por exemplo, a Starkware agora consegue provar 620.000 hashes Poseidon2 por segundo em um laptop M3. Isso significa que, desde que confiemos no Poseidon2 como função hash, podemos resolver o problema do desenvolvimento eficiente do ZK-EVM. Como essas tecnologias funcionam? Como são construídas as provas em campos pequenos? Este artigo irá explorar esses detalhes, com um foco especial nas STARKs da Circle, uma solução compatível com o campo Mersenne31.
Questões comuns ao usar 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 pode simplificar significativamente o processo de prova.
Por exemplo, suponha que o protocolo exija que você gere um compromisso de um polinômio A, satisfazendo A^3(x) + x - A(ωx) = x^N. O protocolo pode exigir que você escolha coordenadas aleatórias r e prove que A(r)^3 + r - A(ωr) = r^N. Em seguida, deduza A(r) = c, você prova que Q = (A - c)/(X - r) é um polinômio.
Para prevenir ataques, precisamos escolher r após o atacante fornecer A. Em protocolos baseados em curvas elípticas, isso é simples: podemos escolher um número aleatório de 256 bits como r. Mas nos STARKs de pequeno campo, apenas cerca de 2 bilhões de r estão disponíveis, e o atacante pode quebrar por exaustão.
Este problema tem duas soluções:
Realizar várias inspeções aleatórias
Campos de extensão
Várias verificações aleatórias são simples e eficazes, mas podem apresentar problemas de eficiência. O domínio expandido é semelhante ao plural, mas baseado em um domínio finito. Introduzimos um novo valor α, declarando que α^2 = um certo valor. Isso cria uma nova estrutura matemática que pode realizar operações mais complexas em um domínio finito.
Através da extensão do domínio, temos valores suficientes para escolher, satisfazendo as necessidades de segurança. A maior parte das operações matemáticas ainda é realizada sobre o campo base, usando apenas campos maiores quando é necessário aumentar a segurança.
Regular FRI
FRI (Fast Reed-Solomon Interactive) protocolo é um passo importante na construção de SNARK ou STARK. Ele simplifica o processo de verificação ao reduzir o problema de provar um polinômio de grau d para um problema de prova de grau d/2. Este processo pode ser repetido várias vezes, cada vez reduzindo o problema pela metade.
O funcionamento do FRI é um processo de simplificação repetido. Começando por provar que o grau do polinómio é d, através de uma série de passos, prova-se finalmente que o grau é d/2. Após cada simplificação, o grau do polinómio gerado diminui gradualmente. Se a saída de alguma fase não corresponder às expectativas, essa ronda de verificação falhará.
Para alcançar a redução gradual do domínio, foi utilizada uma mapeamento de dois para um. Este mapeamento permite reduzir pela metade o tamanho do conjunto de dados, mantendo as mesmas propriedades. Esta operação pode ser imaginada como o processo de estender um segmento ao longo da circunferência por duas voltas.
Para que a técnica de mapeamento seja eficaz, o tamanho do subgrupo de multiplicação original precisa ter um grande fator de potência de 2. O módulo do BabyBear permite que seu maior subgrupo de multiplicação contenha todos os valores diferentes de zero, sendo muito adequado para esta técnica. O tamanho do subgrupo de multiplicação do Mersenne31 tem apenas um fator de potência de 2, limitando seu alcance de aplicação.
O domínio Mersenne31 é muito adequado para operações aritméticas em CPU/GPU de 32 bits, sendo cerca de 1,3 vezes mais rápido que o 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 em círculo está no fato de que, dado um primo p, pode-se encontrar um grupo de tamanho p, com propriedades semelhantes de dois para um. 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 a regra da adição: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
A forma dupla é: 2 * (x,y) = (2x^2 - 1, 2xy)
O Circle FRI primeiro concentra todos os pontos em uma linha reta, e então realiza 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, convertendo as coordenadas x dos dois pontos opostos no círculo para as coordenadas x do ponto multiplicado. Isso poderia ser feito em um espaço bidimensional, mas a operação unidimensional é mais eficiente.
FFTs em Círculo
O grupo Circle também suporta FFT, com uma construção semelhante à FRI. O objeto tratado pelo Circle FFT é o espaço de Riemann-Roch, e não polinômios estritos. Os coeficientes de saída do Circle FFT são específicos da base do Circle FFT.
Como desenvolvedor, você pode praticamente ignorar isso. Os STARKs apenas armazenam polinômios como um conjunto de valores de avaliação. O único lugar onde é necessário FFT é para realizar a extensão de baixo grau: dado N valores, gerar k*N valores sobre o mesmo polinômio.
Quotienting
Nos STARKs da Circle, como não há uma função linear acessível por um único ponto, é necessário usar técnicas diferentes para substituir a operação comercial tradicional. Temos que provar avaliando em dois pontos, adicionando um ponto virtual.
Se o polinómio P for igual a y1 em x1 e igual a y2 em x2, escolhemos a função de interpolação L, que é igual em ambos os pontos. Depois, provamos que P-L é zero nesses dois pontos, e demonstramos que o quociente Q, obtido ao dividir L por L, é um polinómio.
Polinômios que desaparecem
No Circle STARKs, o polinómio de desaparecimento é:
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: no Circle STARKs, reutiliza-se x → 2x^2 - 1. A primeira rodada precisa de um tratamento especial.
Inverter a ordem dos bits
Circle STARKs utiliza uma ordem de bits reversa modificada, invertendo todos os bits, exceto o último, e usando o último bit para determinar se os outros bits devem ser invertidos. Isso reflete a estrutura de dobra única dos Circle STARKs.
Eficiência
Circle STARKs é muito eficiente. Os cálculos normalmente envolvem:
Aritmética nativa: usada para lógica de negócios
Aritmética nativa: usada em criptografia ( como hash Poseidon )
Encontrar parâmetros: realizar vários cálculos através da tabela de consulta de valores
Os STARKs em círculo aproveitam bem o espaço computacional, desperdiçando menos. São um pouco inferiores aos Binius, mas o conceito é mais simples.
Conclusão
Os STARKs da Circle não são mais complexos para os desenvolvedores do que os STARKs convencionais. Compreender o FRI da Circle e os FFTs pode ajudar na compreensão de outros FFTs especiais. Atualmente, a eficiência da camada básica do STARKs está próxima do limite, e as direções de otimização futuras podem incluir:
Maximizar a eficiência aritmética da função de hash e da assinatura
Construção recursiva para melhorar a paralelização
Máquina virtual aritmética para melhorar a experiência de desenvolvimento
Esta página pode conter conteúdo de terceiros, que é fornecido apenas para fins informativos (não para representações/garantias) e não deve ser considerada como um endosso de suas opiniões pela Gate nem como aconselhamento financeiro ou profissional. Consulte a Isenção de responsabilidade para obter detalhes.
19 Curtidas
Recompensa
19
4
Repostar
Compartilhar
Comentário
0/400
NftBankruptcyClub
· 08-09 22:10
A letra está menor, mas a eficiência aumentou...666
Ver originalResponder0
GasWhisperer
· 08-09 22:08
hmm... campos menores = provas mais rápidas, mas podemos confiar no poseidon2? sinto-me dividido sobre essa troca eficiência/segurança, para ser sincero.
Ver originalResponder0
alpha_leaker
· 08-09 21:58
Stark está um pouco assustador.
Ver originalResponder0
ChainDetective
· 08-09 21:54
Acabei de entender, basicamente é uma versão simplificada para cálculos rápidos.
Circle STARKs: Exploração e avanços em provas ZK eficientes de pequeno campo
Explorar Circle STARKs
Nos últimos anos, a tendência no design do protocolo STARKs tem sido a de utilizar campos menores. As primeiras implementações de produção do STARKs usavam campos de 256 bits, ou seja, realizavam operações de módulo em grandes números. No entanto, esse design tem eficiência inferior, e processar grandes números consome muita capacidade computacional. Para resolver esse problema, os STARKs começaram a usar campos menores: primeiro o Goldilocks, depois o Mersenne31 e o BabyBear.
Esta mudança melhorou significativamente a velocidade de prova. Por exemplo, a Starkware agora consegue provar 620.000 hashes Poseidon2 por segundo em um laptop M3. Isso significa que, desde que confiemos no Poseidon2 como função hash, podemos resolver o problema do desenvolvimento eficiente do ZK-EVM. Como essas tecnologias funcionam? Como são construídas as provas em campos pequenos? Este artigo irá explorar esses detalhes, com um foco especial nas STARKs da Circle, uma solução compatível com o campo Mersenne31.
Questões comuns ao usar 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 pode simplificar significativamente o processo de prova.
Por exemplo, suponha que o protocolo exija que você gere um compromisso de um polinômio A, satisfazendo A^3(x) + x - A(ωx) = x^N. O protocolo pode exigir que você escolha coordenadas aleatórias r e prove que A(r)^3 + r - A(ωr) = r^N. Em seguida, deduza A(r) = c, você prova que Q = (A - c)/(X - r) é um polinômio.
Para prevenir ataques, precisamos escolher r após o atacante fornecer A. Em protocolos baseados em curvas elípticas, isso é simples: podemos escolher um número aleatório de 256 bits como r. Mas nos STARKs de pequeno campo, apenas cerca de 2 bilhões de r estão disponíveis, e o atacante pode quebrar por exaustão.
Este problema tem duas soluções:
Várias verificações aleatórias são simples e eficazes, mas podem apresentar problemas de eficiência. O domínio expandido é semelhante ao plural, mas baseado em um domínio finito. Introduzimos um novo valor α, declarando que α^2 = um certo valor. Isso cria uma nova estrutura matemática que pode realizar operações mais complexas em um domínio finito.
Através da extensão do domínio, temos valores suficientes para escolher, satisfazendo as necessidades de segurança. A maior parte das operações matemáticas ainda é realizada sobre o campo base, usando apenas campos maiores quando é necessário aumentar a segurança.
Regular FRI
FRI (Fast Reed-Solomon Interactive) protocolo é um passo importante na construção de SNARK ou STARK. Ele simplifica o processo de verificação ao reduzir o problema de provar um polinômio de grau d para um problema de prova de grau d/2. Este processo pode ser repetido várias vezes, cada vez reduzindo o problema pela metade.
O funcionamento do FRI é um processo de simplificação repetido. Começando por provar que o grau do polinómio é d, através de uma série de passos, prova-se finalmente que o grau é d/2. Após cada simplificação, o grau do polinómio gerado diminui gradualmente. Se a saída de alguma fase não corresponder às expectativas, essa ronda de verificação falhará.
Para alcançar a redução gradual do domínio, foi utilizada uma mapeamento de dois para um. Este mapeamento permite reduzir pela metade o tamanho do conjunto de dados, mantendo as mesmas propriedades. Esta operação pode ser imaginada como o processo de estender um segmento ao longo da circunferência por duas voltas.
Para que a técnica de mapeamento seja eficaz, o tamanho do subgrupo de multiplicação original precisa ter um grande fator de potência de 2. O módulo do BabyBear permite que seu maior subgrupo de multiplicação contenha todos os valores diferentes de zero, sendo muito adequado para esta técnica. O tamanho do subgrupo de multiplicação do Mersenne31 tem apenas um fator de potência de 2, limitando seu alcance de aplicação.
O domínio Mersenne31 é muito adequado para operações aritméticas em CPU/GPU de 32 bits, sendo cerca de 1,3 vezes mais rápido que o 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 em círculo está no fato de que, dado um primo p, pode-se encontrar um grupo de tamanho p, com propriedades semelhantes de dois para um. 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 a regra da adição: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) A forma dupla é: 2 * (x,y) = (2x^2 - 1, 2xy)
O Circle FRI primeiro concentra todos os pontos em uma linha reta, e então realiza 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, convertendo as coordenadas x dos dois pontos opostos no círculo para as coordenadas x do ponto multiplicado. Isso poderia ser feito em um espaço bidimensional, mas a operação unidimensional é mais eficiente.
FFTs em Círculo
O grupo Circle também suporta FFT, com uma construção semelhante à FRI. O objeto tratado pelo Circle FFT é o espaço de Riemann-Roch, e não polinômios estritos. Os coeficientes de saída do Circle FFT são específicos da base do Circle FFT.
Como desenvolvedor, você pode praticamente ignorar isso. Os STARKs apenas armazenam polinômios como um conjunto de valores de avaliação. O único lugar onde é necessário FFT é para realizar a extensão de baixo grau: dado N valores, gerar k*N valores sobre o mesmo polinômio.
Quotienting
Nos STARKs da Circle, como não há uma função linear acessível por um único ponto, é necessário usar técnicas diferentes para substituir a operação comercial tradicional. Temos que provar avaliando em dois pontos, adicionando um ponto virtual.
Se o polinómio P for igual a y1 em x1 e igual a y2 em x2, escolhemos a função de interpolação L, que é igual em ambos os pontos. Depois, provamos que P-L é zero nesses dois pontos, e demonstramos que o quociente Q, obtido ao dividir L por L, é um polinómio.
Polinômios que desaparecem
No Circle STARKs, o polinómio de desaparecimento é: 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: no Circle STARKs, reutiliza-se x → 2x^2 - 1. A primeira rodada precisa de um tratamento especial.
Inverter a ordem dos bits
Circle STARKs utiliza uma ordem de bits reversa modificada, invertendo todos os bits, exceto o último, e usando o último bit para determinar se os outros bits devem ser invertidos. Isso reflete a estrutura de dobra única dos Circle STARKs.
Eficiência
Circle STARKs é muito eficiente. Os cálculos normalmente envolvem:
Os STARKs em círculo aproveitam bem o espaço computacional, desperdiçando menos. São um pouco inferiores aos Binius, mas o conceito é mais simples.
Conclusão
Os STARKs da Circle não são mais complexos para os desenvolvedores do que os STARKs convencionais. Compreender o FRI da Circle e os FFTs pode ajudar na compreensão de outros FFTs especiais. Atualmente, a eficiência da camada básica do STARKs está próxima do limite, e as direções de otimização futuras podem incluir: