Análise dos princípios do Binius STARKs e reflexões sobre a 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, como índices em laços 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, reduzir o tamanho do domínio tornou-se uma estratégia chave.

A largura de codificação da 1ª geração dos STARKs é de 252 bits, a largura de codificação da 2ª geração dos STARKs é de 64 bits, e a largura de codificação da 3ª geração dos STARKs é 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 campo binário permite operações diretas nos bits, com uma codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, a 4ª geração dos STARKs.

Comparado com os novos estudos sobre campos finitos, como Goldilocks, BabyBear e Mersenne31, descobertos nos últimos anos, a pesquisa sobre campos binários remonta à década de 80 do século passado. Atualmente, os campos 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;

• 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 às finais do SHA-3, 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 de domínio torna-se cada vez mais importante para garantir a segurança. E o domínio binário utilizado pelo Binius depende completamente da extensão de domínio para garantir sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos de Prover não precisa ser estendida, 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 precisam aprofundar-se em um domínio de extensão maior para garantir a segurança necessária.

Ao construir sistemas de prova baseados em domínios binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinômio; ao fazer a promessa da árvore 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 aborda essas duas questões 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 de seus valores em "hipercubos"; em segundo lugar, uma vez que o comprimento de cada dimensão do hipercubo é 2, não é possível realizar a extensão padrão de Reed-Solomon como nos STARKs, mas pode-se considerar o hipercubo como um quadrado (square) e realizar 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 de cálculo.

2 Análise dos Princípios

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

• Prova de Oráculo Interativo Polinomial de Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de provas, transforma a relação de cálculo 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 pequeno número de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes maneiras de lidar com expressões polinomiais, o que afeta 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 as igualdades polinomiais geradas pelo PIOP são válidas. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se a um determinado polinômio e, posteriormente, verificar os resultados 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. Diferentes PCS apresentam 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 um campo finito ou curva elíptica apropriada, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:

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

• Plonky2: Adota PLONK PIOP e FRI PCS combinados, e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao campo finito ou curva elíptica utilizada, a fim de 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 uma configuração confiável, e se pode suportar funções 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 domínio binário. Em segundo lugar, Binius adaptou a verificação de produto e permutação do HyperPlonk em seu protocolo de prova de Oracle interativa (PIOP), assegurando uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Em terceiro lugar, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência na verificação de relações multilineares em pequenos domínios. Em quarto lugar, Binius adotou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança ao mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo que ele implementasse um sistema de prova eficiente no domínio binário e reduzisse as despesas normalmente associadas a grandes domínios.

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

Os domínios binários em torre são a chave para a realização de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os domínios binários, essencialmente, suportam 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 domínios binários apoia um processo de aritmética simplificado, ou seja, as operações realizadas sobre os domínios binários podem ser representadas de forma compacta e fácil de verificar na forma algébrica. Essas características, juntamente com a capacidade de aproveitar plenamente suas propriedades hierárquicas através da estrutura em torre, tornam os domínios binários particularmente adequados para sistemas de prova escaláveis, como o Binius.

Onde "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 de domínio binário de k bits. Isso difere dos domínios de primos, que não conseguem fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa ser contido em 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-para-um. No domínio primo Fp, métodos comuns de redução incluem a redução de Barrett, a redução de Montgomery, e métodos especiais de redução para domínios finitos específicos, como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, os métodos de redução comuns incluem a redução especial (como usada no AES), a redução de Montgomery (como usada no POLYVAL) e a redução recursiva (como Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que no domínio binário, tanto a adição quanto a multiplicação não requerem a introdução de transporte, e 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 analisada como dois elementos do domínio torre de 64 bits, quatro elementos do domínio torre de 32 bits, 16 elementos do domínio torre de 8 bits, ou 128 elementos do domínio F2. Essa flexibilidade de representação não requer nenhum custo computacional, apenas uma conversão de tipo (typecast) da string de bits, o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequeno podem ser empacotados em elementos de domínio maiores sem 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 de multiplicação, quadrados e operações de inversão em um domínio torre binário de n bits (que pode ser decomposto em um subdomínio de m bits).

2.2 PIOP: Versão adaptada do HyperPlonk Product e PermutationCheck ------ aplicável ao domínio 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 o correto funcionamento do circuito.

2. PermutationCheck: Verifica se os resultados de 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 busca fornecida, ou seja, f(Bµ) ⊆ T(Bµ), garantindo que certos valores estejam dentro do intervalo especificado.

4. MultisetCheck: verificar se dois conjuntos multivariados 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 de Booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto do polinómio.

6. ZeroCheck: Verifica 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 unidimensionais, reduz a complexidade computacional para o verificador. Além disso, o SumCheck permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam 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 multivariáveis, para aumentar a eficiência do protocolo.

Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius fez 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 o produto deve ser igual a um valor específico; Binius simplificou esse 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 a situação de divisão por zero, resultando na incapacidade de afirmar que U não é zero no hipercubo; Binius tratou corretamente deste problema, mesmo quando o denominador é zero, permitindo que o ProductCheck da Binius continuasse a processar, permitindo a promoção para qualquer valor de produto.

• Verificação de Permutação entre Colunas: O HyperPlonk não possui esta funcionalidade; o Binius suporta a verificação de permutação entre várias colunas, o que permite ao Binius lidar com situações de arranjos polinomiais 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 validação de polinómios multivariados mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não apenas 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 processamento de polinômios virtuais são uma das tecnologias-chave, capazes de gerar e operar de forma eficaz polinômios derivados de manipuladores de entrada ou outros polinômios virtuais. Aqui estão dois métodos-chave:

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