Análise e otimização do Binius STARKs

1. Introdução

Uma das principais razões para a ineficiência dos STARKs é que a maioria dos números em programas reais é bastante pequena, mas 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. Reduzir o tamanho do domínio torna-se uma estratégia crucial.

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 muito espaço desperdiçado. O domínio binário permite a manipulação direta dos bits, com codificação compacta e eficiente, sem espaço desperdiçado, o que pode ser a 4ª geração dos STARKs.

A Binius utiliza técnicas como a verificação de produtos e permutações de HyperPlonk, uma versão melhorada baseada em domínios binários em torre, e compromissos polinomiais de pequenos domínios para aumentar a eficiência de várias maneiras.

2. Análise dos Princípios

Binius é composto por cinco tecnologias-chave:

1. Arithmetização baseada em domínios binários em torre
2. Verificação de produto e permutação da versão adaptada do HyperPlonk
3. Nova prova de deslocamento multivariado
4. Versão melhorada da prova de busca Lasso
5. Esquema de compromisso polinomial de pequeno domínio

2.1 Baseado em domínios binários em forma de torre

O domínio binário em torre suporta operações aritméticas eficientes e um processo de aritmética simplificado. Os elementos do domínio binário podem ser mapeados diretamente para strings de k bits, com a conveniência de um mapeamento um a um.

2.2 versão adaptada da verificação de permutações e somas de produtos HyperPlonk

Binius baseou-se no mecanismo de verificação central do HyperPlonk, incluindo GateCheck, PermutationCheck, LookupCheck, e fez melhorias nas seguintes áreas:

• Otimização do ProductCheck
• Tratamento do problema da divisão por zero
• Verificação de Permutação Cruzada

2.3 Nova prova de deslocamento multivariado

Binius introduziu dois métodos-chave, Packing e operadores de deslocamento, para construir e manipular polinómios virtuais.

2.4 Versão adaptada da prova de busca Lasso

A Binius adaptou o Lasso para operações no domínio binário, introduzindo a versão multiplicativa do protocolo Lasso.

2.5 Compromisso de Polinômio de Baixa Dimensão

A Binius oferece duas soluções de compromisso polinomial Brakedown baseadas em domínios binários, utilizando principalmente compromissos polinomiais em pequenos domínios e avaliação em domínios expandidos, construção geral em pequenos domínios e codificação em blocos com tecnologia de códigos Reed-Solomon.

3. Otimização do Pensamento

3.1 PIOP baseado em GKR

Algoritmo de multiplicação de domínio binário baseado em GKR, convertendo "verificar se 2 inteiros de 32 bits A e B satisfazem A·B =? C" em "verificar se (gA)B =? gC é verdadeiro", reduzindo significativamente o custo de compromisso com o protocolo GKR.

3.2 ZeroCheck PIOP otimização

Foram propostas várias soluções de otimização através do ajuste da distribuição de trabalho entre a parte que prova e a parte que valida,

• Reduzir a transmissão 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 otimização

Ingonyama propôs uma melhoria para o protocolo Sumcheck baseado em pequenos domínios, focando na escolha da troca de rodadas t.

3.4 PCS otimização: FRI-Binius

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

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

4. Resumo

Binius é uma solução de design colaborativo que utiliza "hardware, software e o protocolo Sumcheck acelerado em FPGA", podendo provar rapidamente com uma taxa de utilização de memória muito baixa. No Binius, o gargalo de compromisso do Prover foi praticamente removido, e o novo gargalo está no protocolo Sumcheck, que pode ser resolvido de forma eficiente com hardware dedicado.

O plano FRI-Binius é uma variante do FRI que pode eliminar o custo de incorporação da camada de prova de domínio sem causar um aumento excessivo nos custos da camada de prova agregada. Atualmente, várias equipes estão desenvolvendo tecnologias relacionadas ao Binius, incluindo camadas recursivas, zkVM, entre outras.