💻 computer science

PoSME: Proof of Sequential Memory Execution via Latency-Bound Pointer Chasing with Causal Hash Binding

El artículo presenta PoSME, un primitivo criptográfico que garantiza una computación secuencial sostenida mediante la persecución de punteros con límites de latencia y un enlace causal de hash, logrando una fuerte resistencia a los compromisos tiempo-memoria y limitando la ventaja de los ASICs a la latencia de acceso aleatorio de la memoria DRAM.

Autores originales: David L. Condrey

Publicado 2026-04-20

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: David L. Condrey

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

¡Claro que sí! Imagina que el mundo de la criptografía y la seguridad informática es como un enorme edificio de oficinas donde todos quieren demostrar que han trabajado duro, pero sin hacer trampas.

El artículo que me has pasado presenta una nueva herramienta llamada PoSME (Prueba de Ejecución Secuencial de Memoria). Vamos a desglosarlo usando analogías de la vida real para que sea fácil de entender.

1. El Problema: ¿Cómo saber si alguien realmente trabajó?

Imagina que tienes que resolver un rompecabezas gigante.

El problema actual: Hay formas de demostrar que pasaste tiempo (como un reloj), pero si tienes un robot súper rápido (un chip especial o ASIC), puedes resolverlo en segundos aunque el reloj diga que tardaste horas.
Otro problema: Hay formas de demostrar que usaste mucha memoria (como llenar una habitación de cajas), pero si tienes una habitación muy grande y barata, puedes guardar todo y resolverlo rápido.

Los sistemas actuales o son rápidos pero fáciles de engañar con robots, o son lentos pero fáciles de engañar con mucha memoria. PoSME es la solución que combina lo mejor de ambos mundos: obliga a usar memoria de una manera que no se puede acelerar ni con robots ni con más espacio.

2. La Analogía Principal: El Laberinto de los Espejos Mágicos

Imagina que PoSME es un laberinto gigante lleno de habitaciones (la memoria).

El Laberinto Mutable (Cambia todo el tiempo): A diferencia de un laberinto normal que siempre es igual, este cambia cada vez que entras. Si intentas memorizar el mapa, el mapa se reescribe mientras caminas.
La Búsqueda de la Agujas (Pointer Chasing): Para avanzar, no puedes correr. Tienes que leer una nota en la habitación actual que te dice exactamente dónde ir a la siguiente habitación. Pero esa nota depende de lo que acabas de leer.
- Analogía: Es como si para abrir la puerta 2, necesitaras el código de la puerta 1. Para abrir la 3, necesitas el código de la 2. No puedes abrir la 3 antes que la 2. Tienes que hacerlo en orden, paso a paso.
El "Efecto Dominó" (Enlace Causal): Cada vez que escribes algo en una habitación, no solo guardas el dato, sino que también grabas un "sello de tiempo" que conecta esa habitación con la anterior. Si alguien intenta falsificar una habitación, tendría que falsificar toda la cadena de habitaciones anteriores que la llevaron allí. Es como intentar cambiar una página de un libro de historia sin que se note que faltan las páginas anteriores.

3. ¿Por qué es imposible de hackear con robots (ASICs)?

Aquí está la magia de PoSME.

El Cuello de Botella es la "Velocidad de Viaje": En una computadora normal, el cerebro (el procesador) es muy rápido, pero enviar un mensaje a la memoria (los archivos) tarda un poco, como enviar una carta por correo.
La Trampa: PoSME está diseñado para que el tiempo que tardas en escribir y leer la memoria sea lo que más cuesta, no el cálculo matemático.
- Analogía: Imagina que tienes que correr de un extremo a otro de un estadio gigante para recoger una pelota y volver. No importa si tus piernas son de acero (un robot súper rápido); si el estadio es enorme, tardarás lo mismo en cruzarlo.
El resultado: Las tarjetas gráficas (GPUs) y los chips especiales (ASICs) son excelentes haciendo muchas cosas a la vez (como 1000 personas corriendo en paralelo), pero PoSME obliga a hacer una sola cosa a la vez de forma estricta.
- Dato curioso: El estudio muestra que una computadora de escritorio normal (como la tuya) es 14 a 19 veces más rápida que una tarjeta gráfica de gama alta (como las de los centros de datos) para hacer esta tarea específica. ¡Es como si un coche de Fórmula 1 fuera más lento que una bicicleta en un camino de tierra lleno de baches!

4. Las Tres Grandes Ventajas

Orden estricto: No puedes saltarte pasos. Tienes que hacerlos uno tras otro.
Resistencia a atajos: Si intentas guardar menos memoria (para ahorrar espacio), tendrás que rehacer todo el trabajo desde cero, lo cual te costará mucho más tiempo. Es como si, por ahorrar papel, tuvieras que escribir el libro entero de nuevo cada vez que te equivocas.
Justicia: No necesitas confiar en nadie ni tener un "setup" especial. Cualquiera puede verificar que el trabajo se hizo correctamente.

5. ¿Para qué sirve esto en la vida real?

Criptomonedas justas: Evita que las grandes empresas con robots caros dominen la minería, permitiendo que la gente común con computadoras normales participe.
Prueba de autoría: Si alguien dice "escribí este libro en 2023", PoSME puede probar que realmente pasó el tiempo necesario para escribirlo, sin que puedan copiarlo y pegarlo instantáneamente.
Resistencia a bots: En redes sociales, ayuda a distinguir entre humanos reales (que tardan tiempo en pensar) y bots (que intentan hacer cosas instantáneamente).

En resumen

PoSME es como un candado de tiempo y memoria que se abre solo si caminas lentamente por un laberinto que cambia constantemente. No importa si tienes un coche de carreras (hardware potente) o un mapa gigante (mucho almacenamiento); si no sigues el camino paso a paso y usas la memoria correcta, no podrás abrir la puerta.

Es una forma de decir: "Para ganar aquí, tienes que trabajar duro y lento, tal como lo haría un humano".

Resumen Técnico: PoSME

1. El Problema

El documento aborda la necesidad de sistemas criptográficos que puedan probar que una parte ha realizado un cómputo secuencial sostenido bajo restricciones de recursos concretas. Las primitivas existentes tienen limitaciones significativas:

VDFs (Funciones de Retraso Verificables): Certifican el tiempo secuencial pero son insensibles a la memoria; un ASIC puede acelerarlas arbitrariamente mediante ALUs más rápidas.
PoSW (Pruebas de Trabajo Secuencial): Prueban la traversa de grafos, pero sobre memoria estática e inmutable.
Funciones Difíciles de Memoria (MHF): Como Argon2id, aumentan el costo por presión de memoria, pero son primitivas de un solo disparo sin un sistema de prueba en cadena.
Brecha: Ninguna primitiva actual combina simultáneamente: pasos secuenciales, dureza de memoria, estado mutable, verificación eficiente y resistencia a ASIC basada en latencia.

2. Metodología y Construcción

Los autores proponen PoSME (Proof of Sequential Memory Execution), una primitiva criptográfica que enforces el cómputo secuencial mediante un persecución de punteros (pointer chasing) con límites de latencia sobre un área mutable.

Principios de Diseño Clave:

Persecución de Punteros Dependiente de Datos: La dirección de cada lectura subsiguiente depende del valor de la lectura actual. Esto crea una cadena estrictamente secuencial que no puede paralelizarse.
Estado de Área Mutable: A diferencia de los grafos estáticos, el "área" (arena) de memoria evoluciona en cada paso. Reescribir un bloque requiere replayar su cadena de escritura.
Vinculación Causal Simbiótica: Cada escritura une el valor de los datos y su historial de escritura temporal (hash causal). Ni los datos ni el hash causal pueden fabricarse sin el otro.

Detalles Técnicos:

Estructura: El área se mapea a un hipercubo booleano de dimensión $d_{hc}$ , donde $N = 2^{d_{hc}}$ bloques.
Función de Paso: En cada paso $t$ , se realizan $d$ lecturas secuenciales. Las direcciones se derivan de la salida del hash de la lectura anterior. El bloque escrito se actualiza in-place, vinculando el nuevo dato con el hash causal anterior y el cursor actual.
Verificación:
- Modo Clásico: Utiliza pruebas de Merkle y Fiat-Shamir. El tamaño de la prueba escala con la profundidad de recursión ( $R$ ) y el número de desafíos ( $Q$ ).
- Modo IVC (Cómputo Verificable Incremental): Utiliza plegado de campos binarios (con la tecnología Binius) para lograr un tamaño de prueba constante ( $O(1)$ ), independientemente del número de pasos $K$ . Esto permite una verificación extremadamente eficiente.

3. Contribuciones Clave

Nueva Construcción: PoSME es la primera primitiva que combina estado de área mutable, direccionamiento de persecución de punteros dependiente de datos y vinculación causal simbiótica.
Seguridad Espacio-Tiempo Formal:
- Se demuestra un límite inferior formal de $S \cdot T = \Omega(K^2)$ para grafos DAG causales dinámicos.
- Se extiende a adversarios adaptativos sin pérdida de factores.
- Se introduce el concepto de "estancamiento temporal" (temporal staleness): incluso si un adversario almacena una gran fracción de la memoria, los valores almacenados se vuelven obsoletos rápidamente debido a las escrituras aleatorias, aumentando exponencialmente el costo de recomputación.
Resistencia a ASIC por Latencia: El cuello de botella no es el ancho de banda ni la potencia de cálculo, sino la latencia de acceso aleatorio a la DRAM (40-50 ns en DDR5). El cálculo de hash representa menos del 3.5% del costo por paso.
Validación Empírica:
- Validación matemática y empírica de la uniformidad del Oráculo Aleatorio (ROM) con $\chi^2/df = 1.0004$ .
- Pruebas en 17 plataformas CPU y 4 arquitecturas GPU.

4. Resultados Empíricos

Rendimiento CPU vs. GPU:
- Las GPUs son 14 a 19 veces más lentas que las CPUs de consumo en esta carga de trabajo.
- La ventaja de las GPUs en ancho de banda es irrelevante porque el problema está limitado por la latencia, no por el ancho de banda.
- El hash (BLAKE3) consume menos del 3.5% del tiempo total por paso; el resto es tiempo de espera de la memoria.
Resistencia a la Reducción de Memoria (TMTO):
- Con una densidad de escritura $\rho=4$ (4 escrituras por bloque en promedio), un adversario que no almacena memoria enfrenta una penalización de cómputo de 10x frente a un ejecutor honesto.
- Incluso almacenando el 95% del área, la penalización por recomputación debido a la "estancamiento temporal" es significativa.
Cuello de Botella de Capacidad: Para un adversario que intenta ejecutar múltiples instancias en paralelo (para amortizar la penalización de GPU), la capacidad de VRAM de las GPUs actúa como un límite estricto. Una GPU H100 (80 GiB) solo puede ejecutar ~80 instancias de 1 GiB, utilizando menos del 9% de su ancho de banda total. Esto hace que las CPUs de consumo sean más rentables (10-20x más capacidad de área por dólar).

5. Significado e Implicaciones

PoSME llena un vacío crítico en la criptografía de pruebas de trabajo y funciones de retraso:

Resistencia Estructural a ASIC: Al basar la seguridad en la latencia física de la DRAM (que ha mejorado muy poco en décadas) en lugar del ancho de banda o la velocidad de cálculo, PoSME ofrece una barrera más duradera contra el hardware personalizado.
Aplicaciones: Proporciona una base sólida para:
- Minería resistente a ASIC.
- Atestación de autoría: Probar que un documento fue generado tras un proceso de cómputo específico.
- Resistencia a Sybil: Dificultar la creación de múltiples identidades falsas.
- Retraso Verificable: Combinado con wrappers externos (como TEEs o VDFs tradicionales), puede servir como función de retraso verificable.
Eficiencia de Verificación: Gracias al diseño IVC con campos binarios, la verificación puede ser constante ( $O(1)$ ), lo que es crucial para aplicaciones en cadenas de bloques y clientes ligeros.

En conclusión, PoSME representa un avance fundamental al demostrar que es posible construir primitivas criptográficas donde la memoria mutable y la latencia son los factores determinantes de la seguridad, logrando una resistencia a la aceleración por hardware que las primitivas anteriores no podían ofrecer simultáneamente.