¡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 IV: Cómo hacer Verificable la Evaluación A Ciegas de Polinomios

Ariel Gabizon | Apr 11, 2017

<< Parte III

En este artículo nos apoyamos en lo visto en las Partes II y III para desarrollar un protocolo que haga verificable la evaluación a ciegas de polinomios, que definiremos en breve. En la Parte V empezaremos a ver cómo se puede usar un protocolo de este tipo para construir SNARKs, así que hará falta un poco más de paciencia para conectar todo esto con SNARKs :).

Supongamos, como en la Parte II, que Alice tiene un polinomio \(P\) de grado \(d\) y Bob tiene un punto \(s\in\mathbb{F}_p\) que eligió al azar. Queremos construir un protocolo que permita a Bob llegar a conocer \(E(P(s))\), es decir, la ocultación de \(P\) evaluado en \(s\), con dos propiedades adicionales:

  1. Invisibilidad: Alice no aprenderá \(s\) (y Bob no aprenderá \(P\)).
  2. Verificabilidad: La probabilidad de que Alice envíe un valor que no sea de la forma \(E(P(s))\) para un \(P\) de grado \(d\) que sea conocido por ella y de que este sea a la vez aceptado por Bob, es insignificante.

Esto es lo que llamamos una evaluación a ciegas verificable de un polinomio. El protocolo de la Parte II nos dio el primer punto pero no el segundo. Para obtener verificabilidad necesitamos una versión extendida de la Presunción del Conocimiento del Coeficiente (KCA) que fue presentada en la Parte III.

Las propiedades de verificabilidad e invisibilidad son útiles en conjunto porque hacen que Alice decida qué polinomio \(P\) usará, sin ver \(s\). [1] Esto, en cierto sentido, compromete a Alice a brindar un "polinomio de respuesta" sin ver el "punto de desafío" \(s\). Esta intuición será más clara en las próximas partes de la serie.

Un KCA Extendido

El KCA como lo definimos en la Parte III dice esencialmente algo como esto: Si Bob le da a Alice un \(\alpha\)-pair \((a,b = \alpha\cdot a)\) y luego Alice genera otro \(\alpha\)-pair \((a',b')\), entonces ella conoce un \(c\) tal que \(a'=c\cdot a\). En otras palabras, Alice conoce la relación entre \(a'\) y \(a\).

Ahora, supongamos que en lugar de uno, Bob envía a Alice varios \(\alpha\)-pairs \((a_1,b_1),\ldots,(a_d,b_d)\) (para el mismo \(\alpha\)); y que nuevamente, después de recibir estas parejas, se impone a Alice el desafío de generar otro \(\alpha\)-pair \((a',b')\). Recordemos que el punto principal es que Alice debe hacer esto sin conocer \(\alpha\).

Como vimos en la Parte III, una forma natural para que Alice genere un tal \(\alpha\)-pair sería tomar uno de los pares \((a_i,b_i)\) que recibió de Bob, y multiplicar ambos elementos por un \(c\in\mathbb{F}^*_p\); si \((a_i,b_i)\) era un \(\alpha\)-pair, entonces \((c\cdot a_i,c\cdot b_i)\) lo será también. Pero ¿puede Alice generar \(\alpha\)-pairs de más maneras ahora que ha recibido múltiples \(\alpha\)-pairs? ¿Tal vez usando varios de los \(\alpha\)-pairs simultáneamente para obtener uno nuevo?

La respuesta es sí: por ejemplo, Alice puede elegir dos valores \(c_1,c_2\in \mathbb{F}_p\) y calcular el par \((a',b')=(c_1\cdot a_1 + c_2\cdot a_2, c_1\cdot b_1 + c_2\cdot b_2)\). Un cálculo sencillo muestra que, cuando \(a'\) es distinto de cero, esto es también un \(\alpha\)-pair:

\(b' = c_1\cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2\alpha\cdot a_2 = \alpha (c_1\cdot a_1 + c_2\cdot a_2) = \alpha\cdot a'.\)

Más generalmente, Alice puede tomar cualquier combinación lineal de los pares \(d\) dados ─esto es, elegir cualquier \(c_1,\ldots,c_d\in\mathbb{F}_p\) y definir \((a',b')=(\sum_{i=1}^d c_i a_i,\sum_{i=1}^d c_ib_i)\).

Tengamos en cuenta que, si Alice utiliza esta estrategia para generar su \(\alpha\)-pair, entonces conocerá alguna relación lineal entre \(a'\) y \(a_1,\ldots,a_d\); es decir, ella conoce un \(c_1,\ldots,c_d\) tal que \(a'=\sum_{i=1}^d c_i\cdot a_i\).

El KCA extendido afirma, esencialmente, que esta es la única manera en que Alice puede generar un \(\alpha\)-pair; es decir, cada vez que lo consiga, conocerá una relación lineal tal entre \(a'\) y \(a_1,\ldots,a_d\). Más formalmente, supongamos que \(G\) es un grupo de tamaño \(p\) con un generador \(g\) escrito aditivamente como en la Parte III. La Presunción del Conocimiento del Coeficiente de grado d (d-KCA) [2] en \(G\) es la siguiente:

d-KCA: Supongamos que Bob elige al azar un \(\alpha\in\mathbb{F}_p^*\) y un \(s\in\mathbb{F}_p\), y envía a Alice los \(\alpha\)-pairs \((g,\alpha\cdot g), (s\cdot g,\alpha s\cdot g),\ldots,(s^d\cdot g,\alpha s^d\cdot g)\). Supongamos que Alice luego produce otro \(\alpha\)-pair \((a',b')\). Entonces, con la excepción de una probabilidad insignificante, Alice conoce un \(c_1,\ldots,c_d\in\mathbb{F}_p\) tal que \(\sum_{i=0}^d c_i s^i\cdot g = a'\).

Tengamos en cuenta que en el d-KCA Bob no envía un conjunto arbitrario de \(\alpha\)-pairs, sino uno con una cierta "estructura polinomial". Esto será útil en el siguiente protocolo.

El Protocolo de la Evaluación a Ciegas Verificable

Supongamos que nuestro HH es el mapeo \(E(x)=x\cdot g\) para un generador \(g\) de \(G\), como anteriormente.

Por simplicidad, presentamos el protocolo para este \(E\) en particular:

  1. Bob elige un \(\alpha\in\mathbb{F}_p^*\) al azar y envía a Alice los ocultamientos \(g,s\cdot g,\ldots,s^d\cdot g\) (of \(1,s,\ldots,s^d\)) y también los ocultamientos \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\) (de \(\alpha,\alpha s,\ldots,\alpha s^d\)).
  2. Alice calcula \(a=P(s)\cdot g\) y \(b=\alpha P(s)\cdot g\) utilizando los elementos enviados en el primer paso, y envía ambos a Bob.
  3. Bob comprueba que \(b=\alpha \cdot a\) y acepta si y sólo si esta igualdad se mantiene.

En primer lugar, tengamos en cuenta que dados los coeficientes de \(P\), \(P(s)\cdot g\) es una combinación lineal de \(g,s\cdot g,\ldots,s^d\cdot g\); y \(\alpha P(s)\cdot g\) es una combinación lineal de \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\). Así, al igual que en el protocolo de la Parte II, Alice puede de hecho calcular estos valores a partir de los mensajes de Bob para un polinomio \(P\) que ella conoce.

En segundo lugar, por el d-KCA si Alice envía \(a\), \(b\) tales que \(b=\alpha \cdot a\) entonces casi seguramente conoce \(c_1,\ldots,c_d\in\mathbb{F}_p\) tal que \(a=\sum_{i=0}^d c_is^i\cdot g\). En ese caso, \(a=P(s)\cdot g\) para el polinomio \(P(X)=\sum_{i=0}^d c_i\cdot X^i\) conocido por Alice. En otras palabras, la probabilidad de que Bob acepte en el Paso 3, y que al mismo tiempo Alice no conozca tal \(P\) es insignificante.

Para resumir, utilizando el d-KCA hemos desarrollado un protocolo para la evaluación a ciegas de polinomios verificable. En los próximos posts, veremos cómo esta herramienta se hace presente en las construcciones de SNARK.

[1]En la prueba completamente formal, las cosas son algo más sutiles, ya que Alice puede ver alguna información sobre \(s\) antes de decidir sobre su \(P\) ─por ejemplo, ⇥los ocultamientos de \(s,\ldots,s^d\).
[2]El d-KCA fue introducido en un libro blanco de Jens Groth.

cryptography, zkSNARKs, explainers | Ver todos los tags