Análise dos Princípios dos STARKs da Binius e Reflexões sobre a sua Otimização

1 Introdução

Um dos principais motivos para a ineficiência dos STARKs é que a maioria dos valores em programas reais é relativamente pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvores de Merkle, o uso de codificação Reed-Solomon para expandir os dados resulta em muitos valores redundantes adicionais que 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, 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 um grande desperdício de espaço. Em comparação, o campo binário permite operações diretas em bits, com uma codificação compacta e eficiente, sem nenhum espaço desperdiçado, ou seja, os STARKs de 4ª geração.

Comparado com os domínios finitos descobertos por novas pesquisas nos últimos anos, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre domínios binários remonta à década de 80 do século passado. Atualmente, os domínios binários já são amplamente aplicados 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;

• Os protocolos FRI originais e zk-STARK, bem como a função de hash Grøstl, que chegou à final 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 domínio binário utilizado pela Binius depende completamente da extensão de domínio para garantir a sua segurança e a sua viabilidade 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, o que permite uma 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 uma extensão de domínio maior 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 do trace em STARKs, o tamanho do domínio utilizado deve ser maior 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 que o tamanho após a expansão da codificação.

Binius apresentou uma solução inovadora que trata esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariados (, especificamente polinômios multilineares ), em vez de polinômios univariados, representando todo o trajeto computacional 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 uma extensão padrão de Reed-Solomon como em STARKs, mas o hipercubo pode ser considerado como um quadrado ), e a extensão de Reed-Solomon pode ser baseada nesse quadrado. Este método, enquanto assegura a 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:

• Informação Teórica Prova Interativa Polinomial, PIOP(: O PIOP, como 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 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: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um deles tratando 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 uma equação polinomial gerada por PIOP é verdadeira. 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 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 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 adequada, pode-se 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: utiliza PLONK PIOP combinado com FRI PCS e baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão de forma eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas 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 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 campos 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 produto e permutação do HyperPlonk em seu protocolo de prova Oracle interativa )PIOP(, garantindo uma verificação de consistência segura e eficiente entre as variáveis e suas permutações. Em terceiro lugar, o protocolo introduziu uma nova prova de deslocamento multilateral, otimizando a eficiência da verificação de relações multiliniares em pequenos domínios. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e segurança robusta para o mecanismo de busca. Finalmente, o protocolo utilizou um esquema de compromisso polinomial de pequeno domínio )Small-Field PCS(, permitindo um sistema de prova eficiente no domínio binário e reduzindo as sobrecargas 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 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 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 dos campos binários apoia um processo de aritmética simplificado, ou seja, as operações realizadas em campos binários podem ser representadas em uma forma algébrica compacta e fácil de verificar. Essas características, juntamente com a capacidade de aproveitar plenamente as suas propriedades hierárquicas através da estrutura em torre, tornam os campos binários especialmente adequados para sistemas de prova escaláveis como o Binius.

O termo "canônico" refere-se à representação única e direta de elementos no domínio binário. Por exemplo, no mais básico dos domínios binários F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do domínio binário de k bits. Isso é diferente do domínio primo, que não pode fornecer essa representação canônica dentro do número de bits especificado. Embora o 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 de redução comuns incluem a redução de Barrett, a redução de 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 comumente usados incluem a redução especial (, como usado no AES, a redução de Montgomery ), como usado 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 domínio binário, não é necessário introduzir carry 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: esta 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 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 de domínio F2. Essa flexibilidade de representação não requer nenhum custo computacional, apenas uma conversão de tipo de 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 um 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, elevação ao 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 (.

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

) 2.2 PIOP: versão adaptada do HyperPlonk Product e PermutationCheck------aplicável ao campo 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. Esses checagens essenciais incluem:

1. GateCheck: Verifica se o testemunho de confidencialidade ω 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: Verifica se os resultados da avaliação de dois polinómios multivariados f e g no hipercubo booleano formam 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: Verificar 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 vários 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 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 na 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 realizam o processamento em lote de múltiplas instâncias de verificação de soma.

8. BatchCheck: baseado no SumCheck, verifica 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:

• Otimização do ProductCheck: no HyperPlonk, o ProductCheck exige que o denominador U seja sempre diferente de zero no hipercubo, e o produto deve ser 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 é diferente de zero no hipercubo; o Binius lidou corretamente com este problema, mesmo quando o denominador é zero, o ProductCheck do Binius também consegue continuar a processar, permitindo a promoçã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, o que permite que o Binius lide com situações de arranjo polinomial mais complexas.

Assim, o Binius, através da melhoria do mecanismo existente PIOPSumCheck, aumentou a flexibilidade e a eficiência do protocolo, especialmente ao lidar com a verificação de polinómios multivariáveis mais complexos, proporcionando um suporte funcional mais robusto. Estas melhorias não só resolveram as limitações do HyperPlonk, como também estabeleceram uma base para futuros sistemas de prova 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 deslocamento 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, capazes de gerar e operar eficazmente polinómios derivados de manipuladores de entrada ou outros polinómios virtuais. Aqui estão dois métodos chave:

• Embalagem: Este método passa por