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 é: na maioria dos programas práticos, a maior parte dos valores numéricos é pequena, mas para garantir a segurança da prova baseada em árvores de Merkle, ao usar a codificação de Reed-Solomon para expandir os dados, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que os valores originais sejam muito pequenos. 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 os 32 bits ainda apresentam muito espaço desperdiçado. O domínio binário permite operações diretas em bits, com codificação compacta, eficiente e sem desperdícios, o que pode ser a 4ª geração dos STARKs.

Os domínios binários são amplamente utilizados em criptografia, como AES(F28), GMAC(F2128), QR Code(F28), entre outros. Quando se utiliza domínios menores, a operação de extensão torna-se cada vez mais importante para garantir a segurança. O domínio binário utilizado pelo Binius depende totalmente da extensão para garantir a segurança e a usabilidade. A maioria dos cálculos Prover opera sob o domínio base, sendo eficiente; a verificação de pontos aleatórios e o cálculo FRI exigem uma exploração mais profunda em um domínio de extensão maior para garantir a segurança.

Soluções inovadoras da Binius:

1. usa múltiplas variáveis ( polinômio multivariável ) em vez de polinômio univariável, representando a trajetória de cálculo através de "hipercubo".
2. Veja o hipercubo como quadrado, baseado no quadrado para a expansão de Reed-Solomon.

2. Análise dos Princípios

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

Cinco tecnologias-chave:

1. aritmética baseada em domínio binário em torre
2. Adaptação da verificação de produtos e permutações do HyperPlonk
3. Nova prova de deslocamento multilinear
4. versão melhorada da Lasso de busca de evidências
5. Esquema de compromisso de polinômios de pequeno domínio

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

Vantagens do domínio binário em torre:

• Cálculo eficiente: o domínio binário suporta operações aritméticas eficientes
• Arithmetização eficiente: a estrutura de campo binário suporta o processo de arithmetização simplificado
• Aproveitar ao máximo as características hierárquicas através da estrutura em torre

A string de 128 bits pode ser interpretada de forma flexível:

• Um elemento único em um domínio binário de 128 bits
• Dois elementos de domínio de 64 bits
• Quatro elementos de domínio de 32 bits
• 16 elementos de domínio de 8 bits
• 128 elementos de domínio F2

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

Mecanismo de verificação central Binius:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Binius sobre a melhoria do HyperPlonk:

• ProductCheck otimização
• Tratar corretamente o problema da divisão por zero
• Suporte a PermutationCheck entre colunas

2.3 PIOP: novo argumento de deslocamento multilinear

Método chave:

• Packing: Agrupar elementos menores adjacentes em um elemento maior
• Operador de deslocamento: reorganizar elementos dentro do bloco

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

Vantagens do protocolo Lasso:

• Prova de eficiência alta: compromisso de m+n elementos de campo
• Sem compromisso de grandes tabelas: pode lidar com tabelas super grandes

Binius introduz a versão multiplicativa do protocolo Lasso:

• Gerar o "contador de memória" crescente através da multiplicação de domínio binário.
• O provador compromete-se a garantir um vetor de contagem de leitura não nula para a segurança.

2.5 PCS: versão adaptada Brakedown PCS

Ideia central: packing

Duas opções:

1. Instanciar código concatenado
2. Adotar codificação a nível de bloco, suportar o uso independente de códigos de Reed-Solomon

Compromissos de polinômios de pequeno domínio e avaliação de domínio expandido:

• Promessa na pequena área K
• Avaliar na maior extensão L/K

Codificação em bloco e códigos de Reed-Solomon:

• Permitir pequenos domínios ( como F2) polinômios usando o alfabeto de letras maiúsculas ( como F216) códigos Reed-Solomon de compromisso eficiente

3. Pensamento otimizado

Quatro pontos de otimização chave:

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

Transformar "verificar A·B =? C" em "verificar (gA)B =? gC"

• Apenas um compromisso auxiliar
• Reduzir o custo de Sumchecks

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

Método de otimização:

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

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

Melhorias principais:

• Seleção de alternância de rodadas t
• O impacto do tamanho do domínio
• Otimização do algoritmo de Karatsuba
• Aumento da eficiência da memória

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

Quatro inovações:

1. Polinômio plano
2. Polinômio de desaparecimento de subespaço
3. Embalagem de base algébrica
4. Troca de Anéis SumCheck

FRI-Binius pode reduzir o tamanho da prova Binius em um fator de 10.

4. Resumo

Vantagens da Binius:

• Pode ser usado o menor domínio power-of-two para testemunhas.
• Prova rápida de baixo uso de memória
• Remoção básica do gargalo de compromisso do Prover

Novo Gargalo: Protocolo Sumcheck

• Pode resolver eficientemente com hardware dedicado

FRI-Binius:

• Eliminar custos de incorporação de prova de domínio
• Não causar um aumento exponencial nos custos da camada de prova de agregação

Progresso atual:

• A equipe Irreducible desenvolveu uma camada recursiva, em colaboração com a Polygon, para construir o zkVM baseado em Binius
• JoltzkVM mudou de Lasso para Binius
• Ingonyama implementa a versão FPGA do Binius