Análise dos Princípios dos STARKs da Binius e Reflexões sobre a Otimização

1. Introdução

Uma das principais razões para a baixa eficiência dos STARKs é que a maioria dos números em programas reais é relativamente pequena, mas para garantir a segurança das provas baseadas em árvores de Merkle, ao usar a codificação Reed-Solomon para expandir os dados, muitos valores redundantes adicionais ocupam todo o domínio. Reduzir o tamanho do domínio tornou-se uma estratégia chave.

A largura de codificação da 1ª geração 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 um grande desperdício de espaço. Em comparação, o domínio binário permite operações diretas a nível de bits, com codificação compacta e eficiente, sem desperdício, ou seja, a 4ª geração STARKs.

Comparado com os domínios finitos como Goldilocks, BabyBear e Mersenne31 estudados nos últimos anos, a pesquisa sobre domínios binários remonta à década de 80 e tem sido amplamente aplicada na criptografia, como no domínio AES(F28, no domínio GMAC)F2128, no código Reed-Solomon para QR code(, entre outros.

A Binius utiliza o domínio binário, dependendo completamente da extensão do domínio para garantir segurança e disponibilidade. A maioria dos cálculos do Prover opera de forma eficiente no campo base, enquanto a verificação de pontos aleatórios e o cálculo FRI exigem uma extensão profunda do domínio para garantir segurança.

Binius representa a trajetória de cálculo através de polinómios multivariados em "hipercubo", tratando o hipercubo como quadrado para a extensão de Reed-Solomon, garantindo segurança enquanto melhora significativamente a eficiência de codificação e o desempenho computacional.

![Bitlayer Research: Análise dos princípios STARKs da Binius e reflexões sobre a otimização])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

2. Análise dos Princípios

Binius:HyperPlonk PIOP + Brakedown PCS + binário de domínio.

Inclui cinco tecnologias-chave:

1. Baseado na constituição aritmética do domínio binário em torre

2. Adaptar a verificação de produtos e permutações do HyperPlonk, garantindo a consistência das variáveis e das verificações de permutações

3. Nova prova de deslocamento multilinear, otimizando a eficiência da verificação de relações multilineares em pequenos domínios.

4. Versão melhorada da prova de busca Lasso, que oferece flexibilidade e segurança ao mecanismo de busca.

5. Esquema de compromisso de polinómios de pequeno domínio, implementando um sistema de provas eficiente sobre um domínio binário

) 2.1 Domínios Finitos: Arithmetização baseada em torres de campos binários

O domínio binário em torre suporta operações aritméticas eficientes e simplifica o processo de aritmética, sendo especialmente adequado para sistemas de prova escaláveis como o Binius.

Uma string de 128 bits pode ser vista como um elemento único em um domínio binário de 128 bits, ou pode ser analisada como dois elementos de domínio de 64 bits, quatro elementos de domínio de 32 bits, dezesseis elementos de domínio de 8 bits, ou 128 elementos de domínio F2. Essa flexibilidade não requer sobrecarga computacional, é apenas uma conversão de tipo da string de bits.

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

Binius PIOP baseia-se no HyperPlonk, adotando um mecanismo de verificação central para validar a correção de polinômios e conjuntos multivariáveis, incluindo GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck, BatchCheck.

Binius fez melhorias nas seguintes 3 áreas:

• Otimização do ProductCheck: especializar o valor em 1, simplificar o processo de verificação e reduzir a complexidade de cálculo

• Tratamento do problema de divisão por zero: tratar corretamente a situação em que o denominador é zero, permitindo a generalização para qualquer valor de produto.

• Verificação de Permutação em Múltiplas Colunas: suporta a verificação de permutação entre várias colunas, lidando com casos mais complexos de arranjos polinomiais.

( 2.3 PIOP: novo argumento de deslocamento multilinhar

A construção e manipulação de polinómios virtuais em Binius são tecnologias chave:

• Empacotamento: empacotar elementos de menor posição adjacente em um dicionário em elementos maiores para otimização de operações

• Operador de deslocamento: reorganiza os elementos dentro de um bloco, realizando um deslocamento cíclico com base no deslocamento fornecido.

![Bitlayer Research: Análise dos Princípios STARKs da Binius e Reflexões sobre sua Otimização])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp###

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

O protocolo Lasso permite que a parte que prova se comprometa com um vetor a ∈ Fm e comprove que todos os elementos existem em uma tabela t ∈ Fn previamente especificada.

Binius adapta o Lasso para operações em campos binários, introduzindo a versão multiplicativa do protocolo Lasso, que exige que a parte que prova e a parte que verifica realizem conjuntamente a operação de contagem de "memória" do protocolo de incremento, gerando incrementos a partir da multiplicação em campos binários.

( 2.5 PCS: versão adaptada Brakedown PCS

A ideia central da construção do BiniusPCS é o packing. Oferece 2 tipos de esquemas de compromisso de polinômios Brakedown baseados em domínios binários:

1. Instanciar o código concatenado

2. Utiliza a tecnologia de codificação a nível de bloco, suportando o uso independente de códigos de Reed-Solomon.

A segunda solução simplifica o processo de prova e verificação, o tamanho da prova é ligeiramente maior, mas as vantagens de simplificação e implementação valem a pena.

![Bitlayer Research: Análise do Princípio STARKs da Binius e Reflexões sobre sua Otimização])https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp###

3. Otimização do pensamento

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

Transformar "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.

A operação de multiplicação baseada em GKR requer apenas um compromisso auxiliar, tornando o algoritmo mais eficiente ao reduzir os custos de Sumchecks, especialmente em cenários onde a operação de Sumchecks é mais barata do que a geração de compromissos.

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

Reduzir a transmissão de dados do provador: transferir parte do trabalho para o verificante, diminuindo a quantidade de dados enviados pelo provador.

Reduzir o número de pontos de avaliação do provador: modificar o método de envio do polinómio, reduzindo o número de pontos de avaliação.

Otimização de interpolação algébrica: construir uma decomposição ordenada através da divisão longa de polinômios para realizar a otimização de interpolação.

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

O impacto e o fator de melhoria da mudança de rodadas: a escolha da mudança de rodadas t afeta o desempenho, e o fator de melhoria do ponto de mudança ideal atinge o valor máximo.

Impacto do tamanho do campo base no desempenho: o campo base menor (, como GF)###, apresenta vantagens mais significativas em algoritmos de otimização.

Otimização do algoritmo de Karatsuba: melhoria significativa no desempenho do Sumcheck baseado em pequenos domínios, o algoritmo 4 é cinco vezes mais eficiente que o algoritmo 3.

Melhoria na eficiência de memória: a demanda de memória do algoritmo 4 é O(d·t[2], enquanto o algoritmo 3 é O)2d·t(, adequado para ambientes com recursos limitados.

![Bitlayer Research: Análise do Princípio STARKs da Binius e Reflexões sobre a Otimização])https://img-cdn.gateio.im/webp-social/moments-1db509abaa79939b9e42dcf674a3845a.webp(

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

A FRI-Binius implementa o mecanismo de colapso de domínio binário FRI, trazendo 4 inovações:

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

Com o FRI-Binius, é possível reduzir o tamanho da prova Binius em uma ordem de magnitude, aproximando-se dos sistemas mais avançados.

4. Resumo

A Binius removeu basicamente o gargalo do compromisso Prover, o novo gargalo está no protocolo Sumcheck. O esquema FRI-Binius é uma variante do FRI, que pode eliminar o custo de incorporação do nível de prova do domínio.

A equipe Irreducible desenvolveu uma camada recursiva, em colaboração com a Polygon, para construir um zkVM baseado em Binius. O JoltzkVM mudou de Lasso para Binius para melhorar o desempenho recursivo. Ingonyama implementou a versão FPGA do Binius.

![Bitlayer Research：Binius STARKs原理解析及其优化思考]###https://img-cdn.gateio.im/webp-social/moments-124ffc8ca976b525ccb8efa8d5ad4af1.webp(