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 é: a maioria dos valores em programas reais é bastante pequena, mas, para garantir a segurança da prova baseada em árvore 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, com codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs de 4ª geração.

Comparado com as novas descobertas de domínios finitos, como Goldilocks, BabyBear e Mersenne31 nos últimos anos, 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çada (AES), baseado no domínio F28
• Galois Message Authentication Code ( GMAC ), baseado no domínio F2128
• QR code, usando codificação Reed-Solomon baseada em F28
• Protocólos FRI e zk-STARK originais, assim como a função de hash Grøstl que chegou à fase final do SHA-3, que é baseada no domínio F28, sendo 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 domínio binário utilizado pela Binius depende completamente da extensão de domínio para garantir a sua segurança e usabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não precisa entrar na extensão de domínio, operando apenas no domínio base, alcançando assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e os cálculos FRI ainda precisam aprofundar-se em domínios de extensão maiores 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 de trace 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 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 trata desses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariável (, especificamente um polinômio multilinhar ), em vez de um polinômio univariável, representando toda a trajetória computacional através de seus valores em "hipercubos" (; em segundo lugar, como cada dimensão do hipercubo tem comprimento igual a 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 segurança, melhora significativamente a eficiência de codificação e o desempenho computacional.

2. Análise dos Princípios

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

• Prova Oracle Interativa Polinomial Teórica da Informação (: 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 permitem que o provador envie polinômios gradualmente através da interação com o verificador, permitindo que o verificador valide se o cálculo está correto consultando apenas alguns resultados de avaliação 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, afetando assim o desempenho e a eficiência do sistema SNARK como um todo.

• 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 comprometer-se com um determinado polinômio e posteriormente verificar o resultado 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, entre outros. Diferentes PCS têm desempenhos, segurança e cenários de aplicação distintos.

De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um campo finito ou uma curva elíptica adequada, para construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combina PLONK PIOP e Bulletproofs PCS, baseando-se na curva Pasta. O Halo2 foi projetado com foco na escalabilidade e na remoção da configuração confiável 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 campo finito ou à curva elíptica utilizada, para 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 e a eficiência da verificação do SNARK, mas também determina se o sistema pode alcançar transparência sem a necessidade de um setup confiável, e se pode suportar funcionalidades expandidas, como provas recursivas ou provas agregadas.

Binius: HyperPlonk PIOP + Brakedown PCS + domínios binários. Especificamente, Binius inclui cinco tecnologias-chave para alcançar sua eficiência e segurança. Primeiro, a aritmética baseada em torres de domínios binários )towers of binary fields( 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 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 variáveis e suas permutações. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência da verificação de relações multilineares em pequenos domínios. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, oferecendo 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 a implementação de um sistema de prova eficiente no domínio binário e reduzindo as despesas geralmente associadas a grandes domínios.

) 2.1 Campos finitos: aritmética baseada em torres de campos binários

O campo binário em torre é a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculo eficiente e aritmética eficiente. O campo binário 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 campo binário suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre o campo binário podem ser representadas de 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 o campo binário particularmente adequado para sistemas de prova escaláveis como o Binius.

O termo "canonical" refere-se à representação única e direta de elementos 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 dos domínios primários, 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 a um. No domínio primo Fp, os métodos comuns de redução incluem a redução Barrett, a redução 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 usado em AES ), a redução Montgomery ### como usado em 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 o domínio binário não requer a introdução de transporte em operações de adição e multiplicação, e que 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: 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 pode ser interpretada 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. Esta flexibilidade de representação não requer nenhum custo 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ínios pequenos podem ser agrupados em elementos de domínio maiores sem a necessidade de 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 da multiplicação, quadratura e operação de inversão em domínios torre binários de n bits ) que podem ser decompostos em subdomínios de m bits (.

![Bitlayer Research: Análise do princípio dos STARKs da Binius e suas reflexões sobre 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 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 fundamentais para validar a correção de polinómios e conjuntos multivariáveis. Esses mecanismos de verificação fundamentais 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: Verificar se os resultados da avaliação dos 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 busca 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 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 é 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 um problema de avaliação de polinómios univariáveis, reduz a complexidade computacional para a parte de verificação. 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 múltiplos casos de verificação de soma.

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

Embora Binius e HyperPlonk tenham muitas semelhanças no design do protocolo, Binius fez melhorias nas seguintes 3 áreas:

• Otimização do ProductCheck: no HyperPlonk, o ProductCheck requer que o denominador U seja sempre diferente de zero no hipercubo, e o produto deve ser igual a um valor específico; a Binius simplificou esse 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, resultando na incapacidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius pode continuar a processar, permitindo a generalização para 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 PIOPSumCheck, especialmente ao lidar com a verificação de polinómios multivariados mais complexos, proporcionando 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 provas baseados em campos binários.

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

) 2.3 PIOP: novo argumento de mudança multilinear ------ aplicável ao hipercubo booleano

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

• Packing: Este método empacota os elementos menores em posições adjacentes na ordem do dicionário em elementos maiores.