Análise dos princípios dos STARKs da Binius e reflexões sobre a otimização

1 Introdução

Ao contrário dos SNARKs baseados em curvas elípticas, os STARKs podem ser considerados SNARKs baseados em hash. Uma das principais razões para a ineficiência atual dos STARKs é que a maioria dos valores no programa real são pequenos, como índices em loops, valores verdadeiros e falsos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvore Merkle, quando os dados são estendidos com codificação Reed-Salomão, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que os valores originais sejam muito pequenos. Para resolver esse problema, reduzir o tamanho do domínio torna-se uma estratégia-chave.

Como mostrado na Tabela 1, os STARKs de primeira geração são de 252 bits, os STARKs de segunda geração são de 64 bits e os STARKs de terceira geração são de 32 bits. Em contraste, o domínio binário permite operações diretas de alinhamento de bits e é compacto e eficiente na codificação sem desperdiçar espaço, ou seja, STARKs de 4ª geração.

Tabela 1: Percursos de evolução dos STARKs

| Funcionalidade | STARKs de 1ª geração | STARKs de 2.ª geração | STARKs de 3ª geração | A 4ª geração STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Largura de bit do código | 252 bits | 64 bits | 32 bits | 1bit | | Sistemas Representativos | StarkWare | Plonky2 | BabyBear | Binius |

Em comparação com os domínios finitos descobertos nos últimos anos, como Cachinhos Dourados, BabyBear e Mersenne31, o estudo dos domínios binários remonta aos anos 80 do século passado. Atualmente, domínios binários têm sido amplamente utilizados em criptografia, exemplos típicos incluem:

• Advanced Encryption Standard (AES), baseado em domínios F28;

• Galois Message Authentication Code ( GMAC ), baseado no campo F2128;

• QR Code, usando codificação Reed-Solomon baseada em F28;

• Os protocolos FRI e zk-STARK originais, bem como a função hash Grøstl que chegou ao finalista do SHA-3, que é baseado no domínio F28 e é um algoritmo de hash adequado para recursão.

Ao usar domínios menores, a expansão das operações de domínio torna-se cada vez mais importante para garantir a segurança. O domínio binário usado pela Binius, por outro lado, precisa depender inteiramente da expansão do domínio para garantir sua segurança e disponibilidade real. A maioria dos polinômios envolvidos nos cálculos do Prover não precisa entrar no domínio expandido, mas apenas operar sob o domínio base, alcançando assim alta eficiência em pequenos domínios. No entanto, verificações aleatórias de pontos e cálculos de FRI ainda precisam ser perfurados em uma área de expansão maior para garantir a segurança necessária.

Ao construir um sistema de prova baseado em domínios binários, existem 2 problemas práticos: ao calcular a representação de trace em STARKs, o tamanho do domínio utilizado deve ser maior do que o grau do polinômio; ao comprometer a Merkle tree em STARKs, é necessário fazer a codificação de Reed-Solomon, e o tamanho do domínio utilizado deve ser maior do que o tamanho após a expansão da codificação.

Binius propõe uma solução inovadora que lida com esses dois problemas separadamente e o faz representando os mesmos dados de duas maneiras diferentes: primeiro, usando polinômios multivariados (especificamente, multilineares) em vez de polinômios univariados, e representando toda a trajetória computacional pelo seu valor nos "hipercubos"; Em segundo lugar, como o comprimento de cada dimensão do hipercubo é 2, não é possível fazer a extensão padrão Reed-Solomon como STARKs, mas o hipercubo pode ser tratado como um quadrado baseado na extensão Reed-Salomão. Este método melhora significativamente a eficiência de codificação e o desempenho de computação, garantindo a segurança.

2 Análise de Princípios

A construção da maioria dos sistemas SNARKs atuais geralmente consiste nas seguintes duas partes:

• Information-Theoretic Polynomial Interactive Oracle Proof (PIOP) :P IOP como o núcleo do sistema de prova, transformando as relações computacionais de entradas em equações polinomiais verificáveis. Diferentes protocolos PIOP permitem que o provador envie polinômios passo a passo, interagindo com o validador, permitindo que o validador verifique se o cálculo está correto consultando os resultados da avaliação de um pequeno número de polinômios. Os protocolos PIOP existentes incluem PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, todos os quais lidam com expressões polinomiais de forma diferente, o que afeta o desempenho e a eficiência de todo o sistema SNARK.

• Polynomial Commitment Scheme (PCS): O Polynomial Commitment Scheme é usado para provar se a equação polinomial gerada pelo PIOP é verdadeira. PCS é uma ferramenta criptográfica através da qual um provador pode se comprometer com um determinado polinômio e posteriormente verificar os resultados da avaliação desse polinômio, enquanto oculta outras informações sobre o polinômio. Os esquemas de compromisso polinomial comuns incluem KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) e Brakedown. PCSs diferentes têm diferentes cenários de desempenho, segurança e aplicativos.

De acordo com os requisitos específicos, diferentes PIOP e PCS podem ser selecionados, e combinados com campos finitos adequados ou curvas elípticas, sistemas de prova com diferentes propriedades podem ser construídos. Por exemplo:

• Halo2: Alimentado por PLONK PIOP combinado com PCS à prova de balas e baseado em curvas de massa. Halo2 foi projetado com escalabilidade em mente, bem como remover a configuração confiável do protocolo ZCash.

• Plonky2: Combina PLONK PIOP com FRI PCS e é baseado no domínio Goldilocks. Plonky2 é para recursão eficiente. Ao projetar esses sistemas, o PIOP e o PCS selecionados devem corresponder ao domínio finito ou à curva elíptica usada para garantir a correção, o desempenho e a segurança do sistema. A escolha dessas combinações não só afeta o tamanho da prova e a eficiência de verificação dos SNARKs, mas também determina se o sistema pode alcançar transparência sem a necessidade de configurações confiáveis e se pode suportar funções estendidas, como provas recursivas ou provas agregadas.

Binius: HyperPlonk PIOP + Brakedown PCS + Domínio binário. Especificamente, Binius inclui cinco tecnologias-chave para alcançar sua eficiência e segurança. Em primeiro lugar, a aritmética baseada nas torres de campos binários forma a base de seus cálculos, que podem realizar operações simplificadas nos campos binários. Em segundo lugar, em seu protocolo interativo Oracle Proof Protocol (PIOP), a Binius adaptou o produto HyperPlonk e a verificação de permutação para garantir uma verificação de consistência segura e eficiente entre as variáveis e suas permutações. Em terceiro lugar, o protocolo introduz um novo argumento de deslocamento multilinear para otimizar a eficiência da verificação da relação multilinear em um pequeno domínio. Em quarto lugar, Binius adota uma versão melhorada do argumento de pesquisa Lasso, que fornece flexibilidade e forte segurança para o mecanismo de pesquisa. Finalmente, o protocolo usa um esquema de compromisso polinomial de campo pequeno (PCS de campo pequeno), que lhe permite implementar um sistema de prova eficiente no domínio binário e reduzir a sobrecarga normalmente associada a grandes domínios.

2.1 Campos Finitos: Aritmética baseada em Torres de Campos Binários

O domínio binário da torre é a chave para a computação rápida verificável, que é atribuída principalmente a dois aspetos: computação eficiente e aritmética eficiente. Os domínios binários suportam inerentemente operações aritméticas altamente eficientes, tornando-os ideais para aplicações de criptografia que são sensíveis aos requisitos de desempenho. Além disso, a estrutura de domínio binário suporta um processo aritmético simplificado, ou seja, as operações realizadas no domínio binário podem ser representadas de forma algébrica compacta e facilmente verificável. Essas características, combinadas com a capacidade de tirar o máximo proveito de sua natureza hierárquica através de estruturas de torre, tornam o domínio binário particularmente adequado para sistemas de prova escaláveis, como Binius

onde "canônico" refere-se a uma representação única e direta de um elemento no domínio binário. Por exemplo, no domínio binário mais básico F2, qualquer cadeia de caracteres k-bit pode ser mapeada diretamente para um elemento de domínio binário k-bit. Isto contrasta com o campo dos números primos, que não pode fornecer tal representação canônica dentro da posição dada. Embora um campo de número primo de 32 bits possa estar contido em um sistema de 32 bits, nem toda cadeia de caracteres de 32 bits corresponde exclusivamente a um elemento de domínio, e os campos binários têm a conveniência desse mapeamento um-para-um. No domínio principal Fp, os métodos comuns de redução incluem a redução de Barrett, a redução de Montgomery e métodos especiais de redução para campos finitos específicos, como Mersenne-31 ou Goldilocks-64. No domínio binário F2k, os métodos de redução comumente usados incluem redução especial (por exemplo, usada em AES), redução de Montgomery (por exemplo, usada em POLYVAL) e redução recursiva (por exemplo, Tower). O artigo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" aponta que o domínio binário não precisa introduzir carry tanto na adição quanto na multiplicação, e que a operação quadrada do domínio binário é muito eficiente porque segue (X + Y )2 = X2 + Y 2.

! Pesquisa Bitlayer: Binius STARKs Princípio Análise e Otimização Pensamento

Como mostrado na Figura 1, uma cadeia de caracteres de 128 bits: essa cadeia de caracteres pode ser interpretada de várias maneiras no contexto do domínio binário. Ele pode ser visto como um elemento exclusivo em um domínio binário de 128 bits, ou pode ser resolvido como dois elementos de torre de 64 bits, quatro elementos de torre de 32 bits, 16 elementos de torre de 8 bits ou 128 elementos de domínio F2. A flexibilidade desta representação não requer nenhuma sobrecarga computacional, apenas um typecast de strings bitwise, que é uma propriedade muito interessante e útil. Ao mesmo tempo, pequenos elementos de domínio podem ser empacotados em elementos de domínio maiores sem sobrecarga computacional adicional. O protocolo Binius aproveita esse recurso para melhorar a eficiência computacional. Além disso, o artigo "On Efficient Inversion in Tower Fields of Characteristic Two" explora a complexidade computacional das operações de multiplicação, quadratura e inversão em um domínio binário de torre n-bit que pode ser decomposto em subdomínios m-bit.

2.2 PIOP: Produto HyperPlonk Adaptado e PermutaçãoVerifique ------ para domínios binários

O design PIOP no protocolo Binius pega emprestado do HyperPlonk e emprega uma série de mecanismos de verificação de núcleo para verificar a correção de polinômios e conjuntos multivariados. Esses testes principais incluem:

1. GateCheck: Verifique se a testemunha confidencial ω e a entrada pública x satisfazem a relação de operação do circuito C(x, ω)=0 para garantir o funcionamento correto do circuito.

2. Permutação: Verifique se os resultados da avaliação dos dois polinômios multivariados f e g no hipercubo booleano são relações de permutação f(x) = f(π(x)) assegurar a coerência na disposição entre variáveis polinomiais.

3. LookupCheck: Verifique se o polinômio é avaliado em uma determinada tabela de pesquisa, ou seja, f(Bμ) ⊆ T(Bμ), garantindo que certos valores estejam dentro do intervalo especificado.

4. MultisetCheck: Verifique se os dois conjuntos multivariados são iguais, ou seja, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H para garantir a consistência entre vários conjuntos.

5. ProductCheck: Verifica se a avaliação de um polinômio racional em um hipercubo booleano é igual a um valor declarado ∏x∈Hμ f(x) = s para garantir a correção do produto polinomial.

6. ZeroCheck: Verifique se um polinômio multivariado é zero em qualquer ponto do hipercubo booleano∏x∈Hμ f(x) = 0,∀x ∈ Bμ para garantir a distribuição zero do polinômio.

7. SumCheck: Verifica se o valor da soma do polinômio multivariado é o valor declarado ∑x∈Hμ f(x) = s. Ao transformar o problema de avaliação de polinômios multivariados em avaliação polinomial univariada, a complexidade computacional do verificador é reduzida. Além disso, o SumCheck também permite o processamento em lote, introduzindo números aleatórios, construindo combinações lineares para alcançar o processamento em lote de várias instâncias de verificação de soma.

8. BatchCheck: Com base no SumCheck, verifique a correção de várias avaliações polinomiais multivariadas para melhorar a eficiência do protocolo.

Embora a Binius e a HyperPlonk tenham muitas semelhanças no design do protocolo, a Binius fez melhorias nas seguintes 3 áreas:

• Otimização do ProductCheck: No HyperPlonk, o ProductCheck requer que o denominador U seja diferente de zero em todos os lugares do hipercubo, e o produto deve ser igual a um valor específico; Binius simplifica este processo de verificação especializando este valor para 1, reduzindo assim a complexidade computacional.

• Manipulação do problema divide-zero: HyperPlonk não consegue lidar adequadamente com o caso divide-zero, resultando na incapacidade de afirmar o problema não-zero de U no hipercubo; Binius lida com isso corretamente, e Binius ProductCheck continua a processar mesmo quando o denominador é zero, permitindo generalizações para valores arbitrários do produto.

• PermutationCheck: Este recurso não está disponível no HyperPlonk; Binius suporta PermutationCheck entre várias colunas, o que permite que Binius para lidar com permutações polinomiais mais complexas.

Portanto, através da melhoria do mecanismo PIOPSumCheck existente, Binius melhora a flexibilidade e eficiência do protocolo, especialmente quando se lida com verificação polinomial multivariada mais complexa, e fornece suporte funcional mais forte. Essas melhorias não apenas abordam as limitações do HyperPlonk, mas também fornecem uma base baseada em binários para o futuro