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

1. Introdução

Uma das principais razões para a ineficiência dos STARKs é que a maioria dos valores nos programas reais são bastante pequenos, como os índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, ao usar codificação de Reed-Solomon para expandir os dados, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que os valores originais sejam muito pequenos. Para resolver esse problema, a redução do tamanho do domínio tornou-se uma estratégia chave.

A largura de codificação do STARKs da 1ª geração é de 252 bits, a largura de codificação do STARKs da 2ª geração é de 64 bits, e a largura de codificação do 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, a 4ª geração do STARKs.

Comparado aos 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 em criptografia, com exemplos típicos incluindo:

• 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, utilizando codificação Reed-Solomon baseada em F28;

• Protocólos FRI originais e zk-STARK, bem como a função de hash Grøstl, que chegou à final do SHA-3, baseada no domínio F28, é 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 assegurar 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, permitindo assim 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 provas baseado em campos binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do campo 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 campo utilizado deve ser maior do que o tamanho após a expansão da codificação.

A Binius propôs uma solução inovadora que trata esses dois problemas separadamente e expressa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariados (especificamente polinômios multilineares) em vez de polinômios univariados, representando toda a trajetória de cálculo por seus valores em "hipercubos" (hypercubes); 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 pode-se considerar o hipercubo como um quadrado (square) e realizar a extensão de Reed-Solomon com base 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 do Princípio

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): PIOP, como o núcleo do sistema de prova, transforma a relação computacional 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 os resultados da avaliação de um pequeno número de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que tratam as expressões polinomiais de maneiras diferentes, 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 a igualdade polinomial gerada por 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 sobre o polinômio. Esquemas comuns de compromisso polinomial incluem KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS possuem 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-os com um campo finito ou curva elíptica apropriada, para 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: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar 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 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 constitui a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adaptação da 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 as variáveis e suas permutações. Em terceiro lugar, 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 adotou uma versão aprimorada da prova de busca Lasso, fornecendo flexibilidade e forte segurança ao mecanismo de busca. Por fim, o protocolo utiliza 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 os custos geralmente associados 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 rapidamente verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os campos binários suportam, por natureza, 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 sobre os campos binários podem ser representadas de forma algébrica compacta e fácil de verificar. Essas características, combinadas com a capacidade de aproveitar plenamente suas características hierárquicas através de uma 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 elementos no domínio binário. Por exemplo, no domínio binário básico 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 consegue 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 corresponde, de forma única, a um elemento do domínio, enquanto o domínio binário tem essa conveniência de mapeamento um a um. No domínio primo Fp, métodos comuns de redução incluem a redução de Barrett, a redução de Montgomery, e métodos de redução específicos para domínios finitos como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, métodos de redução comuns incluem reduções especiais (como usadas no AES), redução de Montgomery (como usada no POLYVAL) e redução recursiva (como Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa 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 de (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 de 128 bits no domínio binário, 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, sendo apenas uma conversão de tipo da string de bits, o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio menores podem ser empacotados em elementos de domínio maiores sem necessidade de custo computacional adicional. O protocolo Binius aproveita essa característica para aumentar 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, квадрат e operações de inversão em domínios binários de torre 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 domínio binário

O design 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. Essas verificações essenciais 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 o funcionamento correto do circuito.

2. PermutationCheck: Verifica 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 da disposição 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 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 determinado valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto do polinómio.

6. ZeroCheck: Verifica se um polinómio multivariado é 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 uma avaliação de polinómio univariável, reduz-se 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 permitem 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 múltiplos polinômios multivariados para aumentar a eficiência do protocolo.

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

• Otimização do ProductCheck: no HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em todo o hipercubo e que o produto seja igual a um valor específico; a Binius simplificou 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 situações de divisão por zero, o que impossibilitou afirmar que U é não zero no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, permitindo a promoção a 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 permutação 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, proporcionando 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 mudança multilinear ------ aplicável ao hiper-cubo booleano

No protocolo Binius, a construção e manipulação de polinómios virtuais é uma das tecnologias chave, capaz 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:

• Empacotamento：