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 índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, ao expandir os dados usando codificação de Reed-Solomon, 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 uma grande quantidade de espaço desperdiçado. Em comparação, o campo binário permite operações diretas sobre os bits, com uma codificação compacta e eficiente, sem espaço desperdiçado, ou seja, os STARKs de quarta geração.

Tabela 1: Caminho de derivação STARKs

| Álgebra | Largura de código | Sistema representativo | |------|----------|----------| | 1ª geração | 252bit | StarkWare |
| 2ª geração | 64bit | Plonky2 | | 3ª geração | 32bit | BabyBear | | 4ª Geração | Domínio Binário | Binius |

Em comparação 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 na criptografia, exemplos típicos incluem:

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

• Galois Authentication Code ( GMAC ), baseado no domínio F2128;

• Código QR, utilizando 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, são baseados no domínio F28 e são 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 depende 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, operando apenas no domínio base, conseguindo 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 aprofundar-se em domínios de extensão maiores para garantir a segurança necessária.

Ao construir um sistema de provas 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 comprometer a á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 aborda essas duas questões separadamente e realiza a representação dos mesmos dados de duas formas diferentes: primeiro, usando um polinômio multivariável (, especificamente um polinômio multilinear ), em vez de um polinômio univariável, representando toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, como 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 o hipercubo pode ser visto como um quadrado ), tendo como base esse quadrado para a extensão de Reed-Solomon. Este método, enquanto garante a segurança, melhora 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:

• Prova de Oráculo Interativo Polinomial Teórica da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de prova, transforma relações computacionais 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 incremental, 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, cada um com uma abordagem diferente para o tratamento de expressões polinomiais, o que afeta 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 equação 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, ao mesmo tempo que 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 domínio finito ou curva elíptica adequada, pode-se 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 da configuração confiável do protocolo ZCash.

• Plonky2: utiliza PLONK PIOP em combinação com FRI PCS, e é baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar uma 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 afeta apenas 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 extensíveis 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ínio binário (towers of binary fields) constitui a base de seu cálculo, 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 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 de verificação de relações multilineares em pequenos domínios. Quarto, Binius adotou uma versão aprimorada 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 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

Os campos binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculo eficiente 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 sensíveis ao desempenho. Além disso, a estrutura dos campos binários suporta um processo de aritmética simplificada, ou seja, as operações realizadas sobre o campo binário podem ser representadas em uma forma algébrica compacta e fácil de verificar. Essas características, juntamente com a capacidade de aproveitar plenamente suas propriedades hierárquicas através da estrutura em 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 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 difere do domínio primo, que não pode fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa ser contido em 32 bits, nem toda string de 32 bits pode corresponder 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, 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 frequentemente utilizados incluem a redução especial ) como usada no AES ###, a redução Montgomery ( como usada no POLYVAL ) e a redução recursiva ( como na 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 o uso de 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 + Y2.

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 no domínio binário de 128 bits, ou pode ser interpretada 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), que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos 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, quadratura e operações de inversão em um domínio binário de torre 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 do PIOP no protocolo Binius foi inspirado no HyperPlonk e utiliza uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos multivariáveis. Esses verificadores essenciais incluem:

1. GateCheck: verificar 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: 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((, 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 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: 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 um polinómio multivariável em um problema de avaliação de um polinómio univariável, reduz-se a complexidade computacional para o verificador. 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 soma.

8. BatchCheck: baseado em SumCheck, verifica a correção da avaliação de múltiplos polinômios multivariáveis para melhorar a eficiência do protocolo.

Apesar de Binius ter muitas semelhanças com HyperPlonk no design do protocolo, Binius fez melhorias nas seguintes 3 áreas:

• Otimização do ProductCheck: no HyperPlonk, o ProductCheck requer que o denominador U seja sempre diferente de zero no 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 de divisão por zero: 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; Binius tratou corretamente este 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 ao Binius lidar com situações de arranjo polinomial mais complexas.

Assim, a Binius melhorou a flexibilidade e a eficiência do protocolo através do aprimoramento do mecanismo existente PIOPSumCheck, especialmente ao lidar com a validação de polinômios multivariáveis mais complexos, fornecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para sistemas de prova futuros baseados em campos binários.

( 2.3 PIOP: novo argumento de deslocamento multilinear------aplicável ao hipercubo booleano

No protocolo Binius, virtual