La prueba de conocimiento cero es una forma mágica de probar una declaración sin revelar información adicional. Aquí, proporcionamos una introducción para principiantes a los ZKP…
Estás jugando "¿Dónde está Waldo?" con tus amigos. El primero que lo encuentre gana la copa de oro y el segundo la copa de plata. Eres el primero en encontrarlo, pero no puedes decirles a tus amigos dónde está. Porque arruinarás la oportunidad de que todos los demás ganen el premio del segundo lugar. ¿Qué puedes hacer? ¿Cómo puedes demostrarles a tus amigos que en realidad encontraste a Waldo sin revelar dónde está exactamente? ¿Hay incluso una solución para eso?
Afortunadamente, la respuesta es ¡sí! Aquí está la solución: consigue un tablero muy grande (mucho más grande que la página en la que tenías que encontrar a Waldo) con un pequeño agujero (tan grande como para Waldo). Ve detrás del tablero mientras todos los demás están parados frente a él. Pon la página detrás de la pizarra para que nadie sepa dónde la has puesto exactamente. Justifique la página de manera que se pueda ver a Waldo desde el agujero en el pizarrón. ¡Ahora, todos pueden ver que lo has encontrado! Pero todavía no tienen idea de dónde está en la página, ya que no conocen la posición de la página detrás del tablero. ¡Enfriar! ¿Derecha?
A esto lo llamamos prueba de conocimiento cero (ZKP). Una prueba que demuestra que eres honesto, pero que no le da conocimiento al verificador sobre los secretos que estás ocultando. Parece contradictorio, ¡lo sé! Formulemos el problema para entenderlo mejor. Tenemos un probador que quiere demostrar su honestidad al hacer algo. Puede ser decir la verdad sobre encontrar a Waldo o resolver cualquier otro problema que estemos tratando de resolver. Por otro lado, no quiere revelar nada sobre la solución. Queremos un esquema mediante el cual el probador pueda demostrar su honestidad al verificador. El verificador debería poder verificar la prueba mucho más rápido de lo que se necesita para encontrar la solución por sí mismo.
Otros ejemplos
Suponga que tiene suficiente dinero para comprar un automóvil, pero el concesionario no confía en usted. No querrás revelarles la cantidad de tus ingresos o ahorros. Pero realmente quieres el coche. Se puede usar una prueba de conocimiento cero para demostrarle al distribuidor que tiene suficientes activos para pagarle sin sacrificar su privacidad. Aquí, ZKP se usa para agregar privacidad.
Ahora vamos a entrar en un ejemplo más práctico. Tenemos un gran problema de computación que tomará días resolverlo usando nuestras computadoras personales y portátiles. Además, tenemos acceso a un centro que brinda servicios en la nube que pueden resolver nuestro problema en un par de horas. Queremos usar su servicio, pero ¿cómo podemos asegurarnos de que no nos envíen una respuesta falsa? Si queremos validar su respuesta simplemente calculando la solución, nuevamente lleva días hacerlo. Entonces, ¿por qué siquiera molestarse en ir con ellos en primer lugar? Necesitamos una prueba junto con la respuesta del cálculo que se pueda verificar de manera eficiente. Mucho más rápido que la solución y la prueba en sí mismas. Si disponemos de un mecanismo de este tipo que proporcione una prueba de que todo el cálculo se ha realizado correctamente, entonces podremos utilizar los servicios de este centro sin necesidad de confiar en ellos. Aquí, ZKP se usa para agregar eficiencia y escalabilidad a nuestro sistema.
¿Esperar lo?
Básicamente, cuando queremos probar una declaración, por lo general, le damos al verificador más información de la que necesitamos. Digamos que queremos probar que existe un tricolor para un gráfico. La tricoloración es un problema famoso para los gráficos que pide colorear los vértices de un gráfico con tres colores como máximo, de tal manera que no exista ningún borde con los mismos colores en sus dos extremos.
Aquí hay un ejemplo de tres colores para un gráfico:
Para demostrar que sabemos que existe un coloreado para un gráfico específico, generalmente coloreamos el gráfico con la solución correcta y se lo mostramos al verificador. Ahora, el verificador sabe que el coloreado realmente existe, pero también conoce el coloreado en sí para cada vértice del gráfico. La información que necesitaba el verificador era un solo “sí” o “no” como respuesta a la pregunta “¿este gráfico tiene tricolor o no?”. Lo cual es mucha menos información que la que le dimos como prueba. Por lo tanto, el sistema de prueba debe optimizarse. El análisis de tales sistemas de prueba y la información transmitida en el proceso de prueba se realizó en 1985 [4] por Goldwasser, Micali y Rackoff [1]. Definieron algo llamado pruebas de conocimiento cero en las que no se transmite información adicional al probar una declaración.
A veces las pruebas no son deterministas a diferencia del caso de Waldo. Puede haber pruebas probabilísticas que permitan al verificador asegurarse de la honestidad del probador con una probabilidad abrumadora (con la probabilidad 1- e donde e puede ser arbitrariamente pequeña). Profundicemos en el ejemplo de los tres colores para entenderlo mejor.
Un probador tiene una solución para un gráfico de tres colores y quiere demostrárselo a un verificador, pero no quiere revelar la solución. ¿Qué puede hacer él? Vamos a resolverlo paso a paso. Si el probador no es honesto (es decir, no tiene un tricolor correcto), entonces existe un borde con los mismos colores en ambos extremos. Suponga que el verificador elige aleatoriamente un borde y le pide al probador que revele sus colores. Si el borde contiene diferentes colores en sus extremos, el verificador se convencerá un poco de que el probador tiene la solución correcta. Para estar más convencido, el verificador puede seguir pidiéndole al probador que revele más y más aristas. Sin embargo, de esta forma el verificador está aprendiendo el coloreado borde a borde lo cual no es deseable. Para resolver eso, le pedimos al probador que cambie los colores al azar entre dos rondas de revelación.
¡Problema resuelto! Ahora bien, el verificador no puede aprender nada sobre el coloreado (porque cambiar los colores en cada ronda impide que el verificador relacione los coloreados que ve cada vez con los intentos anteriores), pero se convence de que el probador es honesto con una probabilidad abrumadora. El verificador puede aumentar el número de revelaciones para lograr la probabilidad deseable que quiere saber que el probador es honesto. El número de revelaciones necesarias para lograr altas probabilidades de certeza es relativamente bajo, por lo tanto, el sistema de prueba es eficiente.
Conclusión
Hasta ahora, introduje pruebas de conocimiento cero y traté de convencerte de que realmente existen mostrándote algunos ejemplos. También discutí algunas de sus aplicaciones.
Además, uno de los principales casos de uso de las pruebas de conocimiento cero se encuentra en las cadenas de bloques y las criptomonedas. Se pueden usar para ayudar a la escalabilidad de las cadenas de bloques (descargando una parte del cómputo en la cadena fuera de la cadena) o lograr niveles más altos de privacidad.
Si está interesado o desea obtener más información, puede leer la siguiente parte de esta serie de publicaciones sobre ZKP.
La parte 2 llegará pronto…
Referencias
[1] La complejidad del conocimiento de los sistemas de prueba interactivos: https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf
[2] Notas de Vitalik Buterin sobre el conocimiento cero: https://vitalik.ca/general/2017/11/09/starks_part_1.html
[3] https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/
[4] https://en.wikipedia.org/wiki/Interactive_proof_system
