Análise dos princípios do Binius STARKs e reflexão sobre a sua otimização

1 Introdução

Uma das principais razões para a baixa eficiência dos STARKs é que a maioria dos valores em programas reais é bastante pequena, mas para garantir a segurança da prova baseada em árvores de Merkle, muitos valores de redundância adicionais ocupam todo o domínio ao expandir os dados usando a codificação de Reed-Solomon. Para resolver esse problema, reduzir o tamanho do domínio tornou-se uma estratégia chave.

A largura de codificação dos STARKs de primeira geração é de 252 bits, a de segunda geração é de 64 bits, e a de terceira 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 quarta geração.

Quando se utiliza um domínio menor, a operação de expansã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 expansã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 expansão de domínio, operando apenas no domínio base, o que permite 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 um domínio de expansão maior para garantir a segurança necessária.

A Binius propôs uma solução inovadora que lida com esses dois problemas separadamente e representa os mesmos dados de duas maneiras diferentes: primeiro, utilizando polinômios multivariáveis (especificamente polinômios multilineares) em vez de polinômios univariáveis, representando toda a trajetória de cálculo através dos seus valores em "hipercubos" (hypercubes); em segundo lugar, devido ao comprimento de cada dimensão do hipercubo ser 2, não é possível realizar a extensão padrão de Reed-Solomon como nos STARKs, mas o hipercubo pode ser considerado como quadrado, permitindo a extensão de Reed-Solomon com base nesse quadrado. Este método, enquanto garante a segurança, melhora significativamente a eficiência de codificação e o desempenho computacional.

2 Análise dos Princípios

Binius: HyperPlonk PIOP + Brakedown PCS + domínio binário. Especificamente, Binius inclui cinco tecnologias chave para alcançar sua eficiência e segurança:

1. Arithmetização baseada em torres de campos binários
2. Adaptou a verificação de produto e permutação do HyperPlonk
3. Nova prova de deslocamento multivariado
4. Versão aprimorada da prova de busca Lasso
5. Esquema de Compromisso de Polinómios de Pequeno Campo (Small-Field PCS)

2.1 Domínio Finito: Arithmetização baseada em torres de campos binários

O domínio binário em forma de torre é a chave para a realização de cálculos rápidos e verificáveis, devido a dois aspectos principais: cálculo eficiente e aritmética eficiente. O domínio binário suporta essencialmente operações aritméticas altamente eficientes, tornando-o uma escolha ideal para aplicações criptográficas sensíveis ao desempenho. Além disso, a estrutura do domínio binário suporta um processo de aritmética simplificado, ou seja, as operações realizadas sobre o domínio binário podem ser representadas de forma compacta e de fácil verificação em forma algébrica.

2.2 PIOP: versão adaptada do Produto HyperPlonk e Verificação de Permutação

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. Esses mecanismos de verificação essenciais incluem:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Binius fez melhorias nas seguintes 3 áreas:

• Otimização do ProductCheck
• Tratamento do problema de divisão por zero
• Verificação de Permutação em Colunas

2.3 PIOP: novo argumento de deslocamento multilinear

No protocolo Binius, a construção e o tratamento de polinómios virtuais são uma das tecnologias-chave, incluindo principalmente dois métodos:

• Embalagem
• Operador de deslocamento

2.4 PIOP: versão adaptada do argumento de busca Lasso

O protocolo Lasso é composto pelos seguintes três componentes:

• Abstração de polinômios virtuais em grandes tabelas
• Pesquisa de tabela pequena
• Verificação de múltiplos conjuntos

O protocolo Binius adapta o Lasso à operação no domínio binário, introduzindo a versão de multiplicação do protocolo Lasso.

2.5 PCS：versão adaptada Brakedown PCS

A ideia central da construção do BiniusPCS é packing. O compromisso polinomial Binius utiliza principalmente:

• Compromissos de polinômios de pequeno domínio e avaliação de domínio expandido
• Construção de Domínio Pequeno
• Codificação de bloco e código de Reed-Solomon

3 Otimização do Pensamento

Para melhorar ainda mais o desempenho do protocolo Binius, este artigo apresenta quatro pontos-chave de otimização:

1. PIOP baseado em GKR: para operações de multiplicação em domínio binário
2. ZeroCheck PIOP otimização: ponderação do custo computacional entre Prover e Verifier
3. Otimização do Sumcheck PIOP: otimização para o Sumcheck de pequeno domínio
4. Otimização PCS: Redução do tamanho da prova através da otimização FRI-Binius

3.1 PIOP baseado em GKR: multiplicação de domínio binário baseada em GKR

O algoritmo de multiplicação inteira baseado em GKR converte a verificação "se 2 inteiros de 32 bits A e B satisfazem 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: equilíbrio entre o custo de cálculo do Prover e do Verifier

Principalmente inclui as seguintes direções de otimização:

• Reduzir a transferência de dados da parte comprovadora
• Reduzir o número de pontos de avaliação do provador
• Otimização de interpolação algébrica

3.3 Sumcheck PIOP otimização: protocolo Sumcheck baseado em pequenos domínios

Os principais pontos de otimização incluem:

• Impacto e fator de melhoria na mudança de rodada
• O impacto do tamanho do domínio na performance
• Benefícios da otimização do algoritmo de Karatsuba
• Melhoria da eficiência de memória

3.4 PCS otimização: FRI-Binius reduz o tamanho da prova do Binius

A FRI-Binius implementou o mecanismo de dobra de domínio binário FRI, trazendo inovações em 4 áreas:

• Polinómio achatado
• Polinômio de desaparecimento de subespaço
• Empacotamento de base algébrica
• Troca de Anéis SumCheck

4 Resumo

A proposta de valor da Binius é que pode usar o menor domínio power-of-two para testemunhas, permitindo assim escolher o tamanho do domínio apenas com base no que é necessário. A Binius é uma solução de design colaborativo que utiliza "hardware, software e o protocolo Sumcheck acelerado por FPGA", permitindo provas rápidas com um consumo de memória muito baixo.

O Binius já removeu basicamente o gargalo do compromisso Prover, e o novo gargalo reside no protocolo Sumcheck, onde problemas como avaliações de polinômios e multiplicações de campo podem ser resolvidos de forma eficiente com o uso de hardware especializado. A solução FRI-Binius é uma variante do FRI, que oferece uma opção muito atraente - eliminar os custos de incorporação na camada de prova de campo, sem causar um aumento exorbitante nos custos da camada de prova agregada.

Atualmente, a equipe Irreducible está desenvolvendo sua camada recursiva e anunciou uma parceria com a equipe Polygon para construir um zkVM baseado em Binius; o JoltzkVM está fazendo a transição de Lasso para Binius para melhorar seu desempenho recursivo; a equipe Ingonyama está implementando a versão FPGA do Binius.