Análise dos princípios e reflexões de otimização do Binius STARKs

1. Introdução

Uma das principais razões para a ineficiência dos STARKs é que a maioria dos valores nos programas reais é bastante pequena. No entanto, para garantir a segurança da prova baseada em árvores de Merkle, ao expandir os dados com a codificação de Reed-Solomon, muitos valores de redundância adicionais ocupam todo o domínio. Reduzir o tamanho do domínio tornou-se uma estratégia crucial.

A largura de codificação dos STARKs da 1ª geração é de 252 bits, a da 2ª geração é de 64 bits e a da 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 bit a bit diretas, com codificação compacta e eficiente, sem desperdício de espaço, ou seja, os STARKs da 4ª geração.

Binius utiliza um domínio binário e depende completamente da extensão do domínio para garantir sua segurança e utilidade prática. A maioria dos polinômios envolvidos nos cálculos do Prover não precisa entrar na extensão do domínio, operando apenas no domínio base, o que permite uma alta eficiência em domínios pequenos. No entanto, as verificações de pontos aleatórios e os cálculos de FRI ainda precisam se aprofundar em uma extensão de domínio maior para garantir a segurança necessária.

Binius propôs uma solução inovadora: primeiro, usando polinómios multivariados (especificamente polinómios multiliniares) em vez de polinómios univariados, para representar toda a trajetória de cálculo através dos seus valores no "hipercubo"; em segundo lugar, considerando o hipercubo como quadrado, e baseado nesse quadrado, realizar a expansão de Reed-Solomon. Este método, enquanto assegura a segurança, melhora consideravelmente a eficiência de codificação e o desempenho computacional.

2. Análise do Princípio

Binius inclui cinco tecnologias-chave:

1. Arithmetização baseada em domínio binário em torre
2. Versão adaptada da verificação de produto e permutação do HyperPlonk
3. Nova Prova de Deslocamento Multilinear
4. Versão melhorada da prova de busca Lasso
5. Esquema de compromisso de polinômios de pequeno domínio

2.1 Domínio finito: aritmética baseada em torres de campos binários

O domínio binário em torre suporta operações aritméticas altamente eficientes, permitindo um processo aritmético simplificado. Os elementos do domínio binário têm uma representação única e direta, podendo ser convertidos e empacotados flexivelmente entre domínios de tamanhos diferentes.

2.2 PIOP: versão adaptada do produto HyperPlonk e PermutationCheck

Binius adotou uma série de mecanismos de verificação essenciais, incluindo GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck e BatchCheck.

Em comparação com o HyperPlonk, o Binius fez melhorias nas seguintes áreas:

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

2.3 PIOP: novo argumento de deslocamento multilinear

Binius utiliza dois métodos chave, Packing e operadores de deslocamento, para tratar polinómios virtuais.

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

O protocolo Lasso é composto por três componentes:

• Abstração de Polinômios Virtuais em Grande Escala
• Pesquisa em tabela pequena
• Verificação de múltiplos conjuntos

A Binius introduziu uma versão multiplicativa do protocolo Lasso, que exige que a parte que prova e a parte que valida aumentem conjuntamente a operação de "contagem de memória" do protocolo, não através de uma simples adição de 1, mas sim através do incremento utilizando geradores de multiplicação no campo binário.

2.5 PCS: versão adaptada Brakedown PCS

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 em bloco e tecnologia de código Reed-Solomon

3. Pensamento otimizado

3.1 PIOP baseado em GKR: multiplicação de campo binário baseada em GKR

O algoritmo de multiplicação de inteiros baseado em GKR, ao transformar "verificar se 2 inteiros de 32 bits A e B satisfazem A·B =? C" em "verificar se (gA)B =? gC é verdadeiro", reduz significativamente o custo de compromisso com a ajuda do protocolo GKR.

3.2 ZeroCheck PIOP otimização: Balanço de custos de cálculo entre Prover e Verifier

• Reduzir a transmissão de dados da parte comprovante
• 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

• Impacto e fator de melhoria da mudança de rodada
• O impacto do tamanho da base de domínio no desempenho
• 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 Binius

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

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

4. Resumo

A Binius remove praticamente todos os gargalos de compromisso do Prover, sendo que o novo gargalo está no protocolo Sumcheck. O esquema FRI-Binius é uma variante do FRI, que pode eliminar o custo de incorporação na camada de prova de campo. Atualmente, a equipe Irreducible está desenvolvendo sua camada recursiva e colaborando com a equipe Polygon para construir um zkVM baseado em Binius; o JoltzkVM está mudando de Lasso para Binius; a equipe Ingonyama está implementando a versão FPGA do Binius.