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 em programas reais é bastante 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 utilizar a codificação de Reed-Solomon para expandir os dados, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que os valores originais sejam muito pequenos. Para resolver esse problema, reduzir o tamanho do domínio tornou-se uma estratégia chave.

A largura de codificação da 1ª geração de STARKs é de 252 bits, a largura de codificação da 2ª geração de STARKs é de 64 bits, e a largura de codificação da 3ª geração de STARKs é 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, resultando em codificações compactas e eficientes, sem qualquer espaço desperdiçado, ou seja, a 4ª geração de STARKs.

Comparado 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çado (AES), baseado no domínio F28;

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

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

• Protocólios originais FRI e zk-STARK, bem como a função de hash Grøstl, que chegou à fase final do SHA-3, baseada no campo F28, é um algoritmo de hash muito adequado para recursão.

Quando um domínio menor é utilizado, 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 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, mas apenas operar sob o 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 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 do trace em STARKs, o tamanho do domínio usado deve ser maior do que o grau do polinômio; ao comprometer a Merkle tree em STARKs, é necessário fazer a codificação de Reed-Solomon, e o tamanho do domínio usado deve ser maior do 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 de cálculo através de seus valores em "hipercubos"; em segundo lugar, uma vez que o comprimento de cada dimensão do hipercubo é 2, não é possível realizar a extensão padrão de Reed-Solomon como nos STARKs, mas pode-se considerar o hipercubo como um quadrado, realizando 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 dos Princípios

A construção da maioria dos sistemas SNARKs atualmente geralmente inclui as seguintes duas partes:

• Prova de Oracle Interativa Polinomial Teórica 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 gradualmente por meio da interação com o verificador, permitindo que o verificador valide se o cálculo está correto consultando os resultados da avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que diferem em suas abordagens para o tratamento de expressões polinomiais, impactando 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 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 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 têm desempenho, segurança e cenários de aplicação variados.

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

• Halo2: combinado com 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 a combinação de PLONK PIOP e FRI PCS, baseado no domínio Goldilocks. Plonky2 foi projetado para implementar 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 apenas afeta o tamanho da prova e a eficiência da 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 em torres de campos binários 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 as 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 utilizou uma versão melhorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança para o mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo um sistema de prova eficiente sobre o 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 fundamentais para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: computação eficiente e aritmética eficiente. Os campos binários suportam, por natureza, 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 dos campos binários suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre o campo binário podem ser expressas de forma algébrica compacta e fácil de verificar. Essas características, juntamente com a capacidade de tirar pleno proveito das suas propriedades hierárquicas através da estrutura em torre, tornam os campos binários especialmente 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 de domínio binário de k bits. Isto é diferente dos domínios de primos, que não conseguem fornecer essa representação canônica dentro de um número fixo de bits. Embora o domínio primo de 32 bits possa conter 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 essa conveniência de mapeamento um a 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 reduções especiais (como as usadas no AES), reduções de Montgomery (como as usadas no POLYVAL) e reduções recursivas (como a Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que o domínio binário não requer a introdução de transporte nas 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: essa string pode ser interpretada de várias maneiras no contexto dos domínios binários. Pode ser vista como um elemento único no domínio binário de 128 bits, ou ser 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 de domínio F2. Essa flexibilidade na representação não requer qualquer sobrecarga computacional, sendo apenas uma conversão de tipo da string de bits, o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínios menores podem ser empacotados em elementos de domínios maiores sem a necessidade de sobrecarga 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 das operações de multiplicação, quadrado e inversão em domínios binários de torre de n bits (que podem ser decompostos em subdomínios 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 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. Estas verificações essenciais 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: Verifica 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 procura 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: 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: verifica se um polinómio multivariável é zero em qualquer ponto do hipercubo booleano ∏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 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 em SumCheck, verifica a correção da avaliação de múltiplos polinômios multivariáveis para aumentar a eficiência do protocolo.

Embora o Binius tenha muitas semelhanças de design de protocolo com o HyperPlonk, o Binius fez melhorias nas seguintes 3 áreas:

• ProductCheck otimizado: 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 da divisão por zero: HyperPlonk não conseguiu lidar adequadamente com situações de divisão por zero, o que levou à impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius também consegue 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 ao Binius lidar com situações de permutação 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 multivariados 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 outros polinómios virtuais. Abaixo estão dois métodos chave:

• Embalagem: