Prueba de conocimiento cero no interactiva

Las pruebas de conocimiento cero no interactivas son primitivas criptográficas en las que la información entre un probador y un verificador puede ser autenticada por el probador, sin revelar ningún dato específico más allá de la validez de la propia declaración. Esto hace innecesaria la comunicación directa entre el probador y el verificador, eliminando así cualquier intermediario.

La principal ventaja de las pruebas de conocimiento cero no interactivas es que pueden utilizarse en situaciones donde no existe posibilidad de interacción entre el probador y el verificador, como en las transacciones en línea donde las dos partes no pueden comunicarse en tiempo real. Esto hace que las pruebas de conocimiento cero no interactivas sean particularmente útiles en sistemas descentralizados como las cadenas de bloques , donde las transacciones son verificadas por una red de nodos y no existe una autoridad central que supervise el proceso de verificación. ^{[ 1 ]}

La mayoría de las pruebas de conocimiento cero no interactivas se basan en construcciones matemáticas como la criptografía de curva elíptica o la criptografía basada en emparejamientos , que permiten crear pruebas cortas y fácilmente verificables de la veracidad de una afirmación. A diferencia de las pruebas de conocimiento cero interactivas, que requieren múltiples rondas de interacción entre el probador y el verificador, las pruebas de conocimiento cero no interactivas están diseñadas para ser eficientes y pueden utilizarse para verificar un gran número de afirmaciones simultáneamente. ^{[ 1 ]}

Blum , Feldman y Micali ^{[ 2 ]} demostraron en 1988 que una cadena de referencia común compartida entre el probador y el verificador es suficiente para lograr el conocimiento cero computacional sin requerir interacción. Goldreich y Oren ^{[ 3 ]} dieron resultados de imposibilidad para protocolos de conocimiento cero de una sola pasada en el modelo estándar . En 2003, Shafi Goldwasser y Yael Tauman Kalai publicaron una instancia de un esquema de identificación para el cual cualquier función hash producirá un esquema de firma digital inseguro . ^{[ 4 ]}

El modelo influye en las propiedades que se pueden obtener de un protocolo de conocimiento cero. Pass ^{[ 5 ]} demostró que, en el modelo de cadena de referencia común, los protocolos de conocimiento cero no interactivos no conservan todas las propiedades de los protocolos de conocimiento cero interactivos; por ejemplo, no conservan la negabilidad. También se pueden obtener pruebas de conocimiento cero no interactivas en el modelo de oráculo aleatorio utilizando la heurística de Fiat-Shamir . ^{[ 6 ]}

Aplicaciones de blockchain

En 2012, Alessandro Chiesa et al. desarrollaron el protocolo zk-SNARK, un acrónimo de argumento de conocimiento sucinto no interactivo de conocimiento cero . ^{[ 7 ]} La primera aplicación generalizada de zk-SNARKs fue en el protocolo de cadena de bloques Zerocash , donde la criptografía de conocimiento cero proporciona la base computacional, al facilitar pruebas matemáticas de que una parte posee cierta información sin revelar cuál es esa información. ^{[ 8 ]} Zcash utilizó zk-SNARKs para facilitar cuatro tipos distintos de transacciones: privadas, de protección, de protección y públicas. Este protocolo permitió a los usuarios determinar cuántos datos se compartían con el libro mayor público para cada transacción. ^{[ 9 ]} Ethereum zk-Rollups también utiliza zk-SNARKs para aumentar la escalabilidad . ^{[ 10 ]}

En 2017, se lanzó Bulletproofs ^{[ 11 ] , que permite probar que un valor comprometido está dentro de un rango utilizando un número logarítmico (en la longitud de bits del rango) de elementos de campo y grupo. [ 12 ]} Posteriormente, Bulletproofs se implementó en el protocolo Mimblewimble (la base de Grin y Beam, y Litecoin a través de bloques de extensión) y en la criptomoneda Monero . ^{[ 13 ]}

En 2018, Eli Ben-Sasson , Iddo Bentov, Yinon Horesh y Michael Riabzev presentaron el protocolo zk-STARK ( Zero-Knowledge Scalable Transparent Argument of Knowledge ) ^{[ 14 ]} , que ofrece transparencia (sin configuración de confianza), tiempo de prueba cuasi-lineal y tiempo de verificación polilogarítmico. Los argumentos transparentes sucintos de conocimiento cero son un tipo de sistema de prueba criptográfica que permite a una parte (el probador) demostrar a otra parte (el verificador) que una afirmación es verdadera, sin revelar información adicional más allá de la veracidad de la afirmación en sí. Los zk-STARK son sucintos, lo que significa que permiten la creación de pruebas cortas y fáciles de verificar, y son transparentes, lo que significa que cualquiera puede verificar la prueba sin necesidad de información secreta. ^{[ 14 ]}

A diferencia de la primera generación de zk-SNARKs, los zk-STARKs, por defecto, no requieren una configuración de confianza, lo que los hace particularmente útiles para aplicaciones descentralizadas como las cadenas de bloques. Además, los zk-STARKs pueden usarse para verificar muchas declaraciones a la vez, lo que los hace escalables y eficientes. ^{[ 1 ]}

En 2019, se presentaron zk-SNARKs recursivos HALO sin una configuración de confianza. ^{[ 15 ]} Pickles ^{[ 16 ]} zk-SNARKs, basados ​​en la construcción anterior, impulsan Mina, la primera cadena de bloques sucintamente verificable. ^{[ 17 ]}

A continuación se presenta una lista de protocolos y bibliotecas de prueba de conocimiento cero, junto con comparaciones basadas en transparencia, universalidad y seguridad postcuántica plausible. Un protocolo transparente es aquel que no requiere ninguna configuración de confianza y utiliza aleatoriedad pública. Un protocolo universal es aquel que no requiere una configuración de confianza independiente para cada circuito. Finalmente, un protocolo postcuántico plausible es aquel que no es susceptible a ataques conocidos que involucren algoritmos cuánticos.

Originalmente, ^{[ 2 ]} el conocimiento cero no interactivo se definió únicamente como un sistema de prueba de un solo teorema. En dicho sistema, cada prueba requiere su propia cadena de referencia común nueva. Una cadena de referencia común generalmente no es una cadena aleatoria. Puede, por ejemplo, consistir en elementos de grupo elegidos al azar que todas las partes del protocolo utilizan. Aunque los elementos de grupo son aleatorios, la cadena de referencia no lo es, ya que contiene una cierta estructura (por ejemplo, elementos de grupo) que es distinguible de la aleatoriedad. Posteriormente, Feige, Lapidot y Shamir ^{[ 37 ]} introdujeron las pruebas de conocimiento cero de múltiples teoremas como una noción más versátil para las pruebas de conocimiento cero no interactivas.

La criptografía basada en emparejamientos ha dado lugar a varios avances criptográficos. Uno de estos avances son las pruebas de conocimiento cero no interactivas más potentes y eficientes. La idea seminal fue ocultar los valores para la evaluación de emparejamientos en un compromiso . Utilizando diferentes esquemas de compromiso, esta idea se utilizó para construir sistemas de prueba de conocimiento cero bajo el ocultamiento de subgrupos ^{[ 38 ]} y bajo la suposición de linealidad decisional . ^{[ 39 ]} Estos sistemas de prueba demuestran la satisfacibilidad de circuitos y, por lo tanto, mediante el teorema de Cook-Levin, permiten demostrar la pertenencia para cada lenguaje en NP. El tamaño de la cadena de referencia común y las pruebas es relativamente pequeño; sin embargo, transformar una declaración en un circuito booleano implica una sobrecarga considerable.

Se han propuesto sistemas de prueba bajo la suposición de ocultación de subgrupos, la suposición de linealidad decisional y la suposición de Diffie-Hellman externa que permiten probar directamente las ecuaciones de producto de emparejamiento que son comunes en la criptografía basada en emparejamientos . ^{[ 40 ]}

Bajo supuestos de conocimiento sólidos , se sabe cómo crear sistemas de prueba computacionalmente sólidos de longitud sublineal para lenguajes NP-completos . Más precisamente, la prueba en dichos sistemas consta únicamente de un pequeño número de elementos de grupo bilineales . ^{[ 41 ] [ 42 ]}