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 da prova baseada em árvores de Merkle, ao expandir os dados usando codificação de Reed-Solomon, 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 chave.

A largura de codificação do STARKs de 1ª geração é de 252 bits, a largura de codificação do STARKs de 2ª geração é de 64 bits, e a largura de codificação do STARKs de 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 operações diretas sobre os bits, com codificação compacta e eficiente, sem nenhum espaço desperdiçado, ou seja, o STARKs de 4ª geração.

Em comparação com os domínios finitos descobertos em pesquisas recentes, como Goldilocks, BabyBear e Mersenne31, o estudo dos domínios binários remonta à década de 1980. Atualmente, os domínios binários são amplamente utilizados em criptografia, com exemplos típicos que incluem:

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

• Galois Message Authentication Code ( GMAC ), baseado no campo F2128;

• QR Code, 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, baseada no domínio F28, é 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 assegurar a sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não necessita de entrar na extensão de domínio, funcionando apenas no domínio base, alcançando assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam aprofundar-se em um domínio de extensão maior para garantir a segurança necessária.

Existem 2 problemas práticos ao construir sistemas de prova baseados em domínios binários: no cálculo da representação do traço em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinómio; na promessa da á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.

A Binius propôs uma solução inovadora que aborda esses dois problemas separadamente e representa os 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"; em segundo lugar, como o comprimento de cada dimensão do hipercubo é 2, não é possível realizar uma 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 feita com base 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 de Princípios

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

• Prova Interativa Polinomial de Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de prova, 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 apenas consultando os resultados de avaliação de um pequeno número de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes abordagens para o tratamento de 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 pelo PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se com um determinado polinômio e, posteriormente, verificar os resultados 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 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 o domínio finito ou curva elíptica apropriada, para construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combina PLONK PIOP e Bulletproofs PCS, 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 e FRI PCS combinados, baseado no domínio Goldilocks. Plonky2 é projetado para alcançar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao corpo 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 necessidade de configuração confiável, se pode suportar recursos expandidos 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 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 consistente entre variáveis e suas permutações de forma segura e eficiente. 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, oferecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso de polinômios de pequeno campo (Small-Field PCS), permitindo a implementação de um sistema de provas eficiente sobre o campo binário e reduzindo a sobrecarga geralmente associada a grandes campos.

2.1 Domínios finitos: aritmética baseada em torres de campos binários

Os campos binários em torre são a chave para a implementação de cálculos verificáveis rápidos, principalmente devido a dois aspectos: cálculo eficiente e aritmética eficiente. Os campos 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 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. Essas características, juntamente com a capacidade de aproveitar totalmente suas características hierárquicas através da estrutura de torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis, como o Binius.

O termo "canônica" 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 de campo binário de k bits. Isso é diferente do campo primo, que não pode fornecer essa representação canônica dentro de um número fixo de bits. Embora um campo primo de 32 bits possa ser contido em 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento de campo, enquanto o campo binário possui essa conveniência de mapeamento um-para-um. No campo 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 campos finitos específicos como Mersenne-31 ou Goldilocks-64. No campo binário F2k, os métodos de redução comuns incluem redução especial (como usada no AES), redução Montgomery (como usada no POLYVAL) e redução recursiva (como Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que o campo binário não requer a introdução de transporte em 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 de (X + Y )2 = X2 + Y 2.

Como mostrado na Figura 1, uma string de 128 bits: essa 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 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 qualquer sobrecarga computacional, apenas uma conversão de tipo (typecast) da string de bits, sendo uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio menores podem ser embalados em elementos de domínio maiores sem a necessidade de sobrecarga 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 domínios binários em torre de n bits (podendo ser decompostos em subdomínios de m bits).

2.2 PIOP: versão adaptada do Produto HyperPlonk e PermutationCheck ------ aplicável ao campo binário

O design PIOP no protocolo Binius se baseia no HyperPlonk, adotando uma série de mecanismos de verificação essenciais para validar a correção de polinômios e conjuntos multivariáveis. Esses verificações 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: 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 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 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: Verifica se a avaliação de um polinómio com coeficientes racionais no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto polinómico.

6. ZeroCheck: Verifica 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: verificar 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-se 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 no SumCheck, verifica a correção da avaliação de vários polinômios multivariáveis, a fim de aumentar a eficiência do protocolo.

Embora Binius e HyperPlonk tenham 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 diferente de zero em todo o hipercubo, e o produto deve ser igual a um valor específico; Binius simplificou esse 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, levando a não poder afirmar que U é não nulo no hipercubo; o Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius pode 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 ao Binius lidar com situações de arranjo polinomial mais complexas.

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

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

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

• Embalagem: