Idioma

Los Parámetros de Zcash y cómo serán generados

Ariel Gabizon | Sep 22, 2016

En su base la tecnología de privacidad de Zcash utiliza una novedosa herramienta de privacidad llamada zkSNARK – una pequeña prueba de conocimiento-cero que es sencilla de verificar. Zcash será la primera en utilizar esta poderosa herramienta a gran escala. Para que estas pruebas zkSNARKs funcionen, se requiere una fase de configuración donde se generan los “parámetros del sistema”. Esta fase de configuración es similar a la fase de configuración del cripto-sistema de clave pública, pero con un inconveniente: como en el cripto-sistema de clave-pública, se genera un par (clave-privada, clave pública), pero luego la clave-privada es destruida. De hecho, es fundamental para la integridad del sistema que nadie posea la clave-privada.

La clave-pública (\(\mathsf{pubkey}\)) es el parámetro requerido para el sistema. La clave-privada (\(\mathsf{privkey}\)) corresponde con algo que aquí ha sido llamado “basura tóxica”, y el hecho de tenerla habilita la falsificación de nuevas monedas (pero no habilita violar la privacidad de las transacciones de otros usuarios).

Para reducir este riesgo, Zcash ha diseñado un protocolo multi-usuario con que se generará la \(\mathsf{pubkey}\). El protocolo tiene la propiedad de que la \(\mathsf{privkey}\) corresponde con una concatenación de aleatoriedad secreta de todos los participantes. Entonces, la \(\mathsf{privkey}\) será destruida a menos que todos los participantes sean deshonestos o estén comprometidos.

El propósito de esta publicación es brindar una explicación simplificada de cómo se compone la \(\mathsf{pubkey}\) y cómo funciona el protocolo que la genera.

Cómo se compone la \(\mathsf{pubkey}\)

Supongamos que \(g\) es un generador de un grupo \(G\) en el que el logaritmo discreto es difícil. Asumimos que \(G\) tiene un orden \(r\) para algún primo \(r,\) y que escribimos las operaciones de grupo de forma aditiva. Entonces para \(s\in \mathbb{F}\), donde \(\mathbb{F}\) es un campo de tamaño \(r\), podemos escribir \(s\cdot g\) para indicar la multiplicación escalar de \(g\) por \(s\); es decir \(s\cdot g\) se obtiene de agregar \(s\) copias de \(g\). Una versión simplificada de (\(\mathsf{privkey},\) \(\mathsf{pubkey)}\) es que la \(\mathsf{privkey}\) es simplemente un elemento uniformemente aleatorio \(s\in \mathbb{F}^*\) y que la \(\mathsf{pubkey}\) es una secuencia agrupada de elementos

\(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g)\)

Arriba, \(\mathbb{F}^*\) indica el conjunto de todos los elementos de \(\mathbb{F}.\) que no son 0.

Cómo se genera la \(\mathsf{pubkey}\)

Vamos a decir algunas palabras de por qué la \(\mathsf{pubkey}\) luce de esta forma y cómo se utiliza, pero nos concentraremos ahora en el diseño del protocolo que genera la \(\mathsf{pubkey}\).

Fijemos \(d=2\) por temas de simplicidad; y también omitiremos el primer elemento \(g\) de la \(\mathsf{pubkey}\), dado que su generación es sencilla. Supongamos que tenemos dos partes, Alice y Bob, que desean generar una clave pública válida \(\mathsf{pubkey}=\) \((s\cdot g, s^2\cdot g)\) para el sistema. Ellos quieren hacerlo de forma tal que puedan asegurarse que ninguno de los dos van a conocer \(s.\) Vamos a hacerlo sencillo al principio: supongamos que solo quieren generar \(s\cdot g\) (de nuevo, de forma tal que ninguno conozca \(s)\). Ellos utilizan el siguiente protocolo:

  1. Alice alige un \(a\in \mathbb{F}^*\) aleatorio, y le envía a Bob \(M_1:= a\cdot g\).
  2. Luego Bob elige un \(b\in \mathbb{F}^*\) aleatorio y multiplica \(M_1\) por \(b\). Él responde el mensaje \(M:= b\cdot M_1\) como su resultado común.

Al final del protocolo, tendremos \(M=b\cdot a \cdot g = (a b)\cdot g\). Definamos \(s:= a b\).

Observemos que

  • Bob no puede adivinar \(a\) del mensaje \(M_1\), en tanto que asumimos que el logaritmo discreto es difícil en \(G\). Lo mismo aplica para Alice y \(b\). En particular, ninguno conoce \(s\) que es el producto de \(a\) y \(b\).
  • Para cualquier \(a\in \mathbb{F}^*\) fijo, \(a b\) es un elemento aleatorio de \(\mathbb{F}^*\) cuando \(b\) es aleatorio. Incluso si Alice engaña, en el sentido de que no elegir \(a\) de forma aleatoria como debería hacerlo, por ejemplo si ella elije siempre \(a=4\), de todos modos \(s\) será aleatorio. Lo mismo aplica si Bob es el que engaña no eligiendo \(b\) de forma aleatoria.

Entonces, en tanto uno de ellos siga el protocolo correctamente, \(M=s\cdot g\) será calculado de forma correcta.

Ahora intentemos usar un razonamiento similar para generar \((s\cdot g, s^2\cdot g)\):

  1. Alice elige un \(a\in \mathbb{F}^*,\) aleatorio y envía \((A,B)\) donde \(A:= a\cdot g\) y \(B := a^2\cdot g.\)
  2. Bob elige \(b\in \mathbb{F}^*,\) aleatorio y envía \(M=(b\cdot A, b^2\cdot B)\).

Si Alice y Bob siguen el protocolo, obtendremos \(M= (b a \cdot g, b^2 a^2 \cdot g) = ( a b\cdot g, (a b)^2\cdot g).\) Entonces este vector es una forma correcta de \(s:= ab.\)

Aquí hay un problema: ¿Qué pasa si Bob hace trampa y multiplica \(B\) por algún \(c\neq b^2\)? Entonces obtendríamos \((ab\cdot g, a^2 c \cdot g),\) que no es de la forma \((s\cdot g, s^2\cdot g)\) para cualquier \(s.\) De alguna forma necesitamos verificar que nuestro vector de salida es de la forma \((s\cdot g, s^2\cdot g)\) para algún \(s\). En muchos grupos, se conjetura que esto no es eficiente - es lo que se ha dado en llamar el protocolo de asunción de decisiones Diffie-Hellman. Sin embargo, en nuestro escenario, estamos trabajando con un grupo que tiene una paridad bilinear. Esto es un mapeo de \(e:G\times G\to G_T,\) en el grupo \(G_T\) también de orden \(r\) con generador \(\mathbf{g},\) escrito multiplicativamente como

\(e(a\cdot g, b\cdot g) = \mathbf{g}^{ab}\)

para cualquier \(a,b\in\mathbb{F}.\) Seguidamente, esto nos brinda la posibilidad verificar que la salida \(M\) esté correctamente formada. Simplemente verificamos si

\(e(g,B) = e(A,A).\)

Vemos entonces, que si nadie ha hecho trampa, esta verificación quedará comprobada. Cuando nadie hace trampa, tenemos \(A=s\cdot g,\) y \(B=s^2\cdot g.\) Entonces

\(e(g,B) = e(g,s^2\cdot g) =\mathbf{g}^{s^2}\),

y además

\(e(A,A) = e(s\cdot g,s\cdot g) = \mathbf{g}^{s^2}.\)

Se puede hacer un cálculo similar para ver que cuando \(M\) no tiene esta forma, estos dos valores van a diferir y la verificación fallará.

Cómo se usa la \(\mathsf{pubkey}\)

Recordemos que un polinomio \(P\) de grado \(d\) sobre \(\mathbb{F}\) es una expresión de la forma

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

Podemos evaluar un polinomio en un punto \(s\in \mathbb{F}\) sustituyendo \(s\) por \(X\), y calculando la suma resultante. Un dato útil es que si \(P\) y \(Q\) son polinomios diferentes de grado no mayor a \(d\) pueden coincidir como máximo en \(d\) puntos. En Zcash el que envía necesita construir polinomios \(P\) y \(Q\) de grado \(d\) de alguna forma, y mucha magia matemática garantiza que ambos puedan construir el mismo polinomio, por ejemplo obtener: \(P=Q,\) solamente si la transacción es válida.

\(\mathsf{pubkey}\) can now be used to test if \(P\) y \(Q\) are equal at a point \(s\) not known by the sender. Say

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

y

\(Q(X) = b_0 + b_1\cdot X + b_2\cdot X^2 + \ldots + b_d\cdot X^d\)

Usando una \(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g),\) el que verifica puede calcular

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

y compute \(Q(s)\cdot g\) similarly. The verifier can then check if they are equal.

Since the sender of a non-valid transaction has to construct distinct \(P\) y \(Q\) without knowing \(s,\) the chance that \(P(s)=Q(s)\) is very small.

Descargo de responsabilidad

Hay que tomar en cuenta que esta publicación es una versión muy simplificada del protocolo en cuestión. Más adelante y a través de un whitepaper, se presentará una descripción detallada y completa.

References

Our zkSNARKS use SCIPR Lab's implementation of the Pinnochio protocol, which in turn is based on the work of Gennaro, Gentry, Parno y Raykova. Our protocol for parameter generation builds on a previous work of Ben-Sasson, Chiesa, Green, Tromer y Virza.