Resumen Técnico: MHOT – Estructura de Datos Autenticada Optimizada en Altura para el Compromiso del Estado de Blockchain

1. Declaración del Problema

En los sistemas blockchain modernos, particularmente en Ethereum, el cómputo de la raíz de estado consume aproximadamente entre el 70 % y el 80 % del tiempo total de procesamiento de bloques. La estructura de datos autenticada (ADS) canónica actual, el Merkle Patricia Trie (MPT), sufre de dos limitaciones críticas:

1. Vulnerabilidad Estructural ante Ataques Nurgle: El MPT utiliza un indexado de prefijo fijo, donde cada nivel del árbol consume un número fijo de bits contiguos de la clave. Esta estructura permite que los adversarios exploten prefijos comunes largos (mediante colisiones de hash) para inflar artificialmente las profundidades de las rutas. El "ataque Nurgle" (S&P '24) demuestra que un atacante puede degradar el rendimiento del sistema e incrementar los costos de I/O con un costo de gas insignificante, forzando al trie a materializar rutas comprimidas en estructuras más profundas.
2. El Compromiso Span–Proof (Extensión–Prueba): Para mitigar el crecimiento de la profundidad, uno podría aumentar el "span" (los bits consumidos por nivel). Sin embargo, en los tries basados en prefijos, aumentar el span incrementa exponencialmente el "fanout" (el número de ranuras de los hijos, $2^{span}$). Esto impone un compromiso: un span alto limita la altura pero infla el tamaño de los nodos y de las pruebas exponencialmente; un span bajo mantiene las pruebas compactas pero deja al árbol vulnerable a ataques de profundización.

Las alternativas existentes como los Verkle Tries o LVMT desacoplan el tamaño de la prueba del fanout utilizando compromisos vectoriales (técnicas algebraicas). Sin embargo, estos requieren ceremonias de configuración de confianza (trusted setup), introducen costos de verificación aritmética más altos y a menudo carecen de soporte nativo para pruebas de rango esenciales para la sincronización del estado.

2. Metodología: MHOT

Los autores proponen MHOT (Height-Optimized Authenticated Data Structure), una ADS persistente basada en hash que logra la optimalidad de altura sin configuración de confianza ni criptografía especializada. MHOT adapta la estructura del Height-Optimized Trie (HOT) al compromiso del estado de blockchain a través de cuatro mecanismos clave:

A. Indexación por Bits Discriminativos (Fundamento Estructural)

A diferencia del MPT, que consume prefijos contiguos fijos, MHOT realiza ramificaciones basadas en bits discriminativos. Un bit discriminativo es una posición donde al menos dos claves en un subárbol difieren.

• Acoplamiento Lineal: Este enfoque acopla el span y el fanout de manera lineal en lugar de exponencial. Un nodo compuesto con un fanout $k$ consume hasta $k-1$ bits discriminativos, mientras que un nodo basado en prefijos de ese mismo fanout requiere $\log_2 k$ bits contiguos.
• Span Adaptativo: Los nodos se adaptan a la distribución real de las claves. Las regiones densas usan menos bits por nodo; las regiones dispersas usan más. Esto asegura una altura de árbol demostrablemente mínima para cualquier conjunto de claves dado.
• Resistencia a Nurgle: Debido a que la estructura está determinada por la divergencia real de las claves y no por prefijos fijos, las inserciones adversarias con prefijos compartidos son absorbidas mediante reestructuración interna (por ejemplo, leaf pushdown, parent pull-up) sin necesariamente aumentar la altura global del árbol.

B. Pruebas Jerárquicas (Optimización de Pruebas)

Hashear directamente $k$ hijos en un nodo compuesto resultaría en un overhead de prueba de $O(k)$. MHOT introduce una construcción Merkle de dos capas:

1. Capa Inter-nodo: Conecta los nodos compuestos.
2. Capa Intra-nodo: Cada nodo compuesto mantiene un árbol Merkle binario interno sobre sus $k$ hijos.

• Resultado: Probar la membresía de un hijo requiere solo $O(\log k)$ hashes de hermanos del árbol interno, reduciendo el tamaño de la prueba de una dependencia lineal en el fanout a una dependencia logarítmica. Esto rompe la dependencia lineal del tamaño de la prueba respecto al span.

C. Persistencia Basada en Contenido

Para soportar el compromiso del estado de blockchain, MHOT modifica el diseño original de HOT en memoria:

• Identificadores Deterministas: Los nodos se identifican mediante el hash de su contenido serializado (direccionamiento por contenido), lo que garantiza la determinación estructural (conjuntos de claves idénticos producen árboles idénticos) y la minimización de la confianza.
• Copy-on-Write (CoW): Las modificaciones crean nuevos nodos, invalidando los hashes de los ancestros, lo cual es consistente con la semántica de estado de blockchain.

D. Pipeline de Compromiso por Lotes (Batched Commit Pipeline)

Para manejar el costo computacional de rehashear las rutas:

• Hashing Diferido: Los cálculos de hash se difieren hasta el compromiso del bloque. Los nodos utilizan IDs temporales durante la fase de transacción.
• Paralelismo Estratificado por Altura: Al momento del compromiso, los nodos se finalizan en lotes ordenados por altura (de las hojas hacia la raíz). Dado que los nodos en la misma altura no tienen dependencias de datos, los cálculos de hash pueden paralelizarse eficientemente.
• Diseño Amigable con LSM-Trees: Las claves de almacenamiento están prefijadas por la versión del bloque y la altura, permitiendo escrituras secuenciales por lotes y una compactación eficiente.

3. Contribuciones Clave

1. Identificación del Acoplamiento Span–Proof: El artículo identifica el acoplamiento exponencial entre el span y el fanout en los tries basados en prefijos como la causa raíz de la incapacidad de garantizar simultáneamente una altura máxima acotada y pruebas compactas.
2. Instanciación de MHOT: Adapta HOT para el uso en blockchain, proporcionando una ADS optimizada en altura que resiste distribuciones de claves adversarias mediante el seguimiento de bits discriminativos y nodos compuestos de alto fanout, utilizando únicamente compromisos de hash estándar.
3. Pruebas Jerárquicas: Una novedosa construcción Merkle de dos capas que reduce el overhead de prueba por nodo de $O(k)$ a $O(\log k)$, permitiendo pruebas compactas incluso con un alto fanout.
4. HOT Persistente: Resuelve el problema abierto del despliegue en disco para HOT mediante la introducción de indexación direccionable por contenido y un pipeline de compromiso paralelo.
5. Evaluación Exhaustiva: Benchmarks de MHOT frente a MPT, RainBlock y LVMT bajo cargas de trabajo de la red principal de Ethereum.

4. Resultados Experimentales

Evaluado con cargas de trabajo de la red principal de Ethereum (bloques 13.5M–13.51M) y conjuntos de datos sintéticos:

• Throughput (Rendimiento): MHOT logra hasta un 9× mayor rendimiento de escritura que MPT (260k ops/s vs. 29k ops/s con 100k claves) y supera significativamente a LVMT y RainBlock.
• Amplificación de Escritura: MHOT reduce la amplificación de escritura en un 4× comparado con MPT (0.9–1.6 vs. 2.7–4.8) debido al vaciado por lotes y la reducción de la profundidad del árbol.
• Tamaño de Prueba: Las pruebas de MHOT son 2× más pequeñas que las de MPT (1.1–1.4 KB vs. 2.3–2.9 KB) debido a su estructura de prueba jerárquica.
• Resistencia al Ataque Nurgle: Bajo un escenario de ataque de peor caso donde un adversario controla todo el presupuesto de gas de un bloque (aprox. 15,000 inserciones):
  • MPT: 99.97% de tasa de éxito en el aumento de las profundidades de las claves objetivo.
  • MHOT: 0% de tasa de éxito. La estructura absorbe las colisiones mediante reestructuración interna sin propagar aumentos de profundidad.
• Latencia de Verificación: La verificación de MHOT opera en microsegundos (comparable a MPT), mientras que LVMT (que depende de emparejamientos KZG) incurre en latencias de milisegundos (3–4 órdenes de magnitud más lento).

5. Significado y Reivindicaciones

El artículo argumenta que la optimalidad de la altura, en lugar de la introducción de nuevos primitivos criptográficos, es la abstracción clave para un compromiso de estado de blockchain escalable y resistente a ataques.

• Soluciones Estructurales vs. Criptográficas: MHOT demuestra que los compromisos entre la altura del árbol, el tamaño de la prueba y la resistencia al ataque pueden resolverse estructuralmente mediante la indexación de bits discriminativos, evitando las suposiciones de confianza y los altos costos de verificación de los esquemas de compromiso vectorial (Verkle, LVMT).
• Desplegabilidad Inmediata: Al depender únicamente de funciones hash estándar (Keccak-256 o Blake3) y principios de autenticación Merkle existentes, MHOT ofrece un camino para mejorar el rendimiento y la seguridad sin requerir hard forks para ceremonias de configuración de confianza o cambios en la verificación algebraica.
• Resiliencia: Los resultados sugieren que optimizar la altura y la adaptabilidad de la estructura de datos es suficiente para neutralizar el vector de ataque Nurgle, que anteriormente parecía requerir contramedidas económicas o criptográficas.

Los autores concluyen que el diseño cuidadoso de la estructura de datos puede mejorar fundamentalmente la escalabilidad y la robustez del compromiso de estado en blockchain, ofreciendo una alternativa práctica al estándar actual de MPT.