Análise dos princípios dos STARKs da Binius e reflexão sobre a otimização
1 Introdução
Ao contrário dos SNARKs baseados em curvas elípticas, os STARKs podem ser vistos como SNARKs baseados em hash. Atualmente, uma das principais razões para a ineficiência dos STARKs é: na maioria dos programas reais, a maioria dos valores numéricos é pequena, como índices de loop, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvore de Merkle, ao usar codificação de Reed-Solomon para expandir os dados, muitos valores redundantes ocupam todo o domínio, mesmo que os valores originais sejam pequenos. Para resolver esse problema, reduzir o tamanho do domínio torna-se uma estratégia chave.
A largura de codificação dos STARKs de 1ª geração é de 252 bits, a de 2ª geração é de 64 bits e a de 3ª geração é de 32 bits, mas a codificação de 32 bits ainda tem muito espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, com uma codificação compacta e eficiente, sem desperdício, podendo ser considerada a 4ª geração de STARKs.
Em comparação com os campos finitos recém-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 aplicados na criptografia, como o domínio AES(F28, o domínio GMAC)F2128 e a codificação Reed-Solomon do código QR(F28. O protocolo FRI original e o zk-STARK, bem como a função hash Grøstl, finalista do SHA-3, também são baseados no domínio F28.
Ao usar domínios menores, a operação de extensão torna-se cada vez mais importante para garantir a segurança. O domínio binário usado pela Binius depende completamente da extensão para garantir a segurança e a usabilidade. A maioria dos polinômios envolvidos nos cálculos do Prover só precisa operar 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 ser realizados em um domínio de extensão maior, a fim de garantir a segurança necessária.
Existem dois problemas práticos ao construir sistemas de prova baseados em domínios binários:
No cálculo da 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 do que o tamanho após a expansão da codificação.
A Binius propôs soluções inovadoras para lidar com esses dois problemas:
Usar um polinómio multivariável ) em vez de um polinómio univariável, representando todo o trajeto de cálculo através dos seus valores no "hipercubo".
Devido ao fato de que cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma expansão de Reed-Solomon padrão como nos STARKs, mas o hipercubo pode ser considerado como quadrado, e a expansão de Reed-Solomon pode ser baseada nesse quadrado.
Este método melhora significativamente a eficiência de codificação e o desempenho computacional, ao mesmo tempo que garante a segurança.
2 Análise dos Princípios
Atualmente, a maioria dos sistemas SNARKs geralmente contém duas partes:
Prova de oracle interativo polinomial da teoria da informação ( PIOP ):
Como núcleo do sistema de prova, transforma a relação de cálculo de entrada em igualdades polinomiais verificáveis. Através da interação com o verificador, o provador envia gradualmente polinômios, permitindo que o verificador valide a correção do cálculo avaliando o resultado de poucos polinômios por meio de consultas. Os protocolos PIOP existentes incluem PLONK PIOP, Spartan PIOP e HyperPlonk PIOP.
Esquema de compromisso polinomial (PCS):
Usado para provar se a igualdade polinomial gerada pelo PIOP é válida. PCS é uma ferramenta criptográfica, onde o provador pode se comprometer com um polinômio e verificar seu resultado de avaliação posteriormente, enquanto oculta outras informações do polinômio. Alguns PCS comuns incluem KZG, Bulletproofs, FRI e Brakedown.
De acordo com as necessidades, escolha diferentes PIOP e PCS, e combine com o campo finito ou a curva elíptica apropriada, podendo construir sistemas de prova com diferentes atributos. Por exemplo:
Arithmetização baseada em domínios binários em torre: constitui a base do cálculo, realizando operações simplificadas dentro do domínio binário.
Adaptação da verificação de consistência de produtos e permutações HyperPlonk: garantir a verificação de consistência eficiente entre variáveis e permutações.
Nova prova de deslocamento multilinelar: otimização da eficiência de verificação de relações multilinelares em pequenos domínios
Melhorar a prova de busca Lasso: fornecer flexibilidade e segurança ao mecanismo de busca
Esquema de compromisso de polinómios de pequeno domínio: implementar um sistema de provas eficiente sobre o domínio binário, reduzindo os custos associados a grandes domínios.
( 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários
Os campos binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido ao cálculo eficiente e à aritmética eficiente. Os campos binários suportam essencialmente operações aritméticas altamente eficientes, tornando-se uma escolha ideal para aplicações criptográficas sensíveis ao desempenho. A estrutura dos campos binários suporta um processo de aritmética simplificado, e as operações executadas sobre os campos binários podem ser representadas em uma forma algébrica compacta e facilmente verificável. Essas características, juntamente com a capacidade de aproveitar plenamente suas características hierárquicas através da estrutura em torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis como o Binius.
"canônico" refere-se à forma única e direta de representação de elementos no domínio binário. Por exemplo, no domínio binário básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do domínio binário de k bits. Isso é diferente do domínio primo, que não pode 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 possui essa conveniência de mapeamento um a um.
No campo dos números primos 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 campos finitos específicos como Mersenne-31 ou Goldilocks-64. No campo binário F2k, os métodos de redução utilizados frequentemente incluem a redução especial ) como o AES usa (, a redução Montgomery ) como o POLYVAL usa ### e a redução recursiva ( como Tower ).
O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que o campo binário não requer o transporte em operações de adição e multiplicação, e a operação de quadrado no campo binário é muito eficiente, pois segue a regra simplificada (X + Y)2 = X2 + Y2.
Uma string de 128 bits 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 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 sobrecarga computacional, apenas uma conversão de tipo da string de bits, sendo uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio menores 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.
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 que ( é decomposto em um subcampo de m bits dentro de um campo binário em torre de n bits.
![Bitlayer Research: Análise dos Princípios STARKs da Binius e Reflexões sobre a sua Otimização])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: versão adaptada do produto HyperPlonk e PermutationCheck------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:
GateCheck: verificar se o testemunho de segredo ω e a entrada pública x satisfazem a relação de cálculo do circuito C(x,ω)=0, garantindo 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)(, garantindo 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 múltiplos conjuntos.
ProductCheck: Verifica se a avaliação de um polinómio racional no hipercubo booleano é igual a um determinado valor declarado ∏x∈Hμ f)x( = s, garantindo a correção do produto do polinómio.
ZeroCheck: Verificar se um polinómio multivariável é zero em qualquer ponto no hipercubo booleano ∏x∈Hμ f)x( = 0, ∀x ∈ Bμ, garantindo a distribuição dos zeros do polinómio.
SumCheck: Verifica se a soma do 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-se 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 múltiplas 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.
Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius trouxe melhorias nas seguintes 3 áreas:
ProductCheck otimizado: 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; Binius simplificou este processo de verificação ao especializar esse valor para 1, reduzindo a complexidade computacional.
Tratamento de problemas 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 é diferente de zero no hipercubo; Binius tratou corretamente este problema, mesmo que o denominador seja zero, o ProductCheck do Binius ainda pode continuar a processar, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação entre Colunas: HyperPlonk não tem essa funcionalidade; Binius suporta a verificação de permutação entre várias colunas, permitindo que Binius lide com situações de arranjo polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através de melhorias no mecanismo existente PIOP SumCheck, especialmente ao lidar com a verificação de polinómios multivariáveis mais complexos, fornecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para sistemas de prova futuros baseados em domínios binários.
![Bitlayer Research: Análise dos Princípios STARKs da Binius e Reflexões sobre a Otimização])https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp(
) 2.3 PIOP: novo argumento de deslocamento multilinear ------ aplicável ao hiper-cubo booleano
No protocolo Binius, a construção e o manuseio de polinómios virtuais são uma das tecnologias chave, capazes 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:
Packing: Este método otimiza a operação agrupando elementos menores em posições adjacentes na ordem do dicionário em elementos maiores. O operador Pack é aplicado a blocos de tamanho 2κ e os combina em um único elemento em um domínio de alta dimensão. Através da Extensão Multilinear (Multilinear Extension, MLE), este polinômio virtual pode ser avaliado e processado de forma eficiente, convertendo a função t em outro polinômio, melhorando assim o desempenho computacional.
Operador de deslocamento: o operador de deslocamento reorganiza os elementos dentro do bloco, realizando um deslocamento cíclico com base na quantidade de deslocamento dada o. Este método é aplicável a blocos de tamanho 2b, onde cada bloco executa o deslocamento de acordo com a quantidade de deslocamento. O operador de deslocamento é definido através do suporte da função, garantindo consistência e eficiência ao lidar com polinômios virtuais. A complexidade de avaliação dessa construção cresce linearmente com o tamanho do bloco, sendo especialmente adequado para lidar com grandes conjuntos de dados ou cenários de alta dimensão em hipercubos booleanos.
2.4 PIOP: versão adaptada do argumento de pesquisa Lasso ------ aplicável ao domínio binário
O protocolo Lasso permite que a parte que prova se comprometa a um vetor a ∈ Fm e prove que todos os seus elementos existem em uma tabela pré-especificada t ∈ Fn. O Lasso desbloqueia o conceito de "lookup singularities" (lookup singularities) e pode ser aplicado a esquemas de compromisso de polinômios multilineares. A sua eficiência se reflete em dois aspectos:
Eficiência da prova: Para m buscas em uma tabela de tamanho n, o provador só precisa comprometer m+n elementos de domínio. Esses elementos de domínio são pequenos, todos pertencentes ao conjunto {0,...,m}. No esquema de compromisso baseado em múltiplas operações de potência, o custo computacional do provador é O(m + n) operações de grupo### como
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.
9 gostos
Recompensa
9
4
Republicar
Partilhar
Comentar
0/400
DeadTrades_Walking
· 7h atrás
A compressão de domínio começou a ser divertida!
Ver originalResponder0
zkProofInThePudding
· 7h atrás
Não tenho grandes habilidades, apenas ocupo um pouco de espaço.
Binius: Otimização e Inovação de STARKs Baseados em Domínio Binário
Análise dos princípios dos STARKs da Binius e reflexão sobre a otimização
1 Introdução
Ao contrário dos SNARKs baseados em curvas elípticas, os STARKs podem ser vistos como SNARKs baseados em hash. Atualmente, uma das principais razões para a ineficiência dos STARKs é: na maioria dos programas reais, a maioria dos valores numéricos é pequena, como índices de loop, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvore de Merkle, ao usar codificação de Reed-Solomon para expandir os dados, muitos valores redundantes ocupam todo o domínio, mesmo que os valores originais sejam pequenos. Para resolver esse problema, reduzir o tamanho do domínio torna-se uma estratégia chave.
A largura de codificação dos STARKs de 1ª geração é de 252 bits, a de 2ª geração é de 64 bits e a de 3ª geração é de 32 bits, mas a codificação de 32 bits ainda tem muito espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, com uma codificação compacta e eficiente, sem desperdício, podendo ser considerada a 4ª geração de STARKs.
Em comparação com os campos finitos recém-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 aplicados na criptografia, como o domínio AES(F28, o domínio GMAC)F2128 e a codificação Reed-Solomon do código QR(F28. O protocolo FRI original e o zk-STARK, bem como a função hash Grøstl, finalista do SHA-3, também são baseados no domínio F28.
Ao usar domínios menores, a operação de extensão torna-se cada vez mais importante para garantir a segurança. O domínio binário usado pela Binius depende completamente da extensão para garantir a segurança e a usabilidade. A maioria dos polinômios envolvidos nos cálculos do Prover só precisa operar 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 ser realizados em um domínio de extensão maior, a fim de garantir a segurança necessária.
Existem dois problemas práticos ao construir sistemas de prova baseados em domínios binários:
A Binius propôs soluções inovadoras para lidar com esses dois problemas:
Este método melhora significativamente a eficiência de codificação e o desempenho computacional, ao mesmo tempo que garante a segurança.
2 Análise dos Princípios
Atualmente, a maioria dos sistemas SNARKs geralmente contém duas partes:
Prova de oracle interativo polinomial da teoria da informação ( PIOP ): Como núcleo do sistema de prova, transforma a relação de cálculo de entrada em igualdades polinomiais verificáveis. Através da interação com o verificador, o provador envia gradualmente polinômios, permitindo que o verificador valide a correção do cálculo avaliando o resultado de poucos polinômios por meio de consultas. Os protocolos PIOP existentes incluem PLONK PIOP, Spartan PIOP e HyperPlonk PIOP.
Esquema de compromisso polinomial (PCS): Usado para provar se a igualdade polinomial gerada pelo PIOP é válida. PCS é uma ferramenta criptográfica, onde o provador pode se comprometer com um polinômio e verificar seu resultado de avaliação posteriormente, enquanto oculta outras informações do polinômio. Alguns PCS comuns incluem KZG, Bulletproofs, FRI e Brakedown.
De acordo com as necessidades, escolha diferentes PIOP e PCS, e combine com o campo finito ou a curva elíptica apropriada, podendo construir sistemas de prova com diferentes atributos. Por exemplo:
Binius inclui cinco tecnologias-chave:
Arithmetização baseada em domínios binários em torre: constitui a base do cálculo, realizando operações simplificadas dentro do domínio binário.
Adaptação da verificação de consistência de produtos e permutações HyperPlonk: garantir a verificação de consistência eficiente entre variáveis e permutações.
Nova prova de deslocamento multilinelar: otimização da eficiência de verificação de relações multilinelares em pequenos domínios
Melhorar a prova de busca Lasso: fornecer flexibilidade e segurança ao mecanismo de busca
Esquema de compromisso de polinómios de pequeno domínio: implementar um sistema de provas eficiente sobre o domínio binário, reduzindo os custos associados a grandes domínios.
( 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários
Os campos binários em torre são a chave para a implementação de cálculos rápidos e verificáveis, principalmente devido ao cálculo eficiente e à aritmética eficiente. Os campos binários suportam essencialmente operações aritméticas altamente eficientes, tornando-se uma escolha ideal para aplicações criptográficas sensíveis ao desempenho. A estrutura dos campos binários suporta um processo de aritmética simplificado, e as operações executadas sobre os campos binários podem ser representadas em uma forma algébrica compacta e facilmente verificável. Essas características, juntamente com a capacidade de aproveitar plenamente suas características hierárquicas através da estrutura em torre, tornam os campos binários particularmente adequados para sistemas de prova escaláveis como o Binius.
"canônico" refere-se à forma única e direta de representação de elementos no domínio binário. Por exemplo, no domínio binário básico F2, qualquer string de k bits pode ser mapeada diretamente para um elemento do domínio binário de k bits. Isso é diferente do domínio primo, que não pode 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 possui essa conveniência de mapeamento um a um.
No campo dos números primos 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 campos finitos específicos como Mersenne-31 ou Goldilocks-64. No campo binário F2k, os métodos de redução utilizados frequentemente incluem a redução especial ) como o AES usa (, a redução Montgomery ) como o POLYVAL usa ### e a redução recursiva ( como Tower ).
O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que o campo binário não requer o transporte em operações de adição e multiplicação, e a operação de quadrado no campo binário é muito eficiente, pois segue a regra simplificada (X + Y)2 = X2 + Y2.
Uma string de 128 bits 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 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 sobrecarga computacional, apenas uma conversão de tipo da string de bits, sendo uma propriedade muito interessante e útil. Ao mesmo tempo, elementos de domínio menores 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.
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 que ( é decomposto em um subcampo de m bits dentro de um campo binário em torre de n bits.
![Bitlayer Research: Análise dos Princípios STARKs da Binius e Reflexões sobre a sua Otimização])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: versão adaptada do produto HyperPlonk e PermutationCheck------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:
GateCheck: verificar se o testemunho de segredo ω e a entrada pública x satisfazem a relação de cálculo do circuito C(x,ω)=0, garantindo 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)(, garantindo 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 múltiplos conjuntos.
ProductCheck: Verifica se a avaliação de um polinómio racional no hipercubo booleano é igual a um determinado valor declarado ∏x∈Hμ f)x( = s, garantindo a correção do produto do polinómio.
ZeroCheck: Verificar se um polinómio multivariável é zero em qualquer ponto no hipercubo booleano ∏x∈Hμ f)x( = 0, ∀x ∈ Bμ, garantindo a distribuição dos zeros do polinómio.
SumCheck: Verifica se a soma do 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-se 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 múltiplas 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.
Apesar de Binius e HyperPlonk terem muitas semelhanças no design do protocolo, Binius trouxe melhorias nas seguintes 3 áreas:
ProductCheck otimizado: 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; Binius simplificou este processo de verificação ao especializar esse valor para 1, reduzindo a complexidade computacional.
Tratamento de problemas 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 é diferente de zero no hipercubo; Binius tratou corretamente este problema, mesmo que o denominador seja zero, o ProductCheck do Binius ainda pode continuar a processar, permitindo a generalização para qualquer valor de produto.
Verificação de Permutação entre Colunas: HyperPlonk não tem essa funcionalidade; Binius suporta a verificação de permutação entre várias colunas, permitindo que Binius lide com situações de arranjo polinomial mais complexas.
Assim, a Binius melhorou a flexibilidade e eficiência do protocolo através de melhorias no mecanismo existente PIOP SumCheck, especialmente ao lidar com a verificação de polinómios multivariáveis mais complexos, fornecendo um suporte funcional mais robusto. Essas melhorias não apenas resolveram as limitações do HyperPlonk, mas também estabeleceram uma base para sistemas de prova futuros baseados em domínios binários.
![Bitlayer Research: Análise dos Princípios STARKs da Binius e Reflexões sobre a Otimização])https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp(
) 2.3 PIOP: novo argumento de deslocamento multilinear ------ aplicável ao hiper-cubo booleano
No protocolo Binius, a construção e o manuseio de polinómios virtuais são uma das tecnologias chave, capazes 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:
Packing: Este método otimiza a operação agrupando elementos menores em posições adjacentes na ordem do dicionário em elementos maiores. O operador Pack é aplicado a blocos de tamanho 2κ e os combina em um único elemento em um domínio de alta dimensão. Através da Extensão Multilinear (Multilinear Extension, MLE), este polinômio virtual pode ser avaliado e processado de forma eficiente, convertendo a função t em outro polinômio, melhorando assim o desempenho computacional.
Operador de deslocamento: o operador de deslocamento reorganiza os elementos dentro do bloco, realizando um deslocamento cíclico com base na quantidade de deslocamento dada o. Este método é aplicável a blocos de tamanho 2b, onde cada bloco executa o deslocamento de acordo com a quantidade de deslocamento. O operador de deslocamento é definido através do suporte da função, garantindo consistência e eficiência ao lidar com polinômios virtuais. A complexidade de avaliação dessa construção cresce linearmente com o tamanho do bloco, sendo especialmente adequado para lidar com grandes conjuntos de dados ou cenários de alta dimensão em hipercubos booleanos.
2.4 PIOP: versão adaptada do argumento de pesquisa Lasso ------ aplicável ao domínio binário
O protocolo Lasso permite que a parte que prova se comprometa a um vetor a ∈ Fm e prove que todos os seus elementos existem em uma tabela pré-especificada t ∈ Fn. O Lasso desbloqueia o conceito de "lookup singularities" (lookup singularities) e pode ser aplicado a esquemas de compromisso de polinômios multilineares. A sua eficiência se reflete em dois aspectos: