Análise dos princípios dos STARKs da Binius e reflexões sobre a otimização
1. Introdução
Diferente dos SNARKs baseados em curvas elípticas, os STARKs podem ser considerados como SNARKs baseados em hash. Uma das principais razões para a ineficiência atual dos STARKs é: a maioria dos valores em programas reais é bastante pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvore 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 este problema, reduzir o tamanho do domínio tornou-se uma estratégia chave.
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 um grande desperdício de espaço. 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, a 4ª geração de STARKs.
Comparado com os campos finitos recentemente descobertos, 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 em criptografia, com exemplos típicos incluindo:
Padrão de Criptografia Avançada (AES), baseado no domínio F28;
Galois Message Authentication Code ( GMAC ), baseado no campo 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, 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 garantir a sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos dos Prover não precisa de entrar na extensão de domínio, podendo operar apenas no domínio base, alcançando assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e os cálculos FRI ainda precisam de se aprofundar em domínios de extensão 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 trace em STARKs, o tamanho do domínio utilizado deve ser maior 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 que o tamanho após a expansão da codificação.
Binius propôs uma solução inovadora que aborda esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinómios multivariados (especificamente polinómios multiliniares) em vez de polinómios univariados, representando toda a trajetória de cálculo através dos 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 visto como um quadrado, realizando a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir a segurança, melhora significativamente a eficiência da codificação e o desempenho computacional.
2. Análise do Princípio
A construção da maioria dos sistemas SNARKs atualmente geralmente inclui as seguintes duas partes:
Prova de Oracle Interativa Polinomial de 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 que podem ser verificadas. 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 da avaliação de um pequeno número de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes maneiras de lidar com 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 a igualdade polinomial gerada por PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se com um determinado polinômio e, posteriormente, verificar 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 o domínio finito ou curva elíptica apropriada, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:
• Halo2: combinado com 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: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao campo finito ou curva elíptica utilizada, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não apenas afeta o tamanho da prova SNARK e a eficiência da verificação, mas também determina se o sistema pode alcançar a transparência sem a necessidade de uma configuração confiável, 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 campos binários 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 produtos e permutações do HyperPlonk em seu protocolo de prova de Oracle interativo (PIOP), garantindo uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinhar, otimizando a eficiência na verificação de relações multilineares sobre pequenos campos. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, oferecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequeno campo (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o campo binário e reduzindo a sobrecarga geralmente associada a grandes campos.
2.1 Domínios finitos: aritmética baseada em torres de campos binários
Os domínios binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, 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 a requisitos de desempenho. Além disso, a estrutura do domínio binário suporta um processo de aritmética simplificada, ou seja, as operações realizadas sobre o domínio binário podem ser representadas de forma compacta e fácil de verificar na forma algébrica. Essas características, juntamente com a capacidade de aproveitar plenamente suas propriedades hierárquicas através de uma estrutura em torre, tornam os domínios binários particularmente adequados para sistemas de prova escaláveis como o Binius.
O termo "canônico" refere-se à representação única e direta de elementos no domínio binário. Por exemplo, no domínio binário mais básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de domínio binário de k bits. Isso é diferente dos domínios primários, que não conseguem 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 maneira única a um elemento do domínio, enquanto o domínio binário oferece essa conveniência de mapeamento um a um. No domínio primo Fp, os métodos de redução comuns incluem a redução Barrett, a redução 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 frequentemente utilizados incluem reduções especiais (como as usadas no AES), reduções Montgomery (como as usadas no POLYVAL) e reduções recursivas (como Tower). O artigo "Explorando o Espaço de Design de Implementações de Hardware ECC em Campo Primo vs. Campo Binário" aponta que o domínio binário não requer transporte em operações de adição e multiplicação, e a operação de quadrado do domínio binário é muito eficiente, pois segue a regra simplificada (X + Y )2 = X2 + Y2.
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 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 qualquer sobrecarga computacional, sendo apenas uma conversão de tipo (typecast) da string de bits, o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser empacotados 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 de operações de multiplicação, quadrados e inversão em domínios binários de torre com n bits (que podem ser decompostos em subdomínios de m bits).
2.2 PIOP: versão adaptada do produto HyperPlonk e PermutationCheck------aplicável ao domínio binário
O design do PIOP no protocolo Binius foi inspirado no HyperPlonk, adotando uma série de mecanismos de verificação principais para validar a correção de polinómios e conjuntos multivariados. Esses mecanismos de verificação principais incluem:
GateCheck: Verifica se o testemunho confidencial ω e a entrada pública x satisfazem a relação de cálculo do circuito C(x,ω)=0, para garantir que o circuito funcione corretamente.
PermutationCheck: Verifica se os resultados da avaliação de 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 das permutações entre as variáveis do polinómio.
LookupCheck: Verifica se a avaliação do polinómio está na tabela de procura 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 múltiplos conjuntos.
ProductCheck: Verifica se a avaliação de um polinómio racional no hipercubo de Booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto do polinómio.
ZeroCheck: Verifica se um polinómio multivariável é zero em qualquer ponto do hipercubo booleano ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Detecta 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 um polinómio multivariável em um problema de avaliação de um polinómio univariável, reduz a complexidade computacional do verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam o processamento em lote de várias instâncias de verificação de soma.
BatchCheck: baseado em SumCheck, verifica a correção da avaliação de múltiplos polinômios multivariados para aumentar a eficiência do protocolo.
Embora o Binius tenha muitas semelhanças com o HyperPlonk no design do protocolo, o Binius fez melhorias nas seguintes 3 áreas:
ProductCheck otimizado: No HyperPlonk, o ProductCheck requer que o denominador U seja não nulo em todo o hipercubo, e o produto deve ser igual a um valor específico; a Binius simplifica esse processo de verificação especializando 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 é não nulo sobre o hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação entre Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a realização de Verificação de Permutação entre várias colunas, o que permite ao Binius lidar com situações de permutação polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente, especialmente ao lidar com a verificação de polinómios multivariáveis mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não só resolveram as limitações do HyperPlonk, mas também estabeleceram as bases para futuros sistemas de prova baseados em campos binários.
2.3 PIOP: novo argumento de deslocamento multilinear------aplicável ao hipercubo booleano
No protocolo Binius, a construção e o processamento de polinómios virtuais é uma das tecnologias chave, capaz de gerar e operar de forma eficaz polinómios derivados de manipuladores de entrada ou de outros polinómios virtuais. Aqui estão dois métodos chave:
Compactação: Este método funciona ao colocar o menor dos locais adjacentes na ordem do dicionário.
Ver original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
6 gostos
Recompensa
6
3
Partilhar
Comentar
0/400
SleepyArbCat
· 13h atrás
Ha... ontem à noite fiz um airdrop de vários k Bits, quase morri a dormir.
Ver originalResponder0
SolidityJester
· 13h atrás
32bit aguenta? A ideia é bastante grande.
Ver originalResponder0
DeFiChef
· 13h atrás
O que é que este está a dizer, já estou com a cabeça a andar à roda.
Binius STARKs: Sistema de prova eficiente sob otimização de domínio binário
Análise dos princípios dos STARKs da Binius e reflexões sobre a otimização
1. Introdução
Diferente dos SNARKs baseados em curvas elípticas, os STARKs podem ser considerados como SNARKs baseados em hash. Uma das principais razões para a ineficiência atual dos STARKs é: a maioria dos valores em programas reais é bastante pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvore 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 este problema, reduzir o tamanho do domínio tornou-se uma estratégia chave.
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 um grande desperdício de espaço. 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, a 4ª geração de STARKs.
Comparado com os campos finitos recentemente descobertos, 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 em criptografia, com exemplos típicos incluindo:
Padrão de Criptografia Avançada (AES), baseado no domínio F28;
Galois Message Authentication Code ( GMAC ), baseado no campo 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, 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 garantir a sua segurança e viabilidade prática. A maioria dos polinómios envolvidos nos cálculos dos Prover não precisa de entrar na extensão de domínio, podendo operar apenas no domínio base, alcançando assim alta eficiência em domínios pequenos. No entanto, a verificação de pontos aleatórios e os cálculos FRI ainda precisam de se aprofundar em domínios de extensão 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 trace em STARKs, o tamanho do domínio utilizado deve ser maior 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 que o tamanho após a expansão da codificação.
Binius propôs uma solução inovadora que aborda esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinómios multivariados (especificamente polinómios multiliniares) em vez de polinómios univariados, representando toda a trajetória de cálculo através dos 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 visto como um quadrado, realizando a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir a segurança, melhora significativamente a eficiência da codificação e o desempenho computacional.
2. Análise do Princípio
A construção da maioria dos sistemas SNARKs atualmente geralmente inclui as seguintes duas partes:
Prova de Oracle Interativa Polinomial de 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 que podem ser verificadas. 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 da avaliação de um pequeno número de polinômios. Os protocolos PIOP existentes incluem: PIOP PLONK, PIOP Spartan e PIOP HyperPlonk, cada um com diferentes maneiras de lidar com 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 a igualdade polinomial gerada por PIOP é válida. O PCS é uma ferramenta criptográfica que permite ao provador comprometer-se com um determinado polinômio e, posteriormente, verificar 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 o domínio finito ou curva elíptica apropriada, pode-se construir sistemas de prova com diferentes atributos. Por exemplo:
• Halo2: combinado com 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: combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 foi projetado para alcançar recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS escolhidos devem corresponder ao campo finito ou curva elíptica utilizada, para garantir a correção, desempenho e segurança do sistema. A escolha dessas combinações não apenas afeta o tamanho da prova SNARK e a eficiência da verificação, mas também determina se o sistema pode alcançar a transparência sem a necessidade de uma configuração confiável, 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 campos binários 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 produtos e permutações do HyperPlonk em seu protocolo de prova de Oracle interativo (PIOP), garantindo uma verificação de consistência segura e eficiente entre variáveis e suas permutações. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinhar, otimizando a eficiência na verificação de relações multilineares sobre pequenos campos. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, oferecendo flexibilidade e segurança robusta ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequeno campo (Small-Field PCS), permitindo a implementação de um sistema de prova eficiente sobre o campo binário e reduzindo a sobrecarga geralmente associada a grandes campos.
2.1 Domínios finitos: aritmética baseada em torres de campos binários
Os domínios binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, 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 a requisitos de desempenho. Além disso, a estrutura do domínio binário suporta um processo de aritmética simplificada, ou seja, as operações realizadas sobre o domínio binário podem ser representadas de forma compacta e fácil de verificar na forma algébrica. Essas características, juntamente com a capacidade de aproveitar plenamente suas propriedades hierárquicas através de uma estrutura em torre, tornam os domínios binários particularmente adequados para sistemas de prova escaláveis como o Binius.
O termo "canônico" refere-se à representação única e direta de elementos no domínio binário. Por exemplo, no domínio binário mais básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento de domínio binário de k bits. Isso é diferente dos domínios primários, que não conseguem 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 maneira única a um elemento do domínio, enquanto o domínio binário oferece essa conveniência de mapeamento um a um. No domínio primo Fp, os métodos de redução comuns incluem a redução Barrett, a redução 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 frequentemente utilizados incluem reduções especiais (como as usadas no AES), reduções Montgomery (como as usadas no POLYVAL) e reduções recursivas (como Tower). O artigo "Explorando o Espaço de Design de Implementações de Hardware ECC em Campo Primo vs. Campo Binário" aponta que o domínio binário não requer transporte em operações de adição e multiplicação, e a operação de quadrado do domínio binário é muito eficiente, pois segue a regra simplificada (X + Y )2 = X2 + Y2.
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 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 qualquer sobrecarga computacional, sendo apenas uma conversão de tipo (typecast) da string de bits, o que é uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio pequenos podem ser empacotados 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 de operações de multiplicação, quadrados e inversão em domínios binários de torre com n bits (que podem ser decompostos em subdomínios de m bits).
2.2 PIOP: versão adaptada do produto HyperPlonk e PermutationCheck------aplicável ao domínio binário
O design do PIOP no protocolo Binius foi inspirado no HyperPlonk, adotando uma série de mecanismos de verificação principais para validar a correção de polinómios e conjuntos multivariados. Esses mecanismos de verificação principais incluem:
GateCheck: Verifica se o testemunho confidencial ω e a entrada pública x satisfazem a relação de cálculo do circuito C(x,ω)=0, para garantir que o circuito funcione corretamente.
PermutationCheck: Verifica se os resultados da avaliação de 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 das permutações entre as variáveis do polinómio.
LookupCheck: Verifica se a avaliação do polinómio está na tabela de procura 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 múltiplos conjuntos.
ProductCheck: Verifica se a avaliação de um polinómio racional no hipercubo de Booleano é igual a um valor declarado ∏x∈Hµ f(x) = s, para garantir a correção do produto do polinómio.
ZeroCheck: Verifica se um polinómio multivariável é zero em qualquer ponto do hipercubo booleano ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Detecta 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 um polinómio multivariável em um problema de avaliação de um polinómio univariável, reduz a complexidade computacional do verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares que realizam o processamento em lote de várias instâncias de verificação de soma.
BatchCheck: baseado em SumCheck, verifica a correção da avaliação de múltiplos polinômios multivariados para aumentar a eficiência do protocolo.
Embora o Binius tenha muitas semelhanças com o HyperPlonk no design do protocolo, o Binius fez melhorias nas seguintes 3 áreas:
ProductCheck otimizado: No HyperPlonk, o ProductCheck requer que o denominador U seja não nulo em todo o hipercubo, e o produto deve ser igual a um valor específico; a Binius simplifica esse processo de verificação especializando 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 é não nulo sobre o hipercubo; Binius tratou corretamente este problema, mesmo quando o denominador é zero, o ProductCheck do Binius consegue continuar a processar, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação entre Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a realização de Verificação de Permutação entre várias colunas, o que permite ao Binius lidar com situações de permutação polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo PIOPSumCheck existente, especialmente ao lidar com a verificação de polinómios multivariáveis mais complexos, oferecendo um suporte funcional mais robusto. Essas melhorias não só resolveram as limitações do HyperPlonk, mas também estabeleceram as bases para futuros sistemas de prova baseados em campos binários.
2.3 PIOP: novo argumento de deslocamento multilinear------aplicável ao hipercubo booleano
No protocolo Binius, a construção e o processamento de polinómios virtuais é uma das tecnologias chave, capaz de gerar e operar de forma eficaz polinómios derivados de manipuladores de entrada ou de outros polinómios virtuais. Aqui estão dois métodos chave: