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 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, ao usar a 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 primeira geração é de 252 bits, a largura de codificação dos STARKs de segunda geração é de 64 bits, e a largura de codificação dos STARKs de terceira 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 em bits, codificando de forma compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs de quarta 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çado ( AES ), baseado no domínio F28;

• Galois Código de Autenticação de Mensagens ( GMAC ), baseado no domínio F2128;

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

• O protocolo FRI original e o protocolo zk-STARK, bem como a função hash Grøstl, que chegou às finais do SHA-3, são baseados no domínio F28 e são um algoritmo de hash muito adequado para recursão.

Quando se utilizam domínios menores, a operação de extensão de domínio torna-se cada vez mais importante para garantir a segurança. O campo 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 dos Prover não precisa entrar na extensão de domínio, funcionando apenas no campo 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 ser aprofundados 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 da trace em STARKs, o tamanho do domínio usado 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 usado deve ser maior do que o tamanho após a expansão da codificação.

Binius propôs uma solução inovadora, tratando separadamente esses dois problemas e representando os mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariados ( em vez de polinômios univariados, representando toda a trajetória de cálculo através dos seus valores em "hipercubos" ); em segundo lugar, como cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma extensão padrão de Reed-Solomon como em STARKs, mas pode-se considerar o hipercubo como um quadrado (, baseando a extensão de Reed-Solomon 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 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 ): PIOP(: O PIOP, como o núcleo do sistema de prova, transforma as relações computacionais de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP, através da interação com o validador, permitem que o provador envie polinômios gradualmente, de modo que o validador possa verificar se a computação está correta 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 com uma abordagem diferente 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 que permite ao provador comprometer-se 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.

Conforme as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um campo finito ou curva elíptica apropriada, é possível 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 trusted setup do protocolo ZCash.

• Plonky2: utiliza PLONK PIOP combinado com FRI PCS e é baseado no domínio Goldilocks. Plonky2 é projetado para alcançar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao domínio 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 de verificação, mas também determina se o sistema pode alcançar transparência sem uma configuração de confiança, se pode suportar prova recursiva ou provas agregadas e outras funcionalidades de expansão.

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 )towers of binary fields( constitui a base de seus cálculos, 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 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 utilizou um esquema de compromisso polinomial de pequeno campo )Small-Field PCS(, permitindo a implementação de um sistema de prova eficiente no campo binário e reduzindo as sobrecargas geralmente associadas a grandes campos.

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

Os corpos binários em torre são a chave para implementar cálculos rapidamente verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os corpos binários, por sua natureza, suportam operações aritméticas altamente eficientes, tornando-os uma escolha ideal para aplicações criptográficas que são sensíveis ao desempenho. Além disso, a estrutura dos corpos binários suporta um processo de aritmética simplificada, ou seja, as operações realizadas sobre o corpo binário 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 da torre, tornam os corpos 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 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 é diferente do domínio primo, que não consegue fornecer essa representação canônica dentro de um número fixo de bits. Embora o domínio primo de 32 bits possa ser contido em 32 bits, nem toda string de 32 bits pode corresponder exclusivamente a um elemento de domínio, enquanto o domínio binário possui a conveniência de tal mapeamento um-para-um. No domínio primo Fp, os métodos de redução comuns incluem a redução Barrett, a redução Montgomery, e métodos de redução especiais 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 ( usada no AES ), a redução Montgomery ### usada no POLYVAL (, e a redução recursiva ) como a Tower (. O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indica que o domínio binário não requer a introdução de transportes em operações de adição e multiplicação, e a operação de quadrado no domínio binário é extremamente 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 em um domínio binário de 128 bits, ou pode ser analisada como dois elementos de domínio torre de 64 bits, quatro elementos de domínio torre de 32 bits, 16 elementos de domínio torre de 8 bits, ou 128 elementos de domínio F2. Essa flexibilidade de representação não requer qualquer sobrecarga computacional, apenas uma conversão de tipo da string de bits )typecast(, 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 sobrecarga 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 torre de n bits ) que pode ser decomposto em subdomínios de m bits (.

![Bitlayer Research: Análise dos princípios STARKs da Binius e reflexões sobre a otimização])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

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

O design PIOP no protocolo Binius foi inspirado no HyperPlonk e utiliza uma série de mecanismos de verificação fundamentais para validar a correção de polinómios e conjuntos multivariados. Esses verificadores fundamentais incluem:

1. GateCheck: validar se o testemunho confidencial ω e a entrada pública x satisfazem a relação de operação 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 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 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 vários conjuntos.

5. ProductCheck: verificar 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 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 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 o verificador. Além disso, o SumCheck permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares, permitindo o processamento em lote de várias instâncias de verificação de soma.

8. BatchCheck: baseado no SumCheck, valida a correção da avaliação de vários polinômios multivariados, para aumentar a eficiência do protocolo.

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

• Otimização do ProductCheck: no HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em toda a hipercubo, e o produto deve ser igual a um valor específico; Binius simplifica esse processo de verificação ao especializar esse valor em 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 impossibilidade de afirmar que U é diferente de zero no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, permitindo a generalização para 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, permitindo que o Binius lide 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 existente PIOPSumCheck, especialmente ao lidar com a verificação de polinómios multivariáveis mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não só resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para sistemas de prova futuros baseados em campos binários.

![Bitlayer Research: Análise dos princípios dos STARKs da Binius e reflexões sobre sua otimização])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(

) 2.3 PIOP: novo argumento de deslocamento multilinhar------aplicável ao hiper-cubo booleano

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

• Embalagem: Este método funciona ao