Análise dos princípios dos STARKs da Binius e reflexão sobre a otimização

1 Introdução

Uma das principais razões para a ineficiência dos STARKs é que a maioria dos valores em 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, ao usar codificação de Reed-Solomon para expandir os dados, 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 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 sobre os bits, tornando a codificação compacta, eficiente e sem qualquer espaço desperdiçado, ou seja, a 4ª geração de STARKs.

Comparado 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 já 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 à final do SHA-3, baseada no domínio F28, que é 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. O domínio binário utilizado pela Binius depende completamente da extensão de 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 de domínio, funcionando apenas no domínio base, o que permite uma alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam ser aprofundados em um domínio de extensão maior para garantir a segurança necessária.

Ao construir sistemas de prova com base em domínios binários, existem 2 problemas práticos: ao calcular a representação do trace em STARKs, o tamanho do domínio deve ser maior do 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 deve ser maior do que o tamanho após a expansão da codificação.

A Binius propôs uma solução inovadora que aborda 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 unidimensionais, representando toda a trajetória de cálculo através dos seus valores no "hipercubo" (hypercubes); em segundo lugar, dado 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 considerado como um quadrado (square), e a extensão de Reed-Solomon pode ser baseada nesse quadrado. Este método, enquanto assegura a segurança, aumenta significativamente a eficiência de codificação e o desempenho computacional.

2 Análise de Princípios

Atualmente, a construção da maioria dos sistemas SNARKs geralmente inclui as seguintes duas partes:

• Prova de Oracle Interativa Polinomial de Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o 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 da avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, cada um dos quais trata as expressões polinomiais de maneira diferente, 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 equação polinomial gerada pelo PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se com um determinado polinômio e, posteriormente, verificar o resultado da avaliação desse polinômio, ao mesmo tempo que 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 possuem diferentes desempenhos, níveis de segurança e cenários de aplicação.

De acordo com as necessidades específicas, escolha diferentes PIOP e PCS e, em combinação com um campo finito ou uma curva elíptica adequada, é possível construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combina PLONK PIOP com 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: combina PLONK PIOP com FRI PCS, baseado no domínio Goldilocks. Plonky2 é projetado para implementar recursão eficiente. Ao projetar esses sistemas, a PIOP e o PCS escolhidos devem corresponder ao domínio 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 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çã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 seus cálculos, 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 interativo (PIOP), garantindo a 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 validação de relações multilineares em pequenos domínios. Quarto, 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 de polinômios de pequeno domínio (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o domínio binário e reduzindo os custos normalmente 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 computação rápida e verificável, principalmente devido a dois aspectos: cálculo eficiente e aritmética eficiente. O domínio binário, por sua essência, suporta operações aritméticas altamente eficientes, tornando-o uma escolha ideal para aplicações criptográficas sensíveis ao desempenho. Além disso, a estrutura do domínio binário apoia um processo de aritmética simplificado, ou seja, as operações realizadas no domínio binário podem ser representadas em uma forma algébrica compacta e fácil de verificar. Essas características, combinadas com a capacidade de aproveitar totalmente suas características 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 "canônico" refere-se à representação única e direta de elementos no campo binário. Por exemplo, no campo binário mais básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de campo binário de k bits. Isso é diferente do campo primo, que não pode fornecer essa representação canônica dentro de um número fixo de bits. Embora um campo 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 campo, enquanto o campo binário possui essa conveniência de mapeamento um-para-um. Nos campos primos Fp, os métodos de redução comuns incluem a redução Barrett, a redução Montgomery, e métodos especiais de redução para campos finitos específicos como Mersenne-31 ou Goldilocks-64. No campo binário F2k, os métodos de redução comuns incluem reduções especiais (como usadas no AES), reduções Montgomery (como usadas no POLYVAL) e reduções recursivas (como a Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que no campo binário não é necessário introduzir transporte em operações de adição e multiplicação, e a operação de quadrado no campo 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. Ela pode ser vista como um elemento único em um domínio binário de 128 bits, ou pode ser analisada 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 de 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 menores podem ser empacotados em elementos de domínio maiores sem necessidade de custo computacional adicional. O protocolo Binius aproveita essa característica para aumentar a eficiência computacional. Além disso, o artigo "On Efficient Inversion in Tower Fields of Characteristic Two" explora a complexidade computacional de realizar multiplicação, quadrado e operações de 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 inspira-se 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 das permutações entre as variáveis polinomiais.

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 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 múltiplos conjuntos.

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

6. ZeroCheck: Verificar se um polinómio multivariável é zero em qualquer ponto do hipercubo booleano ∏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 do verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que permitem o processamento em lote de várias instâncias de verificação de soma.

8. BatchCheck: Baseado no SumCheck, verifica 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 fez melhorias nas seguintes 3 áreas:

• ProductCheck otimizado: No HyperPlonk, o ProductCheck exige que o denominador U seja sempre diferente de zero sobre o hipercubo, e que o produto seja igual a um valor específico; a Binius simplifica esse processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade computacional.

• Tratamento do problema da divisão por zero: o HyperPlonk não conseguiu lidar adequadamente com a situação de divisão por zero, levando à impossibilidade de afirmar que U é não nulo no hipercubo; o Binius tratou corretamente deste problema, mesmo quando o denominador é zero, o ProductCheck do Binius pode continuar a processar, permitindo a promoção a qualquer valor de produto.

• Verificação de Permutação entre Colunas: HyperPlonk não possui essa 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 existente de PIOPSumCheck, especialmente ao lidar com a verificaçã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 a base para futuros sistemas de prova baseados em domínios binários.

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

No protocolo Binius, a construção e o processamento de polinómios virtuais é uma das tecnologias-chave, capaz de gerar e operar de forma eficaz polinómios derivados de manipuladores de entrada ou de outros polinómios virtuais. Aqui estão dois métodos-chave:

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