¡Bienvenido! ¿Eres nuevo en Zcash?
La red de Zcash es joven, ¡pero evoluciona rápidamente! ¡Regístrate y nos pondremos en contacto con más información sobre cómo puedes comenzar con Zcash!

Idioma

Explicando SNARKs Parte VI: El Protocolo Pinocchio

Ariel Gabizon | May 10, 2017

<< Parte V

En la parte V vimos cómo un enunciado que Alice quiere probar a Bob puede convertirse en una forma equivalente en el "lenguaje de los polinomios", llamado Programa Aritmético Cuadrático (QAP, por sus siglas en inglés).

En esta parte, mostramos cómo Alice puede enviar una prueba muy corta a Bob mostrando que tiene una asignación satisfactoria de un QAP. Utilizaremos el Protocolo de Pinocchio de Parno, Howell, Gentry y Raykova. Pero primero recordemos la definición que dimos la última vez de un QAP:

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

Como vimos en la Parte V, Alice normalmente querrá demostrar que tiene una asignación satisfactoria que posee algunas restricciones adicionales, por ejemplo \(c_m=7\); pero ignoraremos esto aquí por simplicidad y mostraremos cómo probar simplemente el conocimiento de alguna asignación satisfactoria.

Si Alice tiene una asignación satisfactoria significa que, definiendo \(L,R,O,P\) como lo hicimos arriba, existe un polinomio \(H\) tal que \(P=H\cdot T\). En particular, para cualquier \(s\in\mathbb{F}_p\) tenemos \(P(s)=H(s)\cdot T(s)\).

Supongamos ahora que Alice no tiene una asignación satisfactoria, pero de todas maneras construye \(L,R,O,P\) como arriba a partir de una asignación insatisfactoria \((c_1,\ldots,c_m)\). Entonces tenemos la garantía de que \(T\) no divide a \(P\). Esto significa que para cualquier polinomio \(H\) de grado \(d\) como máximo, \(P\) y \(H\cdot T\) serán polinomios diferentes. Tengamos en cuenta aquí que \(P\) y \(H\cdot T\) son ambos de grado \(2d\) como máximo.

Ahora podemos usar el famoso Lema de Schwartz-Zippel que nos dice que dos polinomios diferentes de grado como máximo \(2d\) pueden ponerse de acuerdo en al menos \(2d\) puntos \(s\in\mathbb{F}_p\). Así, si \(p\) es mucho mayor que \(2d\) la probabilidad de que \(P(s)=H(s)\cdot T(s)\) para una selección aleatoria \(s\in\mathbb{F}_p\) es muy baja.

Esto nos sugiere el siguiente boceto de protocolo para probar si Alice tiene o no una asignación satisfactoria.

  1. Alice elige polinomios \(L,R,O,H\) de grado como máximo \(d\).
  2. Bob elige un punto aleatorio \(s\in\mathbb{F}_p\), y calcula \(E(T(s))\).
  3. Alice envía a Bob los ocultamientos de todos estos polinomios evaluados en \(s\), es decir, \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\).
  4. Bob comprueba si la ecuación deseada se mantiene en \(s\). Es decir, comprueba si \(E(L(s)\cdot R(s)-O(s))=E(T(s)\cdot H(s))\).

De nuevo, el punto es que si Alice no tiene una asignación satisfactoria, terminará usando polinomios en los cuales la ecuación no sea idéntica y, por lo tanto, no se sostienen en la mayoría de las opciones de \(s\). Por lo tanto, Bob los rechazará con alta probabilidad sobre su elección de \(s\) para esos casos.

La pregunta es si tenemos las herramientas para implementar este bosquejo. El punto más crucial es que Alice debe elegir los polinomios que utilizará, sin conocer \(s\). Pero este es exactamente el problema que resolvimos en el protocolo de la evaluación a ciegas verificable, que fue desarrollado en las Partes II-IV.

Dado que tenemos eso, hay cuatro puntos principales de los cuales debemos ocuparnos para convertir este bosquejo en un zk-SNARK. Nos ocuparemos de dos de ellos aquí, y de los otros dos en la siguiente parte.

Asegurarse de que Alice escoja sus polinomios según una asignación

He aquí un punto importante: si Alice no tiene una asignación satisfactoria, no significa que ella no pueda encontrar ningún polinomio \(L,R,O,H\) de grado como máximo \(d\) con \(L\cdot R-O=T\cdot H\); simplemente significa que no puede encontrar polinomios donde \(L,R\) y \(O\) hayan sido "producidos a partir de una asignación"; o sea, 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 el mismo \((c_1,\ldots,c_m)\).

El protocolo de la Parte IV sólo garantiza que ella está usando polinomios \(L,R,O\) del grado correcto, pero no que fueron producidos a partir de una asignación. Este es un punto en el que la prueba formal se vuelve algo sutil; aquí esbozamos la solución de manera imprecisa.

Vamos a combinar los polinomios \(L,R,O\) en un polinomio \(F\) de la siguiente manera:

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

El punto de multiplicar \(R\) por \(X^{d+1}\) y \(O\) por \(X^{2(d+1)}\) es que los coeficientes de \(L,R,O\) "no se mezclan" en \(F\): los coeficientes de \(1,X,\ldots,X^d\) en \(F\) son precisamente los coeficientes de \(L\), los siguientes coeficientes \(d+1\) de \(X^{d+1},\ldots,X^{2d+1}\) son precisamente los coeficientes de \(R\), y los últimos coeficientes \(d+1\) son los de \(O\).

Vamos a combinar los polinomios de la definición QAP de una manera similar, definiendo para cada \(i\in \{1,\ldots,m\}\) un polinomio \(F_i\) cuyos primeros coeficientes \(d+1\) son los coeficientes de \(L_i\), seguidos por los coeficientes de \(R_i\) y luego \(O_i\). Es decir, para cada \(i\in \{1,\ldots,m\}\) definimos el polinomio

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

Tengamos en cuenta que cuando sumamos dos de los \(F_i\), los \(L_i\), \(R_i\), y \(O_i\) "se suman por separado". Por ejemplo, \(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)\).

Más generalmente, supongamos que tenemos \(F=\sum_{i=1}^mc_i\cdot F_i\) para un \((c_1,\ldots,c_m)\). Entonces también tendremos \(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 los mismos coeficientes \((c_1,\ldots,c_m)\). En otras palabras, si \(F\) es una combinación lineal de los \(F_i\) significa que \(L,R,O\) fueron efectivamente producidos a partir de una asignación.

Por lo tanto, Bob le pedirá a Alice que pruebe que \(F\) es una combinación lineal de los \(F_i\). Esto se hace de manera similar al protocolo para la evaluación verificable:

Bob elige un \(\beta\in\mathbb{F}^*_p\) al azar, y envía a Alice los ocultamientos \(E(\beta\cdot F_1(s)),\ldots,E(\beta\cdot F_m(s))\). Luego le pide a Alice que le envíe el elemento \(E(\beta\cdot F(s))\). Si ella tiene éxito, una versión extendida de la Presunción del Conocimiento del Coeficiente" implica que ella sabe cómo escribir \(F\) en forma de una combinación lineal de los \(F_i\).

Añadir la parte de conocimiento-cero ─ ocultar la asignación

En un zk-SNARK Alice quiere ocultar toda la información sobre su asignación. Sin embargo, los ocultamientos \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\) proporcionan alguna información sobre la asignación.

Por ejemplo, dada otra asignación satisfactoria \((c'_1,\ldots,c'_m)\) Bob podría calcular el correspondiente \(L',R',O',H'\) y los ocultamientos \(E(L'(s)),E(R'(s)),E(O'(s)),E(H'(s))\). Si estos resultan ser diferentes de los ocultamientos de Alice, él podría deducir que \((c'_1,\ldots,c'_m)\) no es la asignación de Alice.

Para evitar esta fuga de información, Alice ocultará su asignación agregando un "giro \(T\) aleatorio" a cada polinomio. Es decir, elige un \(\delta_1,\delta_2,\delta_3\in\mathbb{F}^*_p\) aleatorio, y define \(L_z:=L+\delta_1\cdot T,R_z:=R+\delta_2\cdot T,O_z:=O+\delta_3\cdot T\).

Supongamos que \(L,R,O\) fueron producidos a partir de una asignación satisfactoria; por lo tanto, \(L\cdot R-O = T\cdot H\) para algún polinomio \(H\). Como acabamos de añadir un múltiplo de \(T\) en todas partes, \(T\) también divide a \(L_z\cdot R_z-O_z\). Hagamos el cálculo para ver esto:

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

Así, definiendo \(H'=H+L\cdot\delta_2 + \delta_1\cdot R + \delta_1\delta_2\cdot T\), tenemos que \(L_z\cdot R_z-O_z=T\cdot H_z\). Por lo tanto, si Alice utiliza los polinomios \(L_z,R_z,O_z,H_z\) en lugar de \(L,R,O,H\), Bob aceptará siempre.

Por otro lado, estos polinomios evaluados en \(s\in\mathbb{F}_p\) con \(T(s)\neq 0\) (que es todo excepto \(d\) \(s\)'s), no revelan ninguna información sobre la asignación. Por ejemplo, como \(T(s)\) es distinto de cero y \(\delta_1\) es aleatorio, \(\delta_1\cdot T(s)\) es un valor aleatorio, y por lo tanto \(L_z(s)=L(s)+\delta_1\cdot T(s)\) no revela ninguna información sobre \(L(s)\) ya que está enmascarado por este valor aleatorio.

¿Qué nos queda para la próxima vez?

Hemos presentado un bosquejo del Protocolo Pinocchio en el cual Alice puede convencer a Bob de que posee una asignación satisfactoria para un QAP, sin revelar información sobre esa asignación. Hay dos cuestiones principales que todavía deben ser resueltas con el fin de obtener un zk-SNARK:

  • En el bosquejo, Bob necesita un HH que "admita la multiplicación". Por ejemplo, tiene que calcular \(E(H(s)\cdot T(s))\) a partir de \(E(H(s))\) y \(E(T(s))\). Sin embargo, no hemos visto hasta ahora un ejemplo de un HH que permita esto. Hemos visto sólo un HH que admite la adición y las combinaciones lineales.
  • A lo largo de esta serie, hemos discutido protocolos interactivos entre Alice y Bob. Nuestro objetivo final, sin embargo, es permitir que Alice envíe pruebas no interactivas de un único mensaje, que sean públicamente verificables ─ lo que significa que cualquiera que vea esta prueba de un único mensaje estará convencido de su validez, y no sólo Bob (quien ya había mantenido una comunicación previa con Alice).

Ambas cuestiones pueden ser resueltas por el uso de emparejamientos de curvas elípticas, lo que discutiremos en la parte siguiente y final.

cryptography, zkSNARKs, explainers | Ver todos los tags