💻 computer science

A Complexity-Theoretic Approach to Proofs of Space

Este artículo presenta un marco elemental para la construcción de Pruebas de Espacio (PoS) seguras sin depender del modelo de oráculo aleatorio, demostrando que tales protocolos pueden construirse a partir de una combinación de supuestos criptográficos estándar (como funciones hash resistentes a colisiones o SNARGs) y supuestos específicos de complejidad de derandomización.

Autores originales: Marshall Ball, Jiaxin Guan

Publicado 2026-08-11

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Marshall Ball, Jiaxin Guan

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

El Gran Robo de Almacenamiento Digital

Imagina un mundo donde puedes demostrar que posees una biblioteca masiva de libros sin haber mostrado jamás una sola página. Este es el corazón de las Pruebas de Espacio (Proofs of Space), un concepto en el campo de la criptografía y la informática. Es como un casero digital que quiere asegurarse de que un inquilino realmente tiene un almacén lleno de muebles, y no solo un dibujo ingenioso de muebles. El casero (el Verificador) necesita estar seguro de que el inquilino (el Probador) está utilizando una enorme cantidad de memoria persistente para almacenar datos, en lugar de guardar una nota diminuta que diga "tengo los muebles" y luego conjurar mágicamente los muebles solo cuando se le solicita.

Durante años, la única forma de construir estos almacenes digitales dependía de una herramienta mágica e imaginaria llamada "Oráculo Aleatorio". Piensa en esto como una caja negra mágica que escupe respuestas perfectamente aleatorias e impredecibles cada vez que le haces una pregunta. Aunque es útil para la teoría, es como construir una casa sobre un cimiento de pura magia; no sabemos si resistiría en el mundo real. La gran pregunta para los científicos ha sido: ¿Podemos construir una Prueba de Espacio segura utilizando solo las leyes físicas reales de la computación, sin depender de cajas mágicas? Este artículo se sumerge en esa misma pregunta, utilizando las herramientas de la teoría de la complejidad —el estudio de qué tan difíciles son los problemas de resolver— para ver si podemos construir estas pruebas desde cero.

La Gran Idea del Artículo: La Cadena "Profunda"

Los autores, Marshall Ball y Jiaxin Guan, presentan un nuevo marco elemental para construir Pruebas de Espacio sin magia. Su principal hallazgo es que puedes crear estas pruebas si tienes dos ingredientes específicos: un supuesto criptográfico (como funciones hash resistentes a colisiones) y un supuesto de "derandomización" (la creencia de qué tan difíciles son ciertos problemas computacionales para máquinas poderosas y no deterministas).

Para entender su truco, imagina que necesitas demostrar que tienes una pila gigante y desordenada de arena (los datos). La forma antigua requería una caja mágica para garantizar que la arena no pudiera ser comprimida. Los autores se dan cuenta de que, en el mundo real, no necesitamos que la arena sea imposible de comprimir; solo necesitamos que sea difícil de comprimir rápidamente.

Introducen el concepto de Profundidad Computacional. Piensa en una cadena de datos como una historia.

La Configuración: El Probador toma una semilla diminuta (un resumen corto de una historia) y dedica mucho tiempo (Fase 1) a expandirla en una novela masiva y detallada (los datos).
La Trampa: El Verificador luego pide páginas específicas de esa novela.
El Engaño: Si el Probador no escribió realmente toda la novela y solo guardó el resumen corto, tendría que reescribir las páginas desde cero. Pero el Verificador le otorga solo una cantidad mínima de tiempo (Fase 2) para hacer esto.

Los autores demuestran que, si asumes que existen ciertos problemas difíciles (específicamente, que algunos problemas son demasiado difíciles para que los circuitos "no deterministas" los resuelvan rápidamente), puedes crear una función que convierte una semilla corta en una cadena larga. Esta cadena es "profunda": puede ser generada a partir de una semilla corta si tienes mucho tiempo, pero no puede ser reconstruida a partir de una semilla corta si tienes prisa. Es como un rompecabezas que toma un año resolver, pero solo un minuto verificar; si intentas resolverlo en un minuto, simplemente no puedes.

Cómo Funciona la Prueba: El "Árbol de Merkle" y el "Hechizo Mágico"

El artículo describe un protocolo de dos pasos para probar esta "profundidad".

Fase 1: La Configuración (La Larga Espera)
El Verificador envía una semilla aleatoria al Probador. El Probador pasa mucho tiempo (digamos, horas) usando su función "profunda" especial para convertir esa semilla en un archivo masivo de datos. Luego construye un Árbol de Merkle sobre estos datos. Imagina el Árbol de Merkle como la huella digital de todo el archivo. Es como un árbol genealógico donde cada hoja es un fragmento de datos, y cada rama es un hash (una huella digital única) de las dos ramas que tiene debajo. En la parte superior de todo está un único "Root" (Raíz) hash que representa el archivo completo. El Probador almacena este archivo masivo y la Raíz.

Fase 2: La Verificación (El Examen Rápido)
El Verificador pide de repente páginas específicas del archivo (índices aleatorios). El Probador debe proporcionar rápidamente esas páginas y la "ruta" a través del Árbol de Merkle que demuestra que esas páginas pertenecen al archivo original.

Aquí es donde la ingeniosidad de los autores brilla. Para evitar que el Probador intente eludir el protocolo (simplemente guardando la semilla corta e intentando adivinar las páginas), añaden un Argumento Sucinto (una prueba corta).

Opción A (El Supuesto más Fuerte): Utilizan un "SNARG" (una prueba muy corta y no interactiva) para demostrar que el Root hash que enviaron realmente proviene del archivo generado por la semilla. Esto requiere un supuesto fuerte sobre la existencia de ciertas herramientas criptográficas, pero mantiene bajo el gasto de almacenamiento.
Opción B (El Supuesto más Débil): Utilizan un argumento de tipo "Kilian" basado en funciones hash resistentes a colisiones. Este es un supuesto más estándar y "seguro", pero obliga al probador honesto a almacenar un poco más de datos (una cadena "PCP") para demostrar que el árbol de Merkle fue construido correctamente.

Lo Que Descartan y Lo Que Demuestran

El artículo argumenta explícitamente contra la idea de que las Pruebas de Espacio deben depender del modelo de Oráculo Aleatorio. Demuestran que la "caja mágica" no es necesaria. En su lugar, demuestran que, si aceptamos el "supuesto de derandomización" (que algunos problemas son difíciles para circuitos no deterministas), las Pruebas de Espacio son posibles.

También abordan un tipo específico de intento de eludir el protocolo: ¿qué pasa si el Probador almacena una cantidad mínima de datos e intenta "comprimir" el archivo grande sobre la marcha? Los autores demuestran que, si el Probador logra convencer al Verificador de que acepte, debe haber almacenado una cantidad significativa de datos. Específicamente, demuestran que un Probador que intenta eludir el protocolo no puede almacenar significativamente menos que el probador honesto (por ejemplo, si el probador honesto almacena $N$ bits, un Probador que intenta eludir el protocolo no puede salirse con la suya almacenando mucho menos de $N$ bits, dependiendo de la construcción específica utilizada).

La Conclusión

Este artículo no pretende haber construido un producto comercial listo para tu smartphone hoy mismo. En su lugar, proporciona un plano teórico. Demuestra que la tarea "imposible" de probar que tienes un almacén de datos sin magia es, de hecho, posible, siempre que aceptemos ciertos supuestos estándar sobre la dificultad de los problemas computacionales.

Demuestran que:

Funciona: Puedes construir estas pruebas usando "profundidad computacional" en lugar de magia.
Es eficiente: El usuario honesto no necesita hacer nada demasiado extraordinario, aunque sí necesita almacenar los datos.
Es seguro: Si alguien intenta eludir el protocolo almacenando menos datos, las matemáticas dicen que casi con seguridad será atrapado, asumiendo que los problemas difíciles subyacentes sigan siendo difíciles.

En resumen, Ball y Guan han sacado la "Prueba de Espacio" del reino de las cajas negras mágicas y la han plantado firmemente en el suelo de la teoría de la complejidad, mostrándonos que, con los supuestos adecuados, podemos construir almacenes digitales que sean tan seguros como las leyes de la computación lo permiten.

Resumen Técnico: Un Enfoque de la Teoría de la Complejidad para las Pruebas de Espacio

Planteamiento del Problema
Las Pruebas de Espacio (PoS, por sus siglas en inglés), introducidas por Dziembowski et al. [DFKP15], son protocolos de dos fases que permiten a un Probador convencer a un Verificador eficiente de que ha asignado una cantidad significativa de memoria persistente. El protocolo consiste en una fase de inicialización (de larga duración) donde el Probador almacena datos, y una fase de ejecución (de corta duración) donde el Verificador desafía al Probador para demostrar que los datos aún están almacenados.

Una limitación crítica de los protocolos PoS existentes es que sus pruebas de seguridad dependen fuertmente del Modelo de Oráculo Aleatorio (ROM) o de supuestos criptográficos ad hoc. Específicamente, dependen de la incompresibilidad y la extractibilidad simultáneas de las consultas al oráculo aleatorio. Hasta la fecha, no se conocen construcciones que sean seguras en el modelo plano (sin oráculos aleatorios) basadas únicamente en supuestos criptográficos estándar. Existe una falta de supuestos limpios y falsificables respecto a las funciones hash criptográficas que sean suficientes para la seguridad demostrable de estas construcciones.

Metodología y Marco de Trabajo
Este artículo presenta un marco elemental para construir PoS en el modelo plano combinando supuestos de derandomización con supuestos criptográficos. La idea central es que una PoS requiere una cadena $\sigma$ que es paradójicamente tanto compresible desde una descripción corta (dado un tiempo suficiente $T$ ) como incompresible desde cualquier descripción ligeramente más corta (dentro de un tiempo corto $t$ ).

Los autores formalizan esto utilizando la noción de la teoría de la complejidad de profundidad computacional (introducida por Antunes et al. [AFvMV06]). Buscan una función $f$ con alta profundidad computacional:

Compresibilidad de largo tiempo: $f(x)$ puede ser computada a partir de una semilla corta $x$ en un tiempo $T$ .
Incompresibilidad de corto tiempo: $f(x)$ no puede ser reconstruida desde cualquier descripción más corta que $|f(x)|$ dentro de un tiempo $t$ , incluso dado $x$ .

La construcción procede en tres pasos:

Construcción de Funciones de Alta Profundidad:
Los autores utilizan Generadores de Números Pseudoaleatorios (PRGs) de extensión de semilla contra distinguidores no deterministas. Bajo el supuesto de que $E = \text{DTIME}[2^{O(n)}]$ requiere circuitos no deterministas de tamaño exponencial (un supuesto estándar utilizado para mostrar que $\text{AM} = \text{NP}$ ), construyen PRGs que son difíciles para circuitos no deterministas.
- Para lograr una probabilidad abrumadora de incompresibilidad (en lugar de solo un error notable), emplean PRGs multiplicativos contra distinguidores no deterministas. Estos preservan la probabilidad de eventos despreciables, asegurando que la salida del PRG permanezca incompresible con una probabilidad abrumadora.
- Para manejar la incompresibilidad aproximada (resiliencia a errores de distancia de Hamming), componen el PRG con códigos de corrección de errores (ECC) decodificables por lista. Esto asegura que incluso si un adversario recupera una cadena cercana a $f(x)$ , la cadena original permanezca incompresible.
El Lema de Extracción:
Una contribución técnica central es el Lema de Extracción (Lema 11). Establece que si un probador puede mantener un estado pequeño $S$ y responder con éxito a los desafíos de verificación con una probabilidad no despreciable, entonces la cadena subyacente $y = f(x)$ es aproximadamente compresible.
- El lema utiliza un Generador de Conjunto de Impacto (HSG) para seleccionar determinísticamente un conjunto de índices de desafío "útiles" que cubran una gran fracción de la cadena almacenada.
- Esto permite a un extractor recuperar la mayoría de los bits de $y$ a partir del pequeño estado del probador dentro de un tiempo $t$ , contradiciendo la incompresibilidad asumida de $f$ .
Instanciación del Protocolo:
El marco se instancia en dos protocolos específicos de PoS, que difieren en sus supuestos criptográficos y sobrecarga de almacenamiento:
- Construcción 1 (basada en SNARG): Utiliza un Argumento No Interactivo Semi-Universal (SNARG) para $P$ . El Probador almacena la raíz de Merkle de $f(x)$ y una prueba sucinta de que la raíz corresponde a $f(x)$ . Esto depende de la existencia de SNARGs para $P$ (un supuesto fuerte) pero ofrece un almacenamiento casi óptimo para el probador honesto ( $N$ bits).
- Construcción 2 (basada en Kilian): Utiliza el sistema de argumento interactivo de Kilian basado en PCPs y Funciones Hash Resistentes a Colisiones (CRHF). El Probador debe almacenar la cadena PCP de la computación $f(x)$ , lo que conlleva mayores requisitos de almacenamiento para el probador honesto ( $N + \tilde{O}(T)$ ), pero depende de supuestos criptográficos más débiles (CRHF + derandomización).

Resultados Clave
El artículo establece los siguientes teoremas (informalmente):

Teorema 1: Asumiendo que $E$ es difícil para circuitos no deterministas de tamaño exponencial, existen funciones explícitas que son incompresibles en tiempo- $t$ para tamaño $N - O(\rho N \log(1/\rho))$ .
Teorema 2 (instanciación SNARG): Asumiendo que $E$ es difícil para circuitos no deterministas de tamaño exponencial, funciones de un solo sentido y un SNARG semi-universal para $P$ , existe una PoS donde el probador honesto almacena $N$ bits, y el esquema es seguro contra cualquier probador que use $(1-o(1))N$ bits.
Teorema 3 (instanciación CRHF): Asumiendo que $E$ es difícil para circuitos no deterministas de tamaño exponencial y funciones resistentes a colisiones, existe una PoS donde el probador honesto almacena $N$ bits, y el esquema es seguro contra cualquier probador que use $N^{1/c}$ bits (para alguna constante $c$ ).

Significado y Reivindicaciones
Los autores enfatizan que su trabajo proporciona un resultado de factibilidad genérica y pedagógicamente limpio para PoS en el modelo plano.

Rompiendo la Barrera del ROM: Demuestran que las PoS pueden construirse sin oráculos aleatorios, apoyándose en cambio en supuestos de derandomización estándar (dureza de $E$ contra circuitos no deterministas) combinados con primitivas criptográficas estándar.
Compensaciones (Trade-offs): El artículo destaca la compensación entre los supuestos criptográficos y la eficiencia de almacenamiento. El enfoque basado en SNARG minimiza el almacenamiento del probador honesto pero requiere supuestos más fuertes. El enfoque basado en Kilian utiliza supuestos más débiles (CRHF) pero requiere que el probador honesto almacene un PCP de la computación, aumentando significativamente el almacenamiento.
Limitaciones: Los autores declaran explícitamente que su enfoque es la factibilidad teórica, no modelos de amenazas sofisticados o protocolos prácticos. Observan que, aunque su marco genera PoS, no está claro de inmediato cómo adaptar estas ideas para construir Funciones de Dureza de Memoria (MHF), un objeto relacionado que suele derivarse de PoS basadas en ROM. Además, reconocen que el manejo de la composición (un solo probador interactuando con muchos verificadores) requiere más trabajo para asegurar que los costos de almacenamiento no se amorticen.

En resumen, este trabajo cierra la brecha entre la teoría de la complejidad y los protocolos criptográficos, mostrando que la "dureza" requerida para las Pruebas de Espacio puede derivarse de supuestos fundamentales de derandomización en lugar de modelos heurísticos de oráculo aleatorio.

El Gran Robo de Almacenamiento Digital

La Gran Idea del Artículo: La Cadena "Profunda"

Cómo Funciona la Prueba: El "Árbol de Merkle" y el "Hechizo Mágico"

Lo Que Descartan y Lo Que Demuestran

La Conclusión

Más como este