¡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 VII: Emparejamientos de Curvas Elípticas

Ariel Gabizon | Jun 07, 2017

<< Parte VI

En la Parte VI, vimos un esbozo del zk-SNARK Pinocchio. Nos faltaban dos cosas: un HH que sea a la vez compatible con la adición y con la multiplicación ─necesario para los controles del verificador─, y una transición de un protocolo interactivo a un sistema de pruebas no interactivo.

En este post veremos que usando curvas elípticas podemos obtener un tipo de HH limitado, pero suficiente para nuestros propósitos, que soporta la multiplicación. A continuación, demostraremos que este HH limitado también alcanza para convertir nuestro protocolo al sistema no interactivo deseado.

Comenzamos por presentar las curvas elípticas y explicar cómo ellas nos darán el HH necesario.

Curvas elípticas y sus emparejamientos

Supongamos que \(p\) es un primo mayor que \(3\), y tomemos un \(u,v\in\mathbb{F}_p\) tal que \(4u^3+27v^2\neq 0\). Vemos la ecuación

\(Y^2=X^3 +u\cdot X +v\)

Una curva elíptica \({\mathcal C}\) es el conjunto de los puntos \((x,y)\) [1] que satisfacen tal ecuación. Estas curvas nos brindan una forma interesante de construir grupos. Los elementos del grupo serán los puntos \((x,y)\in \mathbb{F}^2_p\) que están en la curva, es decir, que satisfacen la ecuación, junto con un punto especial \({\mathcal O}\), al que por razones técnicas nos referimos a veces como el "punto en el infinito", y sirve como elemento de identidad, es decir, el cero del grupo.

Ahora la pregunta es cómo añadir dos puntos \(P=(x_1,y_1),Q=(x_2,y_2)\) para obtener un tercero. La regla de la adición se deriva de un objeto algo abstracto llamado grupo de la clase divisor de la curva. Para nuestros propósitos, todo lo que necesitamos saber acerca de este grupo de la clase divisor es que impone la siguiente restricción a la definición de adición: la suma de puntos en cualquier línea debe ser cero, es decir, \({\mathcal O}\).

Veamos cómo la regla de la adición se deriva de esta restricción. Imaginemos una línea vertical, definida por una ecuación de la forma \(X=c\). Supongamos que esta línea intersecta la curva en un punto \(P=(x_1,y_1)\). Debido a que la ecuación de la curva es de la forma \(Y^2=f(X)\), si \((x_1,y_1)\) pertenece a la curva, también lo hará el punto \(Q:=(x_1,-y_1)\). Además, puesto que es una línea vertical y la ecuación de la curva es de segundo grado en \(Y\), podemos estar seguros de que estos son los únicos puntos donde la línea y la curva se cruzan.

Test |P+Q=O --> P=-Q|

Por lo tanto, debemos tener \(P+Q={\mathcal O}\) lo que significa que \(P=-Q\); es decir que \(Q\) es el inverso de \(P\) en el grupo.

Ahora veamos dos puntos \(P\) y \(Q\) que tengan una coordenada primera diferente ─es decir, \(x_1\neq x_2\) ─, y veamos cómo sumarlos. Pasamos una línea a través de \(P\) y \(Q\).

Test |P+Q+R=0|

Dado que la curva se define por un polinomio de grado tres en \(X\) y que ya intersecta esta línea (no vertical) en dos puntos, estará garantizada la intersección de la línea en un tercer punto, que denotamos \(R=(x,y)\), y en ningún otro.

Así que deberíamos tener \(P+Q+R={\mathcal O}\), lo que significa que \(P+Q=-R\); y ahora ya sabemos que \(-R\) se obtiene a partir de \(R\) cambiando la segunda coordenada de \(y\) a \(-y\).

Por lo tanto, hemos derivado la regla de la adición para nuestro grupo: dados los puntos \(P\) y \(Q\), pasar una línea a través de ellos, y luego tomar el punto "espejo" del tercer punto de intersección de la línea como el resultado de la adición. [2]

A este grupo se le llama generalmente \({\mathcal C}(\mathbb{F}_p)\) ─ya que consiste en puntos en la curva \({\mathcal C}\) con coordenadas en \(\mathbb{F}_p\) ─, pero vamos a llamarlo \(G_1\) de ahora en adelante. Supongamos por simplicidad que el número de elementos en \(G_1\) es un número primo \(r\), y es diferente de \(p\). Esto es muchas veces el caso, por ejemplo en la curva que Zcash está usando actualmente. En este caso, cualquier elemento \(g\in G_1\) diferente de \({\mathcal O}\) genera \(G_1\).

El entero \(k\) más pequeño para el cual \(r\) divide a \(p^k-1\) es denominado el grado de incrustación de la curva. Se conjetura que cuando \(k\) no es demasiado pequeño, digamos, al menos \(6\), entonces el problema del logaritmo discreto en \(G_1\), es decir, hallar \(\alpha\) de \(g\) y \(\alpha \cdot g\), es muy difícil. (En las curvas BN [3] actualmente utilizadas por Zcash, se cumple que \(k=12\).)

El grupo multiplicativo de \(\mathbb{F}_{p^k}\) contiene un subgrupo de orden \(r\) que llamamos \(G_T\). Podemos ver puntos de la curva con coordenadas en \(\mathbb{F}_{p^k}\) y no sólo en \(\mathbb{F}_p\). Bajo la misma regla de la adición, estos puntos también forman un grupo junto con \({\mathcal O}\) llamado \({\mathcal C}(\mathbb{F}_{p^k})\). Tengamos en cuenta que \({\mathcal C}(\mathbb{F}_{p^k})\) contiene claramente \(G_1\). Además de \(G_1\), \({\mathcal C}(\mathbb{F}_{p^k})\) contendrá un subgrupo adicional \(G_2\) de orden \(r\) (de hecho, contendrá \(r-1\) subgrupos adicionales de orden \(r\)).

Fijar los generadores \(g\in G_1,h\in G_2\). Resulta que existe un mapa eficiente, llamado emparejamiento reducido Tate, que lleva un par de elementos de \(G_1\) y \(G_2\) a un elemento de \(G_T\),

tal que

  1. \(\mathrm{Tate}(g,h)=\mathbf{g}\) para un generador \(\mathbf{g}\) de \(G_T\), y
  2. dado un par de elementos \(a,b \in \mathbb{F}_r\), tenemos \(\mathrm{Tate}(a\cdot g,b\cdot h)=\mathbf{g}^{ab}\).

Definir \(\mathrm{Tate}\) está un poco más allá del alcance de esta serie, y se basa en conceptos de la geometría algebraica, principalmente en el concepto de los divisores. Aquí vemos un bosquejo de la definición de \(\mathrm{Tate}\): [4]

Para \(a\in\mathbb{F}_p\) el polinomio \((X-a)^r\) tiene un cero de multiplicidad \(r\) en el punto \(a\), y ningún otro cero. Para un punto \(P\in G_1\), los divisores nos permiten probar que existe una función \(f_P\) de la curva a \(\mathbb{F}_p\) que también tiene, en cierto sentido preciso, un cero de multiplicidad \(r\) en \(P\) y ningún otro cero. \(\mathrm{Tate}(P,Q)\) se define entonces como \(f_P(Q)^{(p^k-1)/r}\).

Puede que no parezca en absoluto claro lo que esta definición tiene que ver con las propiedades declaradas, y de hecho la prueba de que \(\mathrm{Tate}\) tiene estas propiedades es bastante compleja.  Definiendo \(E_1(x) := x\cdot g, E_2(x):=x\cdot h, E(x):=x\cdot \mathbf{g}\), obtenemos una versión débil de un HH que soporta tanto la adición como la multiplicación: \(E_1,E_2,E\) son HHs que soportan la adición, y dados los ocultamientos \(E_1(x)\), \(E_2(y)\) podemos calcular \(E(xy)\). En otras palabras, si tenemos los ocultamientos "correctos" de \(x\) y de \(y\) podemos obtener un ocultamiento (diferente) de \(xy\). Pero por ejemplo, si tuviéramos ocultamientos de \(x,y,z\) no podríamos obtener un ocultamiento de \(xyz\).

Pasemos a discutir sistemas de pruebas no interactivos. Comenzamos explicando exactamente lo que entendemos por 'no interactivo'.

Pruebas no interactivas en el modelo de cadena de referencia común

La noción más fuerte e intuitiva de una prueba no interactiva es probablemente la siguiente: para probar una cierta pretensión, un prover difunde un solo mensaje a todas las partes, sin una comunicación previa de ningún tipo, y cualquiera que lea este mensaje estará convencido de la afirmación del prover. Esto puede demostrarse como imposible en la mayoría de los casos. [5]

Una noción ligeramente relajada de la prueba no interactiva es permitir una cadena de referencia común (CRS). En el modelo CRS, antes de que se construyan las pruebas, hay una fase de configuración en la que se construye una cadena de acuerdo con un determinado proceso aleatorio y se transmite a todas las partes. Esta cadena se llama CRS y luego se utiliza para ayudar a construir y verificar las pruebas. La suposición es que la aleatoriedad utilizada en la creación de la CRS no es conocida por ninguna de las partes, ya que el conocimiento de esta aleatoriedad podría permitir construir pruebas de afirmaciones falsas.

Explicaremos cómo en el modelo CRS podemos convertir el protocolo de evaluación a ciegas verificable de la Parte IV en un sistema de pruebas no interactivo. Como el protocolo de la Parte VI consistió en algunos de estos subprotocolos, puede convertirse en un sistema de prueba no interactivo de una manera similar.

Un protocolo de evaluación no interactivo

La versión no interactiva del protocolo de evaluación consiste básicamente en publicar el primer mensaje de Bob como CRS. Recordemos que el propósito del protocolo es obtener el ocultamiento \(E(P(s))\) del polinomio \(P\) de Alice en un \(s\in\mathbb{F}_r\) elegido al azar.

Preparación: Se eligen \(\alpha\in \mathbb{F}_r^*,s\in\mathbb{F}_r\) aleatorios y es publicado el CRS:
\((E_1(1),E_1(s),\ldots,E_1(s^d),\) \(E_2(\alpha),E_2(\alpha s),\ldots,E_2(\alpha s^d))\)
.

Prueba: Alice calcula \(a=E_1(P(s))\) y \(b=E_2(\alpha P(S))\) utilizando los elementos del CRS, y el hecho de que \(E_1\) y \(E_2\) soportan combinaciones lineales.

Verification: Fix the \(x,y\in \mathbb{F}_r\) tal que \(a=E_1(x)\) and \(b=E_2(y)\). Bob computes \(E(\alpha x)=\mathrm{Tate}(E_1(x),E_2(\alpha))\) and \(E(y)=\mathrm{Tate}(E_1(1),E_2(y))\), and checks that they are equal. (If they are equal it implies \(\alpha x =y\).)

Como se explica en la Parte IV, Alice sólo puede construir \(a,b\) que superen el control de verificación si \(a\) es el ocultamiento de \(P(s)\) para un polinomio \(P\) de grado \(d\) conocido por ella. La diferencia principal aquí es que Bob no necesita saber \(\alpha\) para el control de verificación, ya que puede usar la función de emparejamiento para calcular \(E(\alpha x)\) solo a partir de \(E_1(x)\) y \(E_2(\alpha)\). Por lo tanto, no necesita construir y enviar el primer mensaje por sí mismo, y este mensaje puede simplemente ser fijado en el CRS.

[1]Podríamos preguntarnos 'El conjunto de puntos de dónde?'. Nos referimos al conjunto de puntos con coordenadas en el cierre algebraico de \(\mathbb{F}_p\). Además, la curva tiene una versión afín y proyectiva. Cuando nos estamos refiriendo a la versión proyectiva también incluimos el "punto en el infinito" \({\mathcal O}\) como un elemento de la curva.
[2]No hemos abordado el caso de sumar \(P\) a sí mismo. Esto se hace usando la línea que es tangente a la curva en \(P\), y tomando \(R\) como el segundo punto de intersección de esta línea con la curva.
[3]https://eprint.iacr.org/2005/133.pdf
[4]El emparejamiento que Zcash utiliza es en realidad el emparejamiento óptimo Ate, que se basa en el emparejamiento reducido de Tate, y se puede calcular más eficientemente que \(\mathrm{Tate}\).
[5]En términos de la teoría de la complejidad computacional, se puede demostrar que sólo los lenguajes en BPP tienen pruebas de conocimiento-cero no interactivas en este sentido estricto. El tipo de enunciados que necesitamos probar en las transacciones de Zcash, como por ejemplo 'Conozco una preimagen hash de esta cadena', corresponden a la clase de complejidad NP que se considera mucho mayor que BPP.
[6]Las imágenes utilizadas fueron tomadas del siguiente artículo y se utilizan bajo la licencia creative commons.

cryptography, zkSNARKs, explainers | Ver todos los tags