Árboles de Merkle

Curiosidad

1. ¿Cómo puede un único valor de hash certificar la inclusión de cuatro mil transacciones distintas?
2. ¿Por qué eligió Satoshi emparejar la última entrada solitaria con ella misma, y cuál fue el costo de esa decisión?
3. ¿Qué vulnerabilidad específica introdujo la regla de emparejamiento duplicado en la implementación inicial de Bitcoin?

Explorar

1. Ralph Merkle presentó una patente para el árbol hash binario en 1979 (concedida en 1982), una estructura de datos diseñada para resumir eficientemente grandes conjuntos de datos. En Bitcoin, esta arquitectura reduce miles de identificadores de transacciones a un único valor de 32 bytes conocido como raíz Merkle. Esta raíz se integra directamente en el encabezado del bloque de 80 bytes, creando un compromiso criptográfico inmutable para cada transacción dentro de ese bloque específico.
2. La construcción avanza de forma recursiva de abajo hacia arriba. Los IDs de las transacciones se concatenan en pares y se procesan mediante un doble hash SHA-256 para generar nodos padre. Este emparejamiento continúa nivel por nivel hasta que queda un único hash raíz. Si algún nivel contiene un número impar de entradas, la entrada final se empareja consigo misma para mantener la estructura binaria, asegurando así que el árbol esté equilibrado en cada etapa.
3. La naturaleza logarítmica de esta estructura permite una verificación de pagos simplificada (SPV). Un cliente ligero no descarga los bloques completos; en su lugar, solicita una rama Merkle a un nodo completo. Esta rama consta únicamente de los hashes de los nodos hermanos a lo largo del camino desde una transacción específica hasta la raíz. Para un bloque con 4,000 transacciones, esta prueba requiere aproximadamente doce valores de hash, una fracción del tamaño total de los datos.
4. Al combinar su propio hash de transacción con estos hashes proporcionados, un cliente ligero vuelve a calcular la raíz Merkle y la compara con el valor que se encuentra en el encabezado del bloque descargado. Si coinciden, se verifica criptográficamente su inclusión sin necesidad de almacenar toda la cadena. Este mecanismo permite que las billeteras móviles funcionen de manera segura en dispositivos con capacidad de almacenamiento y procesamiento limitados.
5. Segregated Witness (SegWit), activado en agosto de 2017, introdujo una segunda estructura de árbol Merkle. Mientras que el árbol original registra los IDs de las transacciones, el árbol de “testigos” registra los IDs de las transacciones de testigo. La raíz de este segundo árbol no se almacena en el encabezado; se registra en una salida OP_RETURN de la transacción coinbase, que los nodos antiguos tratan como datos ordinarios, preservando así la compatibilidad.
6. La regla de emparejamiento consigo misma ocultaba un defecto (CVE-2012-2459). Dado que la última entrada solitaria se empareja consigo misma, una lista de transacciones que termina con un par duplicado genera la misma raíz Merkle que la lista sin el duplicado. Un atacante podría retransmitir esa variante malformada de un bloque válido; los nodos que la rechazaran podrían marcar como inválido el hash del bloque auténtico y desincronizarse con la red. La corrección de 2012 hace que los nodos reconozcan este patrón en lugar de cachear el bloque como defectuoso.

Datos clave

Ejercicio nueve, seis, tres, uno

Verificación de hechos

Fechas, cifras y afirmaciones verificadas con las fuentes publicadas que se enumeran a continuación.

• R. Merkle, US Patent 4,309,569 (1982)
• Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System (2008), sections 7-8
• BIP 141: Segregated Witness (Consensus layer)
• A. M. Antonopoulos & D. A. Harding, Mastering Bitcoin, 3rd ed. (2023), ch. 11