Análise dos princípios STARKs da Binius e considerações sobre a otimização

1 Introdução

STARKs é um sistema de prova baseado em hash, diferente dos SNARKs que são baseados em curvas elípticas. Uma das principais razões para a baixa eficiência dos STARKs atualmente é 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 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 uma grande quantidade de 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 espaço desperdiçado, ou seja, os STARKs da 4ª geração.

Tabela 1: Caminho de Derivação STARKs

| Geração | Largura de bits | Características | |------|------|------| | 1ª Geração | 252bit | Domínio, grande desperdício de espaço | | 2ª geração | 64 bits | Domínio médio, desperdício de espaço relativamente grande | | 3ª Geração | 32bit | Pequeno domínio, ainda há espaço desperdiçado | | 4ª geração | 1bit | domínio binário, sem espaço desperdiçado |

Comparado aos 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 são amplamente utilizados na criptografia, exemplos típicos incluem:

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

• Galois Message Authentication Code ( GMAC ), baseado no campo F2128;

• QR Code, usando codificação Reed-Solomon baseada em F28;

• O protocolo FRI original e o zk-STARK, bem como a função hash Grøstl, que chegou à final do SHA-3, baseada no domínio F28, são algoritmos hash muito adequados para recursão.

Quando se utiliza um domínio menor, a operação de extensão do 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 do 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 do domínio, operando apenas no domínio base, permitindo assim uma alta eficiência no domínio pequeno. 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 com base 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 de 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 lida com esses dois problemas separadamente e realiza a representação dos mesmos dados de duas maneiras diferentes: primeiro, utilizando 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, como cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma extensão padrão de Reed-Solomon como em STARKs, mas o hipercubo pode ser tratado como um quadrado ), e a extensão de Reed-Solomon pode ser baseada nesse quadrado. 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

Atualmente, a maioria dos sistemas SNARKs é construída geralmente em duas partes:

• Informação Teórica Prova Interativa de Oracle Polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como o núcleo do sistema de prova, transforma a relação de cálculo de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP, através da interação com o validador, permitem que o provador envie polinômios gradualmente, de modo que o validador possa verificar 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 têm diferentes formas de lidar com 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 é utilizado 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 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-os com campos finitos ou curvas elípticas adequados, para 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 trusted setup do protocolo ZCash.

• Plonky2: utiliza PLONK PIOP e FRI PCS em conjunto, baseado no domínio Goldilocks. Plonky2 foi 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. Essas escolhas de combinação não apenas afetam o tamanho da prova e a eficiência da verificação do SNARK, mas também determinam 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í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 produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativo (PIOP), garantindo uma verificação consistente 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 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 um sistema de provas eficiente no 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 a chave para a implementaçã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 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 do campo binário suporta um processo de aritmética simplificado, 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 especialmente 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 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 corresponde exclusivamente 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 comuns de redução incluem redução de Barrett, 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 comuns de redução incluem redução especial ) como usada no AES ###, redução de Montgomery ( como usada no POLYVAL ) e redução recursiva ( como Tower ). O artigo "Explorando o Espaço de Design das Implementações de Hardware ECC de Domínio Primo vs. Domínio Binário" aponta que o domínio binário não exige a introdução de transporte em operações de adição e multiplicação, e que 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 cadeia de 128 bits: essa cadeia pode ser interpretada de várias maneiras no contexto do domínio binário. Pode ser vista como um elemento único no domínio binário de 128 bits, ou ser analisada 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 de representação não requer nenhum custo computacional, apenas uma conversão de tipo da cadeia de bits (typecast), que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser empacotados como elementos de domínio maiores sem custo computacional adicional. O protocolo Binius se aproveita dessa 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 para multiplicação, elevação ao quadrado e operações de inversão quando ( é decomposto em subdomínios de m bits ) no domínio binário torre de n bits.

( 2.2 PIOP: versão adaptada do HyperPlonk Product e PermutationCheck------aplicável ao campo binário

O design PIOP no protocolo Binius tomou como referência o HyperPlonk, adotando uma série de mecanismos de verificação essenciais para validar a correção de polinômios e conjuntos multivariados. Esses mecanismos de verificação 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: Verificar se os resultados de avaliação dos 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 procura dada, ou seja, f)Bµ) ⊆ T(Bµ), garantindo que certos valores estão 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: 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 é zero em qualquer ponto no 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 multivariados em avaliação de polinómios univariados, reduz a complexidade computacional para o 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 múltiplas instâncias de verificação de soma.

8. BatchCheck: Com base no SumCheck, valida 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 faz melhorias em 3 aspectos a seguir:

• Otimização do ProductCheck: 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 a situação de divisão por zero, resultando na incapacidade de afirmar que U é não nulo sobre o hipercubo; Binius tratou corretamente este problema, pois mesmo quando o denominador é zero, o ProductCheck da Binius consegue continuar o processamento, 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 o Binius lide com situações de arranjos polinomiais mais complexas.

Portanto, a Binius melhorou o mecanismo PIOPSumCheck existente, aumentando a flexibilidade e a eficiência do protocolo, especialmente ao lidar com a validação de polinómios multivariáveis mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também para não