Análise dos Princípios dos STARKs da Binius e Reflexões 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 é relativamente pequena, mas para garantir a segurança das provas baseadas em árvores de Merkle, muitos valores redundantes adicionais ocupam todo o domínio quando os dados são expandidos usando codificação de Reed-Solomon. Reduzir o tamanho do domínio tornou-se uma estratégia crucial.

A largura de codificação da 1ª geração de STARKs é 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 uma grande quantidade de espaço desperdiçado. O domínio binário permite operações diretas sobre os bits, com codificação compacta e eficiente, sem desperdício de espaço, ou seja, a 4ª geração de STARKs.

Binius adotou as seguintes tecnologias principais:

• Arithmetização baseada em domínios binários em forma de torre
• Versão melhorada da verificação de produto e permutação HyperPlonk
• Nova prova de deslocamento multivariável
• Versão aprimorada da prova de busca Lasso
• Esquema de compromisso polinomial de pequeno domínio

2. Análise do Princípio

2.1 Arithmetização baseada em torres de campos binários

O domínio binário em torre suporta operações aritméticas altamente eficientes, sendo a chave para a realização de cálculos rapidamente verificáveis. As suas vantagens incluem:

• Cálculo eficiente
• Arithmética eficiente
• Suporta processos aritméticos simplificados
• Pode aproveitar plenamente as suas características hierárquicas através da estrutura em torre.

2.2 Versão adaptada do Produto HyperPlonk e Verificação de Permutação

Binius melhorou o HyperPlonk nas seguintes áreas:

• ProductCheck otimizado: especializar o valor para 1, simplificar o processo de verificação
• Tratamento do problema da divisão por zero: mesmo que o denominador seja zero, o processamento pode continuar.
• Verificação de Permutação entre Colunas: suporta a verificação de permutação entre várias colunas

2.3 novo argumento de deslocamento multilinhar

Binius introduziu dois métodos-chave:

• Embalagem: Otimizar operações através da embalagem de elementos adjacentes
• Operador de deslocamento: reorganiza os elementos dentro do bloco com base no deslocamento fornecido.

2.4 versão adaptada do argumento de busca Lasso

A Binius adaptou o Lasso para operações em domínios binários, introduzindo a versão de multiplicação do protocolo Lasso. A parte que prova deve comprometer-se a um vetor de contagem de leitura que é sempre não nulo, para garantir a segurança do protocolo.

2.5 versão adaptada Brakedown PCS

A Binius oferece duas soluções de compromisso polinomial Brakedown baseadas em domínios binários:

• Instanciação de código concatenado
• Utiliza tecnologia de codificação a nível de bloco, suportando o uso independente de códigos Reed-Solomon

3. Otimização do Pensamento

3.1 PIOP baseado em GKR

A operação de multiplicação no domínio binário baseada em GKR requer apenas um compromisso auxiliar, aumentando a eficiência ao reduzir os custos de Sumchecks.

3.2 ZeroCheck PIOP otimização

Foram propostas várias soluções de otimização ajustando a alocação de carga de trabalho entre a parte que prova e a parte que valida:

• Reduzir a transmissão de dados do provedor de prova
• Reduzir o número de pontos de avaliação do provedor de provas
• Otimização de Interpolação Algébrica

3.3 Sumcheck PIOP otimização

Ingonyama propôs uma melhoria para o protocolo Sumcheck baseado em pequenos domínios:

• A seleção de mudança de rodada afeta o desempenho
• Domínios de base menores mostram vantagens mais significativas
• O algoritmo de Karatsuba melhorou o desempenho
• A eficiência de memória foi melhorada

3.4 PCS otimização: FRI-Binius

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

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

4. Resumo

A Binius remove o gargalo do compromisso do Prover, e o novo gargalo está no protocolo Sumcheck. O esquema FRI-Binius é uma variante do FRI, que pode eliminar o custo de incorporação da camada de prova de domínio. Atualmente, várias equipes estão desenvolvendo aplicações relacionadas ao Binius.