Título original encaminhado 'Vitalik explica Binius em detalhes: um sistema de prova eficiente baseado em campos binários'

Esta postagem é principalmente destinada a leitores familiarizados com a criptografia da era de 2019, especialmente SNARKs e STARKs. Se você não está, recomendo ler esses artigos primeiro. Agradecimentos especiais a Justin Drake, Jim Posen, Benjamin Diamond e Radi Cojbasic pelo feedback e revisão.

Nos últimos dois anos, os STARKs se tornaram uma tecnologia crucial e insubstituível para fazer de forma eficiente provas criptográficas fáceis de verificar de declarações muito complicadas (por exemplo, provar que um bloco Ethereum é válido). Uma razão chave é o tamanho pequeno do campo: enquanto os SNARKs baseados em curvas elípticas requerem que você trabalhe com inteiros de 256 bits para ser seguro o suficiente, os STARKs permitem que você use tamanhos de campo muito menores, que são mais eficientes: primeiro o campo Goldilocks (inteiros de 64 bits), e depois Mersenne31 e BabyBear (ambos com 31 bits). Graças a esses ganhos de eficiência, o Plonky2, que usa Goldilocks, é centenas de vezes mais rápido na prova de muitos tipos de computação do que seus antecessores.

Uma pergunta natural a fazer é: podemos levar essa tendência à sua conclusão lógica, construindo sistemas de prova que funcionem ainda mais rapidamente operando diretamente sobre zeros e uns? Isso é exatamente o que Binius está tentando fazer, usando uma série de truques matemáticos que o tornam muito diferente dos SNARKs e STARKs de três anos atrás. Esta postagem passa pelos motivos pelos quais campos pequenos tornam a geração de provas mais eficiente, por que os campos binários são excepcionalmente poderosos e os truques que Binius usa para fazer as provas sobre campos binários funcionarem de forma tão eficaz.

Binius. Até o final deste post, você deverá ser capaz de entender cada parte deste diagrama.

Recap: campos finitos

Uma das tarefas-chave de um sistema de provas criptográficas é operar sobre grandes quantidades de dados, mantendo os números pequenos. Se você puder comprimir uma declaração sobre um grande programa em uma equação matemática envolvendo alguns números, mas esses números forem tão grandes quanto o programa original, você não terá ganho nada.

Para fazer aritmética complicada mantendo os números pequenos, os criptógrafos geralmente usam aritmética modular. Escolhemos algum primo “módulo” p. O operador % significa “pegar o resto de”: 15 % 7=1, 53 % 10=3, etc (observe que a resposta é sempre não negativa, então por exemplo −1 % 10=9).

Você provavelmente já viu a aritmética modular, no contexto de adição e subtração de tempo (por exemplo, que horas são quatro horas depois das 9:00?). Mas aqui, não apenas adicionamos e subtraímos módulo de algum número, também multiplicamos, dividimos e levamos expoentes.

Nós redefinimos:

As regras acima são todas autoconsistentes. Por exemplo, se p=7, então:

5+3=1 (porque 8%7=1)

1-3=5 (porque -2%7=5)

2*5=3

3/5=2

Um termo mais geral para esse tipo de estrutura é um campo finito. Um campo finito é uma estrutura matemática que obedece às leis usuais da aritmética, mas onde há um número limitado de valores possíveis, e assim cada valor pode ser representado em um tamanho fixo.

Aritmética modular (ou campos primos) é o tipo mais comum de campo finito, mas também existe outro tipo: campos de extensão. Você provavelmente já viu um campo de extensão antes: os números complexos. Nós “imaginamos” um novo elemento, que rotulamos como 𝑖, e declaramos que ele satisfaz 𝑖2=−1. Você pode então tomar qualquer combinação de números regulares e 𝑖, e fazer cálculos com isso: (3𝑖+2)∗(2𝑖+4)= 6𝑖2+12𝑖+4𝑖+8=16𝑖+2. Podemos de forma semelhante fazer extensões de campos primos. Conforme começamos a trabalhar em campos menores, as extensões de campos primos se tornam cada vez mais importantes para preservar a segurança, e os campos binários (que a Binius utiliza) dependem exclusivamente de extensões para ter utilidade prática.

Recap: aritmetização

A maneira como SNARKs e STARKs provam coisas sobre programas de computador é através da aritmetização: você converte uma declaração sobre um programa que deseja provar, em uma equação matemática envolvendo polinômios. Uma solução válida para a equação corresponde a uma execução válida do programa.

Para dar um exemplo simples, suponha que eu tenha calculado o 100º número de Fibonacci e que eu queira provar para você qual é. Eu crio um polinômio 𝐹 que codifica os números de Fibonacci: então 𝐹(0)=𝐹(1)=1, 𝐹(2)=2, 𝐹(3)=3, 𝐹(4)=5, e assim por diante por 100 passos. A condição que eu preciso provar é que 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) ao longo do intervalo 𝑥={0,1…98}. Eu posso convencê-lo disso dando-lhe o quociente:

onde Z(x) = (x-0) (x-1) …(x-98). . Se eu puder provar que existe um F e um H que satisfazem essa equação, então F deve satisfazer F(x+2)-F(x+1)-F(x) no intervalo. Se eu verificar adicionalmente que F é satisfeito, F(0)=F(1)=1, então F(100) deve ser o 100º número de Fibonacci na verdade.

Se você quiser provar algo mais complicado, então substitua a relação “simples” 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) por uma equação mais complicada, que basicamente diz que “𝐹(𝑥+1) é a saída da inicialização de uma máquina virtual com o estado 𝐹(𝑥) e executando um passo computacional”. Você também pode substituir o número 100 por um número maior, por exemplo, 100000000, para acomodar mais passos.

Todos os SNARKs e STARKs são baseados nessa ideia de usar uma equação simples sobre polinômios (ou às vezes vetores e matrizes) para representar um grande número de relações entre valores individuais. Nem todos envolvem a verificação de equivalência entre etapas computacionais adjacentes da mesma maneira que acima: PLONK não o faz, por exemplo, e nem R1CS. Mas muitos dos mais eficientes o fazem, porque impor a mesma verificação (ou as mesmas poucas verificações) muitas vezes torna mais fácil minimizar o overhead.

Plonky2: de 256 bits SNARKs e STARKs para 64 bits... apenas STARKs

Há cinco anos, um resumo razoável dos diferentes tipos de prova de conhecimento zero era o seguinte. Existem dois tipos de provas: (baseadas em curva elíptica) SNARKs e (baseadas em hash) STARKs. Tecnicamente, STARKs são um tipo de SNARK, mas na prática é comum usar "SNARK" para se referir apenas à variedade baseada em curva elíptica, e "STARK" para se referir às construções baseadas em hash. SNARKs são pequenos, então você pode verificá-los muito rapidamente e encaixá-los facilmente na cadeia. STARKs são grandes, mas não requerem setups confiáveis, e são resistentes a quantum.

STARKs funcionam tratando os dados como um polinômio, calculando avaliações desse polinômio em um grande número de pontos e usando a raiz de Merkle desses dados estendidos como o "compromisso polinomial"

Um detalhe importante da história aqui é que os SNARKs baseados em curvas elípticas entraram em uso generalizado primeiro: levou até aproximadamente 2018 para que os STARKs se tornassem eficientes o suficiente para usar, graças ao FRI, e até então o Zcash já estava funcionando há mais de um ano. SNARKs baseados em curva elíptica têm uma limitação chave: se você quiser usar SNARKs baseados em curva elíptica, então a aritmética nessas equações deve ser feita com inteiros modulo o número de pontos na curva elíptica. Este é um grande número, geralmente perto de 2256: por exemplo, para a curva bn128, é 21888242871839275222246405745257275088548364400416034343698204186575808495617. Mas a computação real está usando pequenos números: se você pensar em um programa "real" em sua linguagem favorita, a maioria das coisas com as quais ele está trabalhando são contadores, índices em loops, posições no programa, bits individuais representando True ou False, e outras coisas que quase sempre terão apenas alguns dígitos.

Mesmo que seus dados “originais” sejam compostos por números “pequenos”, o processo de comprovação requer o cálculo de quocientes, extensões, combinações lineares aleatórias e outras transformações dos dados, o que leva a um número igual ou maior de objetos que são, em média, tão grandes quanto o tamanho total do seu campo. Isso cria uma ineficiência chave: para provar um cálculo sobre n valores pequenos, você precisa fazer ainda mais cálculos sobre n valores muito maiores. Inicialmente, os STARKs herdaram o hábito de usar campos de 256 bits dos SNARKs e, portanto, sofreram da mesma ineficiência.

Uma extensão de Reed-Solomon de algumas avaliações polinomiais. Mesmo que os valores originais sejam pequenos, os valores extras explodem para o tamanho total do campo (neste caso 2 elevado a 31 -1)

Em 2022, Plonky2 foi lançado. A principal inovação do Plonky2 foi fazer aritmética módulo um primo menor: 2⁶⁴−2³²+1=18446744069414584321. Agora, cada adição ou multiplicação pode sempre ser feita em apenas algumas instruções em uma CPU, e o hashing de todos os dados juntos é 4x mais rápido do que antes. Mas isso tem um porém: essa abordagem é exclusiva do STARK. Se você tentar usar um SNARK, com uma curva elíptica de tamanho tão pequeno, a curva elíptica se torna insegura.

Para continuar a ser seguro, o Plonky2 também precisava introduzir campos de extensão. Uma técnica-chave na verificação de equações aritméticas é a “amostragem em um ponto aleatório”: se você deseja verificar se 𝐻(𝑥)∗𝑍(𝑥) realmente é igual a 𝐹(𝑥+2)−𝐹(𝑥+1)−𝐹(𝑥), você pode escolher algumas coordenadas aleatórias 𝑟, fornecer provas de abertura de comprometimento polinomial provando 𝐻(𝑟), 𝑍(𝑟), 𝐹(𝑟), 𝐹(𝑟+1) e 𝐹(𝑟+2), e então realmente verificar se 𝐻(𝑟)∗𝑍(𝑟) é igual a 𝐹(𝑟+2)−𝐹(𝑟+1)−𝐹(𝑟). Se o atacante puder adivinhar a coordenada antecipadamente, o atacante pode enganar o sistema de prova - daí a necessidade de que seja aleatório. Mas isso também significa que a coordenada deve ser amostrada de um conjunto grande o suficiente para que o atacante não possa adivinhá-la por acaso. Se o módulo estiver perto de 2²⁵⁶, este é claramente o caso. Mas com um módulo de 2⁶⁴−2³²+1, ainda não estamos lá, e se cair para 2³¹−1, definitivamente não é o caso. Tentar falsificar uma prova duas bilhões de vezes até que alguém tenha sorte está absolutamente dentro do alcance das capacidades de um atacante.

Para parar com isso, amostramos 𝑟 de um campo de extensão. Por exemplo, você pode definir 𝑦 onde 𝑦³=5, e tomar combinações de 1, 𝑦 e 𝑦². Isso aumenta o número total de coordenadas para cerca de 2⁹³A maior parte dos polinômios calculados pelo provador não entram neste campo de extensão; eles apenas usam inteiros módulo 2³¹−1 e, assim, você ainda obtém todas as eficiências do uso do campo pequeno. Mas a verificação do ponto aleatório e o cálculo do FRI mergulham neste campo maior para obter a segurança necessária.

De pequenos primos a binário

Computadores realizam aritmética representando números maiores como sequências de zeros e uns, e construindo “circuitos” em cima desses bits para calcular coisas como adição e multiplicação. Os computadores são especialmente otimizados para fazer cálculos com inteiros de 16 bits, 32 bits e 64 bits. Módulos como 2⁶⁴−2³²+1 e 2³¹−1 são escolhidos não apenas porque se encaixam dentro desses limites, mas também porque se alinham bem com esses limites: você pode fazer multiplicação módulo 2⁶⁴−2³²+1 fazendo multiplicação regular de 32 bits e deslocando e copiando as saídas bit a bit em alguns lugares; este artigo explica bem alguns dos truques.

O que seria ainda melhor, no entanto, é fazer cálculos em binário diretamente. E se a adição pudesse ser apenas XOR, sem a necessidade de se preocupar com o 'transporte' do estouro de adicionar 1 + 1 em uma posição de bit para a próxima posição de bit? E se a multiplicação pudesse ser mais paralelizável da mesma forma? E essas vantagens viriam além de poder representar valores Verdadeiro/Falso com apenas um bit.

Captar essas vantagens de fazer computação binária diretamente é exatamente o que Binius está tentando fazer. Uma tabela da apresentação da equipe Binius no zkSummit mostra os ganhos de eficiência:

Apesar de terem aproximadamente o mesmo “tamanho”, uma operação de campo binário de 32 bits consome 5 vezes menos recursos computacionais do que uma operação sobre o campo Mersenne de 31 bits.

De polinômios univariados a hipercubos

Suponhamos que sejamos convencidos por este raciocínio e queiramos fazer tudo sobre bits (zeros e uns). Como nos comprometemos realmente com um polinômio representando um bilhão de bits?

Aqui, enfrentamos dois problemas práticos:

1. Para um polinômio representar muitos valores, esses valores precisam ser acessíveis nas avaliações do polinômio: em nosso exemplo de Fibonacci acima, 𝐹(0), 𝐹(1) ... 𝐹(100), e em um cálculo maior, os índices iriam para os milhões. E o campo que usamos precisa conter números que cheguem a esse tamanho.

2. Provar qualquer coisa sobre um valor ao qual estamos nos comprometendo em uma árvore de Merkle (como todos os STARKs fazem) requer codificá-lo de Reed-Solomon: estendendo 𝑛 valores para, por exemplo, 8𝑛 valores, usando a redundância para evitar que um comprovador malicioso trapaceie falsificando um valor no meio da computação. Isso também requer ter um campo grande o suficiente: para estender um milhão de valores para 8 milhões, você precisa de 8 milhões de pontos diferentes nos quais avaliar o polinômio.

Uma ideia-chave no Binius é resolver esses dois problemas separadamente, e fazer isso representando os mesmos dados de duas maneiras diferentes. Primeiro, o próprio polinômio. SNARKs baseados em curvas elípticas, STARKs da era 2019, Plonky2 e outros sistemas geralmente lidam com polinômios em uma variável: 𝐹(𝑥). Binius, por outro lado, se inspira no protocolo Spartan e trabalha com polinômios multivariados: 𝐹(𝑥1,𝑥2…𝑥𝑘). Na verdade, representamos todo o rastro computacional no "hipercubo" de avaliações onde cada 𝑥𝑖 é 0 ou 1. Por exemplo, se quiséssemos representar uma sequência de números de Fibonacci e ainda estivéssemos usando um campo grande o suficiente para representá-los, poderíamos visualizar os dezesseis primeiros deles como algo assim:

Ou seja, 𝐹(0,0,0,0) seria 1, 𝐹(1,0,0,0) também seria 1, 𝐹(0,1,0,0) seria 2, e assim por diante, até chegarmos a 𝐹(1,1,1,1)=987. Dado um hipercubo de avaliações, existe exatamente um polinômio multilinear (grau-1 em cada variável) que produz essas avaliações. Assim, podemos pensar nesse conjunto de avaliações como representando o polinômio; nunca precisamos realmente nos preocupar em calcular os coeficientes.

Este exemplo é, claro, apenas para ilustração: na prática, o objetivo de ir a um hipercubo é permitir-nos trabalhar com bits individuais. A maneira 'Binius-nativa' de contar números de Fibonacci seria usar um cubo de dimensão superior, usando cada conjunto de ex. 16 bits para armazenar um número. Isso requer alguma astúcia para implementar a adição de inteiros em cima dos bits, mas com o Binius não é muito difícil.

Agora, chegamos à codificação de apagamento. A maneira como os STARKs funcionam é: você pega 𝑛 valores, estende Reed-Solomon para um número maior de valores (geralmente 8𝑛, geralmente entre 2𝑛 e 32𝑛), e seleciona aleatoriamente alguns ramos de Merkle da extensão e realiza algum tipo de verificação neles. Um hipercubo tem comprimento 2 em cada dimensão. Portanto, não é prático estendê-lo diretamente: não há espaço suficiente para amostrar ramos de Merkle a partir de 16 valores. Então, o que fazemos em vez disso? Fingimos que o hipercubo é um quadrado!

Simple Binius - um exemplo

Veraquipara uma implementação em Python deste protocolo.

Vamos passar por um exemplo, usando inteiros regulares como nosso campo por conveniência (em uma implementação real, esses serão elementos de campo binário). Primeiro, pegamos o hipercubo ao qual queremos nos comprometer e o codificamos como um quadrado:

Agora, estendemos Reed-Solomon o quadrado. Ou seja, tratamos cada linha como sendo um polinômio de grau 3 avaliado em x = {0, 1, 2, 3} e avaliamos o mesmo polinômio em x = {4, 5, 6, 7}:

Observe que os números explodem rapidamente! É por isso que em uma implementação real, sempre usamos um campo finito para isso, em vez de inteiros regulares: se usássemos inteiros módulo 11, por exemplo, a extensão da primeira linha seria apenas [3, 10, 0, 6].

Se quiser brincar com a extensão e verificar os números aqui por si mesmo, pode usarmeu código de extensão Reed-Solomon simples aqui.

Em seguida, tratamos essa extensão como colunas e criamos uma árvore de Merkle das colunas. A raiz da árvore de Merkle é nosso compromisso.

Agora, suponhamos que o provador queira provar uma avaliação deste polinômio em algum ponto 𝑟={𝑟0,𝑟1,𝑟2,𝑟3}. Há uma nuance no Binius que o torna um pouco mais fraco do que outros esquemas de compromisso de polinômios: o provador não deve saber, ou ser capaz de adivinhar, 𝑠, até depois de se comprometer com a raiz de Merkle (em outras palavras, 𝑟 deve ser um valor pseudo-aleatório que depende da raiz de Merkle). Isso torna o esquema inútil para “busca de banco de dados” (por exemplo, “ok você me deu a raiz de Merkle, agora me prove 𝑃(0,0,1,0)!”). Mas os protocolos reais de prova de conhecimento zero que geralmente usamos não precisam de “busca de banco de dados”; eles simplesmente precisam verificar o polinômio em um ponto de avaliação aleatório. Portanto, essa restrição está ok para nossos propósitos.

Suponhamos que escolhemos 𝑟={1,2,3,4} (o polinômio, neste ponto, avalia-se em -137; você pode confirmarcom este código. Agora, vamos entrar no processo de realmente fazer a prova. Nós dividimos 𝑟 em duas partes: a primeira parte {1,2} representando uma combinação linear de colunas dentro de uma linha, e a segunda parte {3,4} representando uma combinação linear de linhas. Nós calculamos um "produto tensorial", tanto para a parte da coluna:

E para a parte da fila:

O que isso significa é: uma lista de todos os possíveis produtos de um valor de cada conjunto. No caso da linha, obtemos:

[(1-r2)(1-r3), (1-r3), (1-r2)r3, r2*r3]

Use r={1,2,3,4} (então r2=3 e r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

Agora, calculamos uma nova “linha” 𝑡′, tomando essa combinação linear das linhas existentes. Ou seja, nós pegamos:

Você pode ver o que está acontecendo aqui como uma avaliação parcial. Se multiplicássemos o produto tensorial completo ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) pelo vetor completo de todos os valores, você obteria a avaliação 𝑃(1,2,3,4)=−137. Aqui estamos multiplicando um produto tensorial parcial que usa apenas metade das coordenadas de avaliação, e estamos reduzindo uma grade de valores 𝑁 para uma linha de valores 𝑁. Se você der esta linha a outra pessoa, ela pode usar o produto tensorial da outra metade das coordenadas de avaliação para completar o restante da computação.

O provador fornece ao verificador esta nova linha, 𝑡′, bem como as provas de Merkle de algumas colunas selecionadas aleatoriamente. Isso é 𝑂(𝑁) dados. Em nosso exemplo ilustrativo, o provador fornecerá apenas a última coluna; na vida real, o provador precisaria fornecer algumas dezenas de colunas para alcançar segurança adequada.

Agora, aproveitamos a linearidade dos códigos de Reed-Solomon. A propriedade chave que usamos é: fazer uma combinação linear de uma extensão de Reed-Solomon dá o mesmo resultado que uma extensão de Reed-Solomon de uma combinação linear. Esse tipo de "independência de ordem" frequentemente acontece quando você tem duas operações que são ambas lineares.

O verificador faz exatamente isso. Eles calculam a extensão de 𝑡′ e calculam a mesma combinação linear de colunas que o provador calculou antes (mas apenas para as colunas fornecidas pelo provador) e verificam que esses dois procedimentos dão a mesma resposta.

Neste caso, estendendo 𝑡′, e calculando a mesma combinação linear ([6,−9,−8,12]) da coluna, ambos dão a mesma resposta: −10746. Isso prova que a raiz de Merkle foi construída "de boa fé" (ou pelo menos "suficientemente próxima"), e corresponde a 𝑡′: pelo menos a grande maioria das colunas são compatíveis entre si e com 𝑡′.

Mas o verificador ainda precisa verificar mais uma coisa: verificar realmente a avaliação do polinômio em {𝑟0..𝑟3}. Até agora, nenhum dos passos do verificador realmente dependia do valor que o provador afirmou. Então, aqui está como fazemos essa verificação. Pegamos o produto tensorial do que rotulamos como a parte 'coluna' do ponto de avaliação:

Em nosso exemplo, onde r={1,2,3,4} então a metade da coluna selecionada é {1,2}), isso equivale:

Então agora pegamos essa combinação linear de 𝑡′:

Que é exatamente igual à resposta que você obtém se avaliar o polinômio diretamente.

O acima está bem próximo de uma descrição completa do protocolo “simples” Binius. Isso já tem algumas vantagens interessantes: por exemplo, como os dados são divididos em linhas e colunas, você só precisa de um campo com metade do tamanho. Mas isso não chega perto de realizar todos os benefícios de fazer cálculos em binário. Para isso, precisaremos do protocolo Binius completo. Mas primeiro, vamos ter uma compreensão mais profunda dos campos binários.

Campo binário

O campo possível mais pequeno é a aritmética módulo 2, que é tão pequena que podemos escrever suas tabelas de adição e multiplicação:

Podemos fazer campos binários maiores tomando extensões: se começarmos com 𝐹2 (inteiros módulo 2) e então definirmos 𝑥 onde 𝑥2=𝑥+1, obtemos a seguinte tabela de adição e multiplicação:

Descobrimos que podemos expandir o campo binário para tamanhos arbitrariamente grandes repetindo essa construção. Ao contrário dos números complexos sobre os reais, onde você pode adicionar um novo elemento 𝑖, mas não pode adicionar mais nenhum (quaternion existem, mas são matematicamente estranhos, por exemplo, 𝑎𝑏≠𝑏𝑎), com campos finitos você pode continuar adicionando novas extensões para sempre. Especificamente, definimos os elementos da seguinte forma:

E assim por diante. Isso é frequentemente chamado de construção da torre, por causa de como cada extensão sucessiva pode ser vista como adicionando uma nova camada a uma torre. Esta não é a única maneira de construir campos binários de tamanho arbitrário, mas tem algumas vantagens únicas das quais Binius se beneficia.

Podemos representar esses números como uma lista de bits, por exemplo, 1100101010001111. O primeiro bit representa múltiplos de 1, o segundo bit representa múltiplos de 𝑥0, em seguida, bits subsequentes representam múltiplos de: 𝑥1, 𝑥1∗𝑥0, 𝑥2, 𝑥2∗𝑥0 e assim por diante. Essa codificação é boa porque você pode decompor isso:

Esta é uma notação relativamente incomum, mas eu gosto de representar elementos de campo binário como inteiros, levando em consideração a representação de bits onde os bits mais significativos estão à direita. Ou seja, 1=1, 𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19 e assim por diante. 1100101010001111 é, nesta representação, 61779.

A adição em um campo binário é apenas XOR (assim como a subtração, a propósito); observe que isso significa que x+x=0 para qualquer x. Para multiplicar dois elementos x*y, existe um algoritmo recursivo muito simples: divida cada número ao meio:

Então, divida a multiplicação:

A última peça é a única um pouco complicada, porque você tem que aplicar a regra de redução e substituir 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 por 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1). Existem maneiras mais eficientes de fazer multiplicação, análogas ao algoritmo de Karatsuba e às transformadas rápidas de Fourier, mas deixarei como exercício para o leitor interessado descobrir isso.

A divisão em campos binários é feita combinando multiplicação e inversão. A maneira 'simples mas lenta' de fazer a inversão é uma aplicação do pequeno teorema de Fermat generalizado. Também existe um algoritmo de inversão mais complicado, mas mais eficiente, que você pode encontrar aquiVocê pode usaro código aquibrincar com a adição, multiplicação e divisão de campos binários você mesmo.

Left: tabela de adição para elementos de campo binário de quatro bits (ou seja, elementos compostos apenas por combinações de 1, 𝑥₀，𝑥₁e 𝑥₀𝑥₁).

Certo: tabela de multiplicação para elementos do campo binário de quatro bits.

A coisa bonita sobre este tipo de campo binário é que combina algumas das melhores partes dos inteiros 'regulares' e da aritmética modular. Como os inteiros regulares, os elementos do campo binário são ilimitados: você pode continuar estendendo o quanto quiser. Mas, como a aritmética modular, se você fizer operações com valores dentro de um certo limite de tamanho, todas as suas respostas também permanecem dentro do mesmo limite. Por exemplo, se você tomar potências sucessivas de 42, você obtém:

Após 255 passos, você voltou para 42²⁵⁵ = 1. Assim como os inteiros positivos e a aritmética modular, eles seguem as leis matemáticas usuais: ab=ba, a(b+c)=a b+a*c, há até algumas leis novas e estranhas.

Finalmente, os campos binários facilitam o manuseio dos bits: se você fizer cálculos com números que cabem 2^kbits, então toda a sua saída também caberá 2 k bits. Isso evita constrangimentos. No EIP-4844 da Ethereum, cada “bloco” de um blob deve ser um módulo digital 52435875175126190479447740508185965837690552500527637822603658699938581184513, então codificar os dados binários requer descartar algum espaço e fazer uma verificação adicional para garantir que cada elemento armazene um valor menor que 2²⁴⁸. Isso também significa que as operações de campo binário são super rápidas em computadores - tanto CPUs quanto designs teoricamente ótimos de FPGA e ASIC.

O que tudo isso significa é que podemos fazer algo como a codificação de Reed-Solomon que fizemos acima, de uma maneira que evita completamente a “explosão” de inteiros, como vimos em nosso exemplo, e de uma maneira muito “explosiva”. Maneira “nativa”, o tipo de computação que os computadores são bons. O atributo “split” de campos binários - como fazemos isso 1100101010001111=11001010+10001111*x₃e então dividi-lo de acordo com nossas necessidades também é crucial para alcançar muita flexibilidade.

Full Binius

Ver aquipara uma implementação em Python deste protocolo.

Agora, podemos chegar ao “Binius completo”, que ajusta o “Binius simples” para (i) funcionar em campos binários e (ii) nos permitir comprometer a bits individuais. Este protocolo é complicado de entender, pois fica indo e voltando entre diferentes maneiras de olhar para uma matriz de bits; certamente me levou mais tempo para entender do que o normalmente leva para eu entender um protocolo criptográfico. Mas uma vez que você entende os campos binários, a boa notícia é que não há nenhuma “matemática mais difícil” na qual o Binius dependa. Isso não são emparelhamentos de curvas elípticas, onde há buracos de coelho cada vez mais profundos na geometria algébrica para explorar; aqui, os campos binários são tudo o que você precisa.

Vamos olhar novamente para o diagrama completo:

Até agora, você deve estar familiarizado com a maioria dos componentes. A ideia de "achatar" um hipercubo em uma grade, a ideia de calcular uma combinação de linha e uma combinação de coluna como produtos tensoriais do ponto de avaliação, e a ideia de verificar a equivalência entre "Reed-Solomon estendendo e então calculando a combinação de linha", e "calculando a combinação de linha então Reed-Solomon estendendo", estavam todos no simples Binius.

Quais são as novidades em 'Gate Binius'? Basicamente três coisas:

• Os valores individuais no hipercubo e no quadrado têm que ser bits (0 ou 1)
• O processo de extensão estende bits em mais bits, agrupando bits em colunas e fingindo temporariamente que são elementos de campo maiores
• Após a etapa de combinação de linhas, há uma etapa de "decomposição em bits" elemento a elemento, que converte a extensão de volta em bits

Iremos passar por ambos, por sua vez. Primeiro, o novo procedimento de extensão. Um código de Reed-Solomon tem a limitação fundamental de que, se você estiver estendendo 𝑛 valores para 𝑘∗𝑛 valores, você precisa estar trabalhando em um campo que tenha 𝑘∗𝑛 valores diferentes que você pode usar como coordenadas. Com 𝐹₂ (também conhecido como bits), você não pode fazer isso. E o que fazemos é “empacotar” os adjacentes 𝐹₂elementos juntos em valores maiores. No exemplo aqui, estamos empacotando dois bits de cada vez em elementos em {0,1,2,3}, porque nossa extensão tem apenas quatro pontos de avaliação e isso é suficiente para nós. Em uma prova "real", provavelmente empacotaríamos 16 bits de cada vez. Em seguida, fazemos o código de Reed-Solomon sobre esses valores empacotados e desempacotamo-los novamente em bits.

Agora, a combinação de linha. Para tornar as verificações de 'avaliar em um ponto aleatório' criptograficamente seguras, precisamos que esse ponto seja amostrado de um espaço bastante grande, muito maior do que o próprio hipercubo. Portanto, enquanto os pontos dentro do hipercubo são bits, as avaliações fora do hipercubo serão muito maiores. Em nosso exemplo acima, a 'combinação de linha' acaba sendo [11,4,6,1].

Isso apresenta um problema: sabemos como combinar pares de bits em um valor maior e, em seguida, fazer uma extensão de Reed-Solomon nisso, mas como você faz o mesmo com pares de valores muito maiores?

O truque em Binius é fazê-lo bit a bit: olhamos para os bits individuais de cada valor (por exemplo, para o que rotulamos como “11”, isso é [1,1,0,1]), e então estendemos linha por linha. Ou seja, realizamos o procedimento de extensão na linha 1 de cada elemento, depois na linha 𝑥0, depois no “𝑥₁“linha e, em seguida, no 𝑥₀∗𝑥₁linha, e assim por diante (bem, no nosso exemplo de brinquedo paramos por aqui, mas em uma implementação real iríamos até 128 linhas (sendo a última 𝑥₆∗ …∗ 𝑥₀)).

Recapitulando:

• Nós pegamos os bits no hipercubo e os convertemos em uma grade
• Então, tratamos grupos adjacentes de bits em cada linha como elementos de campo maiores e fazemos aritmética neles para estender as linhas de Reed-Solomon
• Em seguida, pegamos uma combinação de linha de cada coluna de bits e obtemos uma coluna (para quadrados maiores que 4x4, muito menor) de bits para cada linha como saída
• Então, olhamos para a saída como uma matriz e tratamos os bits disso como linhas novamente

Por que isso funciona? Na matemática “normal”, a capacidade de (frequentemente) realizar operações lineares em qualquer ordem e obter o mesmo resultado para de funcionar quando você começa a fatiar um número pelos dígitos. Por exemplo, se eu começo com o número 345, e o multiplico por 8 e depois por 3, eu obtenho 8280, e se fizer essas duas operações na ordem inversa, também obtenho 8280. Mas se eu inserir uma operação de “divisão por dígito” entre os dois passos, tudo se desfaz: se você fizer 8x e depois 3x, você obtém:

Mas se você fizer 3x, e depois 8x, você obtém:

Mas em um campo binário construído com uma estrutura de torre, essa abordagem funciona. A razão está na sua separabilidade: se você multiplicar um valor grande por um valor pequeno, o que acontece em cada segmento permanece em cada segmento. Se multiplicarmos 1100101010001111 por 11, isso é o mesmo que a primeira fatoração de 1100101010001111, que é

E então multiplicando cada componente separadamente por 11.

Colocando tudo junto

Geralmente, os sistemas de prova de conhecimento zero funcionam fazendo declarações sobre polinômios que representam simultaneamente declarações sobre as avaliações subjacentes: assim como vimos no exemplo de Fibonacci, 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) verifica simultaneamente todas as etapas do cálculo de Fibonacci. Verificamos declarações sobre polinômios provando avaliações em um ponto aleatório. Esta verificação em um ponto aleatório substitui a verificação do polinômio inteiro: se a equação polinomial não corresponder, a chance de corresponder a uma coordenada aleatória específica é pequena.

Na prática, uma grande fonte de ineficiência vem do fato de que, em programas reais, a maioria dos números com os quais estamos trabalhando são pequenos: índices em loops for, valores Verdadeiro/Falso, contadores e coisas similares. Mas quando “estendemos” os dados usando a codificação Reed-Solomon para dar a redundância necessária para tornar seguras as verificações baseadas em prova de Merkle, a maioria dos valores “extras” acabam ocupando o tamanho total de um campo, mesmo que os valores originais sejam pequenos.

Para contornar isso, queremos tornar o campo o menor possível. Plonky2 nos levou de números de 256 bits para números de 64 bits, e então Plonky3 foi ainda mais longe, para 31 bits. Mas mesmo isso é subótimo. Com campos binários, podemos trabalhar com bits individuais. Isso torna a codificação 'densa': se seus dados subjacentes reais tiverem n bits, então sua codificação terá n bits, e a extensão terá 8 * n bits, sem sobrecarga extra.

Agora, vamos olhar o diagrama pela terceira vez:

Em Binius, estamos comprometidos com um polinômio multilinear: um hipercubo 𝑃(x₀,x₁,…x_k) onde as avaliações individuais 𝑃(0,0…0), 𝑃(0,0…1) até 𝑃(1,1,…1) estão mantendo os dados que nos importam. Para provar uma avaliação em um ponto, nós “re-interpretamos” os mesmos dados como um quadrado. Em seguida, estendemos cada linha, usando codificação Reed-Solomon sobre grupos de bits, para fornecer aos dados a redundância necessária para que as consultas de ramificação de Merkle aleatórias sejam seguras. Em seguida, calculamos uma combinação linear aleatória de linhas, com coeficientes projetados de modo que a nova linha combinada realmente contenha a avaliação que nos interessa. Tanto esta nova linha criada (que é re-interpretada como 128 linhas de bits), quanto algumas colunas selecionadas aleatoriamente com ramos de Merkle, são passadas para o verificador.

O verificador então faz uma “combinação de linha da extensão” (ou melhor, algumas colunas da extensão), e uma “extensão da combinação de linha”, e verifica se as duas correspondem. Em seguida, eles calculam uma combinação de coluna e verificam se ela retorna o valor que o provador está reivindicando. E aqui está nosso sistema de prova (ou melhor, o esquema de compromisso polinomial, que é o principal bloco de construção de um sistema de prova).

O que não cobrimos?

• Algoritmos eficientes para estender as linhas, que são necessárias para realmente aumentar a eficiência computacional do verificador. Usamos transformadas rápidas de Fourier sobre campos binários, descritos aqui(embora a implementação exata seja diferente, porque este post usa uma construção menos eficiente não baseada em extensão recursiva).
• Aritmetização. Polinômios univariados são convenientes porque você pode fazer coisas como F(X+2)-F(X+1)-F(X) = Z(X)*H(X) para relacionar passos adjacentes no cálculo. Em um hipercubo, "o próximo passo" é muito menos interpretável do que "X+1". Você poderia fazer X+k, potências de k, mas esse comportamento de salto sacrificaria muitas das principais vantagens do Binius. A solução é apresentada no Papel Binius (Veja a Seção 4.3), mas isso é um buraco de coelho profundo em si.
• Como realmente fazer verificações de valor específico com segurança. O exemplo de Fibonacci requer verificar as condições de limite chave: F(0)=F(1)=1 e o valor de F(100). Mas com o Binius 'puro', é inseguro verificar em pontos de avaliação pré-conhecidos. Existem maneiras bastante simples de converter uma verificação de avaliação conhecida em uma verificação de avaliação desconhecida, usando o que são chamados de protocolos de verificação de soma; mas não entramos nesses detalhes aqui.
• Protocolos de pesquisa, outra tecnologia que tem sido recentemente utilizada como uma forma de tornar os sistemas de prova ultraeficientes. Binius pode ser combinado com protocolos de pesquisa para muitas aplicações.
• Indo além do tempo de verificação da raiz quadrada. A raiz quadrada é cara: uma prova de Binius de bits tem cerca de 11 MB de comprimento. Você pode remediar isso usando algum outro sistema de prova para fazer uma “prova de uma prova de Binius”, ganhando assim eficiência de Binius em provar a declaração principal e um tamanho de prova pequeno. Outra opção é o protocolo FRI-Binius muito mais complicado, que cria uma prova de tamanho polilogarítmico (como FRI regular).
• Como Binius afeta o que conta como 'SNARK-friendly'. O resumo básico é que, se você usar o Binius, não precisará mais se preocupar muito em tornar a computação 'amigável à aritmética': os hashes 'regulares' não são mais eficientes do que os hashes aritméticos tradicionais, a multiplicação módulo ou módulo não é mais uma grande dor de cabeça em comparação com a multiplicação módulo , e assim por diante. Mas este é um tópico complicado; muitas coisas mudam quando tudo é feito em binário.

Espero muitas mais melhorias nas técnicas de prova baseadas em campo binário nos próximos meses.

Isenção de responsabilidade:

1. Este artigo é reproduzido a partir de [GatePanews]Encaminhe o Título Original 'Vitalik detalha Binius: um sistema de prova eficiente baseado em campos binários'. Todos os direitos autorais pertencem ao autor original [GateVitalik Buterin*]. Se houver objeções a esta reimpressão, por favor entre em contato com oPortão Aprenderequipe, e eles vão lidar com isso prontamente.
2. Aviso de responsabilidade: As opiniões expressas neste artigo são exclusivamente do autor e não constituem qualquer conselho de investimento.
3. As traduções do artigo para outros idiomas são feitas pela equipe Gate Learn. Salvo menção em contrário, copiar, distribuir ou plagiar os artigos traduzidos é proibido.