Análise dos Princípios dos STARKs da Binius e Reflexões sobre a Otimização

1 Introdução

Um dos principais motivos para a baixa eficiência dos STARKs é que a maioria dos valores nos programas reais é bastante pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, quando os dados são expandidos usando codificação de Reed-Solomon, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que o valor original em si seja muito pequeno. Para resolver esse problema, a redução do 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 uma grande quantidade de espaço desperdiçado. Em comparação, o domínio binário permite operações diretas nos bits, codificando de forma compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs de 4ª geração.

Em comparação com as descobertas recentes de domínios finitos, 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, com exemplos típicos incluindo:

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

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

• Código QR, 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, sendo 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 usado pelo Binius depende completamente da extensão do domínio para garantir a sua segurança e a sua viabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não precisa de entrar na extensão do domínio, mas apenas operar no domínio base, alcançando assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam de aprofundar-se em extensões de domínio maiores para garantir a segurança necessária.

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

Binius propôs uma solução inovadora que lida com esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando 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"; em segundo lugar, uma vez que o comprimento de cada dimensão do hipercubo é 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas é possível considerar o hipercubo como um quadrado, realizando a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir a segurança, melhora significativamente a eficiência de codificação e o desempenho computacional.

2 Análise do Princípio

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

• Prova de Oráculo Interativo Polinomial Teórica da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de prova, transforma a relação computacional de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente, através da interação com o verificador, de modo que o verificador possa validar se o cálculo está correto consultando os resultados de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que diferem na forma como lidam com expressões polinomiais, impactando 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 equação polinomial gerada pelo PIOP é válida. O PCS é uma ferramenta criptográfica através da qual o provador pode se comprometer com um determinado polinômio e, posteriormente, verificar o resultado da avaliação desse polinômio, enquanto oculta outras informações do polinômio. Os esquemas de compromisso polinomial mais comuns incluem KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS têm diferentes desempenhos, segurança e cenários de aplicação.

De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com o domínio finito ou curva elíptica apropriada, podendo assim construir sistemas de prova com diferentes atributos. Por exemplo:

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

• Plonky2: Combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para permitir recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem ser compatíveis com o domínio finito ou curva elíptica utilizada, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não apenas afeta o tamanho da prova SNARK e a eficiência da verificação, mas também determina se o sistema pode alcançar transparência sem a necessidade de configurações confiáveis, 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 seu cálculo, permitindo operações simplificadas dentro do campo binário. Em segundo lugar, Binius adaptou a verificação de produtos e permutações do HyperPlonk em seu protocolo de prova de Oracle interativo (PIOP), garantindo uma verificação de consistência segura e eficiente entre as variáveis e suas permutações. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência na verificação de relações multilineares em pequenos campos. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequenos campos (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente no campo binário e reduzindo a sobrecarga normalmente associada a grandes campos.

2.1 Domínio finito: aritmética baseada em torres de campos binários

Os campos binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os campos binários suportam, por natureza, operações aritméticas altamente eficientes, tornando-os uma escolha ideal para aplicações criptográficas sensíveis ao desempenho. Além disso, a estrutura dos campos binários suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre os campos binários podem ser representadas em uma forma algébrica compacta e fácil de verificar. Essas características, juntamente com a capacidade de aproveitar plenamente suas propriedades hierárquicas através da estrutura em torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis, como o Binius.

O termo "canônico" refere-se à representação única e direta de elementos em um corpo binário. Por exemplo, no corpo binário mais básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de k bits do corpo binário. Isso é diferente dos corpos de prime, pois os corpos de prime não podem fornecer essa representação canônica dentro de um número fixo de bits. Embora um corpo de prime de 32 bits possa ser contido em 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento do corpo, enquanto o corpo binário possui essa conveniência de mapeamento um a um. No corpo de prime 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 corpos finitos específicos, como Mersenne-31 ou Goldilocks-64. No corpo binário F2k, os métodos de redução comumente utilizados incluem reduções especiais (como usadas no AES), reduções de Montgomery (como usadas no POLYVAL) e reduções recursivas (como Tower). O artigo "Explorando o Espaço de Design de Implementações de Hardware ECC em Corpos de Prime vs. Corpos Binários" destaca que no corpo binário, as operações de adição e multiplicação não requerem a introdução de transporte, e a operação de quadrado no corpo binário é muito eficiente, pois segue a regra simplificada de (X + Y )2 = X2 + Y 2.

Como mostrado na Figura 1, uma string de 128 bits: esta string pode ser interpretada de várias maneiras no contexto do domínio binário. Pode ser vista como um elemento único no domínio binário de 128 bits ou ser interpretada como dois elementos de domínio de torre de 64 bits, quatro elementos de domínio de torre de 32 bits, 16 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 de computação, apenas uma conversão de tipo da string de bits, sendo uma propriedade muito interessante e útil. Ao mesmo tempo, os elementos de pequeno domínio podem ser empacotados em elementos de domínio maior sem custo adicional de computação. 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 subdomínios de m bits).

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

O design do PIOP no protocolo Binius se baseia no HyperPlonk, adotando 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 operação 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 das permutações entre as variáveis do polinómio.

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

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 múltiplos 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 polinómico.

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

7. SumCheck: Verifica se a soma de um polinómio multivariável é igual ao valor declarado ∑x∈Hµ f(x) = s. Ao transformar o problema da avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional para a parte de verificação. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam o processamento em lote de múltiplos casos de verificação de soma.

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.

Embora Binius tenha muitas semelhanças de design de protocolo com HyperPlonk, ele faz melhorias nas seguintes 3 áreas:

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

• Tratamento do problema de divisão por zero: HyperPlonk não conseguiu lidar adequadamente com situações de divisão por zero, resultando na incapacidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, permitindo a promoção a qualquer valor de produto.

• Verificação de Permutação entre 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 situações de arranjo polinomial mais complexas.

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, oferecendo um suporte funcional mais forte. 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 multilinear------aplicável ao hipercubo booleano

No protocolo Binius, a construção e manipulação de polinómios virtuais é uma das tecnologias chave, capaz de gerar e operar eficazmente polinómios derivados de manípulos de entrada ou outros polinómios virtuais. Aqui estão dois métodos chave:

• Packing: Este método otimiza a operação ao agrupar elementos menores em posições adjacentes da ordem do dicionário em elementos maiores. O operador Pack é direcionado a blocos de tamanho 2κ e os agrupa.