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

1 Introdução

Uma das principais razões para a baixa eficiência dos STARKs é que a maioria dos valores nos 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 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 a estratégia chave.

A largura de codificação da primeira geração de STARKs é de 252 bits, a largura de codificação da segunda geração de STARKs é de 64 bits, e a largura de codificação da terceira geração de STARKs é 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 nos bits, com codificação compacta e eficiente, sem espaço desperdiçado, ou seja, a quarta geração de STARKs.

Comparado 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á estã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;

• Protocólos FRI originais e zk-STARK, bem como a função de hash Grøstl que chegou à final do SHA-3, que é baseada no domínio F28, são 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 de entrar na extensão de domínio, operando apenas no domínio base, conseguindo 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-se em uma extensão de domínio maior para garantir a segurança necessária.

Ao construir sistemas de prova baseados em domínios binários, existem 2 problemas práticos: ao calcular a representação do traço 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 fazer 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, abordando esses dois problemas separadamente e representando os mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariados ( especificamente polinômios multilinelares ) em vez de polinômios univariados, representando toda a trajetória de cálculo por meio de seus valores nos "hipercubos" (; em segundo lugar, como cada dimensão do hipercubo tem comprimento 2, não é possível realizar a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado ), e a extensão de Reed-Solomon pode ser baseada nesse quadrado. Este método, enquanto garante segurança, aumenta significativamente a eficiência de codificação e o desempenho de cálculo.

2 Análise do Princípio

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

• Informação Teórica de Prova Interativa Polinomial de Oráculo (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como núcleo do sistema de provas, transforma as relações computacionais de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP, através da interação com o verificador, permitem que o provador envie polinômios gradualmente, de modo que o verificador possa validar se o cálculo está correto consultando apenas os resultados de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes formas 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 as igualdades polinomiais geradas pelo PIOP são válidas. 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, ao mesmo tempo em que oculta outras informações do polinômio. Os esquemas de compromisso polinomial mais comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS possuem diferentes desempenhos, segurança e cenários de aplicação.

De acordo com as necessidades específicas, escolha diferentes PIOP e PCS e combine-os com o domínio finito ou curva elíptica apropriada, podendo 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 setup confiável no 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 corpo 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 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, 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 domínios binários (towers of binary fields) constitui a base de seus cálculos, permitindo a implementação de 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 interativa (PIOP), garantindo uma verificação consistente e segura entre as variáveis e suas permutações. Em terceiro lugar, o protocolo introduz uma nova prova de deslocamento multilinear, otimizando a eficiência da verificação de relações multilineares em pequenos domínios. Quarto, Binius utiliza uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo emprega 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 a sobrecarga geralmente associada a grandes domínios.

( 2.1 Domínios Finitos: Arithmetização 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 essencialmente 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 em uma 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 de uma estrutura em torre, tornam o campo binário particularmente adequado para sistemas de prova escaláveis como o Binius.

O termo "canônico" refere-se à representação única e direta de elementos em um campo binário. Por exemplo, no campo binário mais básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do campo binário de k bits. Isso difere dos campos primários, que não podem fornecer tal representação canônica dentro de um número fixo de bits. Embora um campo primário de 32 bits possa caber em 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento do campo, enquanto o campo binário possui essa conveniência de mapeamento um a um. Nos campos primários Fp, os 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 campos finitos específicos, como Mersenne-31 ou Goldilocks-64. No campo binário F2k, os métodos comuns de redução incluem a redução especial ) utilizada no AES ###, a redução de Montgomery ( utilizada no POLYVAL ) e a redução recursiva ( utilizada em Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que no campo binário não é necessário introduzir transporte nas operações de adição e multiplicação, e a operação de quadrado no campo 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 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 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 menores podem ser agrupados em elementos de domínio maiores sem 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, quadrado e operação de inversão em domínios de torre binários de n bits ( decomponíveis em subdomínios de m bits ).

( 2.2 PIOP: versão adaptada do Produto HyperPlonk e Verificação de Permutação------aplicável ao campo binário

O design do PIOP no protocolo Binius é inspirado no HyperPlonk e utiliza uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos de múltiplas variáveis. Estas verificações essenciais incluem:

1. GateCheck: Verificar se o testemunho confidencial ω 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 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 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 múltiplos 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 polinómico.

6. ZeroCheck: Verificar se um polinómio multivariável em um hipercubo booleano em um ponto arbitrário é 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 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 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 várias instâncias de verificação de soma.

8. BatchCheck: Baseado em SumCheck, verifica 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 de design de protocolo com o HyperPlonk, o Binius fez melhorias nas seguintes 3 áreas:

• Otimização do ProductCheck: 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; a Binius simplificou esse processo de verificação, especializando esse valor para 1, reduzindo assim a complexidade computacional.

• Tratamento do problema de divisão por zero: o 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; o Binius tratou corretamente esse problema, mesmo quando o denominador é zero, permitindo que o ProductCheck do Binius continue a processar e possibilite 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 ao Binius lidar com casos de arranjos polinomiais mais complexos.

Assim, a Binius, através da melhoria do mecanismo existente PIOPSumCheck, elevou a flexibilidade e eficiência do protocolo, especialmente ao lidar com validações de polinômios multivariados 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 provas baseados em campos binários.

( 2.3 PIOP: novo argumento de shift multilinear------aplicável ao hipercubo booleano

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