Análise do Princípio dos STARKs da Binius e Reflexões sobre sua Otimização

1 Introdução

Uma das principais razões para a baixa eficiência dos STARKs é que a maioria dos valores nos programas reais é bastante pequena, mas para garantir a segurança das provas baseadas em árvores de Merkle, ao usar a codificação Reed-Solomon para expandir os dados, muitos valores de redundância adicionais ocupam todo o domínio, mesmo que o valor original em si seja muito pequeno. Para resolver esse problema, reduzir o tamanho do domínio tornou-se uma estratégia chave.

A largura de codificação dos STARKs de 1ª geração é de 252 bits, a largura de codificação dos STARKs de 2ª geração é de 64 bits, e a largura de codificação dos STARKs de 3ª geração é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta um grande desperdício de espaço. Em contraste, o domínio binário permite a operação direta sobre os bits, com codificação compacta e eficiente, sem nenhum espaço desperdiçado, ou seja, os STARKs de 4ª geração.

Em comparação com os domínios finitos descobertos em pesquisas recentes como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre domínios binários remonta à década de 1980. Atualmente, os domínios binários são amplamente utilizados na criptografia, exemplos típicos incluem:

• Padrão de Criptografia Avançada (AES), baseado no domínio F28;

• Galois Message Authentication Code ( GMAC ), baseado no domínio F2128;

• QR Code, usando codificação Reed-Solomon baseada em F28;

• Protocólos FRI originais e zk-STARK, bem como a função de hash Grøstl que chegou à final do SHA-3, que é baseada no domínio F28, é um algoritmo de hash muito adequado para recursão.

Quando se utiliza um domínio menor, a operação de extensão do domínio torna-se cada vez mais importante para garantir a segurança. O domínio binário utilizado pela Binius depende completamente da extensão do domínio para garantir a sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não precisa entrar na extensão do domínio, operando apenas no domínio base, conseguindo assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda necessitam de se aprofundar em um domínio de extensão maior para garantir a segurança necessária.

Ao construir um sistema de provas baseado em domínios binários, existem 2 problemas práticos: ao calcular a representação de traço em STARKs, o tamanho do domínio utilizado deve ser maior que o grau do polinômio; ao comprometer a árvore Merkle em STARKs, é necessário realizar a codificação de Reed-Solomon, e o tamanho do domínio utilizado deve ser maior que o tamanho após a expansão da codificação.

A Binius propôs uma solução inovadora que trata separadamente esses dois problemas e representa os mesmos dados de duas maneiras diferentes: primeiro, usando polinómios multivariáveis (especificamente polinómios multilineares) em vez de polinómios univariáveis, representando toda a trajetória de cálculo através dos seus valores em "hipercubos"; segundo, uma vez que cada dimensão do hipercubo tem um comprimento de 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado, permitindo a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir segurança, melhora significativamente a eficiência de codificação e o desempenho computacional.

2 Análise de Princípios

A construção da maioria dos sistemas SNARKs atualmente geralmente inclui as seguintes duas partes:

• Prova de Oracle Interativa Polinomial com Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de prova, transforma a relação de cálculo de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP, através da interação com o verificador, permitem que o provador envie polinômios de forma gradual, de modo que o verificador possa validar se o cálculo está correto consultando os resultados da avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, que têm maneiras diferentes de tratar expressões polinomiais, afetando assim o desempenho e a eficiência de todo o sistema SNARK.

• Esquema de Compromisso Polinomial (Polynomial Commitment Scheme, PCS): O esquema de compromisso polinomial é utilizado para provar se a igualdade polinomial gerada pelo PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provedor comprometer-se com um determinado polinômio e posteriormente verificar o resultado da avaliação desse polinômio, enquanto oculta outras informações sobre o polinômio. Os esquemas de compromisso polinomial mais comuns incluem KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS possuem diferentes desempenhos, segurança e cenários de aplicação.

De acordo com as necessidades específicas, escolha diferentes PIOP e PCS e combine-os com um campo finito adequado ou curva elíptica, podendo assim construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: Combina PLONK PIOP e Bulletproofs PCS, baseado na curva Pasta. O Halo2 foi projetado com foco na escalabilidade e na remoção do setup confiável do protocolo ZCash.

• Plonky2: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao campo finito ou à curva elíptica utilizada, a fim de garantir a correção, o desempenho e a segurança do sistema. A escolha dessas combinações não apenas afeta o tamanho da prova e a eficiência da verificação do SNARK, mas também determina se o sistema pode alcançar transparência sem a necessidade de uma configuração confiável, e se pode suportar funcionalidades expandidas, como provas recursivas ou provas agregadas.

Binius: HyperPlonk PIOP + Brakedown PCS + domínio binário. Especificamente, Binius inclui cinco tecnologias-chave para alcançar sua eficiência e segurança. Primeiro, a aritmética baseada em torres de campos binários constitui a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adaptou a verificação de produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Terceiro, o protocolo introduz uma nova prova de deslocamento multilinear, otimizando a eficiência da verificação de relações multilineares em pequenos domínios. Quarto, Binius utiliza uma versão aprimorada da prova de busca Lasso, oferecendo flexibilidade e forte segurança para o mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo que ele implemente um sistema de prova eficiente sobre o domínio binário e reduzindo os custos geralmente associados a grandes domínios.

2.1 Domínios finitos: aritmética baseada em torres de campos binários

O domínio binário em torre é a chave para implementar cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculo eficiente e aritmética eficiente. O domínio binário suporta essencialmente operações aritméticas altamente eficientes, tornando-o uma escolha ideal para aplicações criptográficas que são sensíveis ao desempenho. Além disso, a estrutura do domínio binário suporta um processo de aritmética simplificado, ou seja, as operações realizadas no domínio binário podem ser representadas de forma compacta e fácil de verificar na forma algébrica. Essas características, juntamente com a capacidade de tirar pleno proveito de suas propriedades hierárquicas através da estrutura de torre, tornam o domínio binário particularmente adequado para sistemas de prova escaláveis, como o Binius.

O termo "canonical" refere-se à representação única e direta de um elemento no domínio binário. Por exemplo, no domínio binário mais básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do domínio binário de k bits. Isso difere dos domínios primários, onde não é possível fornecer essa representação canônica dentro de um número fixo de bits. Embora o domínio primo de 32 bits possa caber dentro de 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento do domínio, enquanto o domínio binário possui essa conveniência de mapeamento um a um. No domínio primo Fp, os métodos de redução comuns incluem a redução de Barrett, a redução de Montgomery e métodos de redução especiais para campos finitos específicos, como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, os métodos de redução comuns incluem reduções especiais (como usadas no AES), reduções de Montgomery (como usadas no POLYVAL) e reduções recursivas (como na Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que no domínio binário não é necessário introduzir transporte em operações de adição e multiplicação, e que a operação de quadrado no domínio binário é muito eficiente, pois segue a regra simplificada (X + Y )2 = X2 + Y 2.

Como mostrado na Figura 1, uma string de 128 bits: essa string pode ser interpretada de várias maneiras no contexto de um domínio binário. Pode ser vista como um elemento único no domínio binário de 128 bits, ou pode ser interpretada como dois elementos de domínio de torre de 64 bits, quatro elementos de domínio de torre de 32 bits, dezesseis elementos de domínio de torre de 8 bits, ou 128 elementos do domínio F2. Essa flexibilidade de representação não requer nenhum custo computacional, sendo apenas uma conversão de tipo da string de bits, o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser empacotados em elementos de domínio maiores sem necessidade de custo computacional adicional. O protocolo Binius aproveita essa característica para melhorar a eficiência computacional. Além disso, o artigo "On Efficient Inversion in Tower Fields of Characteristic Two" explora a complexidade computacional das operações de multiplicação, quadrado e inversão em um domínio binário de torre de n bits (que pode ser decomposto em m bits de subdomínio).

2.2 PIOP: versão adaptada do HyperPlonk Product e PermutationCheck------aplicável ao campo binário

O design do PIOP no protocolo Binius foi inspirado no HyperPlonk e utiliza uma série de mecanismos de verificação essenciais para validar a correção de polinômios e conjuntos multivariados. Essas verificações essenciais incluem:

1. GateCheck: Verifica se o testemunho confidencial ω e a entrada pública x satisfazem a relação de cálculo do circuito C(x,ω)=0, para garantir que o circuito funcione corretamente.

2. PermutationCheck: Verifica se os resultados da avaliação de dois polinómios multivariáveis f e g no hipercubo booleano são uma relação de permutação f(x) = f(π(x)), para garantir a consistência da permutação entre as variáveis do polinómio.

3. LookupCheck: Verifica se a avaliação do polinómio está na tabela de procura dada, ou seja, f(Bµ) ⊆ T(Bµ), garantindo que certos valores estão dentro do intervalo especificado.

4. MultisetCheck: Verifica se dois conjuntos multivariáveis são iguais, ou seja, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantindo a consistência entre vários conjuntos.

5. ProductCheck: Verifica se a avaliação de um polinómio racional no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto polinomial.

6. ZeroCheck: Verifica se um polinómio multivariável em um hipercubo booleano em qualquer ponto é zero ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.

7. SumCheck: Verifica se a soma de polinómios multivariáveis é igual ao valor declarado ∑x∈Hµ f(x) = s. Ao transformar o problema da avaliação de polinómios multivariáveis em um problema de avaliação de polinómios univariados, reduz a complexidade computacional do verificador. Além disso, o SumCheck permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares e realizar o processamento em lote de várias instâncias de verificação de somas.

8. BatchCheck: Baseado no SumCheck, valida a correção da avaliação de múltiplos polinômios multivariados para aumentar a eficiência do protocolo.

Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius faz melhorias nas seguintes 3 áreas:

• ProductCheck otimizado: no HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em todos os pontos do hipercubo, e que o produto seja igual a um valor específico; a Binius simplificou este processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade computacional.

• Tratamento do problema da divisão por zero: HyperPlonk não conseguiu lidar adequadamente com situações de divisão por zero, levando à impossibilidade de afirmar que U é diferente de zero no hipercubo; Binius tratou corretamente esse problema, permitindo que o ProductCheck do Binius continuasse a processar mesmo quando o denominador é zero, permitindo a generalização para qualquer valor de produto.

• Verificação de Permutação de Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a verificação de permutação entre várias colunas, o que permite que o Binius lide com casos de arranjo polinomial mais complexos.

Assim, a Binius melhorou a flexibilidade e a eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente, especialmente ao lidar com a verificação de polinómios multivariáveis mais complexos, proporcionando um suporte funcional mais robusto. Estas melhorias não só resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em campos binários.

2.3 PIOP: novo argumento de deslocamento multilinhar ------ aplicável ao hipercubo booleano

No protocolo Binius, a construção e o manuseio de polinômios virtuais são uma das técnicas chave, capazes de gerar e operar efetivamente polinômios derivados de manipulações de entrada ou de outros polinômios virtuais. Abaixo estão dois métodos chave:

• Packing: Este método otimiza a operação, agrupando elementos menores em posições adjacentes da ordem do dicionário em elementos maiores. O operador Pack é direcionado a blocos de tamanho 2κ e combina-os em um único elemento em um domínio de alta dimensão. Através da expansão multilinear.