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 em programas reais é bastante 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 Reed-Solomon para expandir os dados. Reduzir o tamanho do domínio tornou-se uma estratégia chave.

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

O domínio binário tem sido amplamente utilizado em criptografia, exemplos típicos incluem:

• Padrão Avançado de Criptografia (AES), baseado no domínio F28
• Galois Message Authentication Code ( GMAC ), baseado no domínio F2128
• QR Code, usando codificação Reed-Solomon baseada em F28
• Protocólo FRI original e zk-STARK, bem como a função de hash Grøstl que chegou à final do SHA-3

Quando se utilizam domínios menores, a operação de extensão de domínio torna-se cada vez mais importante para garantir a segurança. O domínio binário utilizado pelo Binius depende completamente da extensão de domínio para assegurar a sua segurança e viabilidade prática.

Binius apresentou uma solução inovadora:

• Usar polinómios multivariáveis (especificamente polinómios multlineares) em vez de polinómios univariáveis, representando toda a trajetória de cálculo através dos seus valores no "hipercubo".
• Considerar o hipercubo como um quadrado e realizar a expansão de Reed-Solomon com base nesse quadrado

2 Análise de Princípios

Binius = HyperPlonk PIOP + Brakedown PCS + 二进制域

Binius inclui cinco tecnologias-chave:

1. Arithmetização baseada em domínios binários 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í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 essencialmente operações aritméticas altamente eficientes.
• Processamento aritmético eficiente: a estrutura do campo binário suporta um processo aritmético simplificado
• Representação flexível: a mesma string pode ser interpretada de várias maneiras no contexto de domínio binário
• Sem necessidade de redução: o campo binário não requer a introdução de transporte nas operações de adição e multiplicação.
• Cálculo de quadrados eficiente: (X + Y)2 = X2 + Y2

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

Mecanismo de verificação central:

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

Comparação com as melhorias do HyperPlonk:

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

2.3 PIOP: novo argumento de deslocamento multilinhar

Método chave:

• Packing: otimizar a operação ao empacotar elementos menores em posições adjacentes na ordem do dicionário em elementos maiores
• Operador de deslocamento: rearranja os elementos dentro do bloco, realizando um deslocamento cíclico com base no deslocamento dado.

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

Vantagens do protocolo Lasso:

• Prova eficiente: para m buscas em uma tabela de tamanho n, apenas é necessário comprometer m+n elementos de domínio.
• Sem necessidade de compromisso com tabelas grandes: se a tabela t for estruturada, não é necessário comprometer-se com ela, podendo processar tabelas extremamente grandes.

Composição do protocolo Lasso:

• Abstração de polinômios virtuais de grandes tabelas
• Pesquisa de tabela pequena
• Verificação de múltiplos conjuntos

A adaptação de Binius para Lasso:

• Introduzir a versão multiplicativa do protocolo Lasso
• Exigir que a parte comprovante se comprometa com um vetor de contagem de leitura que seja sempre não nulo.

2.5 PCS: versão adaptada Brakedown PCS

Ideia central: packing

Duas opções:

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

Principais tecnologias:

• 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 código de Reed-Solomon

3 Pensamento Otimizado

Quatro pontos chave de otimização:

1. PIOP baseado em GKR: para operações de multiplicação no domínio binário
2. ZeroCheck PIOP otimização: Compensação de custos de cálculo entre Prover e Verifier
3. Otimização do PIOP Sumcheck: protocolo Sumcheck baseado em pequenos domínios
4. PCS otimização: FRI-Binius reduz o tamanho da prova Binius

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

Ideia central:

Verifique se "A·B =? C" para 2 inteiros de 32 bits A e B. Converter para
"Verificando (gA)B =? gC se é válido"

Vantagens:

• Apenas um compromisso auxiliar
• Reduzir o custo dos Sumchecks

3.2 ZeroCheck PIOP otimização

Direção de otimização:

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

3.3 Sumcheck PIOP otimização

Melhoria Focal:

• Seleção de mudança de rodada
• O impacto do tamanho do domínio no desempenho
• Ganhos de otimização do algoritmo de Karatsuba
• Aumento da eficiência da memória

Efeitos específicos:

• No caso de um campo GF[2], o desempenho do Algoritmo 4 é quase 30 vezes superior ao do algoritmo ingênuo.
• O algoritmo 4 requer apenas 0.26MB de memória, enquanto o algoritmo 3 requer 67MB

3.4 PCS otimização: FRI-Binius

Quatro pontos inovadores:

1. Polinómio achatado
2. Polinômio de desaparecimento de subespaço
3. Empacotamento da base algébrica
4. Troca de Anel SumCheck

Eficácia: Reduzir a magnitude da prova Binius em um ordem de grandeza

4 Resumo

Vantagens da Binius:

• Pode ser usado o menor domínio de potência de dois para testemunhas.
• Baixo uso de memória, prova rápida
• Removido quase completamente o gargalo de compromisso do Prover

FRI-Binius方案: Eliminar o custo de incorporação da camada de prova de domínio, sem causar um aumento exponencial nos custos da camada de prova agregada.

Últimos desenvolvimentos:

• A equipe Irreducible está desenvolvendo sua camada recursiva e colaborando com a equipe Polygon para construir um zkVM baseado em Binius.
• JoltzkVM está a passar de Lasso para Binius, para melhorar o seu desempenho recursivo.
• A equipe Ingonyama está implementando a versão FPGA do Binius