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 é 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, o uso da codificação de Reed-Solomon para expandir os dados resulta em muitos valores de redundância adicionais ocupando 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 de 1ª geração é de 252 bits, a largura de codificação dos STARKs de 2ª geração é de 64 bits, a largura de codificação dos STARKs de 3ª geração é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta muito espaço desperdiçado. Em comparação, o campo binário permite operações diretas sobre bits, com codificação compacta e eficiente sem qualquer espaço desperdiçado, ou seja, os 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 80 do século passado. Atualmente, os domínios binários 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;

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

• O protocolo FRI original e o zk-STARK, assim como a função de hash Grøstl que chegou à final do SHA-3, que é baseada no campo F28, 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 do Prover não precisa entrar na extensão de domínio, operando apenas sob o 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 necessitam aprofundar-se em uma extensão de domínio 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 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 deve ser maior que o tamanho após a expansão da codificação.

A Binius apresentou uma solução inovadora que trata separadamente esses dois problemas e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando um polinômio multivariável (, especificamente um polinômio multilinear ), em vez de um polinômio univariável, representando toda a trajetória computacional através de seus valores em "hipercubos" (; em segundo lugar, dado que cada dimensão do hipercubo tem comprimento 2, não é possível realizar a expansão padrão de Reed-Solomon como nos STARKs, mas pode-se considerar o hipercubo como um quadrado ), baseado nesse quadrado para realizar a expansão de Reed-Solomon. Este método, ao garantir a segurança, aumenta 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): 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 permitem que o provador envie polinômios gradualmente através da interação com o verificador, permitindo que o verificador valide se o cálculo está correto consultando os resultados de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que tratam as expressões polinomiais de maneiras diferentes, impactando 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 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, podendo 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 a combinação de PLONK PIOP e FRI PCS, baseada no domínio de Goldilocks. Plonky2 foi projetado para realizar recursões de forma eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao campo finito ou à curva elíptica utilizada, a fim de garantir a correção, o desempenho e a segurança do sistema. A escolha dessas combinações não apenas afeta o tamanho da prova do 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 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 (towers of binary fields) forma 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 de HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo uma verificação de consistência segura e eficiente entre as variáveis e suas permutações. Em terceiro lugar, 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, proporcionando flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequeno campo (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o campo binário e reduzindo as despesas normalmente associadas a grandes campos.

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

Os corpos binários em torre são a chave para realizar cálculos verificáveis rapidamente, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os corpos 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 corpo binário suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre o corpo binário 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, fazem com que os corpos binários sejam 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 essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa caber 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 a 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 comumente usados incluem a redução especial ) como usada no AES ###, a redução Montgomery ( como usada no POLYVAL ) e a redução recursiva ( como na Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa que no domínio binário, tanto as operações de adição quanto multiplicação não requerem o 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 domínio binário. Pode ser vista como um elemento único no domínio binário de 128 bits, ou desmembrada em dois elementos de domínio torre de 64 bits, quatro elementos de domínio torre de 32 bits, dezesseis elementos de domínio torre de 8 bits, ou 128 elementos do domínio F2. Esta flexibilidade de representação não requer nenhum custo computacional, é apenas uma conversão de tipo da string de bits (typecast), sendo uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequeno podem ser empacotados em elementos de domínio maiores sem 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, quadrado e inversão em ( que podem ser decompostas em subdomínios de m bits ) no domínio binário de torre de n bits.

( 2.2 PIOP: versão adaptada do Produto HyperPlonk e PermutationCheck------aplicável ao domínio binário

O design do PIOP no protocolo Binius foi inspirado no HyperPlonk e adota uma série de mecanismos de verificação principais, utilizados para validar a correção de polinômios e conjuntos multivariados. Essas verificações principais incluem:

1. GateCheck: Verificar se o testemunho confidencial ω 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 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: Verificar 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 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: 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 de avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional para o validador. 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 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:

• Optimização do ProductCheck: no HyperPlonk, o ProductCheck requer que o denominador U seja não nulo em todo o hipercubo, e o produto deve ser igual a um valor específico; a Binius simplifica esse processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade de cálculo.

• Tratamento do problema de divisão por zero: HyperPlonk não conseguiu tratar adequadamente casos de divisão por zero, levando à incapacidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente deste problema, mesmo quando o denominador é zero, permitindo que o ProductCheck do Binius continuasse 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, permitindo que o 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 existente PIOPSumCheck, especialmente ao lidar com a validação de polinómios multivariáveis mais complexos, proporcionando um suporte funcional mais robusto. Essas melhorias não apenas 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 o manuseio de polinómios virtuais são uma das tecnologias chave, permitindo gerar e operar efetivamente polinómios derivados de manipuladores de entrada ou de outros polinómios virtuais. Abaixo estão dois métodos chave:

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