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 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 expandir os dados usando codificação Reed-Solomon, 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 da 1ª geração de STARKs é de 252 bits, a largura de codificação da 2ª geração de STARKs é de 64 bits, e a largura de codificação da 3ª geração de STARKs é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta uma grande quantidade de 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 desperdício de espaço, ou seja, a 4ª geração de STARKs.
Em comparação com as descobertas recentes de campos finitos, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre campos binários remonta à década de 1980. Atualmente, os campos binários são amplamente utilizados na criptografia, exemplos típicos incluem:
Padrão de Criptografia Avançada (AES), baseado no domínio F28;
Código QR, usando 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 utilizam domínios menores, 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 pela Binius depende totalmente da extensão de domínio para garantir 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, funcionando apenas no domínio base, permitindo assim uma alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e os cálculos FRI ainda precisam aprofundar-se em uma extensão de domínio maior para garantir a segurança necessária.
Ao construir um sistema de prova 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 de 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 que trata estes dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariado (, especificamente um polinômio ) multilinear, em vez de um polinômio univariado, para representar toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, como o comprimento de cada dimensão do hipercubo é 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser considerado como um quadrado ), baseado no qual se pode realizar a extensão de Reed-Solomon. Este método, ao garantir a segurança, aumenta 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 as seguintes duas partes:
Prova de Oráculo Interativo Polinomial com Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de provas, 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 de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, cada um com uma abordagem diferente para o tratamento de 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 é utilizado para provar se a equação polinomial gerada por PIOP é válida. 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 comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS têm diferentes desempenhos, níveis de segurança e cenários aplicáveis.
De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um campo finito ou curva elíptica adequada, podendo 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 setup confiável do protocolo ZCash.
• Plonky2: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 é projetado para alcançar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao domínio finito ou à curva elíptica utilizada, a fim de 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 uma configuração confiável, além de se pode suportar funcionalidades expandidas 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 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 consistência segura e eficiente entre variáveis e suas permutações no seu protocolo de prova Oracle interativo (PIOP), com o uso da verificação de produtos e permutações 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 campos. Quarto, Binius utilizou uma versão melhorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança para o mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso polinomial de pequenos campos (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o campo binário e reduzindo as despesas normalmente associadas a grandes campos.
( 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários
Os domínios binários em torre são a chave para a realização de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os domínios binários suportam essencialmente 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 simplificado, onde 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 o domínio binário particularmente adequado para sistemas de prova escaláveis como o Binius.
O termo "canônico" refere-se à representação única e direta de um elemento no domínio binário. Por exemplo, no mais básico dos domínios binários F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de domínio binário de k bits. Isso difere dos domínios primos, que não podem fornecer essa representação canônica dentro de um número fixo de bits. Embora um 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 oferece essa conveniência de mapeamento um-para-um. Nos domínios primos 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. Nos domínios binários F2k, os métodos de redução comuns incluem a redução especial ), como usado em AES ###, a redução de Montgomery (, como utilizada em POLYVAL ), e a redução recursiva (, como em Tower ). O artigo "Explorando o Espaço de Design das Implementações de Hardware ECC em Domínios Primos vs. Binários" 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 de (X + Y )2 = X2 + Y 2.
Como mostrado na Figura 1, uma string de 128 bits: esta string pode ser interpretada de várias maneiras no contexto de um domínio binário. Pode ser vista como um elemento único em um 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 torre de 8 bits, ou 128 elementos de 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 menores podem ser empacotados como 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, quadrados e operações 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 ).
Figura 1: Domínio binário em torre
( 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 multivariados. Essas verificações essenciais incluem:
GateCheck: Verificar se o testemunho de segredo ω 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 dos dois polinómios multivariáveis 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: Verifica se a avaliação do polinómio está na tabela de pesquisa dada, ou seja, f)Bµ) ⊆ T(Bµ), garantindo 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 de 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 em qualquer ponto é zero ∏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 uma avaliação de polinómios univariáveis, reduz a complexidade computacional para a parte verificadora. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam o processamento em lote de várias instâncias de verificação de soma.
BatchCheck: baseia-se no SumCheck, valida a correção da avaliação de múltiplos polinómios multivariados, para melhorar a eficiência do protocolo.
Embora a Binius e a HyperPlonk tenham muitas semelhanças no design do protocolo, a Binius fez melhorias nas seguintes 3 áreas:
Otimização do ProductCheck: no HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em todo o hipercubo e que o produto seja igual a um valor específico; a Binius simplificou este processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade de cálculo.
Tratamento do problema da divisão por zero: HyperPlonk não conseguiu lidar adequadamente com situações de divisão por zero, levando à impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar o processamento, 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, 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 verificação de polinômios multivariáveis 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 provas baseados em campos binários.
( 2.3 PIOP: novo argumento de deslocamento multilinear------aplicável ao hipercubo booleano
Na protocol Binius, a construção e o processamento de polinômios virtuais são importantes.
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.
10 gostos
Recompensa
10
5
Partilhar
Comentar
0/400
GasBandit
· 4h atrás
E como pensaram em otimizar os starks?
Ver originalResponder0
CryptoComedian
· 4h atrás
Escrever uma tese com largura de pressão, escrevi três gerações e não atingi o padrão.
Ver originalResponder0
BlockchainThinkTank
· 4h atrás
Acreditamos que a otimização zkp ainda está em uma fase inicial, e devemos ter cautela ao considerar soluções de aumento de eficiência para este tipo de projeto.
Ver originalResponder0
MentalWealthHarvester
· 4h atrás
Mais uma vez, é o período de ouro dos meus STARKs. Ainda posso minerar mais.
Ver originalResponder0
LayoffMiner
· 4h atrás
O que está a pensar, o gás não pode descer e ainda faz isso tão profundo.
Nova abordagem de otimização STARKs: Binius impulsiona o desenvolvimento do 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 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 expandir os dados usando codificação Reed-Solomon, 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 da 1ª geração de STARKs é de 252 bits, a largura de codificação da 2ª geração de STARKs é de 64 bits, e a largura de codificação da 3ª geração de STARKs é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta uma grande quantidade de 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 desperdício de espaço, ou seja, a 4ª geração de STARKs.
| Tempo | STARKs | Largura de Codificação | |------|--------|----------| | 2018 | 1ª geração | 252bit | | 2021 | 2ª geração | 64bit | | 2022 | 3ª geração | 32bit | | 2023 | 4ª geração | 1bit |
Tabela 1: Caminho de Derivação de STARKs
Em comparação com as descobertas recentes de campos finitos, como Goldilocks, BabyBear e Mersenne31, a pesquisa sobre campos binários remonta à década de 1980. Atualmente, os campos binários são amplamente utilizados 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 domínio F2128;
Código QR, usando 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 utilizam domínios menores, 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 pela Binius depende totalmente da extensão de domínio para garantir 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, funcionando apenas no domínio base, permitindo assim uma alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e os cálculos FRI ainda precisam aprofundar-se em uma extensão de domínio maior para garantir a segurança necessária.
Ao construir um sistema de prova 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 de 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 que trata estes dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariado (, especificamente um polinômio ) multilinear, em vez de um polinômio univariado, para representar toda a trajetória de cálculo através de seus valores em "hipercubos" (; em segundo lugar, como o comprimento de cada dimensão do hipercubo é 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser considerado como um quadrado ), baseado no qual se pode realizar a extensão de Reed-Solomon. Este método, ao garantir a segurança, aumenta 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 as seguintes duas partes:
Prova de Oráculo Interativo Polinomial com Teoria da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como o núcleo do sistema de provas, 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 de avaliação de um número reduzido de polinômios. Os protocolos PIOP existentes incluem: PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, cada um com uma abordagem diferente para o tratamento de 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 é utilizado para provar se a equação polinomial gerada por PIOP é válida. 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 comuns incluem KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) e Brakedown, entre outros. Diferentes PCS têm diferentes desempenhos, níveis de segurança e cenários aplicáveis.
De acordo com as necessidades específicas, escolha diferentes PIOP e PCS, e combine com um campo finito ou curva elíptica adequada, podendo 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 setup confiável do protocolo ZCash.
• Plonky2: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 é projetado para alcançar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao domínio finito ou à curva elíptica utilizada, a fim de 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 uma configuração confiável, além de se pode suportar funcionalidades expandidas 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 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 consistência segura e eficiente entre variáveis e suas permutações no seu protocolo de prova Oracle interativo (PIOP), com o uso da verificação de produtos e permutações 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 campos. Quarto, Binius utilizou uma versão melhorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança para o mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso polinomial de pequenos campos (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o campo binário e reduzindo as despesas normalmente associadas a grandes campos.
( 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários
Os domínios binários em torre são a chave para a realização de cálculos rápidos e verificáveis, principalmente devido a dois aspectos: cálculos eficientes e aritmética eficiente. Os domínios binários suportam essencialmente 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 simplificado, onde 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 o domínio binário particularmente adequado para sistemas de prova escaláveis como o Binius.
O termo "canônico" refere-se à representação única e direta de um elemento no domínio binário. Por exemplo, no mais básico dos domínios binários F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de domínio binário de k bits. Isso difere dos domínios primos, que não podem fornecer essa representação canônica dentro de um número fixo de bits. Embora um 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 oferece essa conveniência de mapeamento um-para-um. Nos domínios primos 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. Nos domínios binários F2k, os métodos de redução comuns incluem a redução especial ), como usado em AES ###, a redução de Montgomery (, como utilizada em POLYVAL ), e a redução recursiva (, como em Tower ). O artigo "Explorando o Espaço de Design das Implementações de Hardware ECC em Domínios Primos vs. Binários" 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 de (X + Y )2 = X2 + Y 2.
Como mostrado na Figura 1, uma string de 128 bits: esta string pode ser interpretada de várias maneiras no contexto de um domínio binário. Pode ser vista como um elemento único em um 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 torre de 8 bits, ou 128 elementos de 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 menores podem ser empacotados como 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, quadrados e operações 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 ).
Figura 1: Domínio binário em torre
( 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 multivariados. Essas verificações essenciais incluem:
GateCheck: Verificar se o testemunho de segredo ω 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 dos dois polinómios multivariáveis 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: Verifica se a avaliação do polinómio está na tabela de pesquisa dada, ou seja, f)Bµ) ⊆ T(Bµ), garantindo 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 de 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 em qualquer ponto é zero ∏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 uma avaliação de polinómios univariáveis, reduz a complexidade computacional para a parte verificadora. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam o processamento em lote de várias instâncias de verificação de soma.
BatchCheck: baseia-se no SumCheck, valida a correção da avaliação de múltiplos polinómios multivariados, para melhorar a eficiência do protocolo.
Embora a Binius e a HyperPlonk tenham muitas semelhanças no design do protocolo, a Binius fez melhorias nas seguintes 3 áreas:
Otimização do ProductCheck: no HyperPlonk, o ProductCheck exige que o denominador U seja não nulo em todo o hipercubo e que o produto seja igual a um valor específico; a Binius simplificou este processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade de cálculo.
Tratamento do problema da divisão por zero: HyperPlonk não conseguiu lidar adequadamente com situações de divisão por zero, levando à impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente desse problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar o processamento, 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, 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 verificação de polinômios multivariáveis 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 provas baseados em campos binários.
( 2.3 PIOP: novo argumento de deslocamento multilinear------aplicável ao hipercubo booleano
Na protocol Binius, a construção e o processamento de polinômios virtuais são importantes.