Análise dos princípios dos STARKs da Binius e consideraçõ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 em programas reais é bastante pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvore de Merkle, ao usar a 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 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, resultando em codificações compactas e eficientes, sem qualquer desperdício de espaço, ou seja, a quarta geração de STARKs.

Em comparação com as descobertas recentes em campos finitos, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre campos binários remonta à década de 1980. Atualmente, os campos 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 mensagem de autenticação ( GMAC ), baseado no domínio F2128;

• Código QR, usando codificação Reed-Solomon baseada em F28;

• O protocolo FRI original e o protocolo zk-STARK, bem como a função de hash Grøstl, que chegou à final do SHA-3, são baseados no domínio F28 e são algoritmos de hash muito adequados 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 sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos Prover não precisa entrar na extensão de domínio, operando 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.

Ao construir um sistema de provas baseado em domínios binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do domínio deve ser maior do que o grau do polinômio; ao prometer a árvore Merkle em STARKs, é necessário fazer a codificação de Reed-Solomon, e o tamanho do domínio deve ser maior do que o tamanho após a expansão da codificação.

Binius propôs uma solução inovadora que aborda esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, substituindo polinômios univariados por polinômios multivariados (especificamente, multiliniares), representando toda a trajetória de cálculo através de seus valores em "hipercubos"; em segundo lugar, dado que o comprimento de cada dimensão do hipercubo é 2, não é possível realizar a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser considerado como um quadrado, permitindo a extensão de Reed-Solomon baseada nesse quadrado. Este método aumenta significativamente a eficiência de codificação e o desempenho computacional, garantindo ao mesmo tempo a segurança.

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): PIOP, como o núcleo do sistema de prova, transforma a relação de cálculo 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 os resultados de avaliação de um pequeno número de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que têm diferentes maneiras de lidar com 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 comuns de compromisso polinomial 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, 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 do protocolo ZCash.

• Plonky2: utiliza PLONK PIOP em combinação com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem ser compatíveis com o domínio finito ou a 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 SNARK e a eficiência de verificação, mas também determina se o sistema pode alcançar a 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 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 de Oracle interativa (PIOP), garantindo uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Terceiro, 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 robusta segurança 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 prova eficiente sobre o domínio binário e reduzindo a sobrecarga normalmente associada a grandes domínios.

2.1 Domínio finito: aritmética baseada em torres de campos binários

Os campos 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 campos binários suportam essencialmente operações aritméticas altamente eficientes, tornando-os uma escolha ideal para aplicações criptográficas sensíveis a desempenho. Além disso, a estrutura dos campos binários suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre o campo binário podem ser representadas de forma compacta e fácil de verificar em forma algébrica. Essas características, juntamente com a capacidade de aproveitar plenamente suas propriedades hierárquicas através da estrutura de torre, fazem com que os campos binários sejam particularmente adequados para sistemas de prova escaláveis como o Binius.

O termo "canônico" refere-se à maneira única e direta de representar 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 dos domínios primos, que não podem fornecer essa representação canônica dentro de um número fixo de bits. Embora o 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, métodos de redução comuns incluem a redução de Barrett, a redução de 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, métodos de redução comumente utilizados incluem reduções especiais (como as usadas no AES), reduções de Montgomery (como as usadas no POLYVAL) e reduções recursivas (como em Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa que no domínio binário, não é necessário introduzir transporte em operações de adição e multiplicação, e que 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 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 nenhum custo computacional, apenas uma conversão de tipo da string de bits, sendo uma propriedade muito interessante e útil. Além disso, elementos de domínio pequeno podem ser empacotados em elementos de domínio maiores sem custos computacionais adicionais. 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, quadrados e inversões em domínios de torre binária de n bits (decompostos 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 é 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 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 polinomiais.

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 da gama especificada.

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: 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 do polinómio.

6. ZeroCheck: Verificar 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: 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 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 realizam 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.

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

• ProductCheck otimização: No HyperPlonk, o ProductCheck exige que o denominador U seja não zero em todo o hipercubo, e o produto deve ser igual a um valor específico; a 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: HyperPlonk não conseguiu lidar adequadamente com a situação de divisão por zero, resultando na impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, permitindo que o ProductCheck do Binius continuasse a processar, permitindo a promoção para qualquer valor de produto.

• Verificação de Permutação entre Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a realização de 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 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 só resolveram as limitações no HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em campos binários.

2.3 PIOP: novo argumento de deslocamento multilinear ------ 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 de outros polinómios virtuais. Abaixo estão dois métodos chave:

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