Bem vindo! Novo em Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

Idioma

Explicando SNARKs Parte VI: O Protocolo Pinóquio

Ariel Gabizon | May 10, 2017

<< Part V

Na parte V vimos como uma situação na qual Alice gostaria de provar a Bob pode ser convertida em uma forma equivalente na "linguagem dos polinômios" chamada Quadratic Arithmetic Program (QAP).

Nesta parte, mostramos como Alice pode enviar uma prova muito curta para Bob mostrando que ela tem uma atribuição satisfatória para um QAP. Usaremos o Protocolo Pinóquio de Parno, Howell, Gentry e Raykova. Mas primeiro vamos recordar a definição sobre o que é um QAP, que demos no último post:

Um programa aritmético quadrático \(Q\) de grau \(d\) e tamanho \(m\) consiste em polinômios \(L_1,\ldots,L_m\), \(R_1,\ldots,R_m\), \(O_1,\ldots,O_m\) e um polinômio alvo \(T\) de grau \(d\).

Uma tarefa \((c_1,\ldots,c_m)\) satisfaz \(Q\) se definindo \(L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i\) e \(P:=L\cdot R -O\), temos que \(T\) divide \(P\).

Como vimos na Parte V, Alice normalmente quer provar que ela tem uma tarefa satisfatória que possui algumas restrições adicionais, por exemplo \(c_m=7\); mas ignoramos isso aqui por simplicidade, e mostramos como apenas provar o conhecimento de alguma tarefa satisfatória.

Se Alice tem uma atribuição satisfatória significa que, definindo \(L,R,O,P\) como acima, existe um polinômio \(H\) de tal modo que \(P=H\cdot T\). Em particular, para qualquer \(s\in\mathbb{F}_p\) temos \(P(s)=H(s)\cdot T(s)\).

Suponha agora que Alice não tenha uma tarefa satisfatória, mas ela ainda constrói \(L,R,O,P\) como acima a partir de alguma atribuição insatisfatória \((c_1,\ldots,c_m)\). Então temos a garantia de que \(T\) não divide \(P\). Isso significa que para qualquer polinômio \(H\) de grau no máximo \(d\), \(P\) e \(H\cdot T\) serão polinomiais diferentes. Observe que \(P\) e \(H\cdot T\) aqui são ambos de grau máximo \(2d\).

Agora podemos usar o famoso Lema de Schwartz-Zippel que nos diz que dois polinômios diferentes de grau no máximo \(2d\) podem concordar no máximo \(2d\) pontos \(s\in\mathbb{F}_p\). Assim, se \(p\) é muito maior que \(2d\) a probabilidade de que \(P(s)=H(s)\cdot T(s)\) para um aleatoriamente escolhido \(s\in\mathbb{F}_p\) é muito pequena.

Isso sugere o seguinte esboço de protocolo para testar se Alice tem uma tarefa satisfatória.

  1. Alice escolhe polinômios \(L,R,O,H\) de grau no máximo \(d\).
  2. Bob escolhe um ponto aleatório \(s\in\mathbb{F}_p\), e calcula \(E(T(s))\).
  3. Alice envia a Bob os 'esconderijos' <https://z.cash/blog/snark-explain1.html>`_ de todos esses polinômios avaliados em \(s\), exemplo \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\).
  4. Bob verifica se a equação desejada se mantém em \(s\). Ou seja, ele verifica se \(E(L(s)\cdot R(s)-O(s))=E(T(s)\cdot H(s))\).

Novamente, o ponto é que se Alice não tiver uma tarefa satisfatória, ela vai acabar usando polinômios onde a equação não é idêntica e, portanto, não detém, no máximo, as escolhas de \(s\). Portanto, Bob vai rejeitar com alta probabilidade sobre a sua escolha de \(s\) nesse caso.

A questão é se temos as ferramentas para implementar este esboço. O ponto mais crucial é que Alice deve escolher os polinômios que ela usará, sem saber \(s\). Mas este é exatamente o problema que resolvemos no protocolo de avaliação cega verificável, que foi desenvolvido nas Partes II-IV.

Dado que temos isso, há quatro pontos principais que precisam ser abordados para transformar este esboço em um zk-SNARK. Nós lidamos com dois deles aqui, e os outros dois na próxima parte.

Certificando que Alice escolhe polinômios conforme uma atribuição

Aqui está um ponto importante: se Alice não tem uma missão satisfatória, isso não significa que ela não pode encontrar quaisquer polinômios \(L,R,O,H\) de grau no máximo \(d\) com \(L\cdot R-O=T\cdot H\), apenas significa que ela não pode encontrar tais polinômios onde \(L,R\) e \(O\) foram "produzidos a partir de uma atribuição"; Ou seja, que \(L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i\) para o mesmo \((c_1,\ldots,c_m)\).

O protocolo da Parte IV apenas garante que ela está usando alguns polinômios \(L,R,O\) do grau certo, mas não que eles foram produzidos a partir de uma atribuição. Este é um ponto onde a prova formal fica um pouco sutil; aqui esboçamos a solução de forma imprecisa.

Vamos combinar os polinômios \(L,R,O\) em um polinômio \(F\) do seguinte modo:

\(F=L+X^{d+1}\cdot R+X^{2(d+1)}\cdot O\)

O ponto de multiplicação \(R\) por \(X^{d+1}\) e \(O\) por \(X^{2(d+1)}\) é que os coeficientes de \(L,R,O\) "mão misturem" em \(F\): os coeficientes de \(1,X,\ldots,X^d\) em \(F\) são precisamente os coeficientes de \(L\), Os próximos \(d+1\) coeficientes de \(X^{d+1},\ldots,X^{2d+1}\) são precisamente os coeficientes de \(R\), e o último \(d+1\) coeficientes são aqueles de \(O\).

Vamos combinar os polinômios na definição QAP de forma semelhante, Definindo para cada \(i\in \{1,\ldots,m\}\) um polinômio \(F_i\) cujos primeiros \(d+1\) coeficientes de \(L_i\), seguidos os coeficientes de \(R_i\) e então \(O_i\) . Ou seja, para cada \(i\in \{1,\ldots,m\}\) definimos o polinômio

\(F_i=L_i+X^{d+1}\cdot R_i+X^{2(d+1)}\cdot O_i\)

Note que quando nós somamos dois dos \(F_i\)'s o \(L_i\), \(R_i\), e \(O_i\) "soma separadamente" Por exemplo, \(F_1+F_2 = (L_1+L_2)+X^{d+1}\cdot (R_1+R_2)+X^{2(d+1)}\cdot(O_1+O_2)\).

Mais geralmente, suponha que tivemos \(F=\sum_{i=1}^mc_i\cdot F_i\) para alguns \((c_1,\ldots,c_m)\). Então também teremos \(L=\sum_{i=1}^m c_i\cdot L_i, R=\sum_{i=1}^m c_i\cdot R_i, O=\sum_{i=1}^m c_i\cdot O_i\) para os mesmos coeficientes \((c_1,\ldots,c_m)\). Em outras palavras, se \(F\) é uma combinação linear de \(F_i\)'s significa que \(L,R,O\) foram realmente produzidos a partir de uma atribuição.

Portanto, Bob pedirá a Alice para lhe provar que \(F\) é uma combinação linear do \(F_i\)'s. Isso é feito de forma semelhante ao protocolo para avaliação verificável:

Bob escolhe um aleatório \(\beta\in\mathbb{F}^*_p\), e envia para Alice os esconderijos \(E(\beta\cdot F_1(s)),\ldots,E(\beta\cdot F_m(s))\). Ele então pede a Alice para enviar-lhe o elemento \(E(\beta\cdot F(s))\). Se for bem-sucedida, uma versão estendida do Conhecimento de Coeficiente Assunção implica que ela sabe escrever \(F\) como uma combinação linear dos \(F_i\)'s.

Adicionando a parte do conhecimento-nulo - ocultando a atribuição

Em um zk-SNARK Alice quer ocultar todas as informações sobre sua atribuição. No entanto, os esconderijos \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\) fornecem algumas informações sobre a atribuição.

Por exemplo, dado algum outro trabalho satisfatório \((c'_1,\ldots,c'_m)\) Bob poderia calcular o correspondente \(L',R',O',H'\) e esconderijos \(E(L'(s)),E(R'(s)),E(O'(s)),E(H'(s))\). Se estes forem diferentes dos esconderijos de Alice, ele poderia deduzir que \((c'_1,\ldots,c'_m)\) não é a tarefa de Alice.

Para evitar tal vazamento de informações sobre sua atribuição, Alice vai esconder sua atribuição, adicionando um "random \(T\)-shift" para cada polinômio. Ou seja, ela escolhe aleatoriamente \(\delta_1,\delta_2,\delta_3\in\mathbb{F}^*_p\), e define \(L_z:=L+\delta_1\cdot T,R_z:=R+\delta_2\cdot T,O_z:=O+\delta_3\cdot T\).

Suponha que \(L,R,O\) foram produzidos a partir de uma atribuição satisfatória; portanto, \(L\cdot R-O=T\cdot H\) para algum polinômio \(H\). Como acabamos de adicionar um múltiplo de \(T\) em todos os lugares, \(T\) também divide \(L_z\cdot R_z-O_z\). Vamos fazer o cálculo para ver isso:

\(L_z\cdot R_z-O_z = (L+\delta_1\cdot T)(R+\delta_2\cdot T) - O-\delta_3\cdot T\) \(= (L\cdot R-O) + L\cdot \delta_2\cdot T + \delta_1\cdot T\cdot R + \delta_1\delta_2\cdot T^2 - \delta_3\cdot T\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) \(=T\cdot (H+L\cdot \delta_2 + \delta_1\cdot R + \delta_1 \delta_2\cdot T)\)

Assim, definindo \(H'=H+L\cdot\delta_2 + \delta_1\cdot R + \delta_1\delta_2\cdot T\), temos que \(L_z\cdot R_z-O_z=T\cdot H_z\). Portanto, se Alice usa os polinômios \(L_z,R_z,O_z,H_z\) em vez de \(L,R,O,H\), Bob sempre aceitará.

Por outro lado, esses polinômios avaliados em \(s\in\mathbb{F}_p\) com \(T(s)\neq 0\) (que é tudo menos \(d\) \(s\)'s), não revelam nenhuma informação sobre a atribuição. Por exemplo, como \(T(s)\) é não-zero e \(\delta_1\) é aleatório, \(\delta_1\cdot T(s)\) é um valor aleatório, e, portanto, \(L_z(s)=L(s)+\delta_1\cdot T(s)\) não revela informações sobre \(L(s)\) como é mascarado por este valor aleatório.

O que nos resta pela frente?

Apresentamos um esboço do Protocolo Pinóquio no qual Alice pode convencer Bob que la possui uma tarefa satisfatória para um QAP, sem revelar informações sobre essa atribuição. Há duas questões principais que ainda precisam ser resolvidas para obter um zk-SNARK:

  • No esboço, Bob precisa de um HH que "suporte a multiplicação". Por exemplo, ele precisa calcular \(E(H(s)\cdot T(s))\) de \(E(H(s))\) e \(E(T(s))\) Contudo, não vimos até agora um exemplo de um HH que permita isso. Nós somente vimos um HH que suporta combinações de adição e linear.
  • Ao longo desta série, discutimos protocolos interativos entre Alice e Bob. Nosso objetivo final, no entanto, é permitir que Alice envie uma única mensagem com provas não-interativas, que são publicamente verificáveis - o que significa que qualquer pessoa que veja esta prova será convencida de sua validade, não apenas Bob (que teve teve a priori comunicação com Alice).

Ambas estas questões podem ser resolvidas pelo uso de pares de curvas elípticas, que discutiremos na próxima e última parte.

cryptography, zkSNARKs, explainers | Veja todas as tags