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 ineficiência dos STARKs é que a maioria dos valores nas aplicações reais é pequena, mas, para garantir a segurança das provas baseadas em árvores de Merkle, muitos valores de redundância adicionais ocupam todo o domínio ao usar codificação de Reed-Solomon para expandir os dados. Reduzir o tamanho do domínio tornou-se uma estratégia chave.

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 tem muito espaço desperdiçado. O domínio binário permite operações diretas em bits, com codificação compacta e eficiente sem espaço desperdiçado, podendo tornar-se a 4ª geração dos STARKs.

O domínio binário tem sido amplamente utilizado em criptografia, como AES, GMAC, códigos QR, FRI original e protocolos zk-STARK.

Ao usar o domínio binário, a Binius deve depender totalmente da extensão do domínio para garantir a segurança e a viabilidade prática. A maioria dos polinómios envolvidos nos cálculos do Prover não precisa entrar na extensão do domínio, mas pode operar apenas no domínio base, alcançando assim alta eficiência em um pequeno domínio.

Binius propôs uma solução inovadora:

1. usa polinómios multivariáveis em vez de polinómios univariáveis, representando toda a trajetória de cálculo através dos seus valores no "hipercubo".
2. considerar o hipercubo como quadrado para a extensão de Reed-Solomon

2 Análise de Princípios

Binius = HyperPlonk PIOP + Brakedown PCS + domínio binário

Inclui cinco tecnologias-chave:

1. Arithmetização baseada em domínios binários em torre
2. Adaptação da verificação de produto e permutação do HyperPlonk
3. nova prova de deslocamento multilinhar
4. Versão melhorada da Prova de Busca Lasso
5. Esquema de compromisso de polinômios de pequeno domínio

2.1 Campos finitos: aritmética baseada em torres de campos binários

O domínio binário em torre suporta operações aritméticas altamente eficientes e um processo aritmético simplificado.

Uma string de 128 bits pode ser vista como um elemento em um domínio binário de 128 bits, ou pode ser interpretada 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 de representação não requer sobrecarga de cálculo adicional.

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

O design PIOP no protocolo Binius é inspirado no HyperPlonk, utilizando uma série de mecanismos de verificação essenciais:

• GateCheck
• PermutationCheck
• LookupCheck
• MultisetCheck
• ProductCheck
• ZeroCheck
• SumCheck
• 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 de Colunas

2.3 PIOP: novo argumento de deslocamento multilinear

Métodos-chave para a construção e manipulação de polinómios virtuais no protocolo Binius:

• Embalagem
• Operador de deslocamento

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

O protocolo Lasso é composto por três componentes:

• Abstração de polinômios virtuais em um grande conjunto
• 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 multiplicativa do protocolo Lasso.

2.5 PCS: versão adaptada Brakedown PCS

O artigo Binius apresenta 2 esquemas de compromisso polinomial Brakedown baseados em domínios binários:

1. utiliza código concatenado para instanciar
2. utiliza a tecnologia de codificação a nível de bloco, suportando o uso independente de códigos de Reed-Solomon.

Compromissos polinomiais de pequeno domínio com avaliação de domínio ampliado, construção genérica de pequeno domínio e codificação em bloco com códigos de Reed-Solomon e outras tecnologias são utilizadas para construir o compromisso polinomial Binius.

3 Pensamento Otimizado

Quatro pontos chave de otimização:

1. PIOP baseado em GKR: para operações de multiplicação de domínio binário, substituindo o algoritmo Lasso Lookup com o protocolo GKR.

2. ZeroCheck PIOP otimização: Avaliação do custo computacional entre Prover e Verifier

3. Otimização do PIOP de Sumcheck: otimização para Sumcheck em pequenos domínios

4. Otimização PCS: Reduzir o 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 transforma a verificação "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 comprometimento com a ajuda do protocolo GKR.

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

Principais direções de otimização:

• Reduzir a transmissão de dados do provador
• 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

Principais pontos de otimização:

• Impacto e fator de melhoria da troca de rodadas
• O impacto do tamanho do domínio no desempenho
• Benefícios da otimização do algoritmo de Karatsuba
• Aumento da eficiência de memória

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

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

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

4 Resumo

A proposta de valor do Binius é permitir que os testemunhas utilizem o menor domínio de potência de dois. O compromisso de commit do Prover foi basicamente removido do Binius, e o novo gargalo reside no protocolo Sumcheck.

O FRI-Binius é uma variante do FRI que pode eliminar o custo de incorporação da camada de prova da domínio, sem causar um aumento drástico nos custos da camada de prova agregada.

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.