Vitalik Buterin através do Blog de Vitalik Buterin
Este é um espelho da postagem em https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
Esta é a terceira parte de uma série de artigos que explicam como funciona a tecnologia por trás dos zk-SNARKs; os artigos anteriores sobre programas aritméticos quadráticos e pares de curvas elípticas são leitura obrigatória e este artigo pressupõe o conhecimento de ambos os conceitos. Também é assumido o conhecimento básico do que são zk-SNARKs e o que eles fazem. Veja também Artigo de Christian Reitwiessner aqui para outra introdução técnica.
Nos artigos anteriores, apresentamos o programa de aritmética quadrática, uma forma de representar qualquer problema computacional com uma equação polinomial que é muito mais passível de diversas formas de truques matemáticos. Também introduzimos pares de curvas elípticas, que permitem uma forma muito limitada de criptografia homomórfica unidirecional que permite fazer verificação de igualdade. Agora, vamos começar de onde paramos e usar pares de curvas elípticas, juntamente com alguns outros truques matemáticos, para permitir que um provador prove que conhece uma solução para um QAP específico sem revelar mais nada sobre o solução real.
Este artigo se concentrará na Protocolo Pinóquio por Parno, Gentry, Howell e Raykova de 2013 (frequentemente chamado de PGHR13); existem algumas variações no mecanismo básico, portanto, um esquema zk-SNARK implementado na prática pode funcionar de maneira um pouco diferente, mas os princípios básicos permanecerão, em geral, os mesmos.
Para começar, vamos entrar na principal suposição criptográfica subjacente à segurança do mecanismo que vamos usar: o * conhecimento do expoente* suposição.
Basicamente, se você obtiver um par de pontos � e �, onde �⋅�=�, e obtiver um ponto �, então não será possível chegar a �⋅� a menos que � seja “derivado” de � de alguma forma que você sabe. Isso pode parecer intuitivamente óbvio, mas essa suposição na verdade não pode ser derivada de qualquer outra suposição (por exemplo, dureza de log discreto) que normalmente usamos ao provar a segurança de protocolos baseados em curvas elípticas e, portanto, os zk-SNARKs de fato se baseiam em um pouco uma base mais instável do que a criptografia de curva elíptica em geral - embora ainda seja robusta o suficiente para que a maioria dos criptógrafos aceite isso.
Agora, vamos ver como isso pode ser usado. Suponhamos que um par de pontos (�,�) caia do céu, onde �⋅�=�, mas ninguém sabe qual é o valor de �. Agora, suponha que eu encontre um par de pontos (�,�) onde �⋅�=�. Então, a suposição KoE implica que a única maneira pela qual eu poderia ter obtido esse par de pontos seria tomando � e � e multiplicando ambos por algum fator r que eu pessoalmente conheço. Observe também que, graças à magia dos pares de curvas elípticas, verificando que �=�⋅� na verdade não requer saber � – em vez disso, você pode simplesmente verificar se �(�,�)=�(�,�).
Vamos fazer algo mais interessante. Suponha que temos dez pares de pontos caindo do céu: (�1,�1),(�2,�2)…(�10,�10). Em todos os casos, ��⋅�=��. Suponha que eu forneça a você um par de pontos (�,�) onde �⋅�=�. O que você sabe agora? Você sabe que � é alguma combinação linear �1⋅�1+�2⋅�2+…+�10⋅�10, onde conheço os coeficientes �1,�2…�10. Ou seja, a única maneira de chegar a tal par de pontos (�,�) é pegar alguns múltiplos de �1,�2…�10 e somá-los, e fazer o mesmo cálculo com �1,�2… �10.
Observe que, dado qualquer conjunto específico de �1…�10 pontos que você pode querer verificar combinações lineares, você não pode realmente criar os �1…�10 pontos que o acompanham sem saber o que � é, e se você sabe o que � é então que você pode criar um par (�,�) onde �⋅�=� para o que você quiser, sem se preocupar em criar uma combinação linear. Portanto, para que isso funcione, é absolutamente imperativo que quem cria esses pontos seja confiável e realmente exclua - depois de criar os dez pontos. É daí que vem o conceito de “configuração confiável”.
Lembre-se que a solução para um QAP é um conjunto de polinômios (�,�,�) tais que �(�)⋅�(�)−�(�)=�(�)⋅�(�), onde:
- � é uma combinação linear de um conjunto de polinômios {�1…��}
- � é a combinação linear de {�1…��} com os mesmos coeficientes
- � é uma combinação linear de {�1…��} com os mesmos coeficientes
Os conjuntos {�1…��},{�1…��} e {�1…��} e o polinômio � fazem parte do enunciado do problema.
No entanto, na maioria dos casos do mundo real, �,� e � são extremamente grandes; para algo com muitos milhares de portas de circuito, como uma função hash, os polinômios (e os fatores para as combinações lineares) podem ter muitos milhares de termos. Portanto, em vez de fazer com que o provador forneça as combinações lineares diretamente, usaremos o truque que introduzimos acima para que o provador prove que está fornecendo algo que é uma combinação linear, mas sem revelar mais nada.
Você deve ter notado que o truque acima funciona em pontos de curvas elípticas, não em polinômios. Portanto, o que realmente acontece é que adicionamos os seguintes valores à configuração confiável:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Você pode pensar em t como um “ponto secreto” no qual o polinômio é avaliado. � é um “gerador” (algum ponto de curva elíptica aleatório que é especificado como parte do protocolo) e �,��,�� e �� são “resíduos tóxicos”, números que devem ser absolutamente excluídos a todo custo, ou então quem os tiver poderá fazer provas falsas. Agora, se alguém lhe der um par de pontos �, � tais que �⋅��=� (lembrete: não precisamos de �� para verificar isso, pois podemos fazer uma verificação de emparelhamento), então você sabe que o que eles estamos fornecendo é uma combinação linear de �� polinômios avaliados em �.
Portanto, até agora o provador deve fornecer:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Observe que o provador não precisa realmente saber (e não deveria saber!) �,��,�� ou �� para calcular esses valores; em vez disso, o provador deverá ser capaz de calcular esses valores apenas a partir dos pontos que estamos adicionando à configuração confiável.
O próximo passo é garantir que todas as três combinações lineares tenham os mesmos coeficientes. Podemos fazer isso adicionando outro conjunto de valores à configuração confiável: �⋅(��(�)+��(�)+��(�))⋅�, onde � é outro número que deve ser considerado “tóxico desperdício” e descartado assim que a configuração confiável for concluída. Podemos então fazer com que o provador crie uma combinação linear com esses valores com os mesmos coeficientes e use o mesmo truque de emparelhamento acima para verificar se esse valor corresponde ao �+�+� fornecido.
Finalmente, precisamos provar que �⋅�−�=�⋅�. Fazemos isso mais uma vez com uma verificação de emparelhamento:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Onde �ℎ=�⋅�(�). Se a conexão entre esta equação e �⋅�−�=�⋅� não faz sentido para você, volte e leia o artigo sobre pares.
Vimos acima como converter �,� e � em pontos de curva elíptica; � é apenas o gerador (ou seja, o ponto da curva elíptica equivalente ao número um). Podemos adicionar �⋅�(�) à configuração confiável. � é mais difícil; � é apenas um polinômio, e prevemos muito pouco antecipadamente sobre quais serão seus coeficientes para cada solução QAP individual. Portanto, precisamos adicionar ainda mais dados à configuração confiável; especificamente a sequência:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
Na configuração confiável do Zcash, a sequência aqui chega a cerca de 2 milhões; esta é a quantidade de potências de � que você precisa para ter certeza de que sempre será capaz de calcular �(�), pelo menos para a instância específica do QAP com a qual eles se preocupam. E com isso o provador pode fornecer todas as informações para o verificador fazer a verificação final.
Há mais um detalhe que precisamos discutir. Na maioria das vezes, não queremos apenas provar abstratamente que existe alguma solução para algum problema específico; em vez disso, queremos provar a correção de alguma solução específica (por exemplo, provar que se você pegar a palavra “vaca” e hash SHA3 um milhão de vezes, o resultado final começa com 0x73064fe5), ou que existe uma solução se você restringir alguns dos parâmetros. Por exemplo, em uma instanciação de criptomoeda em que os valores das transações e os saldos das contas são criptografados, você deseja provar que conhece alguma chave de descriptografia k tal que:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
O criptografado old_balance
, tx_value
e new_balance
devem ser especificados publicamente, pois são esses os valores específicos que pretendemos verificar naquele momento específico; apenas a chave de descriptografia deve ser ocultada. Algumas pequenas modificações no protocolo são necessárias para criar uma “chave de verificação personalizada” que corresponda a alguma restrição específica nas entradas.
Agora, vamos recuar um pouco. Em primeiro lugar, aqui está o algoritmo de verificação completo, cortesia de Ben Sasson, Tromer, Virza e Chiesa:
A primeira linha trata da parametrização; essencialmente, você pode pensar em sua função como sendo a criação de uma “chave de verificação personalizada” para a instância específica do problema onde alguns dos argumentos são especificados. A segunda linha é a verificação de combinação linear para �,� e �; a terceira linha é a verificação de que as combinações lineares têm os mesmos coeficientes, e a quarta linha é a verificação do produto �⋅�−�=�⋅�.
Ao todo, o processo de verificação consiste em algumas multiplicações de curvas elípticas (uma para cada variável de entrada “pública”) e cinco verificações de emparelhamento, uma das quais inclui uma multiplicação de emparelhamento adicional. A prova contém oito pontos de curva elíptica: um par de pontos cada para �(�),�(�) e �(�), um ponto �� para �⋅(�(�)+�(�)+�(� )), e um ponto �ℎ para �(�). Sete desses pontos estão na curva �� (32 bytes cada, já que você pode compactar a coordenada � em um único bit), e na implementação do Zcash um ponto (��) está na curva torcida em ��2 (64 bytes), então o tamanho total da prova é de aproximadamente 288 bytes.
As duas partes computacionalmente mais difíceis de criar uma prova são:
- Dividindo (�⋅�−�)/� para obter � (algoritmos baseados no Transformação rápida de Fourier pode fazer isso em tempo subquadrático, mas ainda é bastante intensivo em termos computacionais)
- Fazendo multiplicações e adições da curva elíptica para criar os valores �(�),�(�),�(�) e �(�) e seus pares correspondentes
A razão básica pela qual criar uma prova é tão difícil é o fato de que o que era uma única porta lógica binária na computação original se transforma em uma operação que deve ser processada criptograficamente através de operações de curva elíptica se estivermos fazendo dela uma prova de conhecimento zero. . Este fato, juntamente com a superlinearidade das transformadas rápidas de Fourier, significa que a criação da prova leva cerca de 20 a 40 segundos para uma transação Zcash.
Outra questão muito importante é: podemos tentar tornar a configuração confiável um pouco… menos exigente em termos de confiança? Infelizmente não podemos torná-lo completamente confiável; a própria suposição KoE impede a criação de pares independentes (��,��⋅�) sem saber o que � é. No entanto, podemos aumentar muito a segurança usando a computação multipartidária “de” – ou seja, construindo a configuração confiável entre as partes de tal forma que, desde que pelo menos um dos participantes exclua seus resíduos tóxicos, você estará bem. .
Para ter uma ideia de como você faria isso, aqui está um algoritmo simples para pegar um conjunto existente (�,�⋅�,�⋅�2,�⋅�3…) e “adicionar” seu próprio segredo de modo que você precisa do seu segredo e do segredo anterior (ou conjunto anterior de segredos) para trapacear.
O conjunto de saída é simplesmente:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Observe que você pode produzir este conjunto conhecendo apenas o conjunto original e s, e o novo conjunto funciona da mesma maneira que o conjunto antigo, exceto agora usando �⋅� como “resíduo tóxico” em vez de �. Contanto que você e a pessoa (ou pessoas) que criaram o conjunto anterior não deixem de excluir seus resíduos tóxicos e depois conspirem, o conjunto é “seguro”.
Fazer isso para uma configuração confiável completa é um pouco mais difícil, pois há vários valores envolvidos e o algoritmo deve ser feito entre as partes em várias rodadas. É uma área de pesquisa ativa para ver se o algoritmo de computação multipartidária pode ser ainda mais simplificado e exigido para exigir menos rodadas ou mais paralelizável, pois quanto mais você puder fazer isso, mais partes se tornará viável incluir no procedimento de configuração confiável. . É razoável ver por que uma configuração confiável entre seis participantes que se conhecem e trabalham uns com os outros pode deixar algumas pessoas desconfortáveis, mas uma configuração confiável com milhares de participantes seria quase indistinguível de nenhuma confiança – e se você for realmente paranóico , você mesmo pode entrar e participar do procedimento de configuração e certificar-se de ter excluído pessoalmente seu valor.
Outra área de pesquisa ativa é o uso de outras abordagens que não utilizam emparelhamentos e o mesmo paradigma de configuração confiável para atingir o mesmo objetivo; ver A recente apresentação de Eli ben Sasson por uma alternativa (mas esteja avisado, é pelo menos tão matematicamente complicado quanto os SNARKs!)
Agradecimentos especiais a Ariel Gabizon e Christian Reitwiessner pela revisão.
- Conteúdo com tecnologia de SEO e distribuição de relações públicas. Seja amplificado hoje.
- PlatoData.Network Gerativa Vertical Ai. Capacite-se. Acesse aqui.
- PlatoAiStream. Inteligência Web3. Conhecimento Amplificado. Acesse aqui.
- PlatãoESG. Carbono Tecnologia Limpa, Energia, Ambiente, Solar, Gestão de resíduos. Acesse aqui.
- PlatoHealth. Inteligência em Biotecnologia e Ensaios Clínicos. Acesse aqui.
- BlockOffsets. Modernizando a Propriedade de Compensação Ambiental. Acesse aqui.
- Fonte: Platão Inteligência de Dados.