¡Bienvenido! ¿Eres nuevo en 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 Cálculos a Polinomios

Ariel Gabizon | Apr 25, 2017

<< Parte IV

En las tres partes anteriores desarrollamos una cierta maquinaria para tratar con polinomios. En esta parte, mostramos cómo traducir a lenguaje de polinomios los enunciados que queremos probar y verificar. La idea de usar polinomios de esta manera se remonta al trabajo pionero de Lund, Fortnow, Karloff y Nisan.

En 2013, otro trabajo innovador de Gennaro, Gentry, Parno y Raykova definió una traducción extremadamente útil de cálculos a polinomios, llamada Programa de Aritmética Cuadrática (QAP, por sus siglas en inglés). Los QAP se han convertido en la base de las modernas construcciones de zk-SNARK, en particular las utilizadas por Zcash.

En este post explicamos la traducción a QAPs por via de ejemplos. Incluso si nos centramos en un pequeño ejemplo en lugar de la definición general, está claro que es mucho para digerir de una vez, así que prepárate para un cierto esfuerzo mental :).

Supongamos que Alice quiere probar a Bob que conoce \(c_1,c_2,c_3 \in \mathbb{F}_p\) tal que \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\). El primer paso será presentar la expresión calculada a partir de \(c_1,c_2,c_3\) como un circuito aritmético.

Circuitos aritméticos

Un circuito aritmético consiste en puertas que calculan operaciones aritméticas tales como sumas y multiplicaciones, con cables que conectan las puertas. En nuestro caso, el circuito se ve así:

An example of an arithmetic circuit

Los cables inferiores son los cables de entrada, y el cable superior es el cable de salida que da el resultado del cálculo de circuito sobre las entradas.

Como se puede ver en la imagen, etiquetamos los cables y las puertas del circuito de una manera muy particular, necesaria para la siguiente etapa que es la traducción del circuito a un QAP:

  • Cuando el mismo cable saliente entra en más de una puerta, todavía lo consideramos como un solo cable ─es el caso de \(\mathsf{w_1}\) en nuestro ejemplo.
  • Asumimos que las puertas de multiplicación tienen exactamente dos cables de entrada, a los que llamamos el cable izquierdo y el cable derecho.
  • No etiquetamos ni los cables que van de una puerta de adición a una de multiplicación, ni la puerta de adición; consideramos las entradas de la puerta de adición como yendo directamente a la puerta de multiplicación. De esta manera, en el caso de nuestro ejemplo consideramos a \(\mathsf{w_1}\) y \(\mathsf{w_3}\) como entradas derechas de \(\mathsf{g_2}\).

Una asignación legal para el circuito, es una asignación de valores a los cables etiquetados donde el valor de salida de cada puerta de multiplicación es de hecho el producto de las entradas correspondientes.

Así que para nuestro circuito, una asignación legal es de la forma \((c_1,\ldots,c_5)\) donde \(c_4=c_1\cdot c_2\) y \(c_5=c_4\cdot (c_1+c_3)\).

En esta terminología, lo que Alice quiere probar es que conoce una asignación legal \((c_1,\ldots,c_5)\) tal que \(c_5=7\). El siguiente paso es traducir este enunciado a uno sobre polinomios usando QAPs.

Reducción a un QAP

Asociamos cada puerta de multiplicación con un elemento de campo: \(\mathsf{g_1}\) se asociará con \(1\in\mathbb{F}_p\) y \(\mathsf{g_2}\) con \(2\in\mathbb{F}_p\). Llamamos a los puntos \(\{1,2\}\) nuestros puntos objetivo. Ahora necesitamos definir un conjunto de "polinomios de cable izquierdo" \(L_1,\ldots,L_5\), "polinomios de cable derecho" \(R_1,\ldots,R_5\) y "polinomios de cable de salida" \(O_1,\ldots,O_5\).

La idea para la definición es que los polinomios serán generalmente cero en los puntos objetivo, excepto los implicados en la puerta de multiplicación correspondiente del punto objetivo.

Concretamente, siendo \(\mathsf{w_1},\mathsf{w_2},\mathsf{w_4}\) respectivamente los cables izquierdo, derecho y de salida de \(\mathsf{g_1}\); definimos \(L_1=R_2=O_4=2-X\), como el polinomio \(2-X\) que es uno en el punto \(1\) correspondiente a \(\mathsf{g_1}\) y cero en el punto \(2\) correspondiente a \(\mathsf{g_2}\).

Notemos que \(\mathsf{w_1}\) y \(\mathsf{w_3}\) son ambas entradas derechas de \(\mathsf{g_2}\). Por lo tanto, definimos de forma similar \(L_4=R_1=R_3=O_5=X-1\), como el \(X-1\) que es uno en el punto objetivo \(2\) correspondiente a \(\mathsf{g_2}\) y cero en el otro punto objetivo.

Establecemos el resto de los polinomios como siendo el polinomio cero.

Dados valores fijos \((c_1,\ldots,c_5)\), los usamos como coeficientes para definir polinomios de "suma" de izquierda, derecha y salida. Es decir, 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\),

y luego definimos el polinomio \(P:=L\cdot R -O\).

Ahora, después de todas estas definiciones, el punto central es este: \((c_1,\ldots,c_5)\) es una asignación legal para el circuito si y sólo si \(P\) desaparece en todos los puntos objetivo.

Examinemos esto usando nuestro ejemplo. Supongamos que definimos \(L,R,O,P\) como se ha indicado más arriba, dado un \(c_1,\ldots,c_5\). Evaluemos todos estos polinomios en el punto objetivo \(1\):

De todos los \(L_i\) solo \(L_1\) es distinto de cero en \(1\). Así que tenemos \(L(1)=c_1\cdot L_1(1)=c_1\). Del mismo modo, obtenemos \(R(1)=c_2\) y \(O(1)=c_4\).

Por lo tanto, \(P(1)=c_1\cdot c_2-c_4\). Un cálculo similar muestra que \(P(2)= c_4\cdot (c_1+c_3) - c_5\).

En otras palabras, \(P\) desaparece en los puntos objetivo si y sólo si \((c_1,\ldots,c_5)\) es una asignación legal.

Ahora, usamos el siguiente hecho algebraico: Para un polinomio \(P\) y un punto \(a\in\mathbb{F}_p\), tenemos \(P(a)=0\) si y sólo si el polinomio \(X-a\) divide \(P\), es decir, \(P=(X-a)\cdot H\) para algún polinomio \(H\).

Definiendo el polinomio objetivo \(T(X):=(X-1)\cdot (X-2)\), entonces tenemos que \(T\) divide a \(P\) si y sólo si \((c_1,\ldots,c_5)\) es una asignación legal.

Siguiendo la discusión anterior, definimos un QAP de la siguiente manera:

Un Programa Aritmético Cuadrático \(Q\) de grado \(d\) y tamaño \(m\) consiste en los polinomios \(L_1,\ldots,L_m\), \(R_1,\ldots,R_m\), \(O_1,\ldots,O_m\) y un polinomio objetivo \(T\) de grado \(d\).

Una asignación \((c_1,\ldots,c_m)\) satisface \(Q\) si, definiendo \(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\) y \(P:=L\cdot R -O\), resulta que \(T\) divide a \(P\).

Usando esta terminología, Alice quiere demostrar que conoce una asignación \((c_1,\ldots,c_5)\) que satisface el QAP descrito anteriormente con \(c_5=7\).

En resumen, hemos visto cómo un enunciado del tipo "conozco \(c_1,c_2,c_3\) tal que \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\)" puede traducirse en un enunciado equivalente sobre polinomios usando QAPs. En la siguiente parte, veremos un protocolo eficiente para probar a un QAP el conocimiento de una asignación satisfactoria.

[1]En este artículo hemos intentado dar el ejemplo más conciso de una reducción a QAP; recomendamos igualmente el excelente post de Vitalik Buterin para más detalles sobre la transformación de un programa a un QAP .

cryptography, zkSNARKs, explainers | Ver todos los tags