1. Introdução

Distinguidos das SNARKs baseadas em curvas elípticas, STARKs podem ser vistas como SNARKs baseadas 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 laços for, valores booleanos e contadores. No entanto, para garantir a segurança de provas baseadas em árvores de Merkle, a codificação Reed-Solomon é usada para estender dados, resultando em muitos valores redundantes ocupando todo o campo, mesmo quando os valores originais em si são pequenos. Para resolver essa ineficiência, a redução do 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á um espaço significativo desperdiçado. Em contraste, os campos binários permitem manipulação direta a nível de bits, possibilitando uma codificação compacta e eficiente com desperdício mínimo. Essa eficiência é realizada 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 ganhado atenção recentemente, a pesquisa de campos binários remonta aos anos 1980. 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
• 𝐹28
• campo;
• Código de Autenticação de Mensagem Galois (GMAC), baseado no
• 𝐹2128
• campo;
• QR codes, que utilizam codificação Reed-Solomon baseada em
• 𝐹28
• campo;
• Os protocolos originais FRI e zk-STARK, bem como a função hash Grøstl, finalista na competição SHA-3, que é baseada no
• 𝐹28
• campo e é adequado para algoritmos de hash recursivos.

Quando são utilizados 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 pelo 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 de 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 pontos aleatórios 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 de Reed-Solomon.

Binius é uma solução inovadora para resolver esses dois problemas, representando os mesmos dados de duas maneiras diferentes: Primeiro, usando polinômios multivariados (especificamente polinômios multilíneares) em vez de polinômios univariados, representando todo o rastreamento de computação por meio de suas avaliações em "hipercubos". Segundo, uma vez que cada dimensão do hipercubo tem um comprimento de 2, não é possível realizar extensões de Reed-Solomon padrão como em STARKs, mas o hipercubo pode ser tratado como um quadrado e uma extensão de Reed-Solomon pode ser realizada com base nesse quadrado. Esse método não apenas garante segurança, mas também melhora significativamente a eficiência de 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 Informação Teórica: Como o núcleo do sistema de prova, o PIOP transforma relações computacionais da entrada em equações polinomiais verificáveis. Diferentes protocolos PIOP permitem ao provador enviar polinômios incrementalmente por meio de interações com o verificador. Isso permite que o verificador confirme a correção de um cálculo consultando apenas um pequeno número de avaliações polinomiais. Vários protocolos PIOP, como PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, lidam com expressões polinomiais de maneira diferente, afetando o desempenho e a eficiência do sistema SNARK geral.
• Esquema de Compromisso Polinomial (ECP): O ECP é uma ferramenta criptográfica usada para provar que as equações polinomiais geradas pelo PIOP são válidas. Permite que o provador se comprometa com um polinômio e verifique suas avaliações sem revelar informações adicionais sobre o polinômio. Os esquemas comuns de ECP 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 de PIOPs e PCS, e combinando-os com campos finitos ou curvas elípticas adequados, é possível construir sistemas de prova com propriedades distintas. Por exemplo:

• Halo2: Combina PLONK PIOP com Bulletproofs PCS e opera na curva Pasta. O Halo2 é 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 escolhido, o PCS e o campo finito ou curva elíptica é fundamental para garantir a correção, desempenho e 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 em um 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: isso forma a base computacional do Binius, permitindo operações simplificadas dentro do campo binário.
2. Verificações de produto e permutação do produto HyperPlonk: Binius adapta as verificações de produto e permutação do HyperPlonk em seu PIOP para garantir consistência segura e eficiente entre as variáveis e suas permutações.
3. Novo argumento de deslocamento multilinear: Essa otimização melhora a verificação de relacionamentos multilineares dentro de campos pequenos, aumentando a eficiência geral.
4. Argumento de pesquisa Lasso aprimorado: o protocolo incorpora um mecanismo de pesquisa mais flexível e seguro com este argumento avançado.
5. Esquema de Compromisso Polinomial de Campo Pequeno (PCS): Binius utiliza um PCS adaptado para campos pequenos, reduzindo a sobrecarga comumente associada a campos maiores e permitindo um sistema de prova eficiente no campo binário.

Essas inovações permitem que Binius ofereça um sistema SNARK compacto e de alto desempenho, otimizado para campos binários, ao mesmo tempo em que mantém segurança e escalabilidade robustas.

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

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. Campos binários suportam operações aritméticas altamente eficientes, tornando-os ideais para aplicações criptográficas sensíveis ao desempenho. Além disso, 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, os tornam particularmente adequados para sistemas de prova escalonáveis como Binius.

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

,qualquer-bitstream que pode ser diretamente mapeado para um bit binário. Esses diffractômetros de raios-X primários são incompatíveis com o número de bits. Embora 32-bit prime-field-cânfora com 32 bits, not every 32-bit string can unambiguously correspond to a field element, where binary fields provided this one mapping. InferredFieleds

\mathbb{F}_p$, métodos comuns de redução incluem redução de Barrett, 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}$, métodos comuns de redução incluem redução especial (como usado em AES), redução de Montgomery (como usado em POLYVAL) e redução recursiva (como usado 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 os campos binários não requerem propagação de carry na adição ou multiplicação, e o quadrado nos 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. Pode ser vista como um elemento único no campo binário de 128 bits, ou pode ser analisada como dois elementos de campo de torre de 64 bits, quatro elementos de campo de torre de 32 bits, dezesseis elementos de campo de torre de 8 bits ou 128 elementos de

𝐹2

. Essa flexibilidade na representação não incorre em sobrecarga computacional, pois é apenas um tipo de conversão da sequência de bits. Esta é uma propriedade muito interessante e útil, pois elementos de campo menores podem ser empacotados em elementos de campo maiores sem custo computacional adicional. O protocolo Binius aproveita essa propriedade para aprimorar a eficiência computacional. Além disso, o artigoSobre inversão eficiente em campos de torre de característica doisexplora a complexidade computacional da multiplicação, do quadrado e da inversão em

𝑛

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

m

subcampos de bits).

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

O design PIOP no protocolo Binius se inspira no HyperPlonk e incorpora uma série de verificações principais para verificar a correção de polinômios e conjuntos multivariados. Essas verificações são essenciais para garantir a integridade dos cálculos dentro do sistema de prova, especialmente ao operar em campos binários. As verificações-chave 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. C(x,ω) = 0
7. , verificando a execução correta do circuito.
8. PermutationCheck: Verifica se os resultados de avaliação de dois polinômios multivariáveis
9. 𝑓
10. e
11. 𝑔
12. no hipercubo booleano formam 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, isto é,
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 conjuntos diferentes.
19. ProductCheck: Garante que a avaliação de um polinômio racional no hiperplano 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 multivariado avalia-se como zero em algum ponto no hipercubo 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, reduz a complexidade computacional do verificador. O SumCheck também permite o agrupamento, que constrói combinações lineares usando números aleatórios para processar em lote várias instâncias.
30. BatchCheck: Uma extensão do SumCheck, verifica a correção de várias avaliações de polinômios multivariados, 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. Otimização do ProductCheck: No HyperPlonk, o ProductCheck requer o denominador
2. 𝑈
3. ser não nulo em todo o hipercubo e que o produto corresponda a um valor específico. Binius simplifica essa 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 efetivamente os problemas de divisão por zero, tornando desafiador garantir que
5. 𝑈
6. permanece não nulo sobre o hipercubo. Binius resolve isso lidando adequadamente com 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 lacks support for cross-column permutation checks. Binius addresses this limitation by introducing support for cross-column PermutationCheck, enabling the protocol to manage more complex polynomial permutations across multiple columns.

Assim, Binius melhora a flexibilidade e eficiência do protocolo ao aprimorar o mecanismo de verificação PIOP SumCheck existente, especialmente ao fornecer uma funcionalidade mais forte para verificar polinômios multivariados mais complexos. Essas melhorias não apenas abordam as limitações do HyperPlonk, mas também estabelecem a base para sistemas à prova de futuros 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 capacitação da manipulação eficiente de polinômios. Duas técnicas principais são empregadas para essas operações:

• Packing :O método de embalagem otimiza o manuseio de elementos menores, agrupando-os em um domínio maior. Especificamente, os elementos adjacentes em ordem lexicográfica são agrupados em blocos maiores, geralmente de tamanho
• 2𝜅
• . Ao aproveitar a Extensão Multilinear (MLE), os elementos empacotados 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 hiperplano booleano reestruturando a função
• 𝑡
• em uma 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 se aplica a blocos de tamanho
• 2𝑏
• , garantindo que todos os elementos em um bloco sejam deslocados uniformemente de acordo com o deslocamento predefinido. Este operador é particularmente útil ao lidar com polinômios virtuais em espaços de alta dimensão, pois sua complexidade aumenta linearmente com o tamanho do bloco, tornando-o uma técnica ideal para conjuntos de dados grandes ou cálculos complexos de hipercubo booleano.

2.4 PIOP: Um Argumento de Pesquisa de 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

𝑡∈𝐹𝑛

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

• Eficiência de prova: ao conduzir
• 𝑚
• consultas em uma tabela de tamanho
• 𝑛
• , o provador só precisa se comprometer com
• 𝑚+𝑛
• pequenos elementos de campo, com o tamanho do campo extraído do conjunto
• 0,…,𝑚
• . Em esquemas criptográficos que dependem de exponenciação, o custo do provador é
• O(m+n)
• operações em grupo (por exemplo, adições de pontos em curvas elípticas). Essa eficiência é adicionada ao 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 tabela
• 𝑡
• é estruturado, o Lasso não requer um compromisso direto com a tabela, 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⋅c⋅m+c⋅n1/c
• elementos de campo comprometidos. Esses 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 grandes tabelas: O protocolo Lasso combina polinômios virtuais para permitir pesquisas eficientes e operações em grandes tabelas, garantindo escalabilidade sem degradação de desempenho.
2. Pequena Pesquisa de Tabela : No coração do Lasso está a pequena pesquisa de tabela, 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 vários sets: O protocolo também incorpora um mecanismo virtual para executar verificações de vários sets, garantindo que dois conjuntos de elementos correspondam ou cumpram condições predefinidas.

O protocolo Binius adapta Lasso para operações de campo binário, assumindo que o campo atual é um campo primo de grande característica (muito maior do que o comprimento da coluna que está sendo pesquisada). Binius introduz uma versão multiplicativa do protocolo Lasso, exigindo que o provador e verificador incrementem a operação de "contador de memória" do protocolo não simplesmente adicionando 1, mas incrementando usando um gerador multiplicativo dentro do campo binário. No entanto, essa adaptação multiplicativa introduz complexidade adicional: ao contrário de um incremento aditivo, o gerador multiplicativo não incrementa em todos os casos, 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 contador de leitura 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 (Esquema de Compromisso Polinomial) é a compactação. O artigo Binius apresenta dois esquemas Brakedown PCS baseados em campos binários: um instanciado usando códigos concatenados, e outro usando codificação a 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 equilíbrio vale a pena devido aos benefícios de simplificação e implementação que oferece.

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

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

K

, com avaliações ocorrendo em um campo estendido

𝐿/𝐾

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

𝑡(𝑋0,…,𝑋ℓ−1)

pertence ao domínio

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

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

𝐿

. Essa estrutura de compromisso permite consultas eficientes dentro do campo estendido, equilibrando segurança e eficiência computacional.

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

𝐾

, sua dimensão

ℓ

, e o código de bloco linear associado

𝐶

, garantindo ao mesmo tempo que o campo estendido

𝐿

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

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

,𝑡ℎ𝑒𝐵𝑖𝑛𝑖𝑢𝑠𝑝𝑟𝑜𝑡𝑜𝑐𝑜𝑙𝑒𝑚𝑝𝑙𝑜𝑦𝑠𝑏𝑙𝑜𝑐𝑘−𝑙𝑒𝑣𝑒𝑙𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑢𝑠𝑖𝑛𝑔𝑅𝑒𝑒𝑑−𝑆𝑜𝑙𝑜𝑚𝑜𝑛𝑐𝑜𝑑𝑒𝑠.𝑇ℎ𝑖𝑠𝑠𝑐ℎ𝑒𝑚𝑒𝑎𝑙𝑙𝑜𝑤𝑠𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑜𝑓𝑠𝑚𝑎𝑙𝑙−𝑓𝑖𝑒𝑙𝑑𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙𝑠𝑏𝑦𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑡ℎ𝑒𝑚𝑟𝑜𝑤−𝑏𝑦−𝑟𝑜𝑤𝑖𝑛𝑡𝑜𝑙𝑎𝑟𝑔𝑒𝑟𝑓𝑖𝑒𝑙𝑑𝑠(𝑠𝑢𝑐ℎ𝑎𝑠

\mathbb{F}{2^{16}}$ ), utilizando a eficiência e propriedades de distância máxima separável dos códigos de Reed-Solomon. Após a codificação, essas linhas são comprometidas usando uma árvore de Merkle, o que simplifica a complexidade operacional dos compromissos polinomiais de pequenos campos. Essa abordagem permite o manuseio eficiente de polinômios em campos pequenos sem o ônus computacional geralmente associado a campos maiores.

3. Otimizações Binius

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

1. PIOP baseado em GKR: O protocolo GKR (Goldreich-Kalai-Rothblum) é usado para substituir o algoritmo de pesquisa Lasso na multiplicação de campo binário, reduzindo significativamente a sobrecarga no processo de compromisso.
2. ZeroCheck PIOP Otimização: Esta otimização aborda o equilíbrio entre os custos computacionais do Prover e do Verificador, 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 campo pequeno, a Binius reduz a carga computacional geral ao operar sobre campos pequenos.
4. Otimização PCS: Usando a otimização FRI-Binius (Provas Interativas do Oráculo de Reed-Solomon Rápidas de Proximidade de Binius), o Binius reduz o tamanho da prova e melhora o desempenho do protocolo, melhorando a eficiência geral tanto na geração quanto na verificação da prova.

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

No protocolo original do Binius, a multiplicação de campos binários é tratada por meio de um esquema baseado em pesquisa, que vincula a multiplicação a operações de adição linear com base no número de membros em uma palavra. Embora esse método otimize a multiplicação binária em certa medida, ele 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 campos binários.

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

𝐹

. Cada nó neste circuito tem duas entradas para calcular a função necessária. Para reduzir a complexidade computacional do Verificador, o protocolo emprega o protocolo SumCheck, que reduz progressivamente as declarações sobre os valores da porta de saída do circuito para valores de porta de camada mais baixa, eventualmente simplificando as declarações para declarações sobre as entradas. Dessa forma, o Verificador só precisa verificar a exatidã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

Um

e

𝐵

satisfazer

A⋅B=?C

em verificar se

(𝑔𝐴)𝐵=?𝑔𝐶

mantém em

𝐹264∗

Esta transformação, combinada com o protocolo GKR, reduz significativamente as sobrecargas associadas a compromissos de polinômios. Comparado ao esquema anterior baseado em pesquisa de Binius, 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 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 de polinômios de campo binário à medida que as otimizações do Binius avançam.

3.2 Otimização do ZeroCheck PIOP: Equilibrando os Custos Computacionais entre o Provador e o Verificador

O papel Algumas melhorias para o PIOP para ZeroCheckpropõe estratégias para equilibrar os custos computacionais entre o Provador (P) e o Verificador (V), com foco na redução da transmissão de dados e na complexidade computacional. Abaixo estão as principais técnicas 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 Prover envia

𝑣𝑖+1(𝑋)

durante

X=0,...,d+1

, e o Verificador verifica se

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

mantém.

Otimização: O Prover pode evitar enviar

𝑣𝑖+1(1)

, como o Verificador pode calcular isso 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 custos de transmissão para

d2n−1CF+(d+1)2n−1CG

.

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

Durante a rodada

𝑖

, o Prover 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))

.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜

\alpha

𝑎𝑛𝑑

r

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

v_i’(X)

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

v_i(X)

, reduzindo os pontos de avaliação exigidos.O controlo inter-round podeentão ser simplificado como

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

𝑡ℎ𝑒𝑟𝑒𝑏𝑦𝑙𝑜𝑤𝑒𝑟𝑖𝑛𝑔𝑑𝑎𝑡𝑎𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑠𝑠𝑖𝑜𝑛𝑛𝑒𝑒𝑑𝑠𝑎𝑛𝑑𝑒𝑛ℎ𝑎𝑛𝑐𝑖𝑛𝑔𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦.𝑊𝑖𝑡ℎ𝑡ℎ𝑒𝑠𝑒𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑚𝑒𝑛𝑡𝑠,𝑡ℎ𝑒𝑜𝑣𝑒𝑟𝑎𝑙𝑙𝑐𝑜𝑠𝑡𝑖𝑠𝑎𝑝𝑝𝑟𝑜𝑥𝑖𝑚𝑎𝑡𝑒𝑙𝑦

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

𝐹𝑜𝑟

d = 3$ , estas otimizações resultam numa redução de custos por um fator de 5/3.

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

Para um Prover honesto, o polinômio

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

é zero em

𝐻𝑛

e pode ser expresso como

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

. Onde

𝑄𝑖

é computado através da divisão polinomial ordenada, começando a partir de

𝑅𝑛=𝐶

. Divisão sequencial por

𝑥𝑖(𝑥𝑖−1)

calcula

𝑄𝑖

e

𝑅𝑖

, com

𝑅0

representando a extensão multilinear de

𝐶

em

𝐻𝑛

, assumido como zero.

Analisando os Graus de

𝑄𝑖

. Para

𝑗>𝑖

,

𝑄𝑗

mantém o mesmo grau em

𝑥𝑖

como

𝐶

. Para

𝑗=𝑖

, o grau é reduzido em 2 e para

J

, 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

𝑥∈𝐻𝑛−𝑖−1

, pode ser representado como

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

Assim, a cada rodada do protocolo, um novo

𝑄

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

𝐶

e o anterior

𝑄

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

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

No protocolo STARKs implementado por Binius, o gargalo principal para o provador muitas vezes é o protocolo de verificação de soma em vez do Polynomial Commitment Scheme (PCS), devido ao baixo custo de comprometimento.

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, focando nos Algoritmos 3 e 4. Essas melhorias foram implementadas e disponibilizadas publicamente aqui. O Algoritmo 4 incorpora o algoritmo 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. Essa 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 rodadas de troca e fatores de melhoria Otimização do protocolo de verificação de soma de campo pequeno depende da seleção da rodada 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 ideal e depois segue uma tendência parabólica. Quando esse ponto é excedido, a eficiência diminui porque a proporção entre multiplicações de campo base e campo de extensão é maior em campos menores, exigindo uma reversão oportuna para o algoritmo ingênuo.

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

𝑑=3

) O protocolo de verificação de soma de campo pequeno oferece uma melhoria de ordem de magnitude em relação à abordagem ingênua. Por exemplo, no campo base

𝐺𝐹[2]2. Impact of Base Field Size on Performance Smaller base fields (e.g.,

, O Algoritmo 4 é quase 30 vezes mais eficiente do que o algoritmo ingênuo.

𝐺𝐹[2]

) melhoram significativamente a eficiência do algoritmo otimizado devido à maior disparidade entre os custos das multiplicações do campo de extensão e do campo base. Isso resulta em 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 alcança 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 melhora 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 o Algoritmo 3 e

t = 8

para o Algoritmo 4.

1. Melhorias de Eficiência de Memória O protocolo Sumcheck de campo pequeno também aumenta a eficiência de memória. O Algoritmo 4 requer

𝑂(𝑑⋅𝑡)

memória, enquanto o Algoritmo 3 precisa

𝑂(2𝑑⋅𝑡)

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 prova do lado do cliente com recursos limitados.

3.4 Otimização PCS: FRI-Binius Redução do Tamanho da Prova 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

𝑂(𝑁)

. Esse dimensionamento de raiz quadrada limita sua competitividade quando comparado a sistemas que oferecem provas mais sucintas. Em contraste, tamanhos de prova polilogarítmica, como alcançado 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 Binius e melhorar seu desempenho geral em comparação com sistemas mais eficientes.

O papel Provas polilogarítmicas para multilineares sobre torres binárias, referido como FRI-Binius, introduz um novo mecanismo de dobramento 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 em uma base de polinômio de altura de código baixo (LCH) para cálculos otimizados.
• Polinômios de Desaparecimento do Subespaço: Utiliza esses polinômios em conjunto com uma transformada numérica teórica aditiva (NTT) para permitir a decomposição semelhante à FFT, otimizando as operações sobre o campo de coeficientes.
• Empacotamento de Base Algébrica: Facilita o empacotamento eficiente de dados, minimizando a sobrecarga do protocolo relacionada à incorporação.
• Ring-Switching SumCheck: Uma nova otimização SumCheck usando técnicas de troca de anel para melhorar ainda mais o desempenho.

Processo principal do Esquema de Compromisso Polinomial Multilinear (PCS) FRI-Binius

O protocolo FRI-Binius otimiza os esquemas de compromisso polinomial multilinear (PCS) em campos binários, 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. )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑
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 de prova mais eficiente.
8. Fase de Avaliação Nesta fase, o provador e o verificador executam
9. ℓ′
10. rodadas de um protocolo de verificação de soma em anel cruzado combinado com provas de proximidade do oráculo interativo FRI (IOPP). Detalhes importantes 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 do Prover's SumCheck: Comparável ao custo de executar o SumCheck em um campo grande.
    • Custo FRI do Prover: Corresponde aos custos FRI padrão vistos em implementações de grande campo.
    • 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 consegue reduzir o tamanho da sua prova em uma ordem de magnitude, aproximando-se do desempenho dos sistemas criptográficos mais avançados, mantendo-se compatível com campos binários. O método de dobragem FRI, otimizado para campos binários, combinado com empacotamento algébrico e otimizações SumCheck, ajuda a Binius a gerar provas menores sem comprometer a eficiência de verificação.

Essa 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 integral do Binius reside em sua capacidade de usar o menor tamanho de campo de potência de dois para testemunhas, selecionando o tamanho do campo conforme necessário. O Binius é um esquema de co-design para "protocolos de verificação de soma acelerados por hardware, software e FPGA", permitindo provas rápidas com uso muito baixo de memória.

Sistemas de prova como Halo2 e Plonky3 envolvem quatro etapas-chave com intensidade computacional: gerar dados de testemunha, comprometer-se com os dados de testemunha, realizar um argumento de desaparecimento e gerar a prova de abertura.

Por exemplo, com a função hash Keccak em Plonky3 e a função 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 a Binius praticamente eliminou o gargalo do compromisso do provador. O novo gargalo é o protocolo Sumcheck, onde questões como inúmeras avaliações de polinômios e multiplicações de campo podem ser eficientemente abordadas 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 de campo sem causar um aumento significativo de custo na camada de prova agregada.

Atualmente, a equipe do Irredutible está desenvolvendo sua camada recursiva e tem anunciou uma parceria com a equipe da Polygon para construir um zkVM baseado em Binius; o Jolt zkVM está fazendo a transição do Lasso para o Binius para melhorar seu desempenho recursivo; e o A equipe Ingonyama está implementando uma versão FPGA do Binius.

Referências

1. 2024.04 Binius Argumentos Sucintos sobre Torres de Campos Binários
2. 2024.07 Sexta-feira-Binius Provas Polilogarítmicas 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 multilineares em torres binárias
5. 2024.04 ZK11: Binius: um SNARK otimizado para hardware - Jim Posen
6. 2023.12 Episódio 303: Uma Profundidade em Binius com Ulvetanna
7. 2024.09 Projetando zkVMs de alto desempenho
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-um-sistema-de-prova-zk-para-zkevms-d45fd077bfba">2022.10 HyperPlonk, um sistema de prova zk para ZKEVMs

Aviso Legal：

1. Este artigo é republicado da [ bitlayer]. Todos os direitos autorais pertencem ao autor original [lynndell]. Se houver objeções a esta reimpressão, entre em contato com o Gate Learnequipe e eles lidarão com isso prontamente.
2. Isenção de responsabilidade: Os pontos de vista e opiniões expressos 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 gate Learn. Salvo indicação em contrário, é proibido copiar, distribuir ou plagiar os artigos traduzidos.