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

1 Introdução

Uma das principais razões para a ineficiência dos STARKs é: 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 da prova baseada em árvores de Merkle, ao usar codificação de Reed-Solomon para expandir os dados, muitos valores adicionais de redundância 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 da 1ª geração é de 252 bits, a largura de codificação dos STARKs da 2ª geração é de 64 bits, e a largura de codificação dos STARKs da 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, com codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs da 4ª geração.

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

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

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

• Código QR, usando codificação Reed-Solomon baseada em F28;

• O protocolo FRI original e o zk-STARK, assim como a função de hash Grøstl que chegou à final do SHA-3, que é baseada no domínio F28, são algoritmos de hash muito adequados 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 deve depender 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 dos Provers não necessita de entrar na extensão de domínio, operando 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 de se aprofundar 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 de traços em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinômio; ao comprometer a árvore Merkle em STARKs, é necessário fazer 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 apresentou uma solução inovadora, abordando essas duas questões separadamente e representando os mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariados (, especificamente polinômios multilineares ), em vez de polinômios univariados, para representar toda a trajetória de cálculo através de seus valores em hipercubos (; em segundo lugar, como cada dimensão do hipercubo tem um comprimento de 2, não é possível realizar a 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, enquanto garante 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 Teórica da Informação ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): O PIOP, como o núcleo do sistema de prova, transforma a relação de cálculo de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios progressivamente por meio da interação com o verificador, permitindo que o verificador valide se o cálculo está correto consultando apenas os resultados da avaliação de um número limitado de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes abordagens para o tratamento de 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 a igualdade 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 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-os com um domínio finito ou curva elíptica adequada, podendo assim construir sistemas de prova com diferentes atributos. Por exemplo:

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

• Plonky2: utiliza PLONK PIOP e FRI PCS em combinação, e é baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar recursividade eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao campo 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 e a eficiência de 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 domínio binário (towers of binary fields) forma 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 consistente 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 domínios. Quarto, Binius utilizou uma versão melhorada da prova de busca Lasso, proporcionando flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo emprega um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo a implementação de um sistema de provas eficiente sobre o domínio binário e reduzindo as despesas normalmente associadas a grandes domínios.

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

Os campos binários em torre são fundamentais para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculo eficiente e aritmética eficiente. Os campos binários suportam essencialmente 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 do campo binário apoia um processo de aritmética simplificado, ou seja, as operações realizadas no campo binário podem ser representadas de forma algébrica compacta e facilmente verificável. Essas características, somadas à capacidade de tirar pleno proveito de suas características 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 "canonical" refere-se à representação única e direta de um elemento 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 difere dos campos de primos, que não conseguem fornecer essa representação canônica dentro de um número fixo de bits. Embora um campo primo de 32 bits possa ser contido dentro de 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento de 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 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 campo binário F2k, os métodos de redução comumente usados incluem a redução especial ), como usada no AES ###, a redução de Montgomery (, como utilizada no POLYVAL ), e a redução recursiva (, como na Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que no campo binário, tanto a adição quanto a multiplicação não requerem o transporte, e a operação de quadrado no campo binário é muito eficiente, pois segue a regra simplificada de (X + Y )2 = X2 + Y2.

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. Ela 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, 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 computacional, é apenas uma conversão de tipo da string de bits (typecast), 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 custos computacionais adicionais. 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 domínios de torre binária de n bits ( que podem ser decompostos em subdomínios de m bits ).

( 2.2 PIOP: versão adaptada do Produto HyperPlonk e Verificação de Permutação ------ aplicável ao campo binário

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

1. GateCheck: Verifica se o testemunho secreto ω e a entrada pública x satisfazem a relação de cálculo do circuito C)x, ω###=0, para garantir o funcionamento correto do circuito.

2. PermutationCheck: Verificar se os resultados da avaliação de dois polinômios multivariados 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: Verificar se a avaliação do polinômio está na tabela de pesquisa dada, ou seja, f)Bµ) ⊆ T(Bµ), garantindo que certos valores estejam 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 racional no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto do polinómio.

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 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 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 em 3 aspectos a seguir:

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

• Tratamento do problema de divisão por zero: 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; Binius lidou corretamente com este 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 em 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 multivariados mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram as bases 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 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 de outros polinómios virtuais. Aqui estão dois métodos chave:

• Embalagem: Este método passa por