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 nos programas reais é bastante pequena, mas para garantir a segurança das provas baseadas em árvores de Merkle, ao usar a codificação Reed-Solomon para expandir os dados, muitos valores de redundância 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 fundamental.

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 uma grande quantidade de espaço desperdiçado. Em comparação, o domínio binário permite a operação direta sobre os bits, codificando de forma compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs da 4ª geração.

Comparado com as descobertas recentes de domínios finitos 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 na 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;

• QR code, usando codificação Reed-Solomon baseada em F28;

• Protocólos originais FRI e zk-STARK, assim como a função hash Grøstl, que chegou à final do SHA-3, baseada no domínio F28, que é 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 ser estendida, operando apenas no domínio base, o que permite uma alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e os cálculos FRI ainda precisam ser aprofundados em domínios de extensão maiores 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 de trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinômio; ao comprometer a Merkle tree 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 extensão da codificação.

Binius propôs uma solução inovadora que trata separadamente esses dois problemas e representa os mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariados (especificamente polinômios multilineares) em vez de polinômios univariados, representando toda a trajetória de cálculo por meio de seus valores em "hipercubos"; em segundo lugar, uma vez que o comprimento de cada dimensão do hipercubo é 2, não é possível realizar uma extensão padrão de Reed-Solomon como em 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, ao garantir a segurança, melhora significativamente a eficiência de codificação e o desempenho computacional.

2 Análise dos 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 iguais polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente através da interação com o verificador, de modo que o verificador possa validar 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: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, que lidam de maneira diferente com as expressões polinomiais, 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 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 sobre o 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 com um domínio 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: Adota PLONK PIOP combinado com FRI PCS, baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursividade eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos 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 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 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 na 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 utiliza um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo um sistema de provas eficiente sobre o 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

Os domínios 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álculo eficiente e aritmética eficiente. Os domínios binários, em essência, 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 domínio binário suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre o domínio binário podem ser representadas em uma forma algébrica compacta e fácil de verificar. Essas características, juntamente com a capacidade de tirar pleno proveito de suas características 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 do domínio binário de k bits. Isso é diferente do domínio primo, que não pode fornecer tal 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 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 redução Barrett, 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 comumente usados incluem redução especial (como a usada no AES), redução Montgomery (como a usada no POLYVAL) e redução recursiva (como a usada na Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que o domínio binário não requer o 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 (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 pode 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 de domínio F2. Essa flexibilidade de representação não requer nenhum custo computacional, sendo apenas uma conversão de tipo (typecast) da string de bits, o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser agrupados 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, quadrados e inversões 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 HyperPlonk Product e PermutationCheck ------ aplicável ao campo binário

O design do PIOP no protocolo Binius inspira-se no HyperPlonk e utiliza uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos multivariados. Estas verificações essenciais incluem:

1. GateCheck: Verifica se o testemunho secreto ω 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 multivariados 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: 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 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 racional no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto polinomial.

6. ZeroCheck: Verifica se um polinómio multivariável em um hipercubo booleano é zero em um ponto qualquer ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para assegurar 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 de 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 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: Com base no SumCheck, verifica a correção da avaliação de múltiplos polinómios multivariáveis para aumentar a eficiência do protocolo.

Apesar de Binius ter muitas semelhanças de design de protocolo com HyperPlonk, Binius fez melhorias nas seguintes 3 áreas:

• ProductCheck otimizado: 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 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, resultando na impossibilidade de afirmar que U é diferente de zero no hipercubo; o Binius tratou corretamente esse problema, mesmo quando o denominador é zero, o ProductCheck do Binius pode 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 ao Binius lidar com situações de permutação polinomial mais complexas.

Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente, 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 sistemas de prova baseados em domínios binários no futuro.

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

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

• Empacotamento: Este método funciona ao substituir os elementos menores em posições adjacentes na ordem do dicionário.