¡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 I: Escondites Homomórficos

Ariel Gabizon | Feb 28, 2017

Las construcciones de zk-SNARKs implican la cuidadosa combinación de varios ingredientes; entender completamente cómo estos ingredientes trabajan en conjunto puede tomar un tiempo.

Si tuviera que elegir un ingrediente cuyo papel es más prominente, ese ingrediente sería lo que llamaré aquí Escondite Homomórfico (HH, por sus siglas en inglés) [1]. En este post explicamos lo que es un HH, y luego damos un ejemplo de por qué es útil y cómo se construye.

Un HH \(E(x)\) de un número \(x\) es una función que satisface las siguientes propiedades:

He aquí un ejemplo didáctico de por qué el HH es útil para las pruebas de Conocimiento-Cero: Supongamos que Alice quiere probarle a Bob que conoce los números \(x,y\) tales que \(x+y=7\) (claro que no es demasiado emocionante saber tal \(x,y,\) pero este es un buen ejemplo para explicar el concepto).

  1. Alice envía \(E(x)\) y \(E(y)\) a Bob.
  2. Bob calcula \(E(x+y)\) a partir de estos valores (lo cual es capaz de hacer ya que \(E\) es un HH).
  3. Bob también calcula \(E(7),\) y ahora comprueba si \(E(x+y)=E(7).\) Bob aceptará la prueba de Alice sólo si la igualdad se comprueba.

Dado que las diferentes entradas son mapeadas por \(E\) hacia escondites diferentes, Bob aceptará realmente la prueba sólo si Alice envió escondites de \(x,y\) tales que \(x+y=7.\) Por otro lado, Bob no aprende \(x\) e \(y,\) ya que sólo tiene acceso a sus escondites [2].

Ahora veamos un ejemplo de cómo se construyen tales escondites. De hecho no podemos construirlos para enteros regulares con adición regular, sino que debemos fijarnos en los grupos finitos:

Sea \(n\) un entero. Cuando escribimos \(A\;\mathrm{mod}\;n\) para un entero \(A,\) nos referimos a tomar el resto de \(A\) después de dividirlo por \(n.\) Por ejemplo, \(9\;\mathrm{mod}\; 7 = 2\) y \(13\; \mathrm{mod}\;12 = 1.\) Podemos usar la operación \(\mathrm{mod}\; n\) para definir una operación de adición en los números \(\{0,\ldots,n-1\}:\) Hacemos una adición regular pero luego aplicamos \((\mathrm{mod}\; n)\) al resultado para obtener un número en el rango \(\{0,\ldots,n-1\}.\) A veces escribimos \((\mathrm{mod}\; n)\) a la derecha para aclarar que estamos utilizando este tipo de adición. Por ejemplo, \(2+3 = 1\; (\mathrm{mod} \;4).\) Llamamos al conjunto de elementos \(\{0,\ldots,n-1\}\) junto con esta operación de suma, el grupo \(\mathbb{Z}_n\).

Para un número primo \(p\), podemos usar la operación \(\mathrm{mod}\;p\) para definir también una operación de multiplicación sobre los números \(\{1,\ldots,p-1\}\) de manera que el resultado de la multiplicación esté también siempre en el conjunto \(\{1,\ldots,p-1\}\). Realizamos una multiplicación regular de enteros y luego tomamos el resultado \(\mathrm{mod}\; p.\) [3] Por ejemplo, \(2\cdot 4=1\; (\mathrm{mod}\; 7).\)

Llamamos a este conjunto de elementos junto con esta operación, \(\mathbb{Z}_p^*\). \(\mathbb{Z}_p^*\) tiene las siguientes propiedades útiles:

  1. Es un grupo cíclico, lo que significa que existe un elemento \(g\) en \(\mathbb{Z}_p^*\), llamado generador, tal que todos los elementos de \(\mathbb{Z}_p^*\) pueden escribirse como \(g^a\) para un \(a\) en \(\{0,..,p-2\}\), donde definimos \(g^0=1.\)
  2. Se cree que el problema de logaritmo discreto es difícil en \(\mathbb{Z}_p^*\). Esto significa que cuando p es grande, dado un elemento \(h\) en \(\mathbb{Z}_p^*\) es difícil encontrar el entero \(a\) en \(\{0,..,p-2\}\) tal que \(g^a=h\;(\mathrm{mod}\;p).\)
  3. Como ''los exponentes se suman cuando los elementos son multiplicados'', tenemos para \(a,b\) en \(\{0,..,p-2\}\) \(g^a\cdot g^b = g^{a+b\;(\mathrm{mod}\;p-1)}.\)

Usando estas propiedades, construimos ahora un HH que ''admite la adición'' ─lo que significa que \(E(x+y)\) es calculable a partir de \(E(x)\) y \(E(y).\) Suponemos que la entrada \(x\) de \(E\) es de \(\mathbb{Z}_{p-1}\), por lo que está en el rango \(\{0,\ldots,p-2\}.\) Definimos \(E(x)=g^x\) para cada uno de esos valores de \(x\), y afirmamos que \(E\) es un HH: La primera propiedad implica que diferentes valores de \(x\) en \(\mathbb{Z}_{p-1}\) se mapean a diferentes salidas. La segunda propiedad implica que dado \(E(x)=g^x\) es difícil encontrar \(x\). Finalmente, usando la tercera propiedad, dado \(E(x)\) y \(E(y)\) podemos calcular \(E(x+y)\) como \(E(x+y) = g^{x+y\;\mathrm{mod}\; p-1} = g^x\cdot g^y = E(x)\cdot E(y).\)

[1]Escondite homomórfico no es un término utilizado formalmente en la criptografía, y se introduce aquí con fines didácticos. Es similar pero más débil que la noción bien conocida de un compromiso computacionalmente escondido. La diferencia es que un HH es una función determinística de la entrada, mientras que un compromiso utiliza una aleatoriedad adicional. Como consecuencia, los HH esencialmente ''ocultan la mayoría de las x'', mientras que los compromisos ''ocultar todas las x''.
[2]Bob llega a obtener alguna información sobre x e y. Por ejemplo, puede elegir un x' aleatorio, y comprobar si x=x' calculando E(x'). Por esta razón, el protocolo anterior no es realmente un protocolo de Conocimiento-Cero, y sólo se utiliza aquí con fines explicativos. De hecho, como veremos en posts siguientes, el HH se utiliza en última instancia en snarks para ocultar desafíos del verificador más que secretos del homologador.
[3]Cuando p no es un primo, es problemático definir la multiplicación de esta manera. Un problema es que el resultado de la multiplicación puede ser cero incluso cuando ambos argumentos no son cero. Por ejemplo, cuando p=4, podemos obtener 2*2=0 (mod 4).