Pruebas de conocimiento cero

Una prueba de conocimiento cero permite que un probador convenza a un verificador de que una declaración es verdadera sin revelar nada más allá del hecho de su veracidad, una capacidad contraintuitiva con amplios usos criptográficos.

Definition

Una prueba de conocimiento cero es un protocolo interactivo (o no interactivo) en el que un probador convence a un verificador de que una declaración es verdadera, de modo que el verificador no aprende nada más que la validez de la declaración, formalizado por un simulador que reproduce la vista del verificador sin el testigo.

Scope

Este tema abarca los sistemas de prueba interactivos y sus variantes de conocimiento cero: las propiedades definitorias de completitud, solidez y conocimiento cero; el paradigma de simulación; las pruebas de conocimiento; la transformación de Fiat-Shamir a pruebas no interactivas; y los sistemas sucintos modernos (zk-SNARKs y zk-STARKs). Aborda las aplicaciones a la autenticación y la verificación que preserva la privacidad. Excluye la teoría de la complejidad más amplia de las pruebas interactivas y los protocolos (MPC) que utilizan el conocimiento cero como subcomponente.

Core questions

• ¿Cómo puede una prueba transmitir la convicción de la verdad sin filtrar ninguna otra información?
• ¿Qué garantizan la completitud, la solidez y la propiedad de conocimiento cero?
• ¿Cómo captura la existencia de un simulador el concepto de 'no aprender nada'?
• ¿Cómo se hacen no interactivas las pruebas interactivas mediante la transformación de Fiat-Shamir?
• ¿Cómo hacen las pruebas sucintas (SNARKs, STARKs) que el conocimiento cero sea práctico a escala?

Key concepts

• sistema de prueba interactivo
• completitud y solidez
• propiedad de conocimiento cero
• simulador
• prueba de conocimiento
• transformación de Fiat-Shamir
• conocimiento cero no interactivo (NIZK)
• zk-SNARKs y zk-STARKs
• esquemas de compromiso

Key theories

El paradigma de simulación

Un protocolo es de conocimiento cero si para cada verificador existe un simulador eficiente que, sin acceso al testigo secreto, produce una transcripción indistinguible de una interacción real, formalizando la idea de que el verificador no aprende nada.

Completitud, solidez y pruebas de conocimiento

Una prueba interactiva es completa si los probadores honestos convencen a los verificadores honestos y sólida si las declaraciones falsas son rechazadas con alta probabilidad; una prueba de conocimiento garantiza adicionalmente, mediante un extractor de conocimiento, que el probador realmente posee el testigo.

Mechanisms

Un protocolo canónico de tres movimientos (sigma) tiene al probador enviando un compromiso, al verificador enviando un desafío aleatorio y al probador respondiendo; la solidez proviene de la incapacidad del probador para responder a todos los desafíos sin el testigo, y el conocimiento cero de la capacidad del simulador para falsificar transcripciones eligiendo primero el desafío. La transformación de Fiat-Shamir reemplaza el desafío del verificador con un hash del compromiso, produciendo una prueba no interactiva. Los sistemas sucintos utilizan compromisos polinomiales y circuitos aritméticos para producir pruebas cortas y rápidas de verificar.

Clinical relevance

Las pruebas de conocimiento cero permiten la privacidad y la escalabilidad en los sistemas implementados: las criptomonedas que preservan la privacidad (Zcash) ocultan los detalles de las transacciones mientras prueban la validez, los rollups de blockchain utilizan pruebas sucintas para comprimir la computación, las credenciales anónimas y los sistemas de identidad digital prueban atributos (edad, ciudadanía) sin revelarlos, y los esquemas de autenticación prueban la posesión de un secreto sin divulgarlo.

Evidence & guidelines

Las construcciones de conocimiento cero son un área activa de estandarización (el esfuerzo de estándares de la comunidad ZKProof). Los sistemas de producción se basan en bibliotecas SNARK y STARK bien revisadas, aunque los SNARK que requieren una configuración confiable exigen un diseño cuidadoso de la ceremonia, mientras que los STARK evitan la configuración confiable a costa de pruebas más grandes. La solidez depende de suposiciones criptográficas y, para Fiat-Shamir, del modelo de oráculo aleatorio.

History

Goldwasser, Micali y Rackoff introdujeron las pruebas interactivas y el conocimiento cero en 1985, con la versión de la revista apareciendo en 1989. Goldreich, Micali y Wigderson demostraron que cada declaración NP tiene una prueba de conocimiento cero (1987). La transformación de Fiat-Shamir (1986) hizo que las pruebas fueran no interactivas. La década de 2010 trajo argumentos no interactivos sucintos (zk-SNARKs) y STARKs transparentes, moviendo el conocimiento cero de la teoría a los productos de blockchain y privacidad.

Key figures

• Shafi Goldwasser
• Silvio Micali
• Charles Rackoff
• Oded Goldreich
• Amos Fiat
• Adi Shamir

Seminal works

• goldwasser1989
• katz2020
• goldreich2001

Frequently asked questions

¿Cuál es una intuición simple para el conocimiento cero?

Imagine que prueba que puede distinguir dos objetos visualmente idénticos identificando repetidamente cuál de ellos intercambió una parte oculta: cada respuesta correcta aumenta la confianza en que puede distinguirlos, pero el verificador nunca aprende cómo. Repetir un desafío-respuesta muchas veces hace que el engaño sea astronómicamente improbable sin revelar ningún secreto.

¿Las pruebas de conocimiento cero requieren interacción?

La definición original es interactiva, pero la transformación de Fiat-Shamir y las construcciones no interactivas dedicadas (NIZKs, SNARKs, STARKs) producen una única cadena de prueba que cualquiera puede verificar sin interactuar, lo que las hace utilizables en blockchains.