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 ineficiê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 das provas baseadas em árvores de Merkle, ao usar 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 crucial.

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, e 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 uma grande quantidade de espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, com uma 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, a pesquisa sobre domínios binários remonta à década de 1980. Atualmente, os domínios binários já são amplamente utilizados na criptografia, exemplos típicos incluem:

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

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

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

• O protocolo original FRI e o 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 um algoritmo de hash muito adequado para recursão.

Ao usar 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 pelo Binius depende totalmente 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 no domínio base, conseguindo assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo de 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 campos binários, existem 2 problemas práticos: ao calcular a representação do trace em STARKs, o tamanho do campo utilizado deve ser maior do 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 campo utilizado deve ser maior do que o tamanho após a expansão da codificação.

Binius propôs uma solução inovadora que trata essas duas questões separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariável (, especificamente um polinômio multivariável ), em vez de um polinômio univariável, para representar toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, devido ao comprimento de cada dimensão do hipercubo ser 2, não é possível fazer a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado ), com base no qual a extensão de Reed-Solomon pode ser realizada. Este método, ao garantir a segurança, aumenta 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 Baseada em 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 permitem que o provador envie polinômios de forma gradual, interagindo com o verificador, de modo que este possa validar se o cálculo está correto consultando apenas os resultados de avaliação de alguns 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, o que afeta 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 que o provador se comprometa com um determinado polinômio e, posteriormente, valide 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 campo finito ou uma curva elíptica apropriada, 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 do setup confiável do protocolo ZCash.

• Plonky2: Adota o PLONK PIOP combinado com o FRI PCS, e é baseado no domínio Goldilocks. Plonky2 é projetado para implementar recursão eficiente. Ao projetar esses sistemas, os PIOP e PCS escolhidos devem corresponder ao domínio finito ou à curva elíptica utilizada, para garantir a correção, o desempenho e a segurança do sistema. A escolha dessas combinações não só afeta o tamanho da prova e a eficiência de verificação do SNARK, 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 na torre de campos binários (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 produtos e permutações de HyperPlonk em seu protocolo de prova Oracle interativo (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 da verificação de relações multilineares em pequenos domínios. Quarto, Binius utilizou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança ao mecanismo de busca. Por fim, o protocolo emprega um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo um sistema de prova eficiente no domínio binário e reduzindo a sobrecarga normalmente associada a grandes domínios.

( 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 rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes 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 ao desempenho. Além disso, a estrutura dos campos binários suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre os campos binários 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 propriedades hierárquicas por meio de uma estrutura de torre, tornam os campos 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 essa representação canônica dentro de um número fixo de bits. Embora o domínio primo de 32 bits possa ser contido dentro de 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 oferece a conveniência desse 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 comuns incluem a redução especial ), como usada no AES, a redução de Montgomery ###, como utilizada no POLYVAL, e a redução recursiva (, como a Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que no domínio binário não há necessidade de introduzir 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 do domínio binário. Pode ser vista como um elemento único no domínio binário de 128 bits, ou interpretada como dois elementos de domínio torre de 64 bits, quatro elementos de domínio torre de 32 bits, 16 elementos de domínio 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 (typecast), o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio menores podem ser empacotados em elementos de domínio maiores sem custo 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 de multiplicação, quadrado e operações inversas em um domínio binário de torre de n bits ( que pode ser decomposto em um subdomínio 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 se baseia no HyperPlonk, utilizando uma série de mecanismos de verificação essenciais para validar a correção de polinômios e conjuntos multivariados. Essas verificações essenciais incluem:

1. GateCheck: Verifica se a testemunha secreta ω e a entrada pública x satisfazem a relação de operação do circuito C)x, ω(=0, para garantir o funcionamento correto do circuito.

2. PermutationCheck: Verificar 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 ordenação 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 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: 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 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-se a complexidade computacional do verificador. Além disso, o SumCheck 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 para melhorar 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 exige 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 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 incapacidade de afirmar que U é não zero no hipercubo; Binius tratou corretamente desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius ainda consegue continuar o processamento, 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 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 PIOPSumCheck existente, especialmente ao lidar com a verificação de polinómios multivariáveis 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 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, 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 otimiza a operação agrupando elementos menores em posições adjacentes da ordem do dicionário em elementos maiores. O operador Pack opera em blocos de tamanho 2κ e combina-os em domínios de alta dimensão.