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 de produção do STARKs usavam campos de 256 bits, ou seja, realizavam operações de módulo em grandes números, o que tornava esses protocolos compatíveis com assinaturas baseadas em curvas elípticas. No entanto, a eficiência desse design é relativamente baixa; em geral, processar esses grandes números não tem uma aplicação prática e consome muita potência computacional. Para resolver esse problema, o STARKs começou a usar campos menores: primeiro o Goldilocks, depois o Mersenne31 e o BabyBear.

Esta transformação 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. Como funcionam essas tecnologias? Como essas provas são estabelecidas em campos menores? Como esses protocolos se comparam a soluções como a Binius? Este artigo irá explorar esses detalhes, com foco especial em uma solução chamada Circle STARKs, que possui propriedades únicas compatíveis com o campo Mersenne31.

Problemas comuns ao usar campos matemáticos menores

Ao criar uma prova baseada em hash ( ou qualquer tipo de prova ), uma técnica muito importante é a de provar os resultados da avaliação de um polinómio em pontos aleatórios, o que permite verificar indiretamente as propriedades do polinómio. Este método pode simplificar bastante o processo de prova, uma vez que a avaliação em pontos aleatórios é geralmente muito mais fácil do que lidar com o polinómio completo.

Por exemplo, suponha que um sistema de prova exija que você gere um compromisso para um polinômio, A, que deve satisfazer A^3(x) + x - A(ωx) = x^N(, um tipo de prova muito comum no protocolo ZK-SNARK ). O protocolo pode exigir que você escolha uma coordenada aleatória r e prove que A(r) + r - A(ωr) = r^N. Então, você deduz que A(r) = c, você provou que Q = (A - c)/(X - r) é um polinômio.

Para evitar ataques, precisamos escolher r somente após o atacante ter fornecido A. Os parâmetros escolhidos devem vir de um conjunto grande o suficiente para garantir que o atacante não possa prever ou adivinhar esses parâmetros, aumentando assim a segurança do sistema.

No protocolo baseado em curvas elípticas e nos STARKs de 2019, essa questão é simples: todas as nossas operações matemáticas são realizadas em números de 256 bits, portanto podemos escolher r como um número aleatório de 256 bits, e isso é tudo. No entanto, nos STARKs sobre campos menores, encontramos um problema: existem apenas cerca de 2 bilhões de valores possíveis de r que podem ser escolhidos, portanto, um atacante que deseja falsificar uma prova só precisa tentar 2 bilhões de vezes; embora a carga de trabalho seja grande, para um atacante determinado, isso ainda é completamente viável!

Esta questão tem duas soluções:

• Realizar várias inspeções aleatórias
• Campo de extensão

O método de realizar múltiplas verificações aleatórias é o mais simples e eficaz: em vez de verificar em uma coordenada, é melhor repetir a verificação em quatro coordenadas aleatórias. Isso é teoricamente viável, mas há questões de eficiência. Se você estiver lidando com um polinômio de grau inferior a um certo valor e operando em um domínio de determinado tamanho, o atacante pode realmente construir polinômios maliciosos que parecem normais nessas posições. Portanto, se eles podem ou não comprometer o protocolo é uma questão probabilística, e por isso é necessário aumentar o número de verificações para melhorar a segurança geral e garantir uma defesa eficaz contra os ataques dos atacantes.

Isso leva a outra solução: extensão de campos, a extensão de campos é semelhante a números complexos, mas é baseada em campos finitos. Introduzimos um novo valor, denotado como α, e declaramos que ele satisfaz certa relação, como α^2=some value. Desta forma, criamos uma nova estrutura matemática, capaz de realizar operações mais complexas sobre campos finitos. Nesta extensão de campo, o cálculo da multiplicação torna-se a multiplicação usando o novo valor α. Agora podemos operar pares de valores na extensão do campo, e não apenas números individuais. Por exemplo, se estivermos trabalhando em campos como Mersenne ou BabyBear, tal extensão nos permite ter mais opções de valores, aumentando assim a segurança. Para aumentar ainda mais o tamanho do campo, podemos aplicar repetidamente a mesma técnica. Como já usamos α, precisamos definir um novo valor, que no Mersenne31 se manifesta na escolha de α de forma que α^2=some value.

Através da extensão de domínio, agora temos um número suficiente de valores para escolher, satisfazendo as nossas necessidades de segurança. Se estamos a lidar com polinómios de grau inferior a d, cada ronda pode fornecer 104 bits de segurança. Isso significa que temos garantias de segurança suficientes. Se for necessário atingir um nível de segurança mais elevado, como 128 bits, podemos adicionar algum trabalho computacional extra no protocolo para aumentar a segurança.

Os domínios de extensão são utilizados na prática apenas no protocolo FRI( Fast Reed-Solomon Interactive) e em outros cenários que requerem combinações lineares aleatórias. A maioria das operações matemáticas ainda é realizada sobre campos básicos, que geralmente são campos módulo p ou q. Ao mesmo tempo, quase todos os dados de hash são realizados sobre campos básicos, de modo que cada valor só precisa ser hash de quatro bytes. Isso permite aproveitar a eficiência de pequenos campos, enquanto, quando a segurança adicional é necessária, campos maiores podem ser utilizados.

Regular FRI

Ao construir SNARK ou STARK, o primeiro passo é geralmente a arithmetização. Isto é a transformação de um problema de computação arbitrário em uma equação, onde algumas variáveis e coeficientes são polinómios. Especificamente, esta equação geralmente se parece com P(X,Y,Z)=0, onde P é um polinómio, X, Y e Z são parâmetros dados, e o solucionador precisa fornecer os valores de X e Y. Uma vez que se tem uma equação assim, a solução dessa equação corresponde à solução do problema de computação subjacente.

Para provar que você tem uma solução, você precisa demonstrar que o valor que apresentou é de fato um polinômio razoável ( e não uma fração, ou que em alguns lugares parece um polinômio, enquanto em outros é um polinômio diferente, etc. ), e que esses polinômios têm um grau máximo definido. Para isso, utilizamos uma técnica de combinação linear aleatória aplicada passo a passo:

• Suponha que você tenha um valor de avaliação do polinômio A, e você quer provar que seu grau é menor que 2^20
• Considerar o polinómio 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, ou seja, D=B+rC, onde r é um coeficiente aleatório.

Essencialmente, o que acontece é que B isola os coeficientes de grau par de A, e C isola os coeficientes de grau ímpar. Dado B e C, você pode recuperar o polinômio original A: A(x) = B(x^2) + xC(x^2). Se o grau de A for realmente menor que 2^20, então os graus de B e C serão, respectivamente, o grau de A e o grau de A menos 1. Porque a combinação de termos de grau par e ímpar não aumentará o grau. Como D é uma combinação linear aleatória de B e C, o grau de D também deve ser o grau de A, o que permite que você verifique se o grau de A está de acordo com os requisitos através do grau de D.

Primeiro, o FRI simplifica o processo de verificação reduzindo o problema de provar que o polinômio tem grau d para o problema de provar que o polinômio tem grau d/2. Este processo pode ser repetido várias vezes, cada vez simplificando o problema pela metade.

O funcionamento do FRI é repetir este processo de simplificação. Por exemplo, se você começar com um polinômio de grau d, através de uma série de etapas, você acabará provando que o grau do polinômio é d/2. Após cada simplificação, o grau do polinômio gerado diminui gradualmente. Se a saída em alguma etapa não corresponder ao grau do polinômio esperado, então essa rodada de verificação falhará. Se alguém tentar empurrar um polinômio que não tem grau d usando essa técnica, então na saída da segunda rodada, seu grau terá uma certa probabilidade de não corresponder ao esperado, e na terceira rodada, será mais provável que ocorra uma discrepância, levando à falha da verificação final. Esse design pode detectar e rejeitar efetivamente entradas que não estão em conformidade. Se o conjunto de dados for igual a um polinômio de grau d na maioria dos locais, esse conjunto de dados pode passar na verificação do FRI. No entanto, para construir um conjunto de dados assim, o atacante precisa conhecer o polinômio real, portanto, mesmo uma prova com leves deficiências indica que o provador é capaz de gerar uma prova "real".

Vamos entender melhor o que está acontecendo aqui e quais atributos são necessários para que tudo funcione corretamente. A cada passo, reduzimos a ordem do polinômio pela metade, enquanto também reduzimos pela metade o conjunto de pontos ( que estamos focando. O primeiro é a chave para fazer o protocolo FRI) Fast Reed-Solomon Interactive( funcionar corretamente. O segundo torna o algoritmo extremamente rápido: como o tamanho de cada rodada é reduzido pela metade em relação à rodada anterior, o custo computacional total é O) N(, e não O) N*log( N().

Para realizar a redução gradual do domínio, foi utilizado um mapeamento de dois para um, ou seja, cada ponto é mapeado para um dos dois pontos. Este mapeamento permite-nos reduzir o tamanho do conjunto de dados pela metade. Uma vantagem importante deste mapeamento de dois para um é que ele é repetível. Ou seja, quando aplicamos este mapeamento, o conjunto de resultados obtido ainda mantém as mesmas propriedades. Suponha que começamos com um subgrupo multiplicativo ). Este subgrupo é um conjunto S, onde cada elemento x tem seu múltiplo 2x também presente no conjunto. Se realizarmos a operação de quadrado no conjunto S (, ou seja, mapeando cada elemento x do conjunto para x^2), o novo conjunto S^2 também manterá as mesmas propriedades. Esta operação permite-nos continuar a reduzir o tamanho do conjunto de dados, até que eventualmente reste apenas um valor. Embora teoricamente possamos reduzir o conjunto de dados a apenas um valor, na prática, geralmente paramos antes de alcançar um conjunto menor.

Você pode imaginar essa operação como um processo de estender uma linha, por exemplo, um segmento ou arco, ao longo da circunferência, fazendo-a girar duas voltas ao redor da circunferência. Por exemplo, se um ponto na circunferência estiver na posição de x graus, após essa operação, ele se moverá para a posição de 2x graus. Cada ponto na circunferência da posição de 0 a 179 graus tem um ponto correspondente na posição de 180 a 359 graus, e esses dois pontos coincidem. Isso significa que, ao mapear um ponto de x graus para 2x graus, ele coincidirá com um ponto localizado na posição de x+180 graus. Esse processo pode ser repetido. Ou seja, você pode aplicar essa operação de mapeamento várias vezes, movendo a cada vez os pontos na circunferência para suas novas posições.

Para que a técnica de mapeamento seja eficaz, o tamanho do subgrupo multiplicativo original precisa ter uma grande potência de 2 como fator. BabyBear é um sistema com um módulo específico, cujo módulo é um determinado valor, de modo que seu maior subgrupo multiplicativo contém todos os valores não nulos, portanto, o tamanho do subgrupo é 2k−1(, onde k é o número de bits do módulo ). Este tamanho de subgrupo é muito adequado para a técnica mencionada, pois permite reduzir de forma eficaz o grau do polinômio através da aplicação repetida da operação de mapeamento. No BabyBear, você pode escolher um subgrupo de tamanho 2^k ( ou usar diretamente todo o conjunto ), e então aplicar o método FRI para reduzir gradualmente o grau do polinômio a 15 e, por fim, verificar o grau do polinômio. Este método aproveita as propriedades do módulo e o tamanho do subgrupo multiplicativo, tornando o processo de cálculo muito eficiente. Mersenne31 é outro sistema, cujo módulo é um determinado valor, fazendo com que o tamanho do subgrupo multiplicativo seja 2^31 - 1. Neste caso, o tamanho do subgrupo multiplicativo tem apenas uma potência de 2 como fator, o que significa que ele só pode ser dividido por 2 uma vez. O processamento posterior não se aplica mais à técnica mencionada, ou seja, não é possível usar o FFT para uma redução eficaz do grau do polinômio como no BabyBear.

O domínio Mersenne31 é muito adequado para operações aritméticas em CPUs/GPUs de 32 bits existentes. Devido às características do seu módulo (, como 2^31 - 1), muitas operações podem ser realizadas utilizando operações bit a bit eficientes: se a soma de dois números exceder o módulo, o resultado pode ser ajustado utilizando o módulo.