Análise dos princípios dos STARKs da Binius e reflexões sobre a sua otimização
1 Introdução
Uma das principais razões para a ineficiência dos STARKs é que a maioria dos valores nos 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 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 um grande espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, com uma codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs da 4ª geração.
Comparado com os domínios finitos descobertos em pesquisas recentes como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre domínios binários remonta à década de 1980. Atualmente, os domínios binários já são amplamente utilizados na criptografia, exemplos típicos incluem:
Padrão de Criptografia Avançada (AES), baseado no domínio F28
QR Code, utilizando codificação Reed-Solomon baseada em F28
Protocólos FRI originais e zk-STARK, bem como a função de hash Grøstl que chegou à final do SHA-3, que é baseada no domínio F28, é um algoritmo de hash muito adequado para recursão.
Quando se utiliza um domínio menor, 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 pelo Binius depende totalmente da extensão de domínio para garantir sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não precisa entrar na extensão de domínio, mas apenas operar no domínio base, alcançando assim alta eficiência em um domínio pequeno. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam ser aprofundados em uma extensão de domínio maior para garantir a segurança necessária.
Ao construir sistemas de prova baseados em domínios binários, existem 2 problemas práticos: ao calcular a representação de traços 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 fazer 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 apresentou uma solução inovadora que trata separadamente esses dois problemas e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariáveis (, especificamente polinômios multilineares ), em vez de polinômios univariados, representando toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, devido ao comprimento de cada dimensão do hipercubo ser 2, não é possível realizar a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser considerado como um quadrado ), permitindo a extensão de Reed-Solomon baseada nesse quadrado. Este método, enquanto garante segurança, melhora significativamente a eficiência de 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 Oracle Interativa Polinomial Baseada em Teoria da Informação (, PIOP): O PIOP, como o núcleo do sistema de prova, transforma a relação computacional de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente, interagindo com o verificador, de modo que o verificador possa validar 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: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes abordagens para o tratamento de expressões polinomiais, o que impacta 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 as igualdades polinomiais geradas pelo PIOP são válidas. O PCS é uma ferramenta criptográfica através da qual o provador pode se comprometer com um determinado polinômio e, posteriormente, verificar o resultado da avaliação desse polinômio, enquanto oculta outras informações do polinômio. Os esquemas de compromisso polinomial mais comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS possuem diferentes desempenhos, segurança e cenários de aplicação.
De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um campo finito ou curva elíptica apropriada, para construir sistemas de prova com diferentes atributos. Por exemplo:
• Halo2: combina PLONK PIOP e 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: combina PLONK PIOP com FRI PCS, baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS selecionadas devem corresponder ao corpo finito ou à curva elíptica utilizada, a fim de garantir a correção, o desempenho e a segurança do sistema. A escolha dessas combinações não apenas afeta o tamanho da prova e a eficiência da verificação do SNARK, mas também determina se o sistema pode alcançar transparência sem uma configuração confiável e se pode suportar funções expandidas como provas recursivas ou provas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + campos 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 campos binários (towers of binary fields) constitui a base de seus cálculos, permitindo operações simplificadas dentro do campo binário. Em segundo lugar, Binius adaptou a verificação de produto e permutação 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. Em terceiro lugar, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência na verificação de relações multilineares em pequenos campos. 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 utiliza um esquema de compromisso polinomial de pequeno campo (Small-Field PCS), permitindo um sistema de prova eficiente no campo binário e reduzindo a sobrecarga normalmente associada a grandes campos.
( 2.1 Domínios finitos: aritmética baseada em torres de campos binários
Os domínios binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, devido principalmente a dois aspectos: cálculo eficiente e aritmética eficiente. Os domínios binários suportam 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 domínio binário suporta um processo de aritmética simplificada, ou seja, as operações realizadas no domínio binário podem ser representadas de 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 domínios binários particularmente adequados para sistemas de prova escaláveis, como o Binius.
O termo "canônico" refere-se à representação única e direta de elementos no domínio binário. Por exemplo, no domínio binário F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de domínio binário de k bits. Isso é diferente dos domínios primos, que não conseguem fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa caber dentro de 32 bits, nem toda string de 32 bits pode corresponder exclusivamente 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 de Barrett, a redução de Montgomery e métodos de redução especiais para domínios finitos específicos, como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, métodos de redução comuns incluem a redução especial ), como usada no AES ###, a redução de Montgomery (, como usada no POLYVAL ), e a redução recursiva (, como a Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa que, no domínio binário, tanto a adição quanto a multiplicação não requerem o transporte, e 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 string de 128 bits: essa string pode ser interpretada de várias maneiras no contexto de um domínio binário. Ela pode ser vista como um elemento único no domínio binário de 128 bits, ou ser analisada 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 8 bits, ou 128 elementos do 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), o 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 aproveita essa 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 de multiplicação, quadrado e operação 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 inspira-se no HyperPlonk e utiliza uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos de múltiplas variáveis. Essas verificações essenciais incluem:
GateCheck: Verifica se a testemunha secreta ω 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.
PermutationCheck: Verificar se os resultados da avaliação de dois polinómios multivariáveis f e g no hipercubo booleano formam uma relação de permutação f(x) = f(π)x((, para garantir a consistência da permutação entre as variáveis polinomiais.
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 estejam dentro do intervalo especificado.
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 múltiplos conjuntos.
ProductCheck: Verifica se a avaliação de um polinómio racional no hipercubo de Booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto polinomial.
ZeroCheck: Verificar se um polinómio multivariável é zero em qualquer ponto do hipercubo booleano ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Verifica se a soma de um polinómio multivariável é igual ao valor declarado ∑x∈Hµ f(x) = s. Ao transformar o problema de avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional do verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que permitem a verificação em lote de múltiplas instâncias de soma.
BatchCheck: baseado no SumCheck, verifica a correção da avaliação de múltiplos polinómios multivariáveis, para aumentar a eficiência do protocolo.
Embora o Binius e o HyperPlonk tenham muitas semelhanças no design do protocolo, o Binius fez melhorias nas seguintes 3 áreas:
ProductCheck otimizado: No HyperPlonk, o ProductCheck exige que o denominador U seja diferente de zero em toda a hipercubo, e o produto deve ser igual a um valor específico; 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 é diferente de zero no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, 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, o que permite ao Binius lidar com situações de arranjo polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente, especialmente ao lidar com a verificação de polinómios multivariados mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em campos binários.
( 2.3 PIOP: novo argumento de deslocamento multilinhar------aplicável ao hipercubo booleano
No protocolo Binius, múltiplos virtuais
Ver original
Esta página pode conter conteúdos de terceiros, que são fornecidos apenas para fins informativos (sem representações/garantias) e não devem ser considerados como uma aprovação dos seus pontos de vista pela Gate, nem como aconselhamento financeiro ou profissional. Consulte a Declaração de exoneração de responsabilidade para obter mais informações.
6 gostos
Recompensa
6
3
Partilhar
Comentar
0/400
ETHReserveBank
· 23h atrás
na cadeia o custo caiu, quem não ficaria feliz?
Ver originalResponder0
ChainChef
· 07-31 16:01
a cozinhar alguma alpha fresca aqui... binius parece um molho perfeitamente reduzido comparado a essas receitas de 252 bits inchadas, para ser honesto
Binius: Otimização revolucionária dos STARKs de domínio binário
Análise dos princípios dos STARKs da Binius e reflexões sobre a sua otimização
1 Introdução
Uma das principais razões para a ineficiência dos STARKs é que a maioria dos valores nos 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 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 um grande espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, com uma codificação compacta e eficiente, sem qualquer espaço desperdiçado, ou seja, os STARKs da 4ª geração.
Tabela 1: Caminhos de Derivação STARKs
| Álgebra | Largura do código | Exemplo | |------|----------|------| | 1ª geração | 252bit | Ethereum STARKs | | 2ª Geração | 64bit | Plonky2 | | 3ª geração | 32 bits | BabyBear | | 4ª geração | 1bit | Binius |
Comparado com os domínios finitos descobertos em pesquisas recentes como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre domínios binários remonta à década de 1980. Atualmente, os domínios binários já são amplamente utilizados na criptografia, exemplos típicos incluem:
Quando se utiliza um domínio menor, 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 pelo Binius depende totalmente da extensão de domínio para garantir sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não precisa entrar na extensão de domínio, mas apenas operar no domínio base, alcançando assim alta eficiência em um domínio pequeno. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam ser aprofundados em uma extensão de domínio maior para garantir a segurança necessária.
Ao construir sistemas de prova baseados em domínios binários, existem 2 problemas práticos: ao calcular a representação de traços 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 fazer 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 apresentou uma solução inovadora que trata separadamente esses dois problemas e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariáveis (, especificamente polinômios multilineares ), em vez de polinômios univariados, representando toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, devido ao comprimento de cada dimensão do hipercubo ser 2, não é possível realizar a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser considerado como um quadrado ), permitindo a extensão de Reed-Solomon baseada nesse quadrado. Este método, enquanto garante segurança, melhora significativamente a eficiência de 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 Oracle Interativa Polinomial Baseada em Teoria da Informação (, PIOP): O PIOP, como o núcleo do sistema de prova, transforma a relação computacional de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente, interagindo com o verificador, de modo que o verificador possa validar 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: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes abordagens para o tratamento de expressões polinomiais, o que impacta 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 as igualdades polinomiais geradas pelo PIOP são válidas. O PCS é uma ferramenta criptográfica através da qual o provador pode se comprometer com um determinado polinômio e, posteriormente, verificar o resultado da avaliação desse polinômio, enquanto oculta outras informações do polinômio. Os esquemas de compromisso polinomial mais comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS possuem diferentes desempenhos, segurança e cenários de aplicação.
De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um campo finito ou curva elíptica apropriada, para construir sistemas de prova com diferentes atributos. Por exemplo:
• Halo2: combina PLONK PIOP e 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: combina PLONK PIOP com FRI PCS, baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS selecionadas devem corresponder ao corpo finito ou à curva elíptica utilizada, a fim de garantir a correção, o desempenho e a segurança do sistema. A escolha dessas combinações não apenas afeta o tamanho da prova e a eficiência da verificação do SNARK, mas também determina se o sistema pode alcançar transparência sem uma configuração confiável e se pode suportar funções expandidas como provas recursivas ou provas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + campos 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 campos binários (towers of binary fields) constitui a base de seus cálculos, permitindo operações simplificadas dentro do campo binário. Em segundo lugar, Binius adaptou a verificação de produto e permutação 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. Em terceiro lugar, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência na verificação de relações multilineares em pequenos campos. 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 utiliza um esquema de compromisso polinomial de pequeno campo (Small-Field PCS), permitindo um sistema de prova eficiente no campo binário e reduzindo a sobrecarga normalmente associada a grandes campos.
( 2.1 Domínios finitos: aritmética baseada em torres de campos binários
Os domínios binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, devido principalmente a dois aspectos: cálculo eficiente e aritmética eficiente. Os domínios binários suportam 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 domínio binário suporta um processo de aritmética simplificada, ou seja, as operações realizadas no domínio binário podem ser representadas de 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 domínios binários particularmente adequados para sistemas de prova escaláveis, como o Binius.
O termo "canônico" refere-se à representação única e direta de elementos no domínio binário. Por exemplo, no domínio binário F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de domínio binário de k bits. Isso é diferente dos domínios primos, que não conseguem fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa caber dentro de 32 bits, nem toda string de 32 bits pode corresponder exclusivamente 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 de Barrett, a redução de Montgomery e métodos de redução especiais para domínios finitos específicos, como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, métodos de redução comuns incluem a redução especial ), como usada no AES ###, a redução de Montgomery (, como usada no POLYVAL ), e a redução recursiva (, como a Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa que, no domínio binário, tanto a adição quanto a multiplicação não requerem o transporte, e 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 string de 128 bits: essa string pode ser interpretada de várias maneiras no contexto de um domínio binário. Ela pode ser vista como um elemento único no domínio binário de 128 bits, ou ser analisada 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 8 bits, ou 128 elementos do 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), o 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 aproveita essa 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 de multiplicação, quadrado e operação 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 inspira-se no HyperPlonk e utiliza uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos de múltiplas variáveis. Essas verificações essenciais incluem:
GateCheck: Verifica se a testemunha secreta ω 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.
PermutationCheck: Verificar se os resultados da avaliação de dois polinómios multivariáveis f e g no hipercubo booleano formam uma relação de permutação f(x) = f(π)x((, para garantir a consistência da permutação entre as variáveis polinomiais.
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 estejam dentro do intervalo especificado.
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 múltiplos conjuntos.
ProductCheck: Verifica se a avaliação de um polinómio racional no hipercubo de Booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto polinomial.
ZeroCheck: Verificar se um polinómio multivariável é zero em qualquer ponto do hipercubo booleano ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Verifica se a soma de um polinómio multivariável é igual ao valor declarado ∑x∈Hµ f(x) = s. Ao transformar o problema de avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional do verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que permitem a verificação em lote de múltiplas instâncias de soma.
BatchCheck: baseado no SumCheck, verifica a correção da avaliação de múltiplos polinómios multivariáveis, para aumentar a eficiência do protocolo.
Embora o Binius e o HyperPlonk tenham muitas semelhanças no design do protocolo, o Binius fez melhorias nas seguintes 3 áreas:
ProductCheck otimizado: No HyperPlonk, o ProductCheck exige que o denominador U seja diferente de zero em toda a hipercubo, e o produto deve ser igual a um valor específico; 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 é diferente de zero no hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, 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, o que permite ao Binius lidar com situações de arranjo polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente, especialmente ao lidar com a verificação de polinómios multivariados mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em campos binários.
( 2.3 PIOP: novo argumento de deslocamento multilinhar------aplicável ao hipercubo booleano
No protocolo Binius, múltiplos virtuais