Análise dos princípios dos STARKs da Binius e reflexão 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 em programas reais é relativamente 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 codificação 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, a redução do tamanho do domínio tornou-se uma estratégia chave.

A largura de codificação do STARKs da 1ª geração é de 252 bits, a largura de codificação do STARKs da 2ª geração é de 64 bits, e a largura de codificação do STARKs da 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 campo binário permite operações diretas nos bits, com codificação compacta e eficiente, sem desperdício de espaço, ou seja, o STARKs da 4ª geração.

Comparado a novas descobertas de domínios finitos nos últimos anos, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre domínios binários remonta à década de 1980. Atualmente, os domínios binários são amplamente utilizados em criptografia, exemplos típicos incluem:

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

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

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

• O protocolo original FRI e zk-STARK, bem como a função hash Grøstl, que chegou à final do SHA-3, é baseada no domínio F28 e é um algoritmo de hash muito adequado para recursão.

Quando se utiliza um domínio menor, a operação de ampliaçã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 ampliação de domínio para assegurar a sua segurança e viabilidade prática. A maioria dos polinómios envolvidos no cálculo do Prover não precisa entrar na ampliação de domínio, operando apenas no domínio base, o que permite uma 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 ampliação maior para garantir a segurança necessária.

Ao construir um sistema de provas com base em domínios binários, existem 2 problemas práticos: ao calcular a representação de traços em STARKs, o tamanho do domínio 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 domínio utilizado deve ser maior do que o tamanho após a extensão da codificação.

Binius apresentou uma solução inovadora que lida com esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando um polinômio multivariado ( que é especificamente um polinômio multilinhar ) em vez de um polinômio univariado, representando toda a trajetória de cálculo através de seus valores nos "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 pode-se considerar o hipercubo como um quadrado ) e realizar a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir a segurança, melhora consideravelmente 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 de Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de provas, transforma a relação computacional 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 a computação está correta consultando os resultados da avaliação de um pequeno número de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, que têm diferentes formas 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 pelo PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se com um determinado polinômio e, posteriormente, verificar o resultado da avaliação desse polinômio, enquanto oculta outras informações do 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, níveis de 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, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combinando 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 do protocolo ZCash.

• Plonky2: utiliza PLONK PIOP combinado com FRI PCS e baseado no domínio Goldilocks. Plonky2 é projetado para realizar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos 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 só 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 a necessidade de uma configuração confiável, bem como se pode suportar funcionalidades expandidas como provas recursivas ou provas agregadas.

Binius: HyperPlonk PIOP + Brakedown PCS + domínios binários. 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 (towers of binary fields) forma a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adaptou o HyperPlonk para verificação de produtos e permutações em seu protocolo de prova Oracle interativo (PIOP), garantindo verificações de consistência seguras e eficientes entre 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 domínios. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, que oferece flexibilidade e forte segurança para o mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso de polinômios de pequeno domínio (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o domínio binário e reduzindo a sobrecarga geralmente 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 realizaçã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 que são sensíveis ao desempenho. Além disso, a estrutura do campo binário suporta um processo de aritmética simplificado, onde as operações executadas 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 tirar pleno proveito de suas propriedades hierárquicas por meio da estrutura de torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis como o Binius.

O termo "canonical" refere-se à representação única e direta de elementos em um campo binário. Por exemplo, no campo binário F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de campo binário de k bits. Isso é diferente dos campos primos, onde não é possível 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 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, métodos comuns de redução incluem redução de Barrett, redução de 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 ) usada em AES ###, redução de Montgomery ( usada em POLYVAL ), e redução recursiva ( como Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa que, em operações de adição e multiplicação, o campo binário não requer a introdução de transporte, e a operação de quadrado no campo binário é muito eficiente, pois segue a regra simplificada (X + Y )2 = X2 + Y2.

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 do domínio de torre de 64 bits, quatro elementos do domínio de torre de 32 bits, 16 elementos do 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 (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 de inversão em um domínio de torre binária 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 campo binário

O design PIOP no protocolo Binius é inspirado no HyperPlonk e utiliza uma série de mecanismos de verificação fundamentais para validar a correção de polinómios e conjuntos multivariados. Essas verificações principais incluem:

1. GateCheck: Verifica se o testemunho secreto ω e a entrada pública x satisfazem a relação de cálculo 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 disposição das 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: 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 polinomial.

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: Detecta 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 uma avaliação de polinómio univariável, reduz 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 múltiplas instâncias de verificação de somas.

8. BatchCheck: Baseado no SumCheck, verifica a correção da avaliação de múltiplos polinómios multivariáveis, 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:

• 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 simplifica 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, resultando na impossibilidade de afirmar que U é não nulo no hipercubo; o Binius tratou corretamente esse problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, permitindo a generalização para qualquer valor de produto.

• Verificação de Permutação em várias 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 disposição polinomial mais complexas.

Assim, a Binius, através da melhoria do mecanismo PIOPSumCheck existente, aumentou a flexibilidade e eficiência do protocolo, especialmente ao lidar com validações 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 a base para sistemas de provas baseados em corpos binários no futuro.

( 2.3 PIOP: novo argumento de deslocamento multilinhar------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 eficazmente polinómios derivados de manipuladores de entrada ou outros polinómios virtuais. Aqui estão dois métodos essenciais:

• 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 é direcionado a blocos de tamanho 2κ e combina-os em um domínio de alta dimensão.