Análise dos Princípios do Binius STARKs 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 numéricos nos 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, quando os dados são expandidos usando codificação de Reed-Solomon, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que o valor original em si seja muito pequeno. Para resolver este problema, a redução do tamanho do domínio tornou-se uma estratégia chave.
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 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, os STARKs de quarta geração.
Em comparação com os domínios finitos recentemente descobertos em pesquisas como Goldilocks, BabyBear e Mersenne31, 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;
Galois código de autenticação de mensagem ( 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 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 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, operando apenas no domínio base, o que permite uma alta eficiência em domínios pequenos. No entanto, as verificações de pontos aleatórios e os cálculos FRI ainda precisam aprofundar-se em extensões de domínio maiores, 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 traços 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 extensão da codificação.
A Binius propôs uma solução inovadora que trata essas duas questões separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariado (, especificamente um polinômio multilinhar ), em vez de um polinômio univariado, representando 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 a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado ), e a extensão de Reed-Solomon pode ser baseada nesse quadrado. Este método melhora significativamente a eficiência da codificação e o desempenho computacional, enquanto garante a segurança.
2 Análise de Princípios
A construção da maioria dos sistemas SNARKs atualmente geralmente inclui as seguintes duas partes:
Informação Teórica de Prova Interactiva de Oracle Polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, 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 de forma incremental através da interação com o verificador, permitindo que o verificador valide se o cálculo está correto consultando apenas os resultados da 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 diferentes abordagens para o tratamento de 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. PCS é uma ferramenta criptográfica, através da qual o provador pode se comprometer com um determinado polinômio e, posteriormente, verificar os resultados 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 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 o domínio finito ou curva elíptica apropriada, pode-se 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: utiliza PLONK PIOP e FRI PCS combinados, e baseia-se no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao domínio finito ou à curva elíptica utilizada, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não afeta apenas 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 de confiança, e 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 domínio binário (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 produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo a verificação de consistência segura e eficiente entre variáveis e suas permutações. 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 adotou uma versão melhorada da prova de busca Lasso, oferecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o domínio binário, reduzindo a sobrecarga normalmente associada a grandes domínios.
( 2.1 Domínio Finito: 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, 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 características hierárquicas por meio 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 mais básico dos domínios binários F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do domínio binário de k bits. Isso é diferente dos domínios de prime, onde não é possível 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. No domínio primo Fp, 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 utilizada no AES ###, a redução de Montgomery ( como utilizada 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" aponta que o domínio binário não requer o 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: 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 pode 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 8 bits, ou 128 elementos de domínio de F2. Essa flexibilidade de representação não requer nenhum custo computacional, 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 menores podem ser empacotados em 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, quadrados e operações de inversão em ( nos 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 campo 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. Essas verificações essenciais incluem:
GateCheck: Verificar se o testemunho de confidencialidade ω e a entrada pública x satisfazem a relação de cálculo do circuito C)x, ω###=0, para garantir o funcionamento correto do circuito.
PermutationCheck: Verifica 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 busca 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 vários conjuntos.
ProductCheck: Verifica 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 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 de avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional para o validador. 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 somas.
BatchCheck: Baseado em SumCheck, verifica a correção da avaliação de vários polinômios multivariáveis, para aumentar a eficiência do protocolo.
Embora Binius e HyperPlonk tenham muitas semelhanças no design do protocolo, Binius fez melhorias nas seguintes 3 áreas:
Otimização do ProductCheck: no HyperPlonk, o ProductCheck requer que o denominador U seja diferente de zero em todo o hipercubo, e o produto deve ser igual a um valor específico; o 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, levando à impossibilidade de afirmar que U é não nulo sobre o hipercubo; Binius lidou corretamente com esse problema, mesmo quando o denominador é zero, o ProductCheck do Binius também pode 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ções 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 existente PIOPSumCheck, especialmente ao lidar com a verificação de polinómios multivariados mais complexos, proporcionando um suporte funcional mais robusto. Estas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em domínios binários.
( 2.3 PIOP: novo argumento de mudança multilinear ------ 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
4
Republicar
Partilhar
Comentar
0/400
AllTalkLongTrader
· 23h atrás
Quem é que entende isso? Além do star, não percebi nada.
Ver originalResponder0
MerkleDreamer
· 23h atrás
A largura diminuiu, finalmente reduzimos o desperdício.
Ver originalResponder0
PanicSeller
· 23h atrás
Esta otimização está a demorar demasiado, estou cansado.
Binius STARKs nova quebra: otimização de domínio binário e sistema de prova eficiente
Análise dos Princípios do Binius STARKs 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 numéricos nos 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, quando os dados são expandidos usando codificação de Reed-Solomon, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que o valor original em si seja muito pequeno. Para resolver este problema, a redução do tamanho do domínio tornou-se uma estratégia chave.
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 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, os STARKs de quarta geração.
Tabela 1: Caminho de derivação dos STARKs
| Ordem | Largura | Descrição | |------|------|------| | 1ª Geração | 252bit | Baseado em domínio de números primos | | 2ª geração | 64 bits | Domínio Goldilocks | | 3ª Geração | 32bits | Domínio Babybear | | 4ª Geração | 1bit | Domínio Binário |
Em comparação com os domínios finitos recentemente descobertos em pesquisas como Goldilocks, BabyBear e Mersenne31, 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;
Galois código de autenticação de mensagem ( 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 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 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, operando apenas no domínio base, o que permite uma alta eficiência em domínios pequenos. No entanto, as verificações de pontos aleatórios e os cálculos FRI ainda precisam aprofundar-se em extensões de domínio maiores, 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 traços 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 extensão da codificação.
A Binius propôs uma solução inovadora que trata essas duas questões separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, usando um polinômio multivariado (, especificamente um polinômio multilinhar ), em vez de um polinômio univariado, representando 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 a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado ), e a extensão de Reed-Solomon pode ser baseada nesse quadrado. Este método melhora significativamente a eficiência da codificação e o desempenho computacional, enquanto garante a segurança.
2 Análise de Princípios
A construção da maioria dos sistemas SNARKs atualmente geralmente inclui as seguintes duas partes:
Informação Teórica de Prova Interactiva de Oracle Polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, 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 de forma incremental através da interação com o verificador, permitindo que o verificador valide se o cálculo está correto consultando apenas os resultados da 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 diferentes abordagens para o tratamento de 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. PCS é uma ferramenta criptográfica, através da qual o provador pode se comprometer com um determinado polinômio e, posteriormente, verificar os resultados 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 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 o domínio finito ou curva elíptica apropriada, pode-se 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: utiliza PLONK PIOP e FRI PCS combinados, e baseia-se no domínio Goldilocks. Plonky2 foi projetado para realizar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao domínio finito ou à curva elíptica utilizada, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não afeta apenas 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 de confiança, e 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 domínio binário (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 produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo a verificação de consistência segura e eficiente entre variáveis e suas permutações. 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 adotou uma versão melhorada da prova de busca Lasso, oferecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utilizou um esquema de compromisso polinomial de pequeno domínio (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o domínio binário, reduzindo a sobrecarga normalmente associada a grandes domínios.
( 2.1 Domínio Finito: 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, 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 características hierárquicas por meio 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 mais básico dos domínios binários F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do domínio binário de k bits. Isso é diferente dos domínios de prime, onde não é possível 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. No domínio primo Fp, 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 utilizada no AES ###, a redução de Montgomery ( como utilizada 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" aponta que o domínio binário não requer o 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: 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 pode 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 8 bits, ou 128 elementos de domínio de F2. Essa flexibilidade de representação não requer nenhum custo computacional, 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 menores podem ser empacotados em 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, quadrados e operações de inversão em ( nos 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 campo 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. Essas verificações essenciais incluem:
GateCheck: Verificar se o testemunho de confidencialidade ω e a entrada pública x satisfazem a relação de cálculo do circuito C)x, ω###=0, para garantir o funcionamento correto do circuito.
PermutationCheck: Verifica 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 busca 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 vários conjuntos.
ProductCheck: Verifica 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 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 de avaliação de polinómios multivariáveis em avaliação de polinómios univariáveis, reduz a complexidade computacional para o validador. 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 somas.
BatchCheck: Baseado em SumCheck, verifica a correção da avaliação de vários polinômios multivariáveis, para aumentar a eficiência do protocolo.
Embora Binius e HyperPlonk tenham muitas semelhanças no design do protocolo, Binius fez melhorias nas seguintes 3 áreas:
Otimização do ProductCheck: no HyperPlonk, o ProductCheck requer que o denominador U seja diferente de zero em todo o hipercubo, e o produto deve ser igual a um valor específico; o 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, levando à impossibilidade de afirmar que U é não nulo sobre o hipercubo; Binius lidou corretamente com esse problema, mesmo quando o denominador é zero, o ProductCheck do Binius também pode 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ções 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 existente PIOPSumCheck, especialmente ao lidar com a verificação de polinómios multivariados mais complexos, proporcionando um suporte funcional mais robusto. Estas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para futuros sistemas de prova baseados em domínios binários.
( 2.3 PIOP: novo argumento de mudança multilinear ------ aplicável ao hipercubo booleano
No protocolo Binius, múltiplos virtuais