¡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 III: Test y Presunción del Conocimiento del Coeficiente

Ariel Gabizon | Mar 28, 2017

<< Parte II

En la Parte II, vimos cómo Alice puede evaluar a ciegas el escondite \(E(P(s))\) de su polinomio \(P\) de grado \(d,\) en un punto dado \(s\) perteneciente a Bob. Llamamos a esto una evaluación "a ciegas" porque Alice no a llegado a conocer \(s\) en el proceso.

Sin embargo, algo estaba faltando en ese protocolo: el hecho de que Alice sea capaz de calcular \(E(P(s))\) no garantiza que de hecho enviará \(E(P(s))\) a Bob, en lugar de un valor que no esté en absoluto relacionado.

Por lo tanto, necesitamos una manera de "obligar" a Alice a seguir el protocolo correctamente. En la parte IV explicaremos detalladamente cómo hacemos para conseguir esto. En este post, nos centramos en explicar la herramienta básica necesaria para hacerlo, a la cual llamamos aquí el Test del Conocimiento del Coeficiente (KC, por las siglas de Knowledge of Coefficient).

Al igual que antes, denotamos por \(g\) un generador de un grupo \(G\) de orden \(|G|=p\) en donde el logaritmo discreto es difícil. A partir de este post será conveniente escribir nuestro grupo de forma aditiva en vez de multiplicativamente. Es decir, para \(\alpha\in\mathbb{F}_p,\) \(\alpha\cdot g\) denota el resultado de la suma de una cantidad \(\alpha\) de copias de \(g.\)

El Test KC

Para \(\alpha\in\mathbb{F}_p^*\) [1], llamemos a un par de elementos \((a,b)\) en \(G\) un par alfa, o \(\alpha\)-pair, si \(a,b \neq 0\) y \(b=\alpha\cdot a.\)

El Test KC procede de la siguiente manera:

  1. Bob elige al azar \(\alpha\in\mathbb{F}_p^*\) y \(a\in G.\) Luego calcula \(b=\alpha\cdot a.\)
  2. Envía a Alice el par "de desafío" \((a,b).\) Tengamos en cuenta que \((a,b)\) es un \(\alpha\)-pair.
  3. Alice ahora debe responder con un par diferente \((a',b')\) que también sea un \(\alpha\)-pair.
  4. Bob acepta la respuesta de Alice sólo si \((a',b')\) es de hecho un \(\alpha\)-pair. (Ya que él conoce \(\alpha\), puede comprobar si \(b'=\alpha\cdot a'.)\)

Ahora pensemos cómo Alice podría responder con éxito al desafío. Supongamos por un segundo que ella conociera \(\alpha.\) En ese caso, ella podría simplemente elegir cualquier \(a'\) en \(G,\) y calcular \(b'=\alpha\cdot a';\) y finalmente presentar \((a',b')\) como su nuevo \(\alpha\)-pair.

Sin embargo, como la única información que ella tiene sobre \(\alpha\) es \(\alpha\cdot a\) y dado que \(G\) presenta un problema de logaritmo discreto dificil, es de esperar que Alice no sea capaz de encontrar \(\alpha.\)

Entonces, ¿cómo puede responder con éxito al desafío sin conocer \(\alpha?\)

Aquí está la manera natural de hacerlo: Alice simplemente elige algún \(\gamma\in\mathbb{F}_p^*,\) y responde con \((a',b')=(\gamma\cdot a,\gamma\cdot b).\)

En este caso, tenemos:

\(b'=\gamma \cdot b = \gamma \alpha \cdot a = \alpha (\gamma\cdot a) =\alpha \cdot a',\)

por lo tanto \((a',b')\) es efectivamente un \(\alpha\)-pair tal como era requerido.

Tengamos en cuenta que si Alice responde usando esta estrategia, entonces ella conoce la proporción entre \(a\) y \(a'\). Es decir, conoce el coeficiente \(\gamma\) tal que \(a'=\gamma\cdot a.\)

La Presunción del Conocimiento del Coeficiente (KCA, siglas de Knowledge of Coefficient Assumption) [2] afirma que este es siempre el caso, a saber:

KCA: Si Alice da una respuesta válida \((a',b')\) al desafío de Bob \((a,b)\) con una probabilidad no despreciable sobre las elecciones de \(a,\alpha\) de Bob, entonces ella conoce \(\gamma\) tal que \(a'=\gamma\cdot a.\)

El Test y la Presunción del Conocimiento del Coeficiente serán herramientas importantes en la Parte IV.

¿Qué significa exactamente que "Alice conoce" \(\gamma\)?

Podríamos preguntarnos cómo es posible expresar el KCA en términos matemáticos precisos; más específicamente, ¿cómo transformamos la noción de que "Alice conoce \(\gamma\)" en una definición matemática?

Esto se hace aproximadamente de la siguiente manera: decimos que, además de Alice, tenemos otra parte a la que llamamos Extractor de Alice. El Extractor de Alice tiene acceso al estado interior de Alice.

A continuación formulamos el KCA de modo que diga que: cada vez que Alice responde con éxito con un \(\alpha\)-pair \((a',b'),\) el extractor de Alice dará un \(\gamma\) tal que \(a'=\gamma\cdot a.\) [3]

[1]\(\mathbb{F}_p^*\) denota los elementos no nulos de \(\mathbb{F}_p\). Es lo mismo que \(\mathbb{Z}_p^*\) descrito en la Parte I.
[2]Esto se llama comúnmente Presunción del Conocimiento del Exponente en la literatura específica, ya que tradicionalmente se utilizaba para grupos escritos multiplicativamente.
[3]La definición completamente formal debe dar al Extractor "un poco de flexibilidad" por lo que afirma en vez que la probabilidad de que Alice responda con éxito pero el extractor no produzca tales \(\gamma\) es despreciable.

cryptography, zkSNARKs, explainers | Ver todos los tags