Análise dos Princípios dos STARKs da Binius e Reflexões sobre a Otimização
1 Introdução
Uma das principais razões para a baixa eficiência dos STARKs é que a maioria dos valores em programas reais é bastante pequena, como os í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 crucial.
Como mostrado na Tabela 1, a largura de codificação dos STARKs de primeira geração é de 252 bits, a largura de codificação dos STARKs de segunda geração é de 64 bits, e a largura de codificação dos STARKs de terceira 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 codificação compacta e eficiente, sem qualquer desperdício de espaço, ou seja, os STARKs de quarta geração.
Comparado com as novas descobertas de domínios finitos, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre domínios binários remonta à década de 80 do século passado. Atualmente, os domínios binários já estão amplamente aplicados na criptografia, exemplos típicos incluem:
Padrão de Criptografia Avançada (AES), baseado no domínio F28;
Galois Message Authentication Code ( GMAC ), baseado no campo F2128;
Código QR, utilizando codificação Reed-Solomon baseada em F28;
Protocólos FRI originais e zk-STARK, assim 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 utilizam domínios menores, a operação de extensão de domínio torna-se cada vez mais importante para garantir a segurança. E o domínio binário utilizado pela Binius depende completamente da extensão de domínio para assegurar a 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, operando apenas no domínio base, o que permite uma alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam aprofundar-se em um domínio de extensão maior para garantir a segurança necessária.
Ao construir sistemas de prova com base em domínios binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinómio; ao comprometer a árvore 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 para tratar esses dois problemas, representando os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariáveis (, especificamente polinômios multilineares ), em vez de polinômios univariáveis, para representar toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, como cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas podemos considerar o hipercubo como um quadrado ), baseado no qual podemos realizar a extensão de Reed-Solomon. Este método, ao garantir a 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:
Informação Teórica de Provas Interativas de Oracle Polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de provas, transforma a relação computacional 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 pequeno número de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, cada um com diferentes maneiras de tratar expressões polinomiais, afetando assim o desempenho e a eficiência de todo o sistema SNARK.
Esquema de Compromisso Polinomial (Polynomial Commitment Scheme, PCS): O esquema de compromisso polinomial é utilizado para provar se uma equação polinomial gerada por PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se a um determinado polinómio e, posteriormente, verificar os resultados 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 apropriada, podendo 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 de confiança do protocolo ZCash.
Plonky2: Adota PLONK PIOP e FRI PCS combinados, e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao domínio finito ou curva elíptica utilizados, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não só afeta o tamanho da prova SNARK e a eficiência da verificação, mas também determina se o sistema pode alcançar transparência sem a necessidade de configuração confiável, e se pode suportar funcionalidades expandidas como provas recursivas ou provas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + domínios binários. Especificamente, Binius inclui cinco tecnologias-chave para alcançar sua eficiência e segurança. Primeiro, a aritmética baseada em torres de domínios binários (towers of binary fields) constitui a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adaptou a verificação de consistência segura e eficiente entre variáveis e suas permutações no seu protocolo de prova Oracle interativa (PIOP), incorporando a verificação de produto e permutação do HyperPlonk. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência da verificação de relações multilineares em pequenos domínios. Quarto, Binius utiliza uma versão aprimorada da prova de busca Lasso, fornecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo emprega um esquema de compromisso polinomial de pequenos domínios (Small-Field PCS), permitindo a implementação de um sistema de provas eficiente sobre domínios binários e reduzindo a sobrecarga geralmente associada a grandes domínios.
( 2.1 Domínio Finito: Arithmetização baseada em torres de campos binários
Os campos binários em torre são fundamentais para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculo eficiente e aritmética eficiente. Os campos binários suportam essencialmente operações aritméticas de alta eficiência, tornando-os uma escolha ideal para aplicações criptográficas sensíveis a desempenho. Além disso, a estrutura dos campos binários apoia processos aritméticos simplificados, ou seja, as operações realizadas sobre os campos binários podem ser representadas de forma algébrica compacta e fácil de verificar. Estas características, juntamente com a capacidade de tirar pleno proveito de suas propriedades hierárquicas através da estrutura em torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis como o Binius.
Onde "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 é diferente do domínio primo, que não consegue 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, 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, os métodos de redução comuns incluem a redução especial ) usada no AES ###, a redução de Montgomery ( 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" aponta que o domínio binário não requer a introdução de transporte em operações de adição e multiplicação, 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. Pode ser vista como um elemento único no domínio binário de 128 bits ou ser interpretada 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 torre de 8 bits, ou 128 elementos de domínio F2. Essa flexibilidade de representação não requer nenhum custo de computação, apenas uma conversão de tipo da string de bits (typecast), que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser agrupados em elementos de domínio maiores sem necessidade de custo computacional adicional. O protocolo Binius aproveita essa característica para melhorar 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 operações de inversão em domínios de torre binária de n bits que ( podem ser decompostos em subdomínios de m bits ).
( 2.2 PIOP: versão adaptada do Produto HyperPlonk e Verificação de Permutação------aplicável ao domínio binário
O design do PIOP no protocolo Binius foi inspirado no HyperPlonk e utiliza 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 secreto ω e a entrada pública x satisfazem a relação de operação do circuito C)x,ω###=0, para garantir que o circuito funcione corretamente.
PermutationCheck: Verifica se os resultados de avaliação de dois polinómios multivariáveis f e g no hipercubo booleano representam 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: Verifica se a avaliação do polinómio está na tabela de consulta dada, ou seja, f)Bµ) ⊆ T(Bµ), assegurando que certos valores estão 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 vários 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 do polinómio.
ZeroCheck: verificar se um polinómio multivariável em um hipercubo booleano é zero em um ponto arbitrário ∏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 um problema de avaliação de polinómios univariáveis, reduz a complexidade computacional para o verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que possibilitam o processamento em lote de várias instâncias de verificação de somas.
BatchCheck: Com base no SumCheck, valida a correção da avaliação de múltiplos polinómios multivariáveis, para aumentar a eficiência do protocolo.
Embora o Binius tenha muitas semelhanças de design de protocolo com o HyperPlonk, o Binius fez melhorias nas seguintes 3 áreas:
ProductCheck otimizado: no HyperPlonk, o ProductCheck requer que o denominador U seja não nulo em toda a hipercubo, e o produto deve ser igual a um valor específico; Binius simplifica esse processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade computacional.
Tratamento do problema da divisão por zero: HyperPlonk não conseguiu lidar adequadamente com a situação de divisão por zero, resultando na impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius pode continuar a processar, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação entre Colunas: HyperPlonk não possui essa funcionalidade; Binius suporta a Verificação de Permutação entre várias colunas, o que permite ao Binius lidar com situações de arranjos polinomiais mais complexas.
Assim, a Binius melhorou a flexibilidade e a eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente.
Binius: STARKs otimizados em domínios binários
Análise dos Princípios dos STARKs da Binius e Reflexões sobre a Otimização
1 Introdução
Uma das principais razões para a baixa eficiência dos STARKs é que a maioria dos valores em programas reais é bastante pequena, como os í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 crucial.
Como mostrado na Tabela 1, a largura de codificação dos STARKs de primeira geração é de 252 bits, a largura de codificação dos STARKs de segunda geração é de 64 bits, e a largura de codificação dos STARKs de terceira 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 codificação compacta e eficiente, sem qualquer desperdício de espaço, ou seja, os STARKs de quarta geração.
Tabela 1: Caminho de derivação dos STARKs
| Álgebra | Largura de codificação | Implementação representativa | |------|----------|------------| | 1ª Geração | 252bit | StarkWare | | 2ª geração | 64bit | Plonky2 | | 3ª geração | 32bit | BabyBear |
| 4ª Geração | 1bit | Binius |
Comparado com as novas descobertas de domínios finitos, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre domínios binários remonta à década de 80 do século passado. Atualmente, os domínios binários já estão amplamente aplicados na criptografia, exemplos típicos incluem:
Quando se utilizam domínios menores, a operação de extensão de domínio torna-se cada vez mais importante para garantir a segurança. E o domínio binário utilizado pela Binius depende completamente da extensão de domínio para assegurar a 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, operando apenas no domínio base, o que permite uma alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam aprofundar-se em um domínio de extensão maior para garantir a segurança necessária.
Ao construir sistemas de prova com base em domínios binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinómio; ao comprometer a árvore 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 para tratar esses dois problemas, representando os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariáveis (, especificamente polinômios multilineares ), em vez de polinômios univariáveis, para representar toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, como cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas podemos considerar o hipercubo como um quadrado ), baseado no qual podemos realizar a extensão de Reed-Solomon. Este método, ao garantir a 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:
Informação Teórica de Provas Interativas de Oracle Polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de provas, transforma a relação computacional 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 pequeno número de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, cada um com diferentes maneiras de tratar expressões polinomiais, afetando assim o desempenho e a eficiência de todo o sistema SNARK.
Esquema de Compromisso Polinomial (Polynomial Commitment Scheme, PCS): O esquema de compromisso polinomial é utilizado para provar se uma equação polinomial gerada por PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se a um determinado polinómio e, posteriormente, verificar os resultados 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 apropriada, podendo 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 de confiança do protocolo ZCash.
Plonky2: Adota PLONK PIOP e FRI PCS combinados, e é baseado no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, a PIOP e a PCS escolhidas devem corresponder ao domínio finito ou curva elíptica utilizados, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não só afeta o tamanho da prova SNARK e a eficiência da verificação, mas também determina se o sistema pode alcançar transparência sem a necessidade de configuração confiável, e se pode suportar funcionalidades expandidas como provas recursivas ou provas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + domínios binários. Especificamente, Binius inclui cinco tecnologias-chave para alcançar sua eficiência e segurança. Primeiro, a aritmética baseada em torres de domínios binários (towers of binary fields) constitui a base de seus cálculos, permitindo operações simplificadas dentro do domínio binário. Em segundo lugar, Binius adaptou a verificação de consistência segura e eficiente entre variáveis e suas permutações no seu protocolo de prova Oracle interativa (PIOP), incorporando a verificação de produto e permutação do HyperPlonk. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência da verificação de relações multilineares em pequenos domínios. Quarto, Binius utiliza uma versão aprimorada da prova de busca Lasso, fornecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo emprega um esquema de compromisso polinomial de pequenos domínios (Small-Field PCS), permitindo a implementação de um sistema de provas eficiente sobre domínios binários e reduzindo a sobrecarga geralmente associada a grandes domínios.
( 2.1 Domínio Finito: Arithmetização baseada em torres de campos binários
Os campos binários em torre são fundamentais para a implementação de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculo eficiente e aritmética eficiente. Os campos binários suportam essencialmente operações aritméticas de alta eficiência, tornando-os uma escolha ideal para aplicações criptográficas sensíveis a desempenho. Além disso, a estrutura dos campos binários apoia processos aritméticos simplificados, ou seja, as operações realizadas sobre os campos binários podem ser representadas de forma algébrica compacta e fácil de verificar. Estas características, juntamente com a capacidade de tirar pleno proveito de suas propriedades hierárquicas através da estrutura em torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis como o Binius.
Onde "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 é diferente do domínio primo, que não consegue 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, 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, os métodos de redução comuns incluem a redução especial ) usada no AES ###, a redução de Montgomery ( 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" aponta que o domínio binário não requer a introdução de transporte em operações de adição e multiplicação, 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. Pode ser vista como um elemento único no domínio binário de 128 bits ou ser interpretada 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 torre de 8 bits, ou 128 elementos de domínio F2. Essa flexibilidade de representação não requer nenhum custo de computação, apenas uma conversão de tipo da string de bits (typecast), que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser agrupados em elementos de domínio maiores sem necessidade de custo computacional adicional. O protocolo Binius aproveita essa característica para melhorar 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 operações de inversão em domínios de torre binária de n bits que ( podem ser decompostos em subdomínios de m bits ).
( 2.2 PIOP: versão adaptada do Produto HyperPlonk e Verificação de Permutação------aplicável ao domínio binário
O design do PIOP no protocolo Binius foi inspirado no HyperPlonk e utiliza 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 secreto ω e a entrada pública x satisfazem a relação de operação do circuito C)x,ω###=0, para garantir que o circuito funcione corretamente.
PermutationCheck: Verifica se os resultados de avaliação de dois polinómios multivariáveis f e g no hipercubo booleano representam 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: Verifica se a avaliação do polinómio está na tabela de consulta dada, ou seja, f)Bµ) ⊆ T(Bµ), assegurando que certos valores estão 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 vários 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 do polinómio.
ZeroCheck: verificar se um polinómio multivariável em um hipercubo booleano é zero em um ponto arbitrário ∏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 um problema de avaliação de polinómios univariáveis, reduz a complexidade computacional para o verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que possibilitam o processamento em lote de várias instâncias de verificação de somas.
BatchCheck: Com base no SumCheck, valida a correção da avaliação de múltiplos polinómios multivariáveis, para aumentar a eficiência do protocolo.
Embora o Binius tenha muitas semelhanças de design de protocolo com o HyperPlonk, o Binius fez melhorias nas seguintes 3 áreas:
ProductCheck otimizado: no HyperPlonk, o ProductCheck requer que o denominador U seja não nulo em toda a hipercubo, e o produto deve ser igual a um valor específico; Binius simplifica esse processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade computacional.
Tratamento do problema da divisão por zero: HyperPlonk não conseguiu lidar adequadamente com a situação de divisão por zero, resultando na impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius pode continuar a processar, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação entre Colunas: HyperPlonk não possui essa funcionalidade; Binius suporta a Verificação de Permutação entre várias colunas, o que permite ao Binius lidar com situações de arranjos polinomiais mais complexas.
Assim, a Binius melhorou a flexibilidade e a eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente.
![Bitl