¡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 II: Evaluación A Ciegas de Polinomios

Ariel Gabizon | Mar 13, 2017

<< Part I

En este post, recordamos la noción de un polinomio, y explicamos la noción de "evaluación a ciegas" de un polinomio, y cómo es implementado utilizando Cifrado Homomórfico (HH). (Ver la Parte I para una explicación del HH.) En próximos posts, veremos que la evaluación a ciegas es una herramienta central para las construcciones SNARK.

Denotamos por \(\mathbb{F}_p\) el campo de tamaño \(p\); es decir, los elementos de \(\mathbb{F}_p\) son \(\{0,\ldots,p-1\}\) y la suma y la multiplicación se realizan \(\mathrm{mod}\;p\) como es explicado en la Parte I.

Polinomios y combinaciones lineales

Recordemos que un polinomio \(P\) de grado \(d\) sobe \(\mathbb{F}_p\) es una expresión de la fórmula

\(P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + \ldots + a_d\cdot X^d\), for some \(a_0,\ldots,a_d\in\mathbb{F}_p.\)

Podemos evaluar \(P\) en un punto \(s\in {\mathbb{F}_p}\) al sustituir \(s\) por \(X\), y computar la suma resultante

\(P(s) = a_0 + a_1\cdot s + a_2\cdot s^2 + \ldots + a_d\cdot s^d\)

Para quien conozca \(P,\) el valor \(P(s)\) es una combinación lineal de los valores \(1,s,\ldots,s^d\) - donde combinación lineal solo significa una "suma agregada", en el caso de \(P(s)\) los "agregados" serían \(a_0,\ldots,a_d.\)

En el último post, vimos al HH \(E\) definido por \(E(x)=g^x\) w donde lgl era el generador de un grupo con un complejo problema de logartimo discreto. Mencionamos que este HH "soporta adición" en el sentido que \(E(x+y)\) c puede ser computado de \(E(x)\) y \(E(y)\). Además indicamos que también "soporta combinaciones lineales", lo que significa que, dados \(a,b,E(x),E(y),\) podemos computar \(E(ax+by)\). Esto resulta simplemente porque

\(E(ax+by)=g^{ax+by}=g^{ax}\cdot g^{by} = (g^x)^a\cdot (g^y)^b = E(x)^a\cdot E(y)^b.\)

Evaluación a ciegas de un polinomio

Supongamos que Alicia tiene un polinomio \(P\) de grado \(d\), y Roberto tiene un punto \(s\in\mathbb{F}_p\) que ha eligido al azar. Roberto desea aprender \(E(P(s))\), es decir, el HH de la evaluación de \(P\) en \(s.\) Dos maneras sencillas de hacer esto son:

  • Alicia envía \(P\) a Roberto, y él computa \(E(P(s))\) por su cuenta.
  • Roberto envía \(s\) a Alicia; ella computa \(E(P(s))\) y lo envía a Roberto.

Sin embargo, en el problema de evaluación a ciegas queremos que Roberto obtenga \(E(P(s))\) sin \(P\) - lo cual descarta la primera opción; y, más importante aún, no queremos que Alicia obtenga \(s\), lo cual descarta la segunda [1].

Utilizando HH, podemos realizar una evaluación a ciegas de la siguiente manera.

  1. Roberto envía a Alicia los \(E(1),E(s),\ldots,E(s^d).\) ocultos
  2. Alicia computa \(E(P(s))\) a partir de los elementos enviados en el primer paso, y envía \(E(P(s))\) a Roberto. (Alicia puede hacer esto porque \(E\) soporta combinaciones lineales y \(P(s)\) es una combinación lineal de \(1,s,\ldots,s^d.)\)

Ten en cuenta que, al solamente realizar envíos ocultos, ni Alicia conoce \(s\) [2], ni Roberto conoce \(P\).

¿Por qué esto es útil?

En los próximos posts entraremos en mayor detalle sobre cómo la evaluación a ciegas es utilizada en SNARKs. Un primer acercamiento nos dice que el verificador tiene un polinomio "correcto" en mente, y desea asegurarse de que el comprobador lo conoce. Haciendo que el comprobador evalúe el polinomio a ciegas en un punto al azar desconocido por él, asegura que el comprobante dé una respuesta probablemente errónea si el polinomio no es el correcto. Esto, sucesivamente, afirma la frase de Schwartz-Zippel Lemma que dice que "diferentes polinomios son diferentes en la mayoría de sus puntos".

[1]La razón principal por la que no queremos enviar \(P\) a Roberto es que simplemente son elementos - (d+1) grandes, donde, por ejemplo, d~2000000 en el actual protocolo Zcash; esto se relaciona finalmente con la parte "Succinta" de SNARKs. Es verdad que la secuencia oculta que Roberto envía a Alicia es igualmente larga, pero resultará que esta secuencia puede ser "hard-codeada" en los parámetros del sistema, donde el mensaje de Alicia será diferente para cada prueba de SNARK.
[2]De hecho, la propiedad de ocultamiento solo garantiza que \(s\) no sea recuperable de \(E(s)\), pero aquí queremos afirmar que tampoco es recuperable de la secuencia \(E(s),\ldots,E(s^d)\) que potencialmente contiene más informaición sobre \(s\). Esto se deriva de la suposición d-power Diffie-Hellman, que termina siendo una suposición necesaria para la seguridad de SNARK.