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

1. Introdução

Uma das principais razões para a baixa eficiê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 expandir os dados usando codificação de Reed-Solomon, 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.

Como mostrado na Tabela 1, a largura do código STARKs de primeira geração é de 252 bits, a largura do código STARKs de segunda geração é de 64 bits e a largura do código STARKs de terceira geração é de 32 bits, mas a largura do código 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, a quarta geração de STARKs.

| Álgebra | Largura de codificação | Implementação típica | |------|----------|----------| | 1ª Geração | 252bit | StarkWare |
| Segunda Geração | 64bit | Plonky2 | | 3ª geração | 32bit | Plonky3 | | 4ª geração | 1bit | Binius |

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 já são amplamente utilizados na criptografia, exemplos típicos incluem:

• Padrão de Criptografia Avançada (AES), baseado no domínio F2^8
• Código de autenticação de mensagem Galois ( GMAC ), baseado no domínio F2^128
• Código QR, utilizando codificação Reed-Solomon baseada em F2^8
• Protocólos FRI originais e zk-STARK, assim como a função de hash Grøstl que chegou à fase final do SHA-3, que é baseada no domínio F2^8, é 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 totalmente 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 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 aprofundar em uma extensão de domínio maior para garantir a segurança necessária.

Ao construir um sistema de prova baseado no domínio binário, existem 2 problemas práticos: no STARKs, o tamanho do domínio usado para calcular a representação do traço deve ser maior do que o grau do polinômio; ao comprometer a árvore de Merkle no STARKs, é necessário fazer 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.

Binius propôs uma solução inovadora que trata estas duas questões separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinómios multivariados ( em vez de polinómios unidimensionais, representando toda a trajetória de cálculo através dos seus valores em "hipercubos" ); em segundo lugar, uma vez que o comprimento de cada dimensão do hipercubo é 2, não é possível realizar a extensão padrão de Reed-Solomon como nos 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, ao garantir 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:

• Prova de Oracle Interativa Polinomial Teórica da Informação )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: O PIOP, como núcleo do sistema de provas, 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 de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que têm diferentes abordagens para o tratamento de expressões polinomiais, afetando assim o desempenho e a eficiência de todo o sistema SNARK.

• Esquema de Compromissos Polinómicos )Polynomial Commitment Scheme, PCS(: O esquema de compromissos polinómicos é utilizado para provar se a igualdade polinómica gerada por PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se a 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 compromissos polinómicos mais comuns incluem KZG, Bulletproofs, FRI)Fast Reed-Solomon IOPP( e Brakedown, entre outros. Diferentes PCS têm 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 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 com Bulletproofs PCS e é baseado na curva Pasta. O Halo2 foi projetado com foco na escalabilidade e na remoção da configuração confiável do protocolo ZCash.

• Plonky2: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar recursão eficiente. Ao desenhar 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 da 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 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( forma a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adapta a verificação de produto e permutação do HyperPlonk em seu protocolo de prova Oracle interativo )PIOP(, garantindo uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Terceiro, o protocolo introduz uma nova prova de deslocamento multilinear, otimizando a eficiência na verificação de relações multilineares em pequenos domínios. Quarto, Binius utiliza uma versão aprimorada da prova de busca Lasso, oferecendo flexibilidade e forte segurança ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequenos domínios )Small-Field PCS(, permitindo a implementação de um sistema de provas eficiente sobre domínios binários e reduzindo os custos geralmente associados a grandes domínios.

) 2.1 Campo finito: aritmética baseada em torres de campos binários

Os domínios binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os domínios 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 domínio binário suporta um processo de aritmética simplificado, ou seja, as operações realizadas no domínio binário podem ser representadas de forma compacta e fácil de verificar em forma algébrica. Essas características, juntamente com a capacidade de aproveitar plenamente suas propriedades hierárquicas através da estrutura de torre, tornam os domínios binários particularmente adequados para sistemas de prova escaláveis como o Binius.

Onde "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 do domínio primo, que não pode 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 unicamente a um elemento de domínio, enquanto o domínio binário possui essa conveniência de mapeamento um a um. No domínio primo Fp, métodos comuns de redução 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, métodos de redução comuns incluem a redução especial ( como usado no AES ), a redução Montgomery ### como usada no 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 no domínio binário não é necessário introduzir transporte em operações de adição e multiplicação, e a operação de quadrado no domínio binário é muito eficiente, pois segue a regra simplificada )X + Y (^2 = X^2 + 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 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 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. Além disso, elementos de domínio pequenos podem ser empacotados em elementos de domínio maiores sem 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, quadrados e operações de inversão em ) que podem ser decompostas em subdomínios de m bits ( dentro de um domínio de torre binário de n bits.

![Torre Binária])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(

) 2.2 PIOP: versão adaptada do Produto HyperPlonk e Verificação de Permutação------aplicável a campos binários

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 multivariados. Esses mecanismos de verificação incluem:

1. GateCheck: verifica se o testemunho secreto ω e a entrada pública x satisfazem a relação de operação 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 multivariados f e g no hipercubo booleano são uma relação de permutação f###x( = f)π(x)(, para assegurar 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µ(, assegurando que certos valores estão dentro da faixa especificada.

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: verificar se a avaliação de um polinómio racional no hipercubo booleano é igual a um determinado 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 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 polinómios multivariáveis é igual ao valor declarado ∑x∈Hµ f)x( = s. Ao transformar o problema de 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 o 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 em SumCheck, verifica a correção da avaliação de vários polinómios multivariáveis, para aumentar a eficiência do protocolo.

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

• ProductCheck otimizado: No HyperPlonk, o ProductCheck requer que o denominador U seja não nulo em todo o hipercubo, e o produto deve ser igual a um valor específico; 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 à incapacidade de afirmar que U é diferente de zero no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, permitindo que o ProductCheck do Binius continue 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 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 validação de polinômios multivariáveis mais complexos, oferecendo 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 prova baseados em campos binários.

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

Na protocolo Binius, a construção e o tratamento de polinómios virtuais são uma das tecnologias chave, capazes de gerar eficazmente.