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 V: de Computações a Polinômios

Ariel Gabizon | Apr 25, 2017

<< Parte IV

Nas três partes anteriores, desenvolvemos uma certa maquinaria para lidar com polinômios. Nesta parte, mostramos como traduzir declarações que gostaríamos de provar e verificar para a linguagem de polinômios. A ideia de usar polinômios dessa maneira remonta ao trabalho inovador de Lund, Fortnow, Karloff e Nisan.

Em 2013, outro trabalho inovador de Gennaro, Gentry, Parno e Raykova definiu uma tradução extremamente útil de computações em polinômios chamados de Quadratic Arithmetic Program (QAP) . Os QAPs tornaram-se a base para construções modernas de zk-SNARK, em particular aquelas usadas pela Zcash.

Neste post explicamos a tradução para QAPs por exemplos. Mesmo quando se concentrar em um pequeno exemplo, em vez da definição geral, é inevitável que é muito para digerir no início, então esteja preparado para um certo esforço mental :).

Suponha que Alice quer provar a Bob que ela conhece \(c_1,c_2,c_3 \in \mathbb{F}_p\) de tal modo que \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\). O primeiro passo é apresentar a expressão calculada de \(c_1,c_2,c_3\) como um circuito aritmético.

Circuitos Aritméticos

Um circuito aritmético consiste em portas que calculam operações aritméticas como adição e multiplicação, com fios conectando as portas. No nosso caso, o circuito se parece com isto:

An example of an arithmetic circuit

Os fios inferiores são os fios de entrada e o fio superior é o fio de saída que dá o resultado da computação do circuito nas entradas.

Como pode ser visto na imagem, rotulamos os fios e as portas do circuito de uma maneira muito particular, isso é necessário para a etapa seguinte de traduzir o circuito em um QAP:

  • Quando o mesmo fio de saída entra em mais de um portão, ainda o consideramos como um fio - como \(\mathsf{w_1}\) no exemplo.
  • Assumimos que as portas de multiplicação têm exatamente dois fios de entrada, que chamamos de fio esquerdo e fio direito.
  • Nós não rotulamos os fios que vão de uma adição ao portão de multiplicação, nem o portão de adição; Pensamos nas entradas da porta de adição como indo diretamente para a porta de multiplicação. Assim, no exemplo, pensamos em \(\mathsf{w_1}\) e \(\mathsf{w_3}\) como sendo entradas corretas de \(\mathsf{g_2}\).

A atribuição legal para o circuito é uma atribuição de valores aos fios rotulados onde o valor de saída de cada porta de multiplicação é de fato o produto das entradas correspondentes.

Assim, para o nosso circuito, uma atribuição legal tem a seguinte forma: \((c_1,\ldots,c_5)\) onde \(c_4=c_1\cdot c_2\) and \(c_5=c_4\cdot (c_1+c_3)\).

Nesta terminologia, o que Alice quer provar é que ela conhece uma tarefa legal \((c_1,\ldots,c_5)\) tal que \(c_5=7\). O próximo passo é traduzir esta declaração em uma sobre polinômios usando QAPs.

Redução para um QAP

Associamos cada porta de multiplicação com um elemento de campo: \(\mathsf{g_1}\) será associado com \(1\in\mathbb{F}_p\) e \(\mathsf{g_2}\) com \(2\in\mathbb{F}_p\). Chamamos os pontos \(\{1,2\}\) nossos pontos-alvo. Agora precisamos definir um conjunto de "polinômios do fio esquerdo" \(L_1,\ldots,L_5\), "polinômios do fio direito" \(R_1,\ldots,R_5\) e "polinômios de fios de saída" \(O_1,\ldots,O_5\).

A ideia para a definição é que os polinômios serão geralmente zero nos pontos de destino, exceto os envolvidos na porta de multiplicação correspondente do ponto alvo.

Concretamente, como \(\mathsf{w_1},\mathsf{w_2},\mathsf{w_4}\) são, respectivamente, os fios esquerdo, direito e de saída de \(\mathsf{g_1}\); Definimos \(L_1=R_2=O_4=2-X\), como o polinômio \(2-X\) é um no ponto \(1\) correspondente a \(\mathsf{g_1}\) e zero no ponto \(2\) correspondente a \(\mathsf{g_2}\).

Observe que \(\mathsf{w_1}\) e \(\mathsf{w_3}\) são ambas entradas corretas de \(\mathsf{g_2}\). Portanto, definimos de forma semelhante \(L_4=R_1=R_3=O_5=X-1\) - como \(X-1\) é um no ponto alvo \(2\) correspondente a \(\mathsf{g_2}\) e zero no outro ponto alvo.

Definimos o restante dos polinômios como o polinômio zero.

Dados valores fixos \((c_1,\ldots,c_5)\) os utilizamos como coeficientes para definir polinômios de "soma" à esquerda, à direita e à saída. Ou seja, definimos

\(L:=\sum_{i=1}^5 c_i\cdot L_i, R:=\sum_{i=1}^5 c_i\cdot R_i, O:=\sum_{i=1}^5 c_i\cdot O_i\),

e então nós definimos o polinômio \(P:=L\cdot R -O\).

Agora após todas essas definições, o ponto central é este: \((c_1,\ldots,c_5)\) é uma atribuição legal ao circuito se e somente se *|P| desaparece em todos os pontos-alvo*.

Vamos examinar isso usando nosso exemplo. Suponhamos que definimos \(L,R,O,P\) como acima dado alguns \(c_1,\ldots,c_5\). Vamos avaliar todos esses polinômios no ponto alvo \(1\):

De todos os \(L_i\) apenas \(L_1\) não é zero em \(1\). Portanto, temos \(L(1)=c_1\cdot L_1(1)=c_1\). Da mesma forma, obtemos \(R(1)=c_2\) and \(O(1)=c_4\).

Assim, \(P(1)=c_1\cdot c_2-c_4\). um cálculo similar mostra \(P(2)= c_4\cdot (c_1+c_3) - c_5\).

Em outras palavras, \(P\) desaparece nos pontos-alvo se e somente se \((c_1,\ldots,c_5)\) for uma atribuição legal.

Agora, usamos o seguinte fato algébrico: para um polinômio \(P\) e um ponto \(a\in\mathbb{F}_p\), temos \(P(a)=0\) se e somente se o polinômio \(X-a\) divide \(P\), por exemplo \(P=(X-a)\cdot H\) para algum polinômio \(H\).

Definindo o polinômio alvo \(T(X):=(X-1)\cdot (X-2)\), temos portanto que \(T\) divide \(P\) se e somente se \((c_1,\ldots,c_5)\) for uma atribuição legal.

Após a discussão acima, definimos um QAP como segue:

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\).

Nesta terminologia, Alice quer provar que conhece uma tarefa \((c_1,\ldots,c_5)\) satisfazendo o QAP descrito acima com \(c_5=7\).

Para resumir, vimos como uma afirmação como "eu sei \(c_1,c_2,c_3\) tal que \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\)" pode ser traduzida em uma declaração equivalente sobre polinômios usando QAPs. Na próxima parte, veremos um protocolo eficiente para provar o conhecimento de uma atribuição satisfatória a um QAP.

[1]Neste post, tentamos dar o exemplo mais conciso de uma redução para QAP; também recomendamos o excelente post de Vitalik Buterin para mais detalhes sobre a transformação de um programa para um QAP .

cryptography, zkSNARKs, explainers | Veja todas as tags