Análise do Princípio dos STARKs da Binius e Reflexões sobre sua Otimização

1 Introdução

Ao contrário dos SNARKs baseados em curvas elípticas, os STARKs podem ser considerados SNARKs baseados em hash. Uma das principais razões para a atual ineficiência dos STARKs é: a maioria dos valores numéricos em programas reais é bastante pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvore 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 chave.

Como mostrado na Tabela 1, a largura de codificação dos STARKs da 1ª geração é de 252 bits, a largura de codificação dos STARKs da 2ª geração é de 64 bits, e a largura de codificação dos STARKs da 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 nenhum espaço desperdiçado, ou seja, os STARKs da 4ª geração.

Tabela 1: Caminho de derivação STARKs

| Geração | Largura de código | Sistema representativo | |------|----------|----------| | 1ª geração | 252bit | STARK | | 2ª geração | 64bit | Plonky2 | | 3ª geração | 32bit | Mina | | 4ª geração | 1bit | Binius |

Comparado 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 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
• 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
• Protocólos FRI originais e zk-STARK, bem como a função de hash Grøstl, que chegou à final do SHA-3, baseada no domínio F28, que é um algoritmo de hash muito adequado para recursão.

Quando se utiliza um domínio mais pequeno, 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, podendo operar 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 o cálculo FRI ainda precisam aprofundar-se em um domínio de extensão maior para garantir a segurança necessária.

Existem 2 problemas práticos ao construir sistemas de prova baseados em domínios binários: ao calcular a representação do trace nos STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinómio; ao comprometer a árvore de Merkle nos 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 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, representando toda a trajetória computacional através de seus valores em hipercubos (; em segundo lugar, como cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma expansão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado ), baseado no qual a expansão de Reed-Solomon pode ser realizada. 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:

• Informação Teórica de Prova Interativa Polinomial ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): O PIOP, como núcleo do sistema de prova, transforma a relação de cálculo de entrada em equações polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente, interagindo com o verificador, de modo que o verificador possa validar 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, cada um com formas distintas de tratar expressões polinomiais, o que impacta 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 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 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 curva elíptica adequada, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:

• Halo2: combinado com PLONK PIOP e 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: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar 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 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 expansã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ínios 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 do HyperPlonk em seu protocolo de prova de 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 adotou uma versão melhorada da prova de busca Lasso, proporcionando flexibilidade e segurança robusta para o mecanismo de busca. Por fim, o protocolo utilizou 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 a sobrecarga normalmente associada a grandes domínios.

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

O domínio binário em torre é a chave para implementar cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. O domínio binário, por sua essência, suporta operações aritméticas altamente eficientes, tornando-o uma escolha ideal para aplicações criptográficas 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, somadas à capacidade de aproveitar plenamente suas características hierárquicas através da estrutura em torre, tornam o domínio binário particularmente adequado para sistemas de prova escaláveis como o Binius.

O termo "canônico" refere-se à representação única e direta de um elemento no campo binário. Por exemplo, no campo binário mais básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de campo de k bits. Isso difere dos campos primários, que não podem fornecer essa representação canônica dentro de um número fixo de bits. Embora um campo primário de 32 bits possa caber em 32 bits, nem toda string de 32 bits corresponde exclusivamente a um elemento de campo, enquanto o campo binário oferece essa conveniência de mapeamento um a um. Nos campos primários Fp, os 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 campos finitos específicos, como Mersenne-31 ou Goldilocks-64. No campo binário F2k, métodos de redução comuns incluem a redução especial ) usada no AES ###, a redução de Montgomery ( usada no POLYVAL ) e a redução recursiva ( usada na 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 é extremamente eficiente, pois segue a regra simplificada de (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 um domínio binário. Pode ser vista como um elemento único em um domínio binário de 128 bits, ou pode ser analisada 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 torre 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, os elementos de domínio menores podem ser empacotados em elementos de domínio maiores sem custos computacionais adicionais. 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, quadrados 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 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. Essas verificações fundamentais 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((, a fim de garantir a consistência de permutação 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 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 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 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: Detectar 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 unidimensionais, reduz-se 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 permitem o processamento em lote de várias 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:

• ProductCheck otimização: No HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em todo o hipercubo e que o produto seja igual a um valor específico; Binius simplifica este processo de verificação ao especializá-lo 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 desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius pode continuar a processar, permitindo a promoção a qualquer valor de produto.

• Verificação de Permutação entre Colunas: HyperPlonk não possui essa funcionalidade; Binius suporta a Verificação de Permutação entre múltiplas colunas, o que permite que Binius lide com casos de disposição polinomial mais complexos.

Assim, a Binius melhorou a flexibilidade e a eficiência do protocolo através da melhoria do mecanismo existente PIOPSumCheck, especialmente ao lidar com verificações de polinómios multivariáveis mais complexas, proporcionando um suporte funcional mais robusto. Essas melhorias não só resolveram as limitações do HyperPlonk, mas também estabeleceram as bases para futuros sistemas de provas baseados em domínios binários.