1. Introdução

Distinguido dos SNARKs baseados em curvas elípticas, os STARKs podem ser vistos como SNARKs baseados em hash. Um dos principais desafios que contribuem para a atual ineficiência dos STARKs é que a maioria dos valores em programas reais são relativamente pequenos, como índices em loops, valores booleanos e contadores. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, a codificação Reed-Solomon é usada para estender os dados, resultando em muitos valores redundantes ocupando todo o campo, mesmo quando os valores originais são pequenos. Abordar essa ineficiência, reduzindo o tamanho do campo, tornou-se uma estratégia-chave.

Como mostrado na Tabela 1, a primeira geração de STARKs tinha uma largura de codificação de 252 bits, a segunda geração 64 bits e a terceira geração 32 bits. Apesar da redução da largura de codificação na terceira geração, ainda há significativa perda de espaço. Em contraste, os campos binários permitem a manipulação direta de bits, possibilitando a codificação compacta e eficiente com mínimo de perda. Essa eficiência é alcançada na quarta geração de STARKs.

Tabela 1: Caminho de Derivação STARKs

Em comparação com campos finitos como Goldilocks, BabyBear e Mersenne31, que têm recebido atenção recentemente, a pesquisa em campos binários remonta aos anos 80. Hoje, os campos binários são amplamente utilizados em criptografia, com exemplos notáveis incluindo:

• Padrão de Criptografia Avançada (AES), baseado no
• F28
• campo;
• Código de Autenticação de Mensagem Galois (GMAC), com base no
• 𝐹2128
• campo;
• Códigos QR, que utilizam codificação Reed-Solomon com base no
• 𝐹28
• campo;
• Os protocolos originais FRI e zk-STARK, assim como a função de hash Grøstl, finalista na competição SHA-3, que é baseada no
• 𝐹28
• campo e é adequado para algoritmos de hash recursivos.

Quando são usados campos menores, as operações de extensão de campo se tornam cada vez mais importantes para garantir a segurança. O campo binário usado pela Binius depende inteiramente da extensão do campo para garantir tanto a segurança quanto a usabilidade prática. A maioria dos cálculos polinomiais envolvidos nas operações do Prover não precisa entrar no campo estendido, pois eles só precisam operar no campo base, alcançando assim alta eficiência no campo pequeno. No entanto, verificações de ponto aleatório e cálculos FRI ainda devem ser realizados em um campo estendido maior para garantir o nível necessário de segurança.

Existem dois desafios práticos ao construir um sistema de prova baseado em campos binários: Primeiro, o tamanho do campo usado para representação de rastreamento em STARKs deve ser maior do que o grau do polinômio. Segundo, o tamanho do campo usado para o compromisso da árvore de Merkle em STARKs deve ser maior do que o tamanho após a extensão de codificação Reed-Solomon.

Binius é uma solução inovadora para abordar esses dois problemas, representando os mesmos dados de duas maneiras diferentes: Primeiro, usando polinômios multivariados (especificamente multilineares) em vez de polinômios univariados, representando todo o traço computacional através de suas avaliações sobre "hipercubos". Em segundo lugar, como cada dimensão do hipercubo tem um comprimento de 2, não é possível realizar extensões padrão de Reed-Solomon como em STARKs, mas o hipercubo pode ser tratado como um quadrado, e uma extensão Reed-Solomon pode ser realizada com base neste quadrado. Este método não só garante a segurança, mas também melhora muito a eficiência da codificação e o desempenho computacional.

2. Princípios Binius

A construção da maioria dos sistemas SNARK modernos geralmente consiste nos seguintes dois componentes:

• Polynomial Interactive Oracle Proof (PIOP) de Teoria da Informação: Como o núcleo do sistema de prova, o PIOP transforma as relações computacionais da entrada em equações polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios incrementalmente por meio de interações com o verificador. Isso permite que o verificador confirme a correção de uma computação consultando apenas um pequeno número de avaliações de polinômios. Vários protocolos PIOP, como PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, lidam com expressões polinomiais de maneiras diferentes, impactando o desempenho e a eficiência do sistema SNARK como um todo.
• Esquema de Compromisso de Polinómios (PCS): O PCS é uma ferramenta criptográfica usada para provar que as equações polinomiais geradas pelo PIOP são válidas. Permite ao provador comprometer-se com um polinómio e verificar as suas avaliações sem revelar informações adicionais sobre o polinómio. Os esquemas PCS comuns incluem KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) e Brakedown, cada um oferecendo características de desempenho distintas, garantias de segurança e cenários aplicáveis.

Selecionando diferentes esquemas PIOPs e PCS e combinando-os com campos finitos ou curvas elípticas adequadas, é possível construir sistemas de prova com propriedades distintas. Por exemplo:

• Halo2: Combina PLONK PIOP com Bulletproofs PCS e opera na curva Pasta. Halo2 foi projetado com escalabilidade em mente e elimina a configuração confiável anteriormente usada no protocolo ZCash.
• Plonky2: Combina PLONK PIOP com FRI PCS e é baseado no campo Goldilocks. Plonky2 é otimizado para recursão eficiente.

Ao projetar esses sistemas, a compatibilidade entre o PIOP, PCS e campo finito ou curva elíptica escolhidos é fundamental para garantir a correção, o desempenho e a segurança. Essas combinações influenciam o tamanho da prova SNARK, a eficiência da verificação e determinam se o sistema pode alcançar transparência sem uma configuração confiável, além de oferecer suporte a recursos avançados como provas recursivas ou agregação de provas.

Binius combina HyperPlonk PIOP com Brakedown PCS e opera num campo binário. Especificamente, Binius incorpora cinco tecnologias-chave para alcançar eficiência e segurança:

1. Aritmética baseada em torres de campos binários: Esta forma a fundação computacional do Binius, permitindo operações simplificadas dentro do campo binário.
2. Produto HyperPlonk e verificações de permutação: Binius adapta as verificações de produto e permutação do HyperPlonk em seu PIOP para garantir consistência segura e eficiente entre variáveis e suas permutações.
3. Novo argumento de deslocamento multilinear: Esta otimização melhora a verificação de relações multilinares dentro de campos pequenos, aumentando a eficiência geral.
4. Argumento de pesquisa aprimorado do Lasso: O protocolo incorpora um mecanismo de pesquisa mais flexível e seguro com este argumento avançado.
5. Esquema de Compromisso Polinomial de Pequeno Campo (PCS): Binius utiliza um PCS adaptado para pequenos campos, reduzindo a sobrecarga geralmente associada a campos maiores e permitindo um sistema de prova eficiente no campo binário.

Estas inovações permitem que Binius ofereça um sistema SNARK compacto e de alto desempenho, otimizado para campos binários, mantendo ao mesmo tempo segurança robusta e escalabilidade.

2.1 Campos Finitos: Aritmética Baseada em Torres de Campos Binários

As torres de campos binários desempenham um papel crítico na realização de cálculos rápidos e verificáveis devido a dois fatores principais: cálculo eficiente e aritmetização eficiente. Os campos binários suportam inerentemente operações aritméticas altamente eficientes, tornando-os ideais para aplicações criptográficas sensíveis ao desempenho. Além disso, a sua estrutura permite um processo de aritmetização simplificado, onde as operações realizadas em campos binários podem ser representadas em formas algébricas compactas e facilmente verificáveis. Essas características, combinadas com a estrutura hierárquica das torres de campos binários, tornam-nas particularmente adequadas para sistemas de prova escaláveis como Binius.

O termo "canônico" refere-se à representação única e direta de elementos num campo binário. Por exemplo, no campo binário mais básico $\mathbb{F}2

,anyk−bitstringcanbedirectlymappedtoak−bitbinaryfieldelement.Thisdiffersfrom primefields,which donotsuchacanonicalrepresentationwithinagiven numberofbits.Althougha32−bitprimefieldcanfitwithin32bits,notevery32−bitstringcanuniquelycorrespondto a afieldelement,while binaryfields provide thisone−to−onemapping.Inprimefields

Para campos finitos $\mathbb{F}_p$ , os métodos comuns de redução incluem a redução de Barrett, a redução de Montgomery, bem como métodos de redução especializados para certos campos finitos como Mersenne-31 ou Goldilocks-64. Em campos binários $\mathbb{F}{2^k}$ , os métodos comuns de redução incluem redução especial (como usada em AES), redução de Montgomery (como usada em POLYVAL) e redução recursiva (como usada em campos Tower). O artigo Explorando o Espaço de Design de Implementações de Hardware ECC de Campo Primo vs. Campo Binárioobserva que campos binários não requerem propagação de transporte em adição ou multiplicação, e o quadrado em campos binários é altamente eficiente devido à regra de simplificação

(𝑋+𝑌)2=𝑋2+𝑌2

.

Figura 1. Torres do Campo Binário

Conforme mostrado na Figura 1, uma sequência de 128 bits pode ser interpretada de várias maneiras no contexto de um campo binário. Ela pode ser vista como um elemento único no campo binário de 128 bits, ou pode ser analisada como dois elementos do campo de torre de 64 bits, quatro elementos do campo de torre de 32 bits, dezesseis elementos do campo de torre de 8 bits ou 128 elementos de

𝐹2

Esta flexibilidade na representação não incorre em sobrecarga computacional, pois é apenas uma conversão de tipo da sequência de bits. Esta é uma propriedade muito interessante e útil, pois elementos de campo menores podem ser agrupados em elementos de campo maiores sem custo computacional adicional. O protocolo Binius aproveita essa propriedade para aumentar a eficiência computacional. Além disso, o artigo Em Inversão Eficiente em Campos de Torre de Característica Dois explora a complexidade computacional da multiplicação, quadratura e inversão em

𝑛

campos binários da torre de bit (decomponíveis em

m

-bit subfields).

2.2 PIOP: Produto Adaptado HyperPlonk e Verificação de Permutação — Adequado para Campos Binários

O design PIOP no protocolo Binius é inspirado no HyperPlonk e incorpora uma série de verificações principais para verificar a correção de polinómios e conjuntos multivariados. Estas verificações são essenciais para garantir a integridade dos cálculos dentro do sistema de prova, especialmente ao operar sobre campos binários. As verificações principais incluem:

1. gateCheck: Garante que a testemunha privada
2. 𝜔
3. e entrada pública
4. 𝑥
5. satisfazer a relação de operação do circuito
6. 𝐶(𝑥,𝜔)=0
7. , verificando a execução correta do circuito.
8. PermutationCheck: Verifica se os resultados da avaliação de dois polinómios multivariados
9. 𝑓
10. e
11. 𝑔
12. no hipercubo booleano forma uma relação de permutação
13. 𝑓(𝑥)=𝑓(𝜋(𝑥))
14. , garantindo consistência entre as variáveis polinomiais.
15. LookupCheck: verifica se a avaliação de um polinômio está dentro de uma tabela de pesquisa fornecida, ou seja,
16. 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)
17. , garantindo que certos valores estejam dentro de uma faixa especificada.
18. MultisetCheck: Confirma se dois conjuntos multivariados são iguais, ou seja, ${(x{1,i},x{2,i})}{i \in H} = {(y{1,i},y{2,i})}{i \in H}$, garantindo consistência entre diferentes conjuntos.
19. ProductCheck: Garante que a avaliação de um polinômio racional no hiperkube booleano seja igual a um valor declarado, ou seja,
20. ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
21. , confirmando a correção do produto polinomial.
22. ZeroCheck: Verifica se um polinômio multivariável se avalia como zero em algum ponto do hiperplano booleano, ou seja,
23. ∏𝑥∈𝐻𝜇𝑓(𝑥)=0
24. para todos
25. 𝑥∈𝐵𝜇
26. , garantindo a distribuição adequada de zeros no polinômio.
27. SumCheck: Confirma se a soma das avaliações de um polinômio multivariado é igual ao valor declarado, ou seja,
28. ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
29. . Ao reduzir a avaliação de polinômios multivariados para avaliação de polinômios univariados, isso reduz a complexidade computacional do verificador. O SumCheck também permite a criação de lotes, que constrói combinações lineares usando números aleatórios para processar várias instâncias em lote.
30. BatchCheck: Uma extensão do SumCheck, verifica a correção de múltiplas avaliações polinomiais multivariadas, aumentando a eficiência do protocolo.

Embora Binius e HyperPlonk compartilhem várias semelhanças em seus projetos de protocolo, Binius introduz as seguintes melhorias-chave:

1. Optimização do ProdutoCheck: No HyperPlonk, o ProdutoCheck requer o denominador
2. 𝑈
3. ser não nulo em todo o hiperparalelepípedo e que o produto corresponda a um valor específico. Binius simplifica esta verificação definindo o valor do produto como 1, reduzindo a complexidade computacional geral.
4. Tratamento de Problemas de Divisão por Zero: O HyperPlonk não aborda eficazmente os problemas de divisão por zero, tornando desafiante garantir que
5. 𝑈
6. permanece não nulo sobre o hiperespaço. Binius resolve isso tratando adequadamente cenários de divisão por zero, permitindo que o ProductCheck funcione mesmo quando o denominador é zero, permitindo extensões para valores de produto arbitrários.
7. Cross-Column PermutationCheck: HyperPlonk não suporta verificações de permutação entre colunas. Binius resolve essa limitação introduzindo suporte para PermutationCheck entre colunas, permitindo que o protocolo gerencie permutações polinomiais mais complexas em várias colunas.

Assim, Binius melhora a flexibilidade e a eficiência do protocolo ao aprimorar o mecanismo PIOP SumCheck existente, especialmente fornecendo funcionalidade mais forte para verificar polinômios multivariados mais complexos. Essas melhorias não apenas abordam as limitações do HyperPlonk, mas também lançam as bases para sistemas à prova de futuro baseados em campos binários.

2.3 PIOP: Um Novo Argumento de Deslocamento Multilinear - Aplicável ao Hipercubo Booleano

No protocolo Binius, a manipulação e construção de polinômios virtuais desempenham um papel crucial na capacidade de manipulação eficiente de polinômios. Duas técnicas principais são empregadas para essas operações:

• Embalagem: O método de embalagem otimiza a manipulação de elementos menores agrupando-os em um domínio maior. Especificamente, elementos adjacentes em ordem lexicográfica são embalados em blocos maiores, geralmente de tamanho
• 2𝜅
• . Ao alavancar a Extensão Multilinear (MLE), os elementos agrupados são transformados em um novo polinômio virtual, que pode então ser avaliado e processado de forma eficiente. Este método melhora o desempenho das operações no hipercubo booleano ao reestruturar a função
• 𝑡
• numa forma computacionalmente eficiente.
• Operador de deslocamento: o operador de deslocamento rearranja elementos dentro de um bloco, deslocando-os ciclicamente com base em um deslocamento dado
• 𝑜
• . Esta mudança aplica-se a blocos de tamanho
• 2𝑏
• , garantindo que todos os elementos num bloco sejam deslocados uniformemente de acordo com o deslocamento predefinido. Este operador é particularmente útil ao lidar com polinómios virtuais em espaços de elevadas dimensões, uma vez que a sua complexidade aumenta linearmente com o tamanho do bloco, tornando-se uma técnica ideal para grandes conjuntos de dados ou complexas computações booleanas em hipercubos.

2.4 PIOP: Um Argumento de Pesquisa em Lasso Adaptado - Aplicável a Campos Binários

O protocolo Lasso em Binius oferece um método altamente eficiente para provar que elementos em um vetor.

𝑎∈𝐹𝑚

estão contidos dentro de uma tabela predefinida

t∈Fn

. Este argumento de pesquisa introduz o conceito de "Singularidade de Pesquisa" e é adequado para esquemas de compromisso polinomial multilinear. A eficiência de Lasso é destacada em dois aspetos principais:

• Eficiência comprovada : Ao conduzir
• 𝑚
• pesquisas numa tabela de tamanho
• n
• , o provador só precisa comprometer-se a
• 𝑚+𝑛
• elementos de campo pequenos, com o tamanho do campo retirado do conjunto
• 0,...,𝑚
• . Em esquemas criptográficos que dependem de exponenciação, o custo do provador é
• 𝑂(𝑚+𝑛)
• operações em grupo (por exemplo, adições de pontos de curva elíptica). Essa eficiência vem além do custo de verificar se um polinômio multilinear avaliado no hipercubo booleano corresponde a um elemento da tabela.
• Sem compromisso com mesas grandes: Se a mesa
• 𝑡
• é estruturado, o Lasso não requer um compromisso direto com a mesa, tornando possível lidar com tabelas muito grandes (por exemplo,
• 2128
• ou mais). O tempo de execução do provador depende apenas das entradas específicas acessadas na tabela. Para qualquer parâmetro inteiro
• 𝑐>1
• , o principal custo envolve o tamanho da prova, que aumenta à medida que
• 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐
• elementos de campo comprometidos. Estes elementos também são pequenos, retirados do conjunto
• 0,…,max𝑚,𝑛1/𝑐,𝑞−1
• , onde
• 𝑞
• é o maior valor no vetor
• 𝑎
• .

O protocolo Lasso consiste em três componentes principais:

1. Abstração Polinomial Virtual de Tabelas Grandes: O protocolo Lasso combina polinómios virtuais para permitir pesquisas eficientes e operações em tabelas grandes, garantindo escalabilidade sem degradação de desempenho.
2. Pesquisa de Tabela Pequena: No coração do Lasso está a pesquisa de tabela pequena, que verifica se um polinômio virtual avaliado em um hipercubo booleano é um subconjunto das avaliações de outro polinômio virtual. Esse processo é semelhante à detecção de memória offline e se resume a uma tarefa de detecção de multiconjunto.
3. Verificação de Multiconjunto : O protocolo também incorpora um mecanismo virtual para realizar verificações de multiconjunto, garantindo que dois conjuntos de elementos correspondam ou cumpram condições predefinidas.

O protocolo Binius adapta o Lasso para operações em campos binários, assumindo que o campo atual é um campo primo de grande característica (muito maior do que o comprimento da coluna que está sendo procurada). Binius introduz uma versão multiplicativa do protocolo Lasso, exigindo que o provador e o verificador incrementem a operação do "contador de memória" do protocolo não apenas adicionando 1, mas incrementando usando um gerador multiplicativo dentro do campo binário. No entanto, essa adaptação multiplicativa introduz complexidade adicional: diferentemente de um incremento aditivo, o gerador multiplicativo não incrementa em todos os casos, em vez disso, tendo uma única órbita em 0, o que pode apresentar um vetor de ataque. Para mitigar esse ataque potencial, o provador deve se comprometer com um vetor de contagem de leitura que seja diferente de zero em todos os lugares para garantir a segurança do protocolo.

2.5 PCS: Adaptado Brakedown PCS - Aplicável a Campos Pequenos

A ideia central por trás da construção do Binius PCS (Polynomial Commitment Scheme) é a compactação. O artigo do Binius apresenta dois esquemas Brakedown PCS baseados em campos binários: um instanciado usando códigos concatenados, e outro usando codificação de nível de bloco, que suporta o uso independente de códigos Reed-Solomon. O segundo esquema Brakedown PCS simplifica o processo de prova e verificação, embora produza um tamanho de prova ligeiramente maior do que o primeiro; no entanto, esse compromisso vale a pena devido às vantagens de simplificação e implementação que oferece.

O compromisso polinomial Binius utiliza principalmente o compromisso polinomial de campo pequeno com avaliações em um campo estendido, construção universal de campo pequeno e codificação de nível de bloco com técnicas de código Reed-Solomon.

Compromisso Polinomial de Campo Pequeno com Avaliação de Campo Estendido No protocolo Binius, compromissos polinomiais são realizados em um campo pequeno

𝐾

, com avaliações a decorrer num campo expandido

𝐿/𝐾

. Esta técnica garante que um polinómio multilinear

t(X0,...,Xl−1)

pertence ao domínio

𝐾[𝑋0,…,𝑋ℓ−1]

, enquanto os pontos de avaliação estão no campo maior

𝐿

. Esta estrutura de compromisso permite consultas eficientes no campo estendido, equilibrando segurança e eficiência computacional.

Construção Universal de Pequeno Campo Esta construção define parâmetros-chave como o campo

𝐾

, sua dimensão

ℓ

, e o código de bloco linear associado

𝐶

, assegurando simultaneamente que o campo alargado

𝐿

é grande o suficiente para avaliações seguras. Aproveitando as propriedades do campo estendido, o Binius alcança compromissos robustos através de códigos de bloco lineares, mantendo um equilíbrio entre eficiência computacional e segurança.

Codificação de nível de bloco com códigos de Reed-Solomon para polinómios definidos sobre campos pequenos como $\mathbb{F}2

,theBiniusprotocolemploysblock−levelencodingusingReed−Solomoncodes.Thisschemeallowspatientcommitmentoflyssmall−fieldpolynomialsbyencodingthemrow−by−rowintolargerfields(tais como:

\mathbb{F}{2^{16}}$ ), utilizando a eficiência e as propriedades separáveis de distância máxima dos códigos de Reed-Solomon. Após a codificação, estas linhas são comprometidas utilizando uma árvore de Merkle, o que simplifica a complexidade operacional dos compromissos polinomiais de campo pequeno. Esta abordagem permite o tratamento eficiente de polinómios em campos pequenos sem o encargo computacional normalmente associado a campos maiores.

3. Otimizações Binius

Para melhorar ainda mais o desempenho, a Binius incorpora quatro grandes otimizações:

1. Baseado em PIOP GKR: O protocolo GKR (Goldreich-Kalai-Rothblum) é usado para substituir o algoritmo de pesquisa de Lasso na multiplicação de campo binário, reduzindo significativamente o overhead no processo de compromisso.
2. Otimização ZeroCheck PIOP: Essa otimização aborda o equilíbrio entre os custos computacionais do Prover e Verifier, tornando a operação ZeroCheck mais eficiente ao distribuir a carga de trabalho de forma mais eficaz.
3. Otimização PIOP Sumcheck: Ao otimizar o processo de Sumcheck de pequenos campos, Binius reduz a carga computacional geral ao operar em campos pequenos.
4. Otimização PCS: Usando a otimização FRI-Binius (Provas de Oráculo Interativo de Reed-Solomon Rápido de Proximidade), Binius reduz o tamanho da prova e melhora o desempenho do protocolo, melhorando a eficiência geral na geração e verificação da prova.

3.1 PIOP baseado em GKR: multiplicação de campo binário usando GKR

No protocolo original Binius, a multiplicação de campo binário é tratada através de um esquema baseado em pesquisa, que associa a multiplicação às operações de adição linear com base no número de membros em uma palavra. Embora este método otimize a multiplicação binária até certo ponto, ainda introduz compromissos auxiliares linearmente relacionados ao número de membros. Ao adotar uma abordagem baseada em GKR, o protocolo Binius pode reduzir significativamente o número de compromissos necessários, levando a uma maior eficiência nas operações de multiplicação de campo binário.

A ideia central do protocolo GKR (Goldwasser-Kalai-Rothblum) é alcançar um acordo entre o Provador (P) e o Verificador (V) sobre um circuito aritmético em camadas em um campo finito.

𝐹

Cada nó neste circuito tem duas entradas para computar a função requerida. Para reduzir a complexidade computacional do Verificador, o protocolo utiliza o protocolo SumCheck, que reduz progressivamente as alegações sobre os valores da saída do circuito para valores de porta de camada inferior, simplificando as alegações para afirmações sobre as entradas. Dessa forma, o Verificador só precisa verificar a correção das entradas do circuito.

O Algoritmo de multiplicação de inteiros baseado em GKRem Binius transforma a verificação de se dois inteiros de 32 bits

𝐴

e

𝐵

satisfazer

𝐴⋅𝐵=?𝐶

em verificar se

(𝑔𝐴)𝐵=?𝑔𝐶

mantém em

𝐹264∗

. Esta transformação, combinada com o protocolo GKR, reduz significativamente os custos associados aos compromissos polinomiais. Comparado ao esquema baseado em pesquisa Binius anterior, a abordagem de multiplicação baseada em GKR requer apenas um compromisso auxiliar e reduz o custo de SumChecks, tornando o algoritmo mais eficiente, especialmente em casos em que os SumChecks são mais econômicos do que compromissos adicionais. Este método está se tornando uma solução promissora para minimizar os custos de compromisso polinomial de campo binário à medida que as otimizações Binius progridem.

3.2 ZeroCheck PIOP Optimization: Equilibrar Custos Computacionais entre Provador e Verificador

O artigo Algumas melhorias para o PIOP para ZeroCheckpropõe estratégias para equilibrar os custos computacionais entre o Prover (P) e o Verifier (V), com foco na redução da transmissão de dados e na complexidade computacional. Abaixo estão técnicas-chave de otimização:

• Reduzindo a transmissão de dados do Prover

Ao transferir parte da carga computacional para o Verificador, a transmissão de dados do Provador pode ser minimizada. Por exemplo, em rodada

𝑖

, o provador envia

𝑣𝑖+1(𝑋)

para

𝑋=0,…,𝑑+1

e o Verificador verifica se

vi=vi+1(0)+vi+1(1)

mantém.

Otimização: O Prover pode evitar o envio

𝑣𝑖+1(1)

, como o Verificador pode calculá-lo como

𝑣𝑖+1(1)=𝑣𝑖−𝑣𝑖+1(0)

.

Na rodada inicial, o Prover envia

𝑣1(0)=𝑣1(1)=0

, eliminando alguns cálculos de avaliação, o que reduz tanto os custos computacionais quanto os de transmissão para

𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺

.

• Redução do número de pontos de avaliação para o Prover

Durante a rodada

𝑖

, o provador deve enviar

𝑣𝑖+1(𝑋)

, calculado como

𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)

.

Otimização: Em vez disso, o Prover pode enviar

𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),

onde $v_i(X) = v_i'(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))

.AstheVerifiertem acesso a

\alpha

𝑎𝑛𝑑

r

,𝑡ℎ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓

v_i’(X)

𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑡ℎ𝑎𝑡𝑜𝑓

v_i(X)

, reduzindo os pontos de avaliação necessários.O controlo intercalar pode ser simplificado

(1 - \alphai)v{i+1}’(0) + \alpha_i v{i+1}’(1) = v_i’(X),

O terceiro aniversário com os eventos, o verallcostisapprovementos, theoverallcostisaproximadamente

2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.

𝐹𝑜𝑟

d = 3$, essas otimizações geram uma redução de custos por um fator de 5/3.

• Otimização de Interpolação Algébrica

Para um Provador honesto, o polinômio

𝐶(𝑥0,…,𝑥𝑛−1)

é zero em

Hn

e pode ser expresso como

𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)

. Onde

𝑄𝑖

é calculado através da divisão polinomial ordenada, a iniciar a partir de

𝑅𝑛=𝐶

. Divisão sequencial por

𝑥𝑖(𝑥𝑖−1)

computa

𝑄𝑖

e

𝑅𝑖

, com

𝑅0

representando a extensão multilinear de

𝐶

em

𝐻𝑛

, suposto ser zero.

Analisando os Graus de

𝑄𝑖

. Para

𝑗 > 𝑖

,

𝑄𝑗

mantém o mesmo grau em

𝑥𝑖

como

𝐶

. Para

𝑗=𝑖

, o grau é reduzido em 2 e para

𝑗<𝑖

, o grau é no máximo 1. Dado um vetor

𝑟=(𝑟0,…,𝑟𝑖)

,

𝑄𝑗(𝑟,𝑋)

é multilinear para todos

𝑗≤𝑖

. Além disso,

𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)

é o polinômio multilinear único correspondente

𝐶(𝑟,𝑋)

em

𝐻𝑛−𝑖

. Para qualquer

𝑋

e ainda

𝑥∈𝐻𝑛−𝑖−1

, pode ser representado como

𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).

Assim, durante cada rodada do protocolo, um novo

𝑄

é introduzido, e a sua avaliação pode ser derivada de

𝐶

e o anterior

𝑄

, permitindo a otimização da interpolação.

3.3 Otimização PIOP Sumcheck: Protocolo de Sumcheck de Campo Pequeno

No protocolo STARKs implementado por Binius, o principal gargalo para o provador costuma ser o protocolo de verificação de soma, em vez do Esquema de Compromisso Polinomial (PCS), devido ao baixo custo de compromisso.

Figura 2. Relação entre a rodada de troca e a melhoria do fator

Em 2024, Ingonyama propôsmelhorias para protocolos de Sumcheck baseados em pequenos campos, com foco nos Algoritmos 3 e 4. Essas melhorias foram implementadas e disponibilizadas publicamenteaquiO Algoritmo 4 incorpora o algoritmo de Karatsuba no Algoritmo 3, reduzindo o número de multiplicações de campo de extensão em troca de mais multiplicações de campo base. Esta abordagem é mais eficiente quando as multiplicações de campo de extensão são mais caras do que as de campo base.

1. Impacto das Rondas de Troca e Fatores de Melhoria A otimização do protocolo de verificação de soma em campos pequenos depende da seleção da ronda de troca ideal

𝑡

, que marca quando o protocolo reverte da versão otimizada para o algoritmo ingênuo. Experimentos indicam que o fator de melhoria atinge o pico no ponto de transição ótimo e segue uma tendência parabólica. Quando este ponto é excedido, a eficiência diminui porque a relação entre a multiplicação de campos de base e campos de extensão é maior em campos menores, tornando necessária uma reversão oportuna para o algoritmo ingênuo.

Para certas aplicações, como o Cubic Sumcheck (

𝑑=3

), o protocolo Sumcheck de campo pequeno proporciona uma melhoria de ordem de grandeza em relação à abordagem ingênua. Por exemplo, no campo base

GF[2]2. Impacto do Tamanho do Campo Base no Desempenho Campos base menores (por exemplo,

, O Algoritmo 4 supera o algoritmo ingênuo em quase 30 vezes.

𝐺𝐹[2]

) aumenta significativamente a eficiência do algoritmo otimizado devido à maior disparidade entre os custos de multiplicação do campo de extensão e do campo base. Isso leva a um fator de melhoria mais substancial para o algoritmo otimizado.

1. Ganhos de otimização do Algoritmo de Karatsuba O algoritmo de Karatsuba desempenha um papel crucial na melhoria do desempenho do protocolo de verificação de soma de campo pequeno. Para um campo base de

𝐺𝐹[2]

, O Algoritmo 4 atinge fatores de melhoria máxima de 6 para o Algoritmo 3 e 30 para o Algoritmo 4, indicando que o Algoritmo 4 é cinco vezes mais eficiente que o Algoritmo 3. O algoritmo Karatsuba aprimora a eficiência de tempo de execução e otimiza o ponto de transição para ambos os algoritmos, com pontos ótimos em

𝑡=5

para Algoritmo 3 e

𝑡=8

para o Algoritmo 4.

1. Melhorias na eficiência de memória O protocolo de soma de pequenos campos também aumenta a eficiência de memória. O algoritmo 4 requer

𝑂(𝑑⋅𝑡)

memória, enquanto o Algoritmo 3 precisa

O(2d⋅t)

memória. Para

𝑡=8

O Algoritmo 4 usa apenas 0,26 MB de memória, em comparação com os 67 MB necessários pelo Algoritmo 3. Isso torna o Algoritmo 4 particularmente adequado para ambientes com restrição de memória, como provas do lado do cliente com recursos limitados.

3.4 PCS Otimização: FRI-Binius Reduzindo o Tamanho da Prova de Binius

Um dos principais desafios do protocolo Binius é o seu tamanho de prova relativamente grande, que escala com a raiz quadrada do tamanho da testemunha em

𝑂(𝑁)

. Esta escala de raiz quadrada limita a sua competitividade quando comparada a sistemas que oferecem provas mais sucintas. Em contraste, tamanhos de prova polilogarítmicos, como os alcançados por sistemas avançados como Plonky3 através de técnicas como FRI, são essenciais para garantir verificadores verdadeiramente "sucintos". A otimização FRI-Binius visa reduzir o tamanho da prova de Binius e melhorar o seu desempenho geral em comparação com sistemas mais eficientes.

O papelProvas polilogarítmicas para multilinear em torres binárias, referido como FRI-Binius, introduz um mecanismo de dobragem FRI (Prova Interativa do Oráculo de Reed-Solomon Rápido de Proximidade) baseado em campo binário com quatro inovações-chave:

• Polinómios achatados: transforma o polinómio multilinear inicial numa base de polinómios LCH (altura de código reduzida) para cálculo otimizado.
• Polinómios de Desvanecimento de Subespaço: Utiliza estes polinómios em conjunto com uma Transformação Numérica Teórica aditiva (NTT) para permitir uma decomposição semelhante à FFT, otimizando as operações sobre o campo de coeficientes.
• Embalagem de Base Algébrica: Facilita a compactação eficiente de dados, minimizando a sobrecarga do protocolo relacionada à incorporação.
• Ring-Switching SumCheck: Uma nova otimização SumCheck usando técnicas de comutação de anel para melhorar ainda mais o desempenho.

Processo central do esquema de compromisso polinomial multilinear (PCS) FRI-Binius

O protocolo FRI-Binius otimiza esquemas de compromisso polinomial multilinear (PCS) de campo binário, transformando o polinômio multilinear inicial, definido sobre o campo binário

𝐹2

, em um polinômio multilinear sobre um campo maior

𝐾

.

1. Fase de Compromisso A fase de compromisso transforma um
2. ℓ
3. -polinômio multilinear variável (sobre $\mathbb{F}2
4. )incompreensível para ser empacotado
5. \ell'
6. −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟
7. (\mathbb{F}{2^{128}}$ ). Este processo reduz o número de coeficientes em um fator de 128, permitindo uma geração mais eficiente de provas.
8. Fase de Avaliação Nesta fase, o provador e verificador executam
9. ℓ′
10. rodadas de um protocolo de verificação de soma de comutação em anel cruzado combinado com provas de oráculo interativo de proximidade (IOPP) FRI. Detalhes-chave incluem:
    • Provas de Abertura FRI: Estas constituem a maioria do tamanho da prova e são tratadas de forma semelhante às provas FRI padrão sobre campos grandes.
    • Custo SumCheck do Prover: Comparável ao custo de execução do SumCheck em um campo grande.
    • Custo do FRI do Provedor: Corresponde aos custos padrão do FRI observados em implementações em campos grandes.
    • Operações do Verificador: O verificador recebe 128 elementos de
    • 𝐹2128
    • e realiza 128 multiplicações adicionais, permitindo uma verificação eficiente.

Benefícios do FRI-Binius

Ao aplicar este método, a Binius é capaz de reduzir o tamanho da sua prova em uma ordem de grandeza, aproximando-se do desempenho dos sistemas criptográficos de última geração, enquanto continua compatível com campos binários. O método de dobragem FRI, otimizado para campos binários, combinado com o empacotamento algébrico e as otimizações SumCheck, ajuda a Binius a gerar provas menores sem comprometer a eficiência da verificação.

Esta transformação marca um passo significativo em direção à melhoria do tamanho da prova em Binius, garantindo que ele se torne mais competitivo com outros sistemas de ponta, especialmente aqueles focados em tamanhos de prova polilogarítmicos.

Tabela 2: Comparação do Tamanho da Prova Binius vs. FRI-Binius

Tabela 3: Comparação Plonky3 FRI vs. FRI-Binius

4. Conclusão

A proposta de valor inteira do Binius reside na sua capacidade de utilizar o menor tamanho de campo de potência de dois para testemunhas, selecionando o tamanho do campo conforme necessário. Binius é um esquema de co-design para “protocolos de Sumcheck acelerados por hardware, software e FPGA”, permitindo provas rápidas com uso muito baixo de memória.

Sistemas de prova como o Halo2 e o Plonky3 envolvem quatro etapas principais intensivas em computação: gerar dados de testemunho, comprometer-se com os dados de testemunho, realizar um argumento de desaparecimento e gerar a prova de abertura.

Por exemplo, com a função de hash Keccak em Plonky3 e a função de hash Grøstl em Binius, a distribuição computacional para essas quatro etapas-chave é ilustrada na Figura 3.

Figura 3. Menor Custo de Compromisso

Esta comparação mostra que Binius essencialmente eliminou o gargalo de compromisso do provador. O novo gargalo é o protocolo Sumcheck, onde questões como numerosas avaliações polinomiais e multiplicações de campo podem ser abordadas de forma eficiente com hardware especializado.

O esquema FRI-Binius, uma variante de FRI, oferece uma opção altamente atrativa ao remover a sobrecarga de incorporação da camada de prova do campo sem causar um aumento significativo de custo na camada de prova agregada.

Atualmente, a equipe Irreducible está desenvolvendo sua camada recursiva e temanunciou uma parceria com a equipe Polygon para construir um zkVM baseado em Binius; o Jolt zkVM está a transitar de Lasso para Binius para melhorar o seu desempenho recursivo; e o A equipe Ingonyama está implementando uma versão FPGA do Binius.

Referências

1. 2024.04 Binius Succinct Arguments sobre Torres de Campos Binários
2. Provas polilogarítmicas de Fri-Binius de 2024.07 para multilineares sobre torres binárias
3. 2024.08 Multiplicação de Inteiros em Binius: Abordagem baseada em GKR
4. 2024.06 zkStudyClub - FRI-Binius: Provas polilogarítmicas para multilinear sobre torres binárias
5. 2024.04 ZK11: Binius: um SNARK otimizado por hardware - Jim Posen
6. 2023.12 Episódio 303: Uma Imersão em Binius com Ulvetanna
7. 2024.09 Designing high-performance zkVMs
8. 2024.07 Sumcheck e Open-Binius
9. 2024.04 Binius: provas altamente eficientes sobre campos binários
10. 2023.12 SNARKs em campos binários: Binius - Parte 1
11. 2024.06 SNARKs em campos binários: Binius - Parte 2
12. @espressosys/hyperplonk-a-zk-proof-system-for-zkevms-d45fd077bfba">2022.10 HyperPlonk, um sistema à prova de zk para ZKEVMs

Aviso Legal:

1. Este artigo é reproduzido a partir de [bitlayer]. Todos os direitos autorais pertencem ao autor original [lynndell]. Se houver objeções a esta reimpressão, entre em contato com o Gate Aprenderequipa e eles vão tratar disso prontamente.
2. Isenção de Responsabilidade: As visões e opiniões expressas neste artigo são exclusivamente do autor e não constituem qualquer conselho de investimento.
3. As traduções do artigo para outros idiomas são feitas pela equipe de aprendizagem da gate. Salvo indicação em contrário, é proibido copiar, distribuir ou plagiar os artigos traduzidos.