Explorar Circle STARKs

Nos últimos anos, a tendência no design do protocolo STARKs tem sido a de usar campos menores. A implementação mais antiga da produção de STARKs usava campos de 256 bits, ou seja, realizando operações modulares 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, pois, na maioria dos casos, o processamento desses grandes números não tem utilidade prática e consome muita capacidade de computação. Para resolver esse problema, os STARKs começaram a mudar para o uso de campos menores: primeiro Goldilocks, depois Mersenne31 e BabyBear.

Essa transformação aumentou a velocidade de prova, por exemplo, a Starkware consegue provar 620.000 hashes Poseidon2 por segundo em um laptop M3. Isso significa que, desde que confiemos no Poseidon2 como uma função hash, podemos resolver o desafio de desenvolver um ZK-EVM eficiente. Como essas tecnologias funcionam? Como essas provas são estabelecidas em campos menores? Como esses protocolos se comparam a soluções como a Binius? Este artigo 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, uma técnica muito importante é a de provar a propriedade de um polinómio através dos resultados da avaliação do polinómio em pontos aleatórios, o que permite validar indiretamente as propriedades do polinómio. Este método pode simplificar significativamente 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 inteiro.

Para evitar ataques, precisamos escolher r somente após o atacante fornecer A. Fiat-Shamir é uma técnica utilizada para aumentar a segurança do protocolo, evitando ataques ao definir certos parâmetros como um determinado valor de hash. Os parâmetros escolhidos devem vir de um conjunto grande o suficiente para garantir que o atacante não consiga 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, este problema é muito simples: todas as nossas operações matemáticas são realizadas sobre 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 para escolher, portanto, um atacante que queira falsificar uma prova só precisa tentar 2 bilhões de vezes, embora o trabalho seja grande, ainda é completamente viável para um atacante determinado!

Este problema 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 apresenta problemas 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 certo tamanho, o atacante pode efetivamente construir um polinômio malicioso que parece normal nessas posições. Portanto, a questão de saber se eles podem ou não comprometer o protocolo é uma questão de probabilidade, e assim é necessário aumentar o número de verificações para melhorar a segurança geral, garantindo que seja possível defender-se efetivamente contra os ataques do atacante.

Isto leva a outra solução: corpos extensionais, que são semelhantes a corpos múltiplos, mas são baseados em corpos finitos. Introduzimos um novo valor, denotado por α, e declaramos que ele satisfaz uma certa relação, como α2=um certo valor. Desta forma, criamos uma nova estrutura matemática que permite operações mais complexas sobre corpos finitos. Neste corpo extensional, o cálculo da multiplicação torna-se a multiplicação usando o novo valor α. Agora podemos operar pares de valores no corpo estendido, e não apenas números individuais. Por exemplo, se estivermos a trabalhar em campos como Mersenne ou BabyBear, tal extensão permite-nos ter mais valores à escolha, aumentando assim a segurança. Para aumentar ainda mais o tamanho do campo, podemos aplicar repetidamente a mesma técnica. Uma vez que já utilizamos α, precisamos definir um novo valor, que em Mersenne31 se traduz em escolher α de forma que α2=um certo valor.

Através da extensão do domínio, agora temos um número suficiente de valores para escolher, satisfazendo as nossas necessidades de segurança. Se estivermos 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 alcançar um nível de segurança mais elevado, como 128 bits, podemos adicionar algum trabalho computacional extra ao protocolo para aumentar a segurança.

O domínio expandido é utilizado na prática apenas nos protocolos FRI 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 precisa apenas de hash de quatro bytes. Isso permite aproveitar a eficiência de campos pequenos, enquanto, quando é necessário aumentar a segurança, pode-se usar campos maiores.

FRI Regular

Na construção de SNARK ou STARK, o primeiro passo geralmente é a aritmetização. Isso envolve a transformação de um problema de cálculo arbitrário em uma equação, onde algumas variáveis e coeficientes são polinômios. Especificamente, essa equação geralmente se parecerá 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 tal equação é obtida, a solução dessa equação corresponde à solução do problema de cálculo subjacente.

Para provar que você tem uma solução, você precisa demonstrar que os valores que você apresentou são de fato polinômios razoáveis (e não frações, ou que em alguns lugares parecem ser um polinômio e em outros lugares são polinômios diferentes, etc.), e que esses polinômios têm um grau máximo específico. Para isso, usamos uma técnica de combinação linear aleatória aplicada passo a passo:

• Suponha que você tenha um valor de avaliação de um polinômio A, e você quer provar que seu grau é menor que 2^20
• Considerando 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 pares de A, e C isola os coeficientes ímpares. 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á em conformidade 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 grau do polinômio é d para o problema de provar que o grau do polinômio é d/2. Este processo pode ser repetido várias vezes, reduzindo o problema pela metade a cada vez.

O funcionamento do FRI é repetir esse processo de simplificação. Por exemplo, se você começar provando que o grau do polinômio é d, através de uma série de etapas, você acabará provando que o grau do polinômio é d/2. A cada simplificação, o grau do polinômio gerado diminui gradualmente. Se a saída em alguma fase não for o grau de 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 atender ao esperado, e na terceira rodada, a probabilidade de não estar correto aumentará, resultando na falha da verificação final. Esse design pode detectar e rejeitar efetivamente entradas que não atendem aos requisitos. Se o conjunto de dados for igual a um polinômio de grau d na maioria das posições, esse conjunto de dados pode passar na verificação do FRI. No entanto, para construir tal conjunto de dados, o atacante precisa conhecer o polinômio real, portanto, mesmo uma prova com pequenas falhas indica que o provador é capaz de gerar uma prova "real".

Vamos entender melhor o que está acontecendo aqui e quais são as propriedades necessárias para que tudo funcione corretamente. A cada passo, reduzimos o grau do polinômio pela metade, ao mesmo tempo que diminuímos pela metade o conjunto de pontos (o conjunto de pontos em que estamos interessados). O primeiro é fundamental para que o protocolo FRI funcione 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 que reduzamos 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 preserva 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 no conjunto. Se aplicarmos a operação de quadrado ao conjunto S (ou seja, mapeando cada elemento x no conjunto para x^2), o novo conjunto S^2 também preservará as mesmas propriedades. Esta operação nos permite continuar a reduzir o tamanho do conjunto de dados, até que, finalmente, reste apenas um valor. Embora, teoricamente, possamos encolher o conjunto de dados até que reste apenas um valor, na prática, normalmente paramos antes de chegar a 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 vezes ao redor da circunferência. Por exemplo, se um ponto na circunferência está 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 que está 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 os pontos na circunferência para suas novas posições a cada vez.

Para que a técnica de mapeamento seja eficaz, o tamanho do subgrupo de multiplicação 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 subgrupo de multiplicação máximo contém todos os valores diferentes de zero, portanto, o tamanho do subgrupo é 2k−1 (onde k é o número de bits do módulo). Esse tamanho de subgrupo é muito adequado para a técnica mencionada, pois permite reduzir eficientemente o grau do polinômio por meio 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, em seguida, aplicar o método FRI para reduzir gradualmente o grau do polinômio até 15 e, no final, verificar o grau do polinômio. Este método aproveita as propriedades do módulo e o tamanho do subgrupo de multiplicação, tornando o processo de cálculo muito eficiente. Mersenne31 é outro sistema, cujo módulo é um determinado valor, de modo que o tamanho do subgrupo de multiplicação é 2^31 - 1. Neste caso, o tamanho do subgrupo de multiplicação tem apenas uma potência de 2 como fator, o que significa que pode ser dividido por 2 apenas uma vez. O tratamento subsequente não se aplica mais à técnica mencionada, ou seja, não é possível usar FFT para uma redução eficiente 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. Isso se deve às características do seu módulo (por exemplo, 2^31 - 1), que permitem que muitas operações sejam realizadas utilizando operações de bits eficientes: se a soma de dois números exceder o módulo, o resultado pode ser reduzido a um intervalo apropriado através de operações de deslocamento com o módulo. As operações de deslocamento são uma forma de cálculo muito eficiente. Na multiplicação, instruções específicas da CPU (geralmente chamadas de instruções de deslocamento de bits altos) podem ser usadas para processar o resultado. Essas instruções podem calcular eficientemente a parte alta da multiplicação, aumentando assim a eficiência do cálculo. No domínio Mersenne31, devido às características acima, as operações aritméticas são cerca de 1,3 vezes mais rápidas do que no domínio BabyBear. Mersenne31 oferece maior eficiência computacional. Se o FRI puder ser implementado no domínio Mersenne31, isso aumentará significativamente a eficiência computacional, tornando o FRI aplicável.