Intuición sobre ZKP: la cueva de Alí Babá

Una prueba de conocimiento cero (ZKP) permite que un probador convenza a un verificador de que conoce un secreto (o de que un enunciado es verdadero) sin revelar el secreto en sí. Tiene tres propiedades: completitud, solidez y conocimiento cero.

Si el probador conoce el secreto, siempre puede convencer al verificador. Un probador honesto que sigue el protocolo tendrá éxito con probabilidad 1 (o con probabilidad abrumadora). El verificador no rechazará una prueba válida.

Un probador deshonesto (que no conoce el secreto) no puede convencer al verificador salvo con probabilidad despreciable. Cada ronda de interacción reduce la probabilidad de engaño: después de k rondas, la probabilidad de éxito de un tramposo es como máximo 2^{-k}.

El verificador no aprende nada más allá del hecho de que el enunciado es verdadero. Formalmente, existe un simulador que, sin conocer el secreto, produce una transcripción indistinguible de una interacción real entre el probador y el verificador. El verificador no obtiene ningún conocimiento adicional.

Una cueva tiene un pasadizo circular con una puerta mágica en el centro. La probadora (Alice) afirma que conoce la contraseña. El verificador (Bob) espera fuera. Alice entra y toma el camino de la izquierda o de la derecha. Bob grita por qué lado debe salir. Si Alice conoce la contraseña, siempre sale correctamente. Probabilidad de engaño por ronda: 1/2.

Después de 20 rondas, un tramposo tiene una probabilidad de éxito de 2^{-20}, aproximadamente 1 entre un millón. Alice (que conoce la contraseña) tiene éxito todas las veces. Bob nunca aprende la contraseña: solo ve a Alice salir por el lado solicitado. Esto es conocimiento cero.

Las ZKP interactivas requieren un intercambio de mensajes entre el probador y el verificador. Las ZKP no interactivas (NIZK) utilizan la transformación de Fiat-Shamir: sustituyen el desafío aleatorio del verificador por un hash del compromiso (hash = oráculo aleatorio). El resultado es una única cadena de prueba que cualquiera puede verificar.

Una ZKP es una prueba de conocimiento (PoK) si la estrategia del probador implica que podría extraerse el secreto. Esto es más sólido que demostrar simplemente que un enunciado es verdadero. Las firmas ECDSA y Schnorr son pruebas de conocimiento no interactivas de la clave privada.

Autenticación mediante contraseña sin enviar la contraseña. Verificación de edad sin revelar la fecha de nacimiento. Pruebas de rango (su salario está dentro de un intervalo) sin revelar el salario. Blockchain: demostrar que conoce una transacción válida sin revelar la transacción.

Conocimiento cero perfecto: la salida del simulador es idéntica a la transcripción real. ZK estadístico: indistinguible salvo con probabilidad insignificante. ZK computacional: indistinguible para verificadores de tiempo polinómico. Garantías más débiles = pruebas más eficientes.

La cueva utiliza un protocolo de 3 movimientos: compromiso → desafío → respuesta. Formalmente se denomina protocolo Sigma. La mayoría de las ZKP prácticas (Schnorr, Pedersen, Fiat-Shamir) son protocolos Sigma o composiciones de estos. El nombre proviene de la forma Σ del diagrama del flujo de mensajes.

¿Después de cuántas rondas del protocolo de la cueva de Ali Baba la probabilidad de éxito de un tramposo es inferior a 1/1000?

Las ZKP demuestran el conocimiento de un secreto sin revelarlo. Tres propiedades: completitud, solidez y conocimiento cero. La cueva de Ali Baba ilustra una ZKP interactiva. Siguiente tema: protocolos Sigma e identificación de Schnorr.