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 em programas reais é bastante pequena, 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 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.

Como mostrado na Tabela 1, 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 muito espaço desperdiçado. Em comparação, o domínio binário permite operações diretas em bits, com uma codificação compacta e eficiente sem desperdício de espaço, ou seja, os STARKs de 4ª geração.

Tabela 1: Caminho de Derivação STARKs

| Álgebra | Largura de bits | Domínio | |------|------|------| | 1ª Geração | 252bit | Campo Primo | | 2ª Geração | 64bit | Goldilocks | | 3ª geração | 32 bits | Campo primo | | 4ª geração | 1bit | domínio binário |

Comparado a Goldilocks, BabyBear, Mersenne31 e outras descobertas de domínios finitos nos últimos anos, 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 F28;

• Galois Message Authentication Code ( GMAC ), baseado no domínio F2128;

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

• Protocólos originais FRI e zk-STARK, assim como a função de hash Grøstl, que chegou à fase final do SHA-3, é baseada no domínio F28 e é 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 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 do Prover não precisa entrar na extensão de domínio, operando apenas sob o domínio base, conseguindo assim 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 domínios de extensão maiores, 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 do que o grau do polinômio; ao comprometer a árvore Merkle em STARKs, deve-se 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 estes dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando polinómios multivariáveis ( em vez de polinómios univariáveis, representando toda a trajetória computacional 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 nos STARKs, mas pode-se considerar o hipercubo como um quadrado (, realizando a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir a segurança, melhora significativamente a eficiência da 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 com Teoria da Informação ) Information-Theoretic Polynomial Interactive Oracle Proof, PIOP (: O PIOP, como núcleo do sistema de prova, transforma a relação computacional de entrada em igualdades polinomiais que podem ser verificadas. Diferentes protocolos PIOP permitem que o provador envie polinômios de forma gradual 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 número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que tratam as expressões polinomiais de maneira diferente, influenciando 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 pelo PIOP é válida. O PCS é uma ferramenta criptográfica, através da qual o provador pode 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 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.

De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um domínio finito ou curva elíptica adequada, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combina PLONK PIOP e 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 em combinação com FRI PCS e é baseado no domínio Goldilocks. O Plonky2 foi projetado para realizar recursão de forma eficiente. Ao projetar esses sistemas, as PIOP e PCS escolhidas devem corresponder ao domínio finito ou à curva elíptica utilizada, a fim de garantir a correção, o desempenho e a segurança do sistema. A escolha dessas combinações não só afeta o tamanho da prova e a eficiência de 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, além de 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 nas torres de campos binários )towers of binary fields( constitui a base de seu cálculo, 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 interativa )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 da verificação de relações multilineares em pequenos campos. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequenos campos )Small-Field PCS(, permitindo a implementação de um sistema de provas eficiente sobre o campo binário e reduzindo a sobrecarga normalmente associada a grandes campos.

) 2.1 Domínios Finitos: Arithmetização 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 aritimética eficiente. Os campos binários suportam 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 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. Estas características, juntamente com a capacidade de tirar pleno proveito da sua estrutura hierárquica por meio da 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 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 diretamente mapeada 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 um domínio primo de 32 bits possa ser contido dentro de 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 a conveniência dessa correspondência 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 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 (, como usada no AES ), a redução de Montgomery ###, como utilizada no POLYVAL (, e a redução recursiva ), como em Tower (. O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa 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 de um domínio binário. Pode ser vista como um elemento único em um domínio binário de 128 bits, ou 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 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. Ao mesmo tempo, elementos de domínio pequenos 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 das operações de multiplicação, quadrado e inversão em um domínio binário de torre de n bits ) que pode ser decomposto em subdomínios de m bits (.

![Torre de Domínio Binário])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(

Figura 1: Domínio binário em torre

) 2.2 PIOP: versão adaptada do produto HyperPlonk e PermutationCheck------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 essenciais para validar a correção de polinómios e conjuntos multivariados. Esses mecanismos de verificação essenciais 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: verificar se os resultados da avaliação dos 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 permutação entre as variáveis polinomiais.

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: 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 um polinómio multivariável em um problema de avaliação de um polinómio univariável, reduz a complexidade computacional para o 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 várias instâncias de verificação de somas.

8. BatchCheck: baseado no SumCheck, valida a correção da avaliação de múltiplos polinómios multivariados, a fim de melhorar a eficiência do protocolo.

Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius fez melhorias em três áreas a seguir:

• 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 este processo de verificação ao especializar este valor para 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 incapacidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius ainda pode continuar a processar, permitindo a generalização para qualquer valor de produto.

• Verificação de Permutação em Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a verificação de permutação entre várias colunas, o que permite ao Binius lidar com situações de disposição polinomial mais complexas.

Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo existente PIOPSumCheck, 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 no HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em campos binários.

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

Na protocolo Binius, a construção e o tratamento de polinómios virtuais são fundamentais.