Las Crónicas de ZK: Conocimiento Cero

En nuestro primer encuentro, hice un gran esfuerzo por transmitir la importancia de la computación verificable en sí misma. En mi opinión, es realmente un primer paso necesario. Hay mucho valor en construir desde los cimientos, quitar el hype, y visualizar de verdad dónde se ubica el conocimiento cero en el universo de posibilidades, de modo que podamos definir con claridad cuándo importa y, crucialmente, cuándo no.

Pero hay otra razón por la que no saltamos directamente a ZK: todavía no estábamos listos.

Honestamente, ni siquiera es que sea súper complicado ni nada por el estilo, ¡no te asustes! Es solo que no habría tenido mucho sentido perderse en formalismos, ya que probablemente se habrían sentido raros y confusos.

Pues bien, después de pasar por todas las dificultades de los artículos anteriores (especialmente el último), creo que nuestra comprensión de este tema debería ser lo suficientemente madura para apreciar plenamente lo que se viene.

Así que por fin llegó el momento. Por fin estamos listos.

Es hora de hablar sobre el conocimiento cero (zero knowledge), y de ver finalmente algunas definiciones formales sobre una de las ideas más contraintuitivas de toda la informática: que se puede probar que algo es verdadero sin revelar nada sobre por qué lo es.

Intuición

Empecemos con la pregunta que nos gustaría responder hoy: ¿qué significa realmente no revelar nada?

Si le hiciéramos esta pregunta a la mayoría de las personas (o al menos, a alguien que nunca haya oído hablar de ZK), obtendríamos una respuesta bastante intuitiva: no revelar nada significa no compartir ninguna información (sobre algo).

¿Cierto? No significa compartir algo de información: o revelas, o no revelas. Es un asunto bastante binario.

Sin embargo, ese no es nuestro caso. Después de todo, estamos intentando probar algo sobre un cómputo. No podemos convencer a nadie de nada sin intercambiar al menos algo de información con esa persona. Así que en realidad siempre estamos revelando algún poquito.

Por lo tanto, necesitamos hacer zoom en cuáles son esos datos intercambiados. Aquí podemos encontrar todo un espectro de posibilidades: la pieza explícita de información más pequeña que podríamos enviar es un único bit, mientras que la cantidad máxima de información a compartir es el testigo completo del enunciado que queremos probar.

Dato curioso: según la teoría de la información, ¡la cantidad mínima real de información que puedes compartir es cero bits!

Un solo bit es lo más cerca que podemos estar de no revelar realmente nada. O sea, es fácil imaginar que esta cantidad de información probablemente no sea muy significativa para un verificador, ya que le costaría mucho derivar alguna relación entre el enunciado de nuestro probador y el bit compartido.

Bien, ¿y qué tal dos bits de información? ¿O tres? ¿O cuatro? Claramente, debe haber un límite. ¿Cuándo los datos se vuelven realmente significativos para el verificador? ¿Cuándo empiezan a darle pistas sobre el enunciado original?

Y ahí radica la verdadera esencia del conocimiento cero:

¿Cuánta información podemos compartir sin que le resulte útil al verificador, excepto para convencerse de la verdad de lo que queremos probar?¿Cuánta información podemos compartir sin que le resulte útil al verificador, excepto para convencerse de la verdad de lo que queremos probar?

Información útil. Esa es la idea clave aquí. ¡Así que intentemos pensar en una forma de determinar cuándo la información se vuelve útil!

Midiendo la Utilidad

Ok, todo muy lindo, pero ¿cómo empezamos siquiera a abordar este asunto?

Bueno, acá va una idea: si una prueba recibida por el verificador es indistinguible de algo que podría haber generado por su cuenta, ¡eso significa que no aprende nada nuevo de la información recibida!

Hagamos una pausa en esa idea por un segundo. ¿A qué nos referimos con que el verificador genere la prueba por su cuenta? Después de todo, no conoce realmente la información secreta de la que el probador supuestamente demuestra tener conocimiento.

Para este propósito, entonces, vamos a necesitar un nuevo artilugio: el simulador.

Simuladores

Primero, intentemos visualizar a qué nos referimos con simular.

En un protocolo interactivo, un probador y un verificador intercambian una secuencia de mensajes, a la cual, como ya sabemos, llamamos transcripción. Todo el sentido de la interacción es que el verificador desafíe al probador, y obtenga respuestas muy específicas que en última instancia funcionen como una prueba.

Con esto en mente, ya podemos describir qué es un simulador: es un algoritmo hipotético cuya única responsabilidad es fabricar transcripciones válidas para el protocolo que estemos estudiando, pero lo hace sin interactuar con un probador.

En otras palabras, lo hace sin conocimiento del testigo secreto detrás del enunciado que se está probando.

Sé que todo esto suena raro, especialmente cuando todavía no sabemos cómo construir un simulador así. Te pido que tengas paciencia y asumas por ahora que tal simulador existe, para que podamos desarmar esto conceptualmente antes de ver un ejemplo.

Asumiendo entonces que existe, notemos que le exigimos al simulador producir no cualquier tipo de transcripción, sino específicamente transcripciones aceptantes (es decir, que pasen la verificación). Esta es una observación crucial: cualquier transcripción producida por el simulador se verá como una prueba válida.

Con esto en mente, podemos hacer un pequeño experimento mental. Intentaremos construir un conjunto de transcripciones aceptantes.

Lo haremos en dos pasos: primero, ejecutaremos el protocolo real muchas veces, y recolectaremos todos los resultados. Imaginemos que los ponemos en una bolsa. Luego, ejecutaremos el simulador muchas veces también, y recolectaremos sus salidas en esa misma bolsa.

De esta bolsa de transcripciones, el verificador elegirá una de estas al azar. Ya sabemos que es una transcripción aceptante, así que naturalmente pasaría la validación del verificador, pero ahora nos hacernos otra pregunta:

¿Puede el verificador determinar si la transcripción seleccionada fue simulada?¿Puede el verificador determinar si la transcripción seleccionada fue simulada?

Si el verificador no tiene una forma eficiente de distinguir las reales de las falsas, entonces estas transcripciones son verdaderamente indistinguibles entre sí.

Si quisiéramos ponernos súper técnicos, lo que exigimos es que la distribución de las transcripciones reales producidas por el protocolo sea indistinguible de la distribución producida por el simulador.

Y esa es la intuición central en juego: ¡todo lo que el verificador ve podría haber sido generado igualmente a través de una simulación, que no guarda relación alguna con la información secreta!

Muy bien, ¡eso suena prometedor! Pero hay un obstáculo evidente para toda esta línea de razonamiento: ¿cómo puede un simulador fabricar una transcripción si no conoce el secreto? Y si puede, ¿no significa eso que el sistema de pruebas está roto?

Quedémonos con esa idea en mente, porque es una muy buena pregunta, y volveremos a ella. Por ahora, veamos de qué va la construcción de un simulador.

Conocimiento Cero con Verificador Honesto

Hay otra salvedad que deberíamos mencionar. Cuando definimos informalmente un simulador, dijimos que necesita reproducir transcripciones aceptantes. En otras palabras, tiene que reproducir la vista de un verificador, pero ¿quién dijo que el verificador juega con las reglas esperadas?

En efecto, un simulador necesita poder producir la vista de cualquier verificador, incluso uno que se comporte de forma inesperada, o que se desvíe del protocolo de maneras ingeniosas.

Es una distinción sutil, pero complica bastante las cosas. Y así, para empezar a mojarnos los pies, quizás deberíamos evitar este caso general y centrarnos en un escenario simplificado: asumir que el verificador se comportará bien.

En otras palabras, estamos diciendo que cada vez que deba enviar un desafío aleatorio, realmente lo hará, ¡y que el desafío realmente será aleatorio!

Si un protocolo puede simularse bajo este supuesto, podemos decir que satisface Conocimiento Cero con Verificador Honesto, o HVZK para abreviar (por sus siglas en inglés). Es una noción más débil que el conocimiento cero completo, pero aun así es muy útil, porque muchos protocolos clásicos satisfacen HVZK.

Asumir que el verificador se comporta honestamente nos permitirá ver cómo la simulación puede funcionar realmente en la práctica. Y para hacer esto, usaremos un tipo de protocolo que ya conocemos.

Simulando un Protocolo Sigma

Hace algunos artículos, presentamos los protocolos sigma (o protocolos Σ para abreviar), de los cuales el más simple era el protocolo de Schnorr.

Si recuerdas, es un protocolo que podemos usar para probar el conocimiento de un logaritmo discreto para el valor público $y$ (es decir, $y = g^x$, y la afirmación es que el probador conoce $x$). Como breve recordatorio, funciona en tres pasos:

1. El probador primero envía un compromiso con un factor de cegado aleatorio $t = g^r$.
2. El verificador responde con un desafío aleatorio $c$.
3. El probador contesta con $s = r + cx$.

Al final de todo, el verificador comprueba:

$$g^s = t \cdot y^c$$

Y la transcripción de toda esta interacción es simplemente el vector $(t, c, s)$.

¡Bien! Ahora todo lo que necesitamos hacer es idear una forma de simular esto. Puede parecer una tarea abrumadora al principio, pero en realidad hay un truco muy sencillo que podemos usar para este protocolo en particular. Si reordenamos el paso de verificación, obtenemos:

$$t = g^s \cdot y^{-c}$$

No es un cambio tan grande, y aun así, habilita una estrategia de simulación bien simple para el protocolo:

1. Elegir valores aleatorios para $c$ y $s$.
2. Calcular $t$.
3. Construir la transcripción $(t, c, s)$.

Y así sin más, ¡hemos obtenido una transcripción que el verificador aceptará, sin ningún conocimiento del secreto $x$! Notablemente, nuestra transcripción es indistinguible de una generada a través de la interacción real. Por lo tanto, el protocolo de Schnorr satisface HVZK: ¡es de conocimiento cero siempre que el verificador sea honesto!

Genial, ¿no?

Solidez de Conocimiento

Aunque el último ejemplo funciona perfectamente bien en la práctica, probablemente sigas con esa pregunta de antes rondando, así que abordémosla de frente:

Si las transcripciones pueden simularse sin conocer el secreto, ¿cómo puede el verificador confiar en que el probador realmente lo conoce?Si las transcripciones pueden simularse sin conocer el secreto, ¿cómo puede el verificador confiar en que el probador realmente lo conoce?

Justo cuando estábamos logrando algo de progreso... ¿parece que de repente volvimos al punto de partida? ¿O al menos que nos estamos perdiendo algo importante?

En efecto, el argumento de la simulación es solo la mitad de la historia. Para que el conocimiento cero tenga pleno sentido, también debemos asegurarnos de alguna manera de que el probador conoce el secreto.

Así, junto con el argumento del simulador, debemos introducir otro concepto: el de solidez de conocimiento, y la capacidad de extraer información del probador.

El Extractor

Ok, entonces, si las transcripciones reales son indistinguibles de las transcripciones simuladas, ¿cómo hacemos para mostrar que el probador realmente conoce el testigo secreto?

En primer lugar, esta vez debemos centrarnos en lo que sucede durante las interacciones reales entre un probador y un verificador, no en las simulaciones. Es cierto que una transcripción no filtra información... pero ¿qué hay de múltiples transcripciones para el mismo compromiso?

Intuitivamente, podemos imaginar que si el probador realmente conoce el testigo, entonces debería estar listo para responder a múltiples desafíos, devolviendo consistentemente respuestas aceptantes.

O, a la inversa, si no tuviera conocimiento del secreto, ¡es muy probable que no esté preparado para responder a un bombardeo de desafíos!

Nota que esto descarta naturalmente la simulación, donde calculábamos el compromiso original. ¡En este escenario, estamos fijando ese compromiso inicial!

Podemos imaginar que a medida que se responden correctamente más y más desafíos, nuestra confianza en que el probador tiene el conocimiento necesario aumenta.

Si bien esto puede tener sentido, deberíamos intentar ser un poco más precisos. Para eso, lo llevaremos al extremo: imagina que podemos interactuar tantas veces como queramos con el probador. Con suficientes interacciones, quizás podamos hacer un poco más que convencernos de la verdad del enunciado: ¡tal vez podamos recuperar el testigo!

Esta es la idea detrás de un extractor: un algoritmo eficiente que interactúa con el probador, y usa múltiples respuestas aceptantes para recuperar el testigo. Si resulta que un algoritmo así existe para un protocolo, entonces podemos decir que el protocolo satisface la solidez de conocimiento: cualquier probador capaz de producir pruebas aceptantes debe realmente conocer el testigo.

Y como siempre, creo que la mejor manera de afianzar estas ideas es con un ejemplo.

Un Extractor Simple

Una vez más, apuntaremos nuestra atención a los viejos y queridos protocolos Σ, de los cuales elegiremos nuevamente el más simple que podemos encontrar: ¡el protocolo de Schnorr!

¡Sí! Este tiene una estrategia de extracción muy fácil de explicar. De hecho... ¡ya la hemos visto en acción!

Cuando hablamos de los protocolos Σ, echamos un breve vistazo a la idea de solidez especial: la capacidad de extraer el secreto a partir de solo dos transcripciones aceptantes (para el mismo compromiso). Esta es en realidad una característica que todo protocolo Σ comparte, y es en parte lo que los hace tan simples de examinar en cuanto a conocimiento cero y solidez de conocimiento.

Dado que esto ya se cubrió, veamos solamente un breve recordatorio. A partir de dos interacciones que producen transcripciones aceptantes de la forma $(t, c, s)$ y $(t, c’, s’)$, podemos obtener:

$$g^s = t \cdot y^c, \ g^{s’} = t \cdot y^{c’}$$

Si combinamos estas expresiones dividiéndolas entre sí, obtendremos esto:

$$g^{s-s’} = y^{c-c’} = g^{x(c-c’)}$$

Y luego, simplemente comparando los exponentes del primer y el último miembro de esa expresión, podemos escribir una ecuación muy simple que nos permite encontrar $x$ con bastante facilidad.

$$x = (s {-} s')(c {-} c')^{-1}$$

Esto también cierra nuestra pregunta anterior sobre qué sucede con los simuladores. Sino, intenta correr este extractor sobre una transcripción simulada: el simulador eligió $c$ y $s$ primero y derivó $t$ a partir de ellos, así que no puede responder a un segundo desafío $c’$ para ese mismo $t$. Hacerlo implicaría calcular un logaritmo discreto, es decir, conocer $x$. Un simulador puede falsificar una única interacción, pero solo un probador que realmente conoce el testigo puede sobrevivir a que se le pregunte de nuevo.

Naturalmente, no todos los protocolos ofrecen una manera tan sencilla de analizar la solidez de conocimiento, lo que nos lleva a dar una definición un poco más general de cómo funcionaría el proceso.

Dicho con mayor precisión: si un probador puede producir transcripciones aceptantes con probabilidad no despreciable, podemos imaginar un extractor $E$: un algoritmo con acceso de oráculo al probador, libre de enviar tantos desafíos como quiera, y que espera una respuesta válida cada vez.

Si tal algoritmo puede recuperar siempre $x$, entonces el protocolo tiene solidez de conocimiento: cualquier probador lo suficientemente convincente como para pasar debe conocer realmente el secreto.

Para resumir, en pocas palabras: la solidez de conocimiento significa que cualquier probador que pueda responder desafíos de manera convincente debe contener suficiente información como para que podamos extraer el testigo. O sea, ¡debe conocer la información secreta!

Resumen

¡Y con eso, hemos quitado con éxito el velo de misticismo alrededor del conocimiento cero!

Tampoco estuvo tan mal, ¿no? Una vez que la intuición hace clic, creo que incluso puede sentirse bastante natural.

El concepto de conocimiento cero ha llegado a tener muchas interpretaciones en un sentido pragmático. En cierto modo, se ha entrelazado con la idea de computación verificable, y por eso comenzamos la serie con esa distinción. Cuando hablamos de la comprensión popular, se lo ha asociado con esta idea de "no revelar nada". Pero la verdadera esencia del conocimiento cero (y de su contraparte, la solidez de conocimiento) es lo que hemos presentado hoy, y se define en términos de simuladores y extractores.

Y recuerda, uno de los puntos clave a llevarnos hoy es que el conocimiento cero por sí solo no es suficiente: también debemos asegurarnos de que el testigo secreto sea realmente conocido por el probador.

Si bien todavía nos quedan un montón de métodos y técnicas por ver, hay un asunto pendiente que deberíamos abordar como seguimiento inmediato de las definiciones que vimos hoy.

Todos nuestros argumentos de hoy se basaron en interacciones entre probador y verificador. Sin embargo, la mayoría de las pruebas se convierten a sus versiones no interactivas. ¿Qué pasa entonces? ¿Se vuelven irrelevantes todos los conceptos que cubrimos?

¡Lo descubriremos en la próxima entrega!