Análise dos princípios dos STARKs da Binius e reflexõ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 nos 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, muitos valores de redundância adicionais ocupam todo o domínio ao usar a codificação de Reed-Solomon para expandir os dados, 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, 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 um grande espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, com codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs de 4ª geração.

Comparado aos campos finitos descobertos em pesquisas recentes, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre campos binários remonta à década de 1980. Atualmente, os campos 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 Message Authentication Code ( GMAC ), baseado no domínio F2128;

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

• O protocolo FRI original e o zk-STARK, bem como a função de hash Grøstl que chegou à final do SHA-3, que é baseada no domínio F28, é um algoritmo de hash muito adequado 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 a sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não precisa de entrar na extensã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 os cálculos FRI ainda precisam de se aprofundar em um domínio de extensão maior para garantir a segurança necessária.

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

Binius propôs uma solução inovadora que trata esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariáveis (, especificamente polinômios multilineares ), em vez de polinômios univariáveis, representando toda a trajetória computacional através de seus valores nos "hipercubos" (; em segundo lugar, como cada dimensão do hipercubo tem comprimento 2, não é possível realizar a extensão padrão de Reed-Solomon como nas STARKs, mas é possível 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 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 as seguintes duas partes:

• Prova de Oráculo Interativo Polinomial Baseada em 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 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 de forma gradual, permitindo que o verificador valide se o cálculo está correto consultando apenas alguns resultados de avaliação polinomial. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, cada um com uma maneira diferente de tratar 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 é usado para provar se a igualdade polinomial gerada por 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 comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS têm desempenhos, segurança e cenários de aplicação distintos.

De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um campo finito ou curva elíptica adequada, podendo construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combina 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 alcançar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao campo finito ou à curva elíptica utilizada, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não só afeta o tamanho da prova SNARK e a eficiência de 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 funções 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 campos binários (towers of binary fields) constitui a base de seu cálculo, permitindo a realização de 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 interativo (PIOP), garantindo a verificação de consistência segura e eficiente entre as 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 segurança robusta para o mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente no domínio binário e reduzindo as sobrecargas normalmente associadas a grandes domínios.

( 2.1 Domínios finitos: aritmética baseada em torres de campos binários

Os domínios binários em torre são fundamentais para a realização de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: computação eficiente e aritmética eficiente. Os domínios binários suportam essencialmente operações aritméticas altamente eficientes, tornando-os uma escolha ideal para aplicações criptográficas com requisitos sensíveis ao desempenho. Além disso, a estrutura do domínio binário suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre o domínio binário 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 através da estrutura em torre, tornam os domínios 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 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 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 incluído em 32 bits, nem toda string de 32 bits corresponde de forma única a um elemento de domínio, enquanto o domínio binário possui essa conveniência de mapeamento um a um. No domínio primo Fp, 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, 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 em 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: essa string pode ser interpretada de várias maneiras no contexto de campos binários. Pode ser vista como um elemento único em um campo binário de 128 bits, ou ser analisada como dois elementos de campo torre de 64 bits, quatro elementos de campo torre de 32 bits, 16 elementos de campo torre de 8 bits, ou 128 elementos de campo F2. Essa flexibilidade de representação não requer nenhum custo computacional, apenas uma conversão de tipo da string de bits (typecast), que é uma propriedade muito interessante e útil. Além disso, os elementos de campo pequenos podem ser agrupados em elementos de campo maiores sem necessidade de 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 da multiplicação, elevação ao quadrado e operações de inversão em campos torre binários de n bits ( decomponíveis em subcampos de m bits ).

( 2.2 PIOP: versão adaptada do HyperPlonk Product e PermutationCheck------aplicável a campos binários

O design do PIOP no protocolo Binius foi 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. Esses mecanismos de verificação fundamentais 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: 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 permutaçã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 multivariados 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: 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 polinomial.

6. ZeroCheck: verificar se um polinómio multivariável em um hipercubo booleano em qualquer ponto é 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 corresponde 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 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 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 zero em todo o hipercubo, e que o produto seja igual a um valor específico; Binius simplifica este processo de verificação ao especializar esse valor para 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 zero no hipercubo; Binius lidou corretamente com 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 entre Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a Verificação de Permutação entre várias colunas, permitindo que Binius lide com casos de arranjo polinomial mais complexos.

Assim, o 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 multivariados mais complexos, oferecendo 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 provas 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 tratamento 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 outros polinómios virtuais. Abaixo estão dois métodos-chave:

• Empacotamento: Este método otimiza a operação empacotando elementos menores em posições adjacentes da ordem do dicionário em elementos maiores. O operador Pack é direcionado a blocos de tamanho 2κ e os combina em alto