Análise dos Princípios dos STARKs da Binius e Reflexões sobre a Sua Otimização
1 Introdução
Ao contrário dos SNARKs baseados em curvas elípticas, os STARKs podem ser vistos como SNARKs baseados em hash. Uma das principais razões para a baixa eficiência dos STARKs atualmente é: a maioria dos números em programas reais é relativamente 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, a redução do tamanho do domínio tornou-se uma estratégia chave.
A largura de codificação dos STARKs de 1ª geração é de 252 bits, a 2ª geração é de 64 bits e a 3ª geração é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta um grande desperdício de espaço. Em comparação, o domínio binário permite a manipulação direta de bits, com codificação compacta e eficiente, sem desperdício de espaço, podendo ser considerado como a 4ª geração de STARKs.
Em comparação com as descobertas de novas pesquisas nos últimos anos, como Goldilocks, BabyBear e Mersenne31 em domínios finitos, a pesquisa sobre domínios binários remonta à década de 1980. Atualmente, os domínios binários são amplamente utilizados na criptografia, exemplos típicos incluem:
Padrão de Criptografia Avanç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, baseada no domínio F28, é um algoritmo de hash muito adequado para recursão.
Quando se utiliza um campo menor, a operação de extensão de campo torna-se cada vez mais importante para garantir a segurança. O campo binário utilizado pela Binius depende totalmente da extensão de campo para assegurar 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 campo, operando apenas no campo base, o que permite uma alta eficiência em campos pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam se aprofundar em uma extensão de campo maior para garantir a segurança necessária.
Ao construir um sistema de provas baseado em domínios binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinômio; ao comprometer a árvore Merkle em STARKs, é necessário 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.
Binius propôs uma solução inovadora, abordando essas duas questões separadamente e representando os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariável ( que é especificamente um polinômio multilinhar ) em vez de um polinômio univariável, representando toda a trajetória computacional 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 uma extensão padrão de Reed-Solomon como no caso dos STARKs, mas o hipercubo pode ser considerado como um quadrado ), baseando-se nesse quadrado para realizar a extensão de Reed-Solomon. Este método, ao garantir segurança, melhora significativamente a eficiência da codificação e o desempenho computacional.
2 Análise dos Princípios
A construção da maioria dos sistemas SNARKs atualmente geralmente inclui duas partes:
Prova de Oracle Interativa Polinomial em Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de prova, transforma a relação de cálculo de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP, através da interação com o verificador, permitem que o provador envie polinômios gradualmente, de modo que o verificador possa validar se o cálculo está correto consultando os resultados de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que têm maneiras diferentes de lidar com expressões polinomiais, afetando assim o desempenho e a eficiência do sistema SNARK como um todo.
Esquema de Compromisso Polinomial (Polynomial Commitment Scheme, PCS): O esquema de compromisso polinomial é usado para provar se a igualdade polinomial gerada pelo PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se a um determinado polinômio e verificar posteriormente o resultado da avaliação desse polinômio, enquanto oculta outras informações sobre o polinômio. Os esquemas de compromisso polinomial mais comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS têm diferentes desempenhos, segurança e cenários de aplicação.
De acordo com as necessidades específicas, escolha diferentes PIOP e PCS e combine com um campo finito ou curva elíptica apropriados, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:
• Halo2: combina PLONK PIOP e Bulletproofs PCS, baseado na curva Pasta. O Halo2 foi projetado com foco na escalabilidade e na remoção da configuração confiável no protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão de forma eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao campo 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 a transparência sem uma configuração confiável e se pode suportar funcionalidades expansíveis, como provas recursivas ou provas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + domínio binário. Especificamente, Binius inclui cinco tecnologias-chave para alcançar sua eficiência e segurança. Primeiro, a aritmética baseada em torres de domínio binário (towers of binary fields) forma a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adapta a verificação de produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Terceiro, o protocolo introduz uma nova prova de deslocamento multilinear, otimizando a eficiência na verificação de relações multilineares em pequenos domínios. Quarto, Binius utiliza 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 domínio (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente no domínio binário e reduzindo a sobrecarga geralmente associada a grandes domínios.
( 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários
O domínio binário em torre é a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. O domínio binário suporta essencialmente operações aritméticas altamente eficientes, tornando-o 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 simplificado, ou seja, as operações executadas 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 características hierárquicas através da estrutura em torre, tornam o domínio binário particularmente adequado para sistemas de prova escaláveis como o Binius.
O termo "canonical" refere-se à representação única e direta de elementos no domínio binário. Por exemplo, no domínio binário mais básico F2, qualquer string de k bits pode ser diretamente mapeada para um elemento de domínio binário de k bits. Isso difere do domínio primo, que não pode fornecer essa representação canônica dentro de um número fixo de bits. Embora o domínio primo de 32 bits possa ser contido em 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento do domínio, enquanto o domínio binário possui essa conveniência de mapeamento um-para-um. No domínio primo Fp, métodos comuns de redução incluem a redução de Barrett, a redução de Montgomery, e métodos especiais de redução para domínios finitos específicos como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, métodos de redução comumente usados incluem a redução especial ) como usada no AES ###, a redução de Montgomery ( como usada no POLYVAL ) e a redução recursiva ( como na Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" 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 do 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 do domínio de torre de 64 bits, quatro elementos do domínio de torre de 32 bits, 16 elementos do domínio de torre de 8 bits, ou 128 elementos do domínio F2. Essa flexibilidade de representação não requer qualquer sobrecarga computacional, apenas uma conversão de tipo da string de bits (typecast), que é uma propriedade muito interessante e útil. Ao mesmo tempo, os elementos de domínio pequenos podem ser agrupados em elementos de domínio maiores sem necessidade de sobrecarga 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 da multiplicação, quadratura e inversão em um domínio de torre binário de n bits ( que pode ser decomposto em subdomínios 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 PIOP no protocolo Binius foi inspirado no HyperPlonk, adotando uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos multivariáveis. Estas verificações essenciais incluem:
GateCheck: validar se o testemunho confidencial ω e a entrada pública x satisfazem a relação de operação do circuito C)x,ω###=0, a fim de garantir que o circuito funcione corretamente.
PermutationCheck: Verificar se os resultados da avaliação de dois polinómios multivariados f e g no hipercubo booleano são uma relação de permutação f(x) = f(π)x((, para garantir a consistência da permutação entre as variáveis do polinómio.
LookupCheck: Verificar 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: Verificar se a avaliação de um polinómio racional no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto polinomial.
ZeroCheck: Verificar se um polinómio multivariável em um hipercubo booleano é zero em qualquer ponto ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Verifica se a soma de um polinómio multivariável é igual ao valor declarado ∑x∈Hµ f(x) = s. Ao transformar o problema da avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional para a parte de verificação. Além disso, o SumCheck permite processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam o processamento em lote de múltiplos casos de verificação 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 a Binius e a HyperPlonk tenham muitas semelhanças no design do protocolo, a Binius fez melhorias em 3 áreas a seguir:
ProductCheck otimizado: No HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em todo o hipercubo, e o produto deve ser igual a um valor específico; 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 desse problema, permitindo que o ProductCheck do Binius continuasse a processar mesmo quando o denominador é zero, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação em Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a verificação de permutações entre várias colunas, permitindo que o Binius lide 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 existente PIOPSumCheck, especialmente ao lidar com a validação de polinômios multivariáveis mais complexos, fornecendo um suporte funcional mais robusto. Essas melhorias não apenas resolvem as limitações do HyperPlonk, mas também estabelecem uma base para futuros sistemas de prova baseados em campos binários.
( 2.3 PIOP: novo argumento de mudança multilinear ------ aplicável ao hipercubo booleano
Na protocolo Binius, a construção e manipulação de polinómios virtuais é uma das tecnologias chave, capaz de gerar e operar de forma eficaz os múltiplos derivados de um manipulador de entrada ou de outros polinómios virtuais.
Ver original
Esta página pode conter conteúdo de terceiros, que é fornecido apenas para fins informativos (não para representações/garantias) e não deve ser considerada como um endosso de suas opiniões pela Gate nem como aconselhamento financeiro ou profissional. Consulte a Isenção de responsabilidade para obter detalhes.
Análise dos Princípios dos STARKs da Binius: Inovação no Domínio Binário e Otimização de Desempenho
Análise dos Princípios dos STARKs da Binius e Reflexões sobre a Sua Otimização
1 Introdução
Ao contrário dos SNARKs baseados em curvas elípticas, os STARKs podem ser vistos como SNARKs baseados em hash. Uma das principais razões para a baixa eficiência dos STARKs atualmente é: a maioria dos números em programas reais é relativamente 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, a redução do tamanho do domínio tornou-se uma estratégia chave.
A largura de codificação dos STARKs de 1ª geração é de 252 bits, a 2ª geração é de 64 bits e a 3ª geração é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta um grande desperdício de espaço. Em comparação, o domínio binário permite a manipulação direta de bits, com codificação compacta e eficiente, sem desperdício de espaço, podendo ser considerado como a 4ª geração de STARKs.
Em comparação com as descobertas de novas pesquisas nos últimos anos, como Goldilocks, BabyBear e Mersenne31 em domínios finitos, a pesquisa sobre domínios binários remonta à década de 1980. Atualmente, os domínios binários são amplamente utilizados na criptografia, exemplos típicos incluem:
Quando se utiliza um campo menor, a operação de extensão de campo torna-se cada vez mais importante para garantir a segurança. O campo binário utilizado pela Binius depende totalmente da extensão de campo para assegurar 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 campo, operando apenas no campo base, o que permite uma alta eficiência em campos pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam se aprofundar em uma extensão de campo maior para garantir a segurança necessária.
Ao construir um sistema de provas baseado em domínios binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinômio; ao comprometer a árvore Merkle em STARKs, é necessário 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.
Binius propôs uma solução inovadora, abordando essas duas questões separadamente e representando os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariável ( que é especificamente um polinômio multilinhar ) em vez de um polinômio univariável, representando toda a trajetória computacional 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 uma extensão padrão de Reed-Solomon como no caso dos STARKs, mas o hipercubo pode ser considerado como um quadrado ), baseando-se nesse quadrado para realizar a extensão de Reed-Solomon. Este método, ao garantir segurança, melhora significativamente a eficiência da codificação e o desempenho computacional.
2 Análise dos Princípios
A construção da maioria dos sistemas SNARKs atualmente geralmente inclui duas partes:
Prova de Oracle Interativa Polinomial em Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de prova, transforma a relação de cálculo de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP, através da interação com o verificador, permitem que o provador envie polinômios gradualmente, de modo que o verificador possa validar se o cálculo está correto consultando os resultados de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, que têm maneiras diferentes de lidar com expressões polinomiais, afetando assim o desempenho e a eficiência do sistema SNARK como um todo.
Esquema de Compromisso Polinomial (Polynomial Commitment Scheme, PCS): O esquema de compromisso polinomial é usado para provar se a igualdade polinomial gerada pelo PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se a um determinado polinômio e verificar posteriormente o resultado da avaliação desse polinômio, enquanto oculta outras informações sobre o polinômio. Os esquemas de compromisso polinomial mais comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS têm diferentes desempenhos, segurança e cenários de aplicação.
De acordo com as necessidades específicas, escolha diferentes PIOP e PCS e combine com um campo finito ou curva elíptica apropriados, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:
• Halo2: combina PLONK PIOP e Bulletproofs PCS, baseado na curva Pasta. O Halo2 foi projetado com foco na escalabilidade e na remoção da configuração confiável no protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão de forma eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao campo 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 a transparência sem uma configuração confiável e se pode suportar funcionalidades expansíveis, como provas recursivas ou provas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + domínio binário. Especificamente, Binius inclui cinco tecnologias-chave para alcançar sua eficiência e segurança. Primeiro, a aritmética baseada em torres de domínio binário (towers of binary fields) forma a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adapta a verificação de produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Terceiro, o protocolo introduz uma nova prova de deslocamento multilinear, otimizando a eficiência na verificação de relações multilineares em pequenos domínios. Quarto, Binius utiliza 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 domínio (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente no domínio binário e reduzindo a sobrecarga geralmente associada a grandes domínios.
( 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários
O domínio binário em torre é a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. O domínio binário suporta essencialmente operações aritméticas altamente eficientes, tornando-o 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 simplificado, ou seja, as operações executadas 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 características hierárquicas através da estrutura em torre, tornam o domínio binário particularmente adequado para sistemas de prova escaláveis como o Binius.
O termo "canonical" refere-se à representação única e direta de elementos no domínio binário. Por exemplo, no domínio binário mais básico F2, qualquer string de k bits pode ser diretamente mapeada para um elemento de domínio binário de k bits. Isso difere do domínio primo, que não pode fornecer essa representação canônica dentro de um número fixo de bits. Embora o domínio primo de 32 bits possa ser contido em 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento do domínio, enquanto o domínio binário possui essa conveniência de mapeamento um-para-um. No domínio primo Fp, métodos comuns de redução incluem a redução de Barrett, a redução de Montgomery, e métodos especiais de redução para domínios finitos específicos como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, métodos de redução comumente usados incluem a redução especial ) como usada no AES ###, a redução de Montgomery ( como usada no POLYVAL ) e a redução recursiva ( como na Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" 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 do 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 do domínio de torre de 64 bits, quatro elementos do domínio de torre de 32 bits, 16 elementos do domínio de torre de 8 bits, ou 128 elementos do domínio F2. Essa flexibilidade de representação não requer qualquer sobrecarga computacional, apenas uma conversão de tipo da string de bits (typecast), que é uma propriedade muito interessante e útil. Ao mesmo tempo, os elementos de domínio pequenos podem ser agrupados em elementos de domínio maiores sem necessidade de sobrecarga 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 da multiplicação, quadratura e inversão em um domínio de torre binário de n bits ( que pode ser decomposto em subdomínios 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 PIOP no protocolo Binius foi inspirado no HyperPlonk, adotando uma série de mecanismos de verificação essenciais para validar a correção de polinómios e conjuntos multivariáveis. Estas verificações essenciais incluem:
GateCheck: validar se o testemunho confidencial ω e a entrada pública x satisfazem a relação de operação do circuito C)x,ω###=0, a fim de garantir que o circuito funcione corretamente.
PermutationCheck: Verificar se os resultados da avaliação de dois polinómios multivariados f e g no hipercubo booleano são uma relação de permutação f(x) = f(π)x((, para garantir a consistência da permutação entre as variáveis do polinómio.
LookupCheck: Verificar 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: Verificar se a avaliação de um polinómio racional no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto polinomial.
ZeroCheck: Verificar se um polinómio multivariável em um hipercubo booleano é zero em qualquer ponto ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Verifica se a soma de um polinómio multivariável é igual ao valor declarado ∑x∈Hµ f(x) = s. Ao transformar o problema da avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional para a parte de verificação. Além disso, o SumCheck permite processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam o processamento em lote de múltiplos casos de verificação 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 a Binius e a HyperPlonk tenham muitas semelhanças no design do protocolo, a Binius fez melhorias em 3 áreas a seguir:
ProductCheck otimizado: No HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em todo o hipercubo, e o produto deve ser igual a um valor específico; 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 desse problema, permitindo que o ProductCheck do Binius continuasse a processar mesmo quando o denominador é zero, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação em Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a verificação de permutações entre várias colunas, permitindo que o Binius lide 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 existente PIOPSumCheck, especialmente ao lidar com a validação de polinômios multivariáveis mais complexos, fornecendo um suporte funcional mais robusto. Essas melhorias não apenas resolvem as limitações do HyperPlonk, mas também estabelecem uma base para futuros sistemas de prova baseados em campos binários.
( 2.3 PIOP: novo argumento de mudança multilinear ------ aplicável ao hipercubo booleano
Na protocolo Binius, a construção e manipulação de polinómios virtuais é uma das tecnologias chave, capaz de gerar e operar de forma eficaz os múltiplos derivados de um manipulador de entrada ou de outros polinómios virtuais.