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 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 uma estratégia chave.

A largura de codificação dos STARKs da 1ª geração é de 252 bits, a largura de codificação dos STARKs da 2ª geração é de 64 bits, e a largura de codificação dos STARKs da 3ª geração é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta um grande desperdício de espaço. Em comparação, o domínio binário permite operações diretas sobre os bits, resultando em uma codificação compacta e eficiente, sem nenhum espaço desperdiçado, ou seja, os STARKs da 4ª geração.

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á 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, 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, que é baseada no domínio F28, é um algoritmo de hash muito adequado para recursão.

Quando domínios menores são utilizados, a operação de extensão de domínio torna-se cada vez mais importante para garantir a segurança. E 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 do Prover não precisa entrar na extensão de domínio, operando apenas sob o 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 de FRI ainda precisam ser aprofundados em um domínio de extensão maior para garantir a segurança necessária.

Ao construir um sistema de provas baseado em domínios binários, existem 2 problemas práticos: ao calcular a representação de 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.

A Binius apresentou uma solução inovadora que trata esses dois problemas separadamente e realiza a representação dos mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariáveis (especificamente polinômios multilineares) em vez de polinômios univariáveis, representando toda a trajetória de cálculo através de seus valores em "hipercubos" (hypercubes); em segundo lugar, uma vez que cada dimensão do hipercubo tem comprimento igual a 2, não é possível realizar uma extensão padrão de Reed-Solomon como em 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 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 de Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de prova, transforma as relações de cálculo 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 apenas alguns resultados de avaliação de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes maneiras de lidar com expressões polinomiais, o que afeta 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 que permite ao provador comprometer-se com 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 campo finito ou uma curva elíptica adequada, podendo construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combinando 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: utiliza PLONK PIOP e FRI PCS em conjunto, baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar recursões eficientes. 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, 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 uma configuração confiável e se pode suportar funcionalidades de extensão, 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 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 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 utilizou uma versão aprimorada da prova de busca Lasso, oferecendo flexibilidade e forte segurança para o mecanismo de busca. Por fim, o protocolo emprega um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo um sistema de prova eficiente sobre o domínio binário e reduzindo os custos normalmente associados a grandes domínios.

2.1 Domínios finitos: 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á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 a requisitos de desempenho. Além disso, a estrutura dos domínios binários suporta um processo de aritmética simplificada, ou seja, as operações realizadas sobre os domínios binários 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 da estrutura em torre, tornam os domínios 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 de domínio binário de k bits. Isso é diferente dos domínios de números primos, que não podem fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa ser incluído em 32 bits, nem toda string de 32 bits pode corresponder de forma única 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, os métodos de redução comuns incluem reduções especiais (como usadas no AES), reduções Montgomery (como usadas no POLYVAL) e reduções recursivas (como a Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa que, tanto as operações de adição quanto as de multiplicação no domínio binário não requerem transporte, e a operação de quadrado no domínio binário é muito eficiente, pois segue a regra de simplificação (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 no domínio binário de 128 bits, ou 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 sobrecarga computacional, 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 menor podem ser empacotados em elementos de domínio maiores sem necessidade de sobrecarga 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 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).

2.2 PIOP: versão adaptada do Produto HyperPlonk e Verificação de Permutação------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 multivariáveis. Esses mecanismos de verificação 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: 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 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 estejam dentro do intervalo especificado.

4. MultisetCheck: Verifica se dois conjuntos multivariados 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 em múltiplas variáveis no hipercubo de Boole é 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 um problema de 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 possibilitam 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.

Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius fez melhorias nas seguintes 3 áreas:

• ProductCheck otimizado: No HyperPlonk, o ProductCheck exige que o denominador U seja sempre diferente de zero no hipercubo e que o produto seja igual a um valor específico; Binius simplificou este 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 a situação de divisão por zero, o que levou a não poder afirmar que U é não nulo no hipercubo; Binius tratou corretamente deste problema, mesmo quando o denominador é zero, o ProductCheck da Binius consegue continuar 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 que 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 sistemas de prova futuros baseados em campos binários.

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

No protocolo Binius, a construção e manipulação de polinómios virtuais é uma das tecnologias chave, capaz de gerar e operar eficazmente polinómios derivados de manipuladores de entrada ou outros polinómios virtuais. Aqui estão dois métodos chave:

• Packing: Este método otimiza a operação agrupando elementos menores em posições adjacentes na ordem do dicionário em elementos maiores. O operador Pack opera em blocos de tamanho 2κ e os combina.