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, como os índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, ao usar a codificação de 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 chave.

A largura de codificação dos STARKs de primeira geração é de 252 bits, a largura de codificação dos STARKs de segunda geração é de 64 bits, e a largura de codificação dos STARKs de terceira 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 operar diretamente sobre os bits, com uma codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs de quarta geração.

Comparado aos domínios finitos descobertos em pesquisas recentes, como Goldilocks, BabyBear e Mersenne31, a pesquisa em domínios binários remonta à década de 1980. 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;

• Código de autenticação de mensagem Galois ( GMAC ), baseado no domínio F2128;

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

• O protocolo FRI original e o zk-STARK, bem como a função hash Grøstl, que chegou à fase final do SHA-3, baseando-se 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 praticidade. A maioria dos polinómios envolvidos nos cálculos do 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 os cálculos 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 prova baseado em domínios binários, existem 2 problemas práticos: ao calcular a representação da trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinômio; ao fazer o compromisso da árvore Merkle em STARKs, é necessário realizar a codificação de Reed-Solomon, e o tamanho do domínio deve ser maior do que o tamanho após a extensão da codificação.

Binius propôs uma solução inovadora que aborda esses dois problemas de forma separada, e realiza a representação dos 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, para representar toda a trajetória computacional através dos seus valores em "hipercubos" (; em segundo lugar, como cada dimensão do hipercubo tem comprimento 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 segurança, melhora significativamente a eficiência da codificação e o desempenho computacional.

2 Análise do Princípio

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

• Prova de Oracle Interativa Polinomial Teórica 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 validador, permitem que o provador envie polinômios gradualmente, permitindo que o validador verifique 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, cada um com diferentes maneiras de lidar com expressões polinomiais, afetando assim o desempenho e a eficiência de todo o sistema SNARK.

• Polinomial Commitment Scheme ( Polynomial Commitment Scheme, PCS ): O esquema de compromisso polinomial é usado para provar se uma igualdade polinomial gerada por PIOP é verdadeira. PCS é uma ferramenta criptográfica, através da qual, o provador pode se comprometer com um determinado polinômio e depois verificar o resultado da avaliação desse polinômio, enquanto oculta outras informações do polinômio. 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 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 da configuração confiável do protocolo ZCash.

• Plonky2: utiliza a combinação de PLONK PIOP e FRI PCS, e é baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao domínio 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 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 domínio binário (towers of binary fields) 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 produto e permutação do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo a 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 domínios. Quarto, Binius utilizou uma versão aprimorada da prova de busca Lasso, oferecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo empregou um esquema de compromisso polinomial em pequenos domínios (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente no domínio binário e reduzindo a sobrecarga normalmente associada a grandes domínios.

( 2.1 Campo finito: aritmética baseada em torres de campos binários

Os campos binários em torre são fundamentais para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os campos binários 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 campo binário suporta um processo de aritmética simplificado, onde 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 plenamente sua hierarquia através da estrutura em torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis, como o Binius.

Onde "canônico" refere-se à representação única e direta de elementos no campo binário. Por exemplo, no campo binário F2 mais básico, qualquer string de k bits pode ser mapeada diretamente para um elemento do 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 caber em 32 bits, nem toda string de 32 bits pode corresponder de maneira única a um elemento do campo, enquanto o campo binário possui essa conveniência de mapeamento um-para-um. No campo primo Fp, os métodos comuns de redução 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 a redução especial ) como usada no AES ###, a redução Montgomery ( como usada no POLYVAL ) e a redução recursiva ( como Tower ). O artigo "Explorando o Espaço de Design de Implementações de Hardware ECC de Campo Primo vs. Campo Binário" aponta que o campo binário não requer o 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: 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 interpretada 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 8 bits, ou 128 elementos de domínio F2. Essa flexibilidade de representação não requer nenhum custo computacional, apenas uma conversão de tipo da string de bits (typecast), o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser compactados em elementos de domínio maiores sem necessidade de custo computacional adicional. O protocolo Binius se aproveita dessa 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 da multiplicação, quadratura e operações de inversão em domínios de torre binária de n bits ( que podem ser decompostos 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, utilizando uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos multivariados. Estes mecanismos de verificação essenciais incluem:

1. GateCheck: verificar 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 procura 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: 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 tem algum ponto que é zero ∏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 avaliação de polinómios univariáveis, reduz a complexidade computacional para o 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 múltiplos polinómios multivariáveis, a fim de 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:

• Otimização do ProductCheck: no HyperPlonk, o ProductCheck requer 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 simplifica esse 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, resultando na incapacidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente este problema, pois mesmo quando o denominador é zero, o ProductCheck da 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 arranjos polinomiais mais complexas.

Assim, o Binius melhorou a flexibilidade e a eficiência do protocolo através de melhorias no mecanismo existente PIOPSumCheck, especialmente ao lidar com a verificação de polinômios multivariados mais complexos, fornecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em campos binários.

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

No protocolo Binius, a construção e o processamento 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:

• Packing: Este método passa por