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 é: a maioria dos valores numéricos em programas reais é bastante pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, ao usar codificação de Reed-Solomon para expandir os dados, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que o valor original em si seja muito pequeno. Para resolver esse problema, reduzir o tamanho do domínio tornou-se uma estratégia crucial.
A largura de codificação da primeira geração de STARKs é de 252 bits, a largura de codificação da segunda geração de STARKs é de 64 bits, e a largura de codificação da terceira 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 a manipulação direta de bits, com codificação compacta e eficiente, sem qualquer desperdício de espaço, ou seja, a quarta geração de STARKs.
Comparado a descobertas recentes em campos finitos como Goldilocks, BabyBear e Mersenne31, a pesquisa em 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 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, assim como a função de hash Grøstl que chegou à fase 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, mas apenas operar no domínio base, permitindo 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 uma extensão de domínio maior para garantir a segurança necessária.
Ao construir sistemas de prova baseados 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 expansão da codificação.
Binius propôs uma solução inovadora que trata esses dois problemas separadamente e realiza a representação dos mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariados ( especificamente polinômios multilineares ) em vez de polinômios univariados, 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 expansão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado ), baseado no qual a expansão de Reed-Solomon pode ser realizada. Este método, ao garantir a segurança, melhora significativamente a eficiência de 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 Teórica da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de provas, transforma as relações computacionais de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente através da interação com o verificador, de modo que o verificador possa validar se o cálculo está correto consultando os resultados da avaliação de poucos 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, impactando 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 é usado 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 o resultado da avaliação desse polinômio, enquanto oculta outras informações do polinômio. Alguns esquemas de compromisso polinomial 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: combinando PLONK PIOP e Bulletproofs PCS, baseado na curva Pasta. O Halo2 foi projetado com foco na escalabilidade e na eliminação do trusted setup do protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado com FRI PCS e é baseado 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 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 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, 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 (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 produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo verificações de consistência seguras e eficientes entre variáveis e suas permutações. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência na validação de relações multilineares em pequenos campos. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequenos campos (Small-Field PCS), permitindo a implementação de um sistema de provas eficiente no campo binário e reduzindo a sobrecarga normalmente associada a grandes campos.
( 2.1 Domínio Finito: Arithmetização baseada em torres de campos binários
Os domínios 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 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 apoia um processo de aritmética simplificada, onde as operações realizadas sobre o 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 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 um elemento no domínio binário. Por exemplo, no mais básico domínio binário 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 podem fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa caber em 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento de domínio, enquanto o domínio binário oferece 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 ( usada na Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa 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 do domínio binário. Pode ser vista como um elemento único no domínio binário de 128 bits ou ser analisada como dois elementos do domínio de torre de 64 bits, quatro elementos do domínio de torre de 32 bits, 16 elementos do domínio de torre de 8 bits, ou 128 elementos do domínio F2. Essa flexibilidade de representação não requer nenhum custo computacional, apenas a conversão de tipo da string de bits (typecast), o que é uma propriedade muito interessante e útil. Ao mesmo tempo, os elementos de domínio pequenos podem ser empacotados em elementos de domínio maiores sem 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 das operações de multiplicação, quadrado e inversão em subdomínios de m bits ( no domínio binário de torre de n bits.
![Bitlayer Research: Análise dos princípios STARKs da Binius e suas reflexões sobre otimização])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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 se baseia no HyperPlonk, utilizando uma série de mecanismos de verificação fundamentais para validar a correção de polinômios e conjuntos multivariados. Essas verificações fundamentais incluem:
GateCheck: Verificar 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 da permutação entre as variáveis do polinómio.
LookupCheck: validar se a avaliação do polinômio está na tabela de consulta dada, ou seja, f(Bµ) ⊆ T)Bµ(, garantindo que certos valores estejam dentro do intervalo especificado.
MultisetCheck: Verifica se dois conjuntos multivariados são iguais, ou seja, {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantindo a consistência entre múltiplos conjuntos.
ProductCheck: verificar se a avaliação de um polinômio racional no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f)x( = s, para garantir a correção do produto polinomial.
ZeroCheck: Verificar se um polinómio multivariável em um hipercubo booleano é zero em qualquer ponto ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Detecta 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 do verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares e realizar o processamento em lote de várias instâncias de verificação de soma.
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.
Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius faz 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 o produto deve ser igual a um valor específico; a Binius simplifica esse processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade computacional.
Tratamento do problema de divisão por zero: HyperPlonk não conseguiu lidar adequadamente com a situação de divisão por zero, levando à impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente deste 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 de Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a Verificação de Permutação entre várias colunas, o que permite ao Binius lidar com situações de arranjo polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo existente PIOPSumCheck, especialmente ao lidar com a validação de polinómios multivariáveis mais complexos, oferecendo um suporte funcional mais forte. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram as bases para futuros sistemas de prova baseados em campos binários.
![Bitlayer Research: Análise dos princípios STARKs da Binius e reflexão sobre a otimização])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: novo argumento de mudança multilateral------aplicável ao hipercubo booleano
No protocolo Binius, a construção e o processamento de polinómios virtuais são uma das tecnologias-chave, capazes de gerar e operar eficazmente polinómios derivados de manipuladores de entrada ou de outros polinómios virtuais. Aqui estão dois métodos-chave:
Embalagem: Este método é
Ver original
Esta página pode conter conteúdo de terceiros, que é fornecido apenas para fins informativos (não para representações/garantias) e não deve ser considerada como um endosso de suas opiniões pela Gate nem como aconselhamento financeiro ou profissional. Consulte a Isenção de responsabilidade para obter detalhes.
Binius STARKs: Aplicações inovadoras e otimização de desempenho em domínios binários
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 é: a maioria dos valores numéricos em programas reais é bastante pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, ao usar codificação de Reed-Solomon para expandir os dados, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que o valor original em si seja muito pequeno. Para resolver esse problema, reduzir o tamanho do domínio tornou-se uma estratégia crucial.
A largura de codificação da primeira geração de STARKs é de 252 bits, a largura de codificação da segunda geração de STARKs é de 64 bits, e a largura de codificação da terceira 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 a manipulação direta de bits, com codificação compacta e eficiente, sem qualquer desperdício de espaço, ou seja, a quarta geração de STARKs.
Comparado a descobertas recentes em campos finitos como Goldilocks, BabyBear e Mersenne31, a pesquisa em 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 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, assim como a função de hash Grøstl que chegou à fase 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, mas apenas operar no domínio base, permitindo 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 uma extensão de domínio maior para garantir a segurança necessária.
Ao construir sistemas de prova baseados 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 expansão da codificação.
Binius propôs uma solução inovadora que trata esses dois problemas separadamente e realiza a representação dos mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariados ( especificamente polinômios multilineares ) em vez de polinômios univariados, 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 expansão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser visto como um quadrado ), baseado no qual a expansão de Reed-Solomon pode ser realizada. Este método, ao garantir a segurança, melhora significativamente a eficiência de 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 Teórica da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): O PIOP, como núcleo do sistema de provas, transforma as relações computacionais de entrada em igualdades polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios gradualmente através da interação com o verificador, de modo que o verificador possa validar se o cálculo está correto consultando os resultados da avaliação de poucos 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, impactando 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 é usado 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 o resultado da avaliação desse polinômio, enquanto oculta outras informações do polinômio. Alguns esquemas de compromisso polinomial 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: combinando PLONK PIOP e Bulletproofs PCS, baseado na curva Pasta. O Halo2 foi projetado com foco na escalabilidade e na eliminação do trusted setup do protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado com FRI PCS e é baseado 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 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 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, 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 (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 produtos e permutações do HyperPlonk em seu protocolo de prova Oracle interativa (PIOP), garantindo verificações de consistência seguras e eficientes entre variáveis e suas permutações. Terceiro, o protocolo introduziu uma nova prova de deslocamento multilinear, otimizando a eficiência na validação de relações multilineares em pequenos campos. Quarto, Binius adotou uma versão aprimorada da prova de busca Lasso, proporcionando flexibilidade e forte segurança ao mecanismo de busca. Por fim, o protocolo utiliza um esquema de compromisso polinomial de pequenos campos (Small-Field PCS), permitindo a implementação de um sistema de provas eficiente no campo binário e reduzindo a sobrecarga normalmente associada a grandes campos.
( 2.1 Domínio Finito: Arithmetização baseada em torres de campos binários
Os domínios 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 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 apoia um processo de aritmética simplificada, onde as operações realizadas sobre o 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 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 um elemento no domínio binário. Por exemplo, no mais básico domínio binário 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 podem fornecer essa representação canônica dentro de um número fixo de bits. Embora um domínio primo de 32 bits possa caber em 32 bits, nem toda string de 32 bits pode corresponder de forma única a um elemento de domínio, enquanto o domínio binário oferece 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 ( usada na Tower ). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" observa 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 do domínio binário. Pode ser vista como um elemento único no domínio binário de 128 bits ou ser analisada como dois elementos do domínio de torre de 64 bits, quatro elementos do domínio de torre de 32 bits, 16 elementos do domínio de torre de 8 bits, ou 128 elementos do domínio F2. Essa flexibilidade de representação não requer nenhum custo computacional, apenas a conversão de tipo da string de bits (typecast), o que é uma propriedade muito interessante e útil. Ao mesmo tempo, os elementos de domínio pequenos podem ser empacotados em elementos de domínio maiores sem 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 das operações de multiplicação, quadrado e inversão em subdomínios de m bits ( no domínio binário de torre de n bits.
![Bitlayer Research: Análise dos princípios STARKs da Binius e suas reflexões sobre otimização])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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 se baseia no HyperPlonk, utilizando uma série de mecanismos de verificação fundamentais para validar a correção de polinômios e conjuntos multivariados. Essas verificações fundamentais incluem:
GateCheck: Verificar 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 da permutação entre as variáveis do polinómio.
LookupCheck: validar se a avaliação do polinômio está na tabela de consulta dada, ou seja, f(Bµ) ⊆ T)Bµ(, garantindo que certos valores estejam dentro do intervalo especificado.
MultisetCheck: Verifica se dois conjuntos multivariados são iguais, ou seja, {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantindo a consistência entre múltiplos conjuntos.
ProductCheck: verificar se a avaliação de um polinômio racional no hipercubo booleano é igual a um valor declarado ∏x∈Hµ f)x( = s, para garantir a correção do produto polinomial.
ZeroCheck: Verificar se um polinómio multivariável em um hipercubo booleano é zero em qualquer ponto ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, para garantir a distribuição dos zeros do polinómio.
SumCheck: Detecta 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 do verificador. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios para construir combinações lineares e realizar o processamento em lote de várias instâncias de verificação de soma.
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.
Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius faz 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 o produto deve ser igual a um valor específico; a Binius simplifica esse processo de verificação ao especializar esse valor para 1, reduzindo assim a complexidade computacional.
Tratamento do problema de divisão por zero: HyperPlonk não conseguiu lidar adequadamente com a situação de divisão por zero, levando à impossibilidade de afirmar que U é não nulo no hipercubo; Binius tratou corretamente deste 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 de Colunas: HyperPlonk não possui esta funcionalidade; Binius suporta a Verificação de Permutação entre várias colunas, o que permite ao Binius lidar com situações de arranjo polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através da melhoria do mecanismo existente PIOPSumCheck, especialmente ao lidar com a validação de polinómios multivariáveis mais complexos, oferecendo um suporte funcional mais forte. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram as bases para futuros sistemas de prova baseados em campos binários.
![Bitlayer Research: Análise dos princípios STARKs da Binius e reflexão sobre a otimização])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: novo argumento de mudança multilateral------aplicável ao hipercubo booleano
No protocolo Binius, a construção e o processamento de polinómios virtuais são uma das tecnologias-chave, capazes de gerar e operar eficazmente polinómios derivados de manipuladores de entrada ou de outros polinómios virtuais. Aqui estão dois métodos-chave: