Análise dos princípios STARKs da Binius e considerações sobre a otimização
1 Introdução
Uma das principais razões para a ineficiência dos STARKs é que a maioria dos valores em programas reais é bastante pequena, mas, para garantir a segurança das provas baseadas em árvores de Merkle, ao expandir os dados usando codificação de Reed-Solomon, muitos valores redundantes adicionais ocupam todo o campo. Para resolver esse problema, reduzir o tamanho do campo tornou-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 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 nos bits, com codificação compacta e eficiente, sem qualquer desperdício de espaço, ou seja, os STARKs de 4ª geraçã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 completamente da extensão de domínio para garantir 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, permitindo assim uma alta eficiência no domínio pequeno. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam ser aprofundados em uma extensão de domínio maior 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 fazer o compromisso da árvore Merkle em STARKs, é necessário realizar 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 trata essas duas questões separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinómios multivariados (especificamente, polinómios multilineares) em vez de polinómios unidimensionais, representando toda a trajetória computacional através dos seus valores em "hipercubos"; em segundo lugar, dado que cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas é possível considerar o hipercubo como quadrado, realizando a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir segurança, melhora significativamente a eficiência da codificação e o desempenho computacional.
2 Análise de Princípios
A construção da maioria dos sistemas SNARKs atualmente normalmente inclui as seguintes duas partes:
Prova de Oracle Interativa Polinomial Teórica da Informação (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP)
Esquema de Compromisso Polinomial (Polynomial Commitment Scheme, PCS)
Binius: HyperPlonk PIOP + Brakedown PCS + domínio binário. Especificamente, Binius inclui cinco tecnologias chave para alcançar sua eficiência e segurança:
Arithmetização baseada em domínios binários em torre
Verificação de produto e permutação da versão adaptada do HyperPlonk
Nova prova de deslocamento multilateral
Versão melhorada da busca Lasso
Esquema de compromisso polinomial de pequeno domínio
2.1 Campos finitos: aritmética 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, devido principalmente a dois aspectos: cálculo eficiente e aritmética eficiente. Os campos binários, em essência, suportam 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 dos campos binários suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre os campos binários podem ser expressas em uma forma algébrica compacta e fácil de verificar.
No campo de 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 domínios finitos específicos como Mersenne-31 ou Goldilocks-64. No campo binário F2k, os métodos de redução comumente utilizados incluem redução especial (como a utilizada no AES), redução Montgomery (como a utilizada no POLYVAL) e redução recursiva (como a utilizada na Tower).
O domínio binário não requer o transporte tanto em adição como em multiplicação, e a operação de quadrado no domínio binário é muito eficiente, pois segue a regra simplificada de (X + Y )2 = X2 + Y 2.
2.2 PIOP: versão adaptada do Produto HyperPlonk e PermutationCheck
O design PIOP no protocolo Binius é inspirado no HyperPlonk, utilizando uma série de mecanismos de verificação essenciais para validar a correção de polinômios e conjuntos multivariados. Esses mecanismos de verificação essenciais incluem:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius fez as seguintes melhorias em comparação com o HyperPlonk:
Otimização do ProductCheck
Tratamento do problema de divisão por zero
Verificação de Permutação Cruzada
2.3 PIOP: novo argumento de desvio multilinear
No protocolo Binius, a construção e o tratamento 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
Operador de deslocamento
2.4 PIOP: versão adaptada do argumento de busca Lasso
O protocolo Lasso permite que a parte que prova comprometa um vetor a ∈ Fm e prove que todos os seus elementos estão presentes em uma tabela previamente especificada t ∈ Fn. O protocolo Lasso é composto pelos seguintes três componentes:
Abstração de polinômios virtuais de grandes tabelas
Pesquisa de pequenas tabelas
Verificação de múltiplas coleções
O protocolo Binius adapta o Lasso para operações em domínios binários, introduzindo uma versão de multiplicação do protocolo Lasso.
2.5 PCS：Versão adaptada Brakedown PCS
A ideia central da construção do BiniusPCS é o packing. O artigo do Binius apresenta duas propostas de compromisso polinomial Brakedown baseadas em domínios binários:
Utilizar código concatenado para instanciar
Utilizando a tecnologia de codificação a nível de bloco, suporta o uso separado de códigos de Reed-Solomon
Binius compromisso polinomial utiliza principalmente as seguintes tecnologias:
Compromissos de polinómios de pequeno domínio e avaliação de domínio expandido
Estrutura Genérica de Domínio Pequeno
Codificação em bloco e código de Reed-Solomon
3 Otimização do pensamento
Para melhorar ainda mais o desempenho do protocolo Binius, este artigo propõe quatro pontos-chave de otimização:
PIOP baseado em GKR: para operações de multiplicação em domínios binários
Otimização do ZeroCheck PIOP: Avaliação de custos computacionais entre Prover e Verifier.
Otimização do PIOP Sumcheck: otimização para Sumcheck em pequenos domínios
Otimização PCS: através da otimização FRI-Binius
3.1 PIOP baseado em GKR: multiplicação de campo binário baseada em GKR
O algoritmo de multiplicação de inteiros baseado no GKR transforma a verificação "A·B =? C" para "verificar se (gA)B =? gC é válido", reduzindo significativamente o custo de compromisso com a ajuda do protocolo GKR.
3.2 ZeroCheck PIOP otimização: balanceamento do custo de cálculo entre Prover e Verifier
O artigo "Some Improvements for the PIOP for ZeroCheck" propõe várias soluções de otimização para ajustar a distribuição da carga de trabalho entre a parte que prova (P) e a parte que valida (V), a fim de equilibrar os custos. As principais otimizações incluem:
Reduzir a transferência de dados do provador
Reduzir o número de pontos de avaliação do provedor de prova
Otimização de Interpolação Algébrica
3.3 Verificação de Soma PIOP otimizada: protocolo de verificação de soma baseado em pequenos domínios
Ingonyama propôs em 2024 uma solução de melhoria para o protocolo Sumcheck baseado em pequenos domínios e disponibilizou o código de implementação como código aberto. As principais otimizações incluem:
O impacto da mudança de rodada e o fator de melhoria
O impacto do tamanho do domínio no desempenho
Benefícios da otimização do algoritmo Karatsuba
Melhoria da eficiência da memória
3.4 PCS otimização: FRI-Binius reduz o tamanho da prova de Binius
O artigo "Provas Polilogarítmicas para Multilineares sobre Torres Binárias", abreviado como FRI-Binius, implementou o mecanismo de dobra FRI sobre o domínio binário, trazendo 4 inovações em diferentes aspectos:
Polinômio achatado
Polinômio de desaparecimento do subespaço
Empacotamento de base algébrica
Troca de Anéis SumCheck
Com o FRI-Binius, é possível reduzir a dimensão da prova de Binius em uma ordem de magnitude.
4 Resumo
Binius é uma solução de design colaborativo que utiliza "hardware, software e o protocolo Sumcheck acelerado em FPGA", permitindo provas rápidas com uma taxa de uso de memória muito baixa. No Binius, o gargalo de compromisso do Prover foi praticamente eliminado, e o novo gargalo reside no protocolo Sumcheck, onde muitos problemas de avaliações de polinômios e multiplicação de campos podem ser resolvidos de forma eficiente com hardware dedicado.
A solução FRI-Binius, uma variante do FRI, oferece uma opção muito atraente – eliminar os custos de incorporação da camada de prova de domínio, sem levar a um aumento dos custos na camada de prova agregada. Atualmente, a equipe Irreducible está desenvolvendo sua camada recursiva e anunciou uma colaboração com a equipe da Polygon para construir um zkVM baseado em Binius; o JoltzkVM está mudando de Lasso para Binius para melhorar seu desempenho recursivo; a equipe Ingonyama está implementando uma versão FPGA do Binius.
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.
26 gostos
Recompensa
26
8
Republicar
Partilhar
Comentar
0/400
AirdropF5Bro
· 13h atrás
Oh oh, esta onda do starknet, hein?
Ver originalResponder0
¯\_(ツ)_/¯
· 08-12 16:41
Esta otimização está muito forte, de 252 para binário.
Ver originalResponder0
SerumSquirter
· 08-10 20:16
A eficiência está a aumentar e o domínio está a diminuir.
Ver originalResponder0
GateUser-afe07a92
· 08-10 09:35
Que chatice, próximo.
Ver originalResponder0
ForkTongue
· 08-10 09:20
Escreveu muito bem, mas o profissional não entendeu...
Ver originalResponder0
NullWhisperer
· 08-10 09:16
hmm... a otimização de campo binário parece teoricamente elegante, mas vamos falar sobre aqueles casos limites nas operações de campo de extensão...
Ver originalResponder0
HalfBuddhaMoney
· 08-10 09:15
Há quanto tempo não traduzo o domínio de largura zero? Desta vez vou deixar claro.
Ver originalResponder0
NonFungibleDegen
· 08-10 09:08
ser esta coisa marcante é baseada em... binários = número vai subir, finalmente algum alfa real, não este cope da merkle tree
Análise dos Princípios dos STARKs Binius: Otimização do Domínio Binário e Compromissos Polinómicos Eficientes
Análise dos princípios STARKs da Binius e considerações sobre a otimização
1 Introdução
Uma das principais razões para a ineficiência dos STARKs é que a maioria dos valores em programas reais é bastante pequena, mas, para garantir a segurança das provas baseadas em árvores de Merkle, ao expandir os dados usando codificação de Reed-Solomon, muitos valores redundantes adicionais ocupam todo o campo. Para resolver esse problema, reduzir o tamanho do campo tornou-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 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 nos bits, com codificação compacta e eficiente, sem qualquer desperdício de espaço, ou seja, os STARKs de 4ª geraçã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 completamente da extensão de domínio para garantir 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, permitindo assim uma alta eficiência no domínio pequeno. No entanto, a verificação de pontos aleatórios e o cálculo FRI ainda precisam ser aprofundados em uma extensão de domínio maior 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 fazer o compromisso da árvore Merkle em STARKs, é necessário realizar 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 trata essas duas questões separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinómios multivariados (especificamente, polinómios multilineares) em vez de polinómios unidimensionais, representando toda a trajetória computacional através dos seus valores em "hipercubos"; em segundo lugar, dado que cada dimensão do hipercubo tem comprimento 2, não é possível realizar uma extensão padrão de Reed-Solomon como nos STARKs, mas é possível considerar o hipercubo como quadrado, realizando a extensão de Reed-Solomon com base nesse quadrado. Este método, ao garantir segurança, melhora significativamente a eficiência da codificação e o desempenho computacional.
2 Análise de Princípios
A construção da maioria dos sistemas SNARKs atualmente normalmente inclui as seguintes duas partes:
Binius: HyperPlonk PIOP + Brakedown PCS + domínio binário. Especificamente, Binius inclui cinco tecnologias chave para alcançar sua eficiência e segurança:
2.1 Campos finitos: aritmética 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, devido principalmente a dois aspectos: cálculo eficiente e aritmética eficiente. Os campos binários, em essência, suportam 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 dos campos binários suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre os campos binários podem ser expressas em uma forma algébrica compacta e fácil de verificar.
No campo de 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 domínios finitos específicos como Mersenne-31 ou Goldilocks-64. No campo binário F2k, os métodos de redução comumente utilizados incluem redução especial (como a utilizada no AES), redução Montgomery (como a utilizada no POLYVAL) e redução recursiva (como a utilizada na Tower).
O domínio binário não requer o transporte tanto em adição como em multiplicação, e a operação de quadrado no domínio binário é muito eficiente, pois segue a regra simplificada de (X + Y )2 = X2 + Y 2.
2.2 PIOP: versão adaptada do Produto HyperPlonk e PermutationCheck
O design PIOP no protocolo Binius é inspirado no HyperPlonk, utilizando uma série de mecanismos de verificação essenciais para validar a correção de polinômios e conjuntos multivariados. Esses mecanismos de verificação essenciais incluem:
Binius fez as seguintes melhorias em comparação com o HyperPlonk:
2.3 PIOP: novo argumento de desvio multilinear
No protocolo Binius, a construção e o tratamento 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:
2.4 PIOP: versão adaptada do argumento de busca Lasso
O protocolo Lasso permite que a parte que prova comprometa um vetor a ∈ Fm e prove que todos os seus elementos estão presentes em uma tabela previamente especificada t ∈ Fn. O protocolo Lasso é composto pelos seguintes três componentes:
O protocolo Binius adapta o Lasso para operações em domínios binários, introduzindo uma versão de multiplicação do protocolo Lasso.
2.5 PCS：Versão adaptada Brakedown PCS
A ideia central da construção do BiniusPCS é o packing. O artigo do Binius apresenta duas propostas de compromisso polinomial Brakedown baseadas em domínios binários:
Binius compromisso polinomial utiliza principalmente as seguintes tecnologias:
3 Otimização do pensamento
Para melhorar ainda mais o desempenho do protocolo Binius, este artigo propõe quatro pontos-chave de otimização:
3.1 PIOP baseado em GKR: multiplicação de campo binário baseada em GKR
O algoritmo de multiplicação de inteiros baseado no GKR transforma a verificação "A·B =? C" para "verificar se (gA)B =? gC é válido", reduzindo significativamente o custo de compromisso com a ajuda do protocolo GKR.
3.2 ZeroCheck PIOP otimização: balanceamento do custo de cálculo entre Prover e Verifier
O artigo "Some Improvements for the PIOP for ZeroCheck" propõe várias soluções de otimização para ajustar a distribuição da carga de trabalho entre a parte que prova (P) e a parte que valida (V), a fim de equilibrar os custos. As principais otimizações incluem:
3.3 Verificação de Soma PIOP otimizada: protocolo de verificação de soma baseado em pequenos domínios
Ingonyama propôs em 2024 uma solução de melhoria para o protocolo Sumcheck baseado em pequenos domínios e disponibilizou o código de implementação como código aberto. As principais otimizações incluem:
3.4 PCS otimização: FRI-Binius reduz o tamanho da prova de Binius
O artigo "Provas Polilogarítmicas para Multilineares sobre Torres Binárias", abreviado como FRI-Binius, implementou o mecanismo de dobra FRI sobre o domínio binário, trazendo 4 inovações em diferentes aspectos:
Com o FRI-Binius, é possível reduzir a dimensão da prova de Binius em uma ordem de magnitude.
4 Resumo
Binius é uma solução de design colaborativo que utiliza "hardware, software e o protocolo Sumcheck acelerado em FPGA", permitindo provas rápidas com uma taxa de uso de memória muito baixa. No Binius, o gargalo de compromisso do Prover foi praticamente eliminado, e o novo gargalo reside no protocolo Sumcheck, onde muitos problemas de avaliações de polinômios e multiplicação de campos podem ser resolvidos de forma eficiente com hardware dedicado.
A solução FRI-Binius, uma variante do FRI, oferece uma opção muito atraente – eliminar os custos de incorporação da camada de prova de domínio, sem levar a um aumento dos custos na camada de prova agregada. Atualmente, a equipe Irreducible está desenvolvendo sua camada recursiva e anunciou uma colaboração com a equipe da Polygon para construir um zkVM baseado em Binius; o JoltzkVM está mudando de Lasso para Binius para melhorar seu desempenho recursivo; a equipe Ingonyama está implementando uma versão FPGA do Binius.