Introducción
Las zero knowledge proofs aparecieron por primera vez en un paper de 1985, “The knowledge complexity of interactive proof systems“, que proporciona una definición de zero knowledge proofs (ZKPs) ampliamente utilizada hoy en día:
Una zero knowledge proof es una forma de demostrar la validez de una afirmación sin revelar la afirmación en sí. Dicho de otro modo, un protocolo zero knowledge es un método por el cual una parte (el probador) demuestra a otra parte (el verificador) que algo es cierto, sin revelar ninguna información adicional aparte del hecho de que esta afirmación específica es cierta.
Las zero knowledge proofs han mejorado a lo largo de los años y hoy en día tienen un gran número de aplicaciones.
¿Por qué necesitamos zero knowledge proofs?
Considera cómo podrías probar una afirmación (por ejemplo, “Soy ciudadano del país X”) a otra parte (por ejemplo, un proveedor de servicios). Necesitarías proporcionar “evidencia” para respaldar tu afirmación, como un pasaporte nacional o una licencia de conducir.
Pero hay problemas con este enfoque, principalmente la falta de privacidad. La Información Personal Identificable (IPI) compartida con los proveedores de servicios se almacena en bases de datos que son vulnerables a los ataques de hackers. Dado que el robo de datos de identidad es un problema en alza, existe una necesidad de medios que permitan compartir información sensible y a la vez protejan la privacidad.
¿Cómo funcionan las zero knowledge proofs?
Una zero knowledge proof te permite demostrar la veracidad de una afirmación sin compartir el contenido de la afirmación, ni revelar cómo descubriste la verdad. Para hacer esto posible, los protocolos de zero knowledge se basan en algoritmos que toman algunos datos como entrada y devuelven ‘verdadero’ o ‘falso’ como salida.
Un protocolo zero knowledge debe cumplir con los siguientes criterios:
- Totalidad: si la entrada es válida, el protocolo siempre devuelve ‘verdadero’. Por lo tanto, si la afirmación subyacente es verdadera, y el probador y el verificador actúan honestamente, la prueba puede ser aceptada.
- Solidez: si la entrada es inválida, es teóricamente imposible engañar al protocolo para que devuelva ‘verdadero’. Por lo tanto, un probador mentiroso no puede engañar a un verificador honesto para que crea que una afirmación inválida es válida (excepto con un margen de probabilidad muy pequeño).
- Cero conocimiento: el verificador no aprende nada sobre una afirmación, más allá de su validez o falsedad (tienen “cero conocimiento” sobre la afirmación). Este requisito también impide que el verificador derive la entrada original (el contenido de la afirmación).
Una zero knowledge proof consta de cuatro elementos: testigo, desafío, respuesta y verificación:
- Testigo: el probador quiere demostrar conocimiento de alguna información que sólo él conoce. Nos referimos a esta información secreta como al “testigo” o “compromiso” de la prueba. El probador define un conjunto de preguntas, que sólo pueden ser respondidas por alguien con conocimiento del testigo, y las compartirá con un verificador. El probador comienza un proceso iterativo de prueba eligiendo aleatoriamente una pregunta, calculando la respuesta y enviándola al verificador.
- Desafío: el verificador elige aleatoriamente otra pregunta del conjunto y pide al probador que la responda.
- Respuesta: el probador acepta la pregunta, calcula la respuesta y la devuelve al verificador.
- Verificación: la respuesta permite al verificador comprobar si el probador realmente tiene acceso al testigo. Para asegurar que el probador no está adivinando a ciegas y obteniendo las respuestas correctas por casualidad, el verificador elige más preguntas para responder. Al repetir esta interacción muchas veces, la posibilidad de que el probador falsifique el conocimiento del testigo disminuye significativamente hasta que el verificador esté satisfecho.
Lo anterior describe la estructura de una ‘zero knowledge proof interactiva’. Los primeros protocolos utilizaban pruebas interactivas, donde la verificación de la validez de una afirmación requería comunicación de ida y vuelta entre probadores y verificadores.
Ejemplo 1
Para ver un caso más aterrizado, ilustraremos cómo podría funcionar el uso de zero knowledge proofs para probar la afirmación “Soy ciudadano del país X”:
Supongamos que existe un sistema o un protocolo que tiene acceso a información verificada y segura de todos los ciudadanos (p.e. una base de datos gubernamental hipotética), y este sistema ha sido diseñado para poder proporcionar zero knowledge proofs.
- Testigo: tú, el probador, afirmas que eres ciudadano de un país específico (digamos, el País X), e introduces esta información en el sistema, que toma esta información y genera un “testigo” o “compromiso”. Este testigo es una función criptográfica de la afirmación[1]. Este testigo se envía al verificador (el proveedor de servicios en tu caso).
- Desafío: el verificador luego escoge un “desafío”, que podría una pregunta específica, y la introduce en el sistema.
- Respuesta: a partir de la información introducida por el probador (el testigo) y la proporcionada por el verificador (el desafío), el sistema produce una “respuesta”.
- Verificación: si el testigo, el desafío y la respuesta son consistentes de acuerdo con el mecanismo criptográfico utilizado, se verifica la prueba y el verificador tiene la seguridad de tu afirmación de ser ciudadano del País X. Si no coincide, se niega la afirmación.
La belleza de este proceso es que el verificador nunca llega a conocer tu identidad real o cualquier otro detalle, solo sabe que eres ciudadano del País X basándose en la prueba verificada por el sistema. El sistema, si está diseñado para ser verdaderamente de zero knowledge, tampoco conserva ninguna información de la transacción, preservando tu privacidad.
Ejemplo 2
Otra forma de ilustrar el concepto de zero knowledge proofs es con el problema clásico del “Grafo Bicolorable”. Este ejemplo ilustra cómo los zero knowledge proofs pueden utilizarse para demostrar el conocimiento de un secreto, sin revelar el secreto en sí. Supongamos que tenemos una amiga llamada Alicia que quiere probar a Carlos que ella conoce una solución a este problema sin revelarla realmente.
Tenemos un grafo con varios nodos y aristas. Una “coloración” de este grafo consiste en usar dos colores (por ejemplo, rojo y azul) para colorear todos los nodos del grafo, de tal manera que ningún par de nodos conectados por una misma arista tengan el mismo color. Alicia afirma que sabe una coloración válida del grafo, y quiere convencer a Carlos de este hecho sin revelar la coloración en sí.
- Compromiso: Alicia crea una copia del grafo, lo colorea según su coloración secreta, pero luego cubre cada nodo de forma opaca. Luego muestra este grafo tapado a Carlos. En este punto, Carlos puede verificar que el grafo tiene la misma forma que el original, pero no puede ver la coloración.
- Desafío: Carlos selecciona una arista al azar y le pide a Alicia que revele los colores de los dos nodos en sus extremos.
- Respuesta: Alicia desbloquea los dos nodos que Carlos señaló. Carlos ahora puede ver que estos dos nodos están efectivamente coloreados de manera diferente, pero no obtiene información sobre la coloración de los otros nodos.
- Verificación: Si Alicia abre correctamente los nodos cada vez que Carlos selecciona una arista aleatoriamente, después de suficientes iteraciones, Carlos se convencerá de que Alicia debe conocer una coloración válida. Sin embargo, Carlos nunca aprende cuál es la coloración, ya que la figura se mueve de tal manera que él nunca sabe qué nodos está destapando.
Este es un ejemplo simplificado de una zero knowledge proof. Los protocolos zero knowledge utilizados en la práctica son matemáticamente complejos y utilizan criptografía avanzada, pero los principios son los mismos: el probador convence al verificador de que sabe un secreto, sin revelar el secreto en sí.
[1] Junto con algunos datos aleatorios para asegurar que el testigo es único, incluso para la misma afirmación
