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

1 Introdução

Diferente dos SNARKs baseados em curvas elípticas, os STARKs podem ser vistos como SNARKs baseados em hash. Uma das principais razões para a ineficiência atual dos STARKs é: a maioria dos valores numéricos 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, quando os dados são expandidos 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.

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 sobre os bits, com codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, a quarta geração de STARKs.

Comparado a Goldilocks, BabyBear, Mersenne31 e outras descobertas recentes em campos finitos, a pesquisa sobre campos binários remonta à década de 1980. Atualmente, os campos binários são amplamente utilizados em criptografia, exemplos típicos incluem:

• Padrão de Criptografia Avançada ( AES ), baseado no domínio F28;

• Galois código de autenticação de mensagem ( 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 à fase 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 garantir sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos dos Provers não precisa entrar na extensão de domínio, operando apenas no domínio base, conseguindo assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e os cálculos de FRI ainda precisam aprofundar-se em um domínio de extensão 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 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 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 apresentou uma solução inovadora que trata separadamente esses dois problemas e representa os mesmos dados de duas maneiras diferentes: primeiro, usando múltiplas variáveis (, especificamente polinômios multilineares ) em vez de polinômios univariados, representando toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, devido ao fato de que cada dimensão do hipercubo tem comprimento 2, não é possível realizar a extensão padrão de Reed-Solomon como em STARKs, mas o hipercubo pode ser considerado um quadrado ), baseado no qual a extensão de Reed-Solomon pode ser realizada. Este método, ao garantir a segurança, aumenta significativamente a eficiência de 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:

• Informação teórica da prova interativa polinomial do oráculo (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como o núcleo do sistema de provas, transforma a relação computacional de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP, por meio 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 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, cada um deles com maneiras diferentes de tratar expressões polinomiais, impactando assim o desempenho e a eficiência de todo o sistema SNARK.

• Polinomial Commitment Scheme (Polynomial Commitment Scheme, PCS ): O esquema de compromisso polinomial é usado para provar se a equação polinomial gerada pelo 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 compromisso polinomial mais 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 campo finito adequado ou uma curva elíptica, 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 da configuração confiável no protocolo ZCash.

• Plonky2: utiliza PLONK PIOP combinado com FRI PCS, 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 domínio finito ou curva elíptica utilizada, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não só 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 um setup confiável, e se pode suportar funcionalidades expandidas como provas recursivas ou provas 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 adaptou 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 introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência da verificação de relações multilineares em pequenos domínios. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso polinomial de pequenos domínios (Small-Field PCS), permitindo um sistema de prova eficiente sobre domínios binários e reduzindo a sobrecarga geralmente associada a grandes domínios.

( 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários

Os domínios binários em torre são fundamentais para a implementação de computações rápidas e verificáveis, principalmente devido a dois aspectos: cálculo eficiente 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 apoia um processo de aritmética simplificado, onde as operações realizadas sobre o domínio binário podem ser representadas de 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 de torre, tornam os domínios binários particularmente 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 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 estar 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-para-um. No domínio primo Fp, os métodos de redução comuns 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, os métodos de redução comuns incluem a redução especial ) usada em AES ###, a redução Montgomery ( usada em POLYVAL ) e a redução recursiva ( como a Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que no domínio binário, a adição e a multiplicação não requerem transporte, e 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 do campo binário. Pode ser vista como um elemento único no campo binário de 128 bits, ou pode ser interpretada como dois elementos de campo de torre de 64 bits, quatro elementos de campo de torre de 32 bits, 16 elementos de campo de torre de 8 bits, ou 128 elementos do campo F2. Essa flexibilidade de representação não requer nenhum custo computacional, apenas uma conversão de tipo da string de bits (typecast), que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de campo menores podem ser empacotados em elementos de campo 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 da multiplicação, quadrados e operações de inversão em campos de torre binária de n bits, quando ( pode ser decomposto em subcampos de m bits ).

( 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 multivariáveis. 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 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((, a fim de garantir a consistência da permutaçã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: 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 em um hipercubo booleano é zero em qualquer ponto ∏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ómios univariáveis, reduz a complexidade computacional do verificador. Além disso, o SumCheck também permite 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 somas.

8. BatchCheck: baseado no SumCheck, verifica a correção da avaliação de múltiplos polinómios multivariados 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 não nulo em toda a hipercubo, e o produto deve ser igual a um valor específico; a Binius simplificou este processo de verificação, especializando 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 a não poder afirmar que U é diferente de zero no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius continua 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, o que permite ao Binius lidar com situações de arranjo 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 verificação 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 prova baseados em domínios binários.

( 2.3 PIOP: novo argumento de mudança multilinear ------ aplicável ao hipercubo booleano

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

• Packing: Este método utiliza a posição adjacente de menor valor na ordem do dicionário