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 é: 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 chave.

Como mostrado na Tabela 1, 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 um grande espaço desperdiçado. Em comparação, o domínio binário permite operações diretas nos bits, com codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs de quarta geração.

Tabela 1: Caminho de Derivação STARKs

Em comparação com os domínios finitos recentemente descobertos em pesquisas, 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 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, usando codificação Reed-Solomon baseada em F28;

• O protocolo FRI original e o protocolo 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 utilizam 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 pela Binius deve depender completamente da extensão de domínio para assegurar a 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, funcionando apenas no domínio base, permitindo assim uma alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam ser aprofundados 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 de 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 utilizado deve ser maior do que o tamanho após a expansão da codificação.

A Binius propôs uma solução inovadora que trata esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariável (, especificamente um polinômio multilinhar ), 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 realizar uma extensão padrão de Reed-Solomon como no STARKs, mas o hipercubo pode ser considerado como um quadrado ), com base no qual se pode realizar a extensão de Reed-Solomon. Este método, ao garantir a segurança, melhora significativamente a eficiência de 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 de Oracle Polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de prova, transforma a relação computacional de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente por meio da interação com o verificador, permitindo que o verificador valide se a computação está correta consultando apenas alguns resultados de avaliação polinomial. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, cada um tratando as expressões polinomiais de maneira diferente, o que afeta o desempenho e a eficiência do sistema SNARK como um todo.

• Esquema de Compromisso Polinomial (Polynomial Commitment Scheme, PCS): O esquema de compromisso polinomial é utilizado para provar se uma equação polinomial gerada pelo PIOP é verdadeira. O PCS é uma ferramenta criptográfica, através da qual o provador pode se comprometer a um determinado polinômio e, posteriormente, verificar os resultados 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 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 domínio finito ou curva elíptica apropriados, é possível 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 do setup 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 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í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) 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 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 forte segurança ao 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 as despesas geralmente associadas a grandes domínios.

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

Os campos binários em torre são fundamentais 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 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, 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 tirar pleno proveito da sua hierarquia através da estrutura em 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 um elemento no domínio binário. Por exemplo, no mais básico domínio binário F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do domínio binário de k bits. Isso é diferente dos domínios primos, que não conseguem fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa estar contido em 32 bits, nem toda string de 32 bits pode corresponder de maneira única a um elemento do domínio, enquanto o domínio binário oferece essa conveniência de mapeamento um a um. No domínio primo Fp, os 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, os métodos de redução comumente usados incluem a redução especial ) como utilizado no AES ###, a redução Montgomery ( como usada no POLYVAL ) e a redução recursiva ( como 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 é necessário 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 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 de campos binários. Pode ser vista como um elemento único no campo binário de 128 bits, ou pode ser interpretada como dois elementos de campo de torre de 64 bits, quatro elementos de campo de torre de 32 bits, 16 elementos de campo de 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. Ao mesmo tempo, elementos de campo pequenos podem ser empacotados como elementos de campo maiores sem custo computacional adicional. O protocolo Binius aproveita essa 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 de operações de multiplicação, quadrado e inversão em campos de torre de n bits que ( podem ser decompostos em subcampos de m bits ).

Figura 1: Domínio Binário em Torre

( 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 é inspirado no HyperPlonk e utiliza uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos multivariados. Esses verificadores essenciais incluem:

1. GateCheck: validar se o testemunho secreto ω 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: Verificar se os resultados de 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((, a fim de garantir a consistência da 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 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 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 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: Detectar 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 para a parte de verificação. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que possibilitam o processamento em lote de várias instâncias de verificação de somas.

8. BatchCheck: baseado no SumCheck, valida a correção da avaliação de múltiplos polinômios multivariados, para aumentar a eficiência do protocolo.

Embora a Binius e a HyperPlonk tenham muitas semelhanças no design do protocolo, a Binius fez melhorias nas seguintes 3 áreas:

• Otimização do ProductCheck: No HyperPlonk, o ProductCheck exige que o denominador U seja sempre diferente de zero no hipercubo, e que o produto seja igual a um valor específico; a Binius simplifica esse processo de verificação ao especializá-lo para 1, reduzindo assim a complexidade computacional.

• Tratamento do problema de divisão por zero: HyperPlonk não conseguiu lidar adequadamente com situações de divisão por zero, levando à incapacidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente deste 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 esta funcionalidade; Binius suporta a verificação de permutação entre várias colunas, o que permite que o Binius lide com casos de arranjo polinomial mais complexos.

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

( 2.3 PIOP: novo argumento de mudança multilinhar------aplicável a