Merkle Trees: la estructura detrás de Git, Bitcoin e IPFS

Cada vez que ejecutás git pull, clonás un repositorio de GitHub o un wallet liviano de Bitcoin verifica una transacción, una estructura de datos inventada en 1979 está trabajando en silencio. Se llama Merkle Tree, y es la pieza fundamental que permite verificar la integridad de datos enormes en milisegundos. Hoy la usan Git, Bitcoin, IPFS, Cassandra, DynamoDB, ZFS y casi cualquier sistema distribuido serio.

Qué es un Merkle Tree

Un Merkle Tree (o árbol de hashes) es un árbol binario donde cada nodo hoja contiene el hash criptográfico de un bloque de datos, y cada nodo interno contiene el hash de la concatenación de sus dos hijos. La raíz es un único hash que representa criptográficamente todo el contenido del árbol.

El concepto fue patentado por Ralph Merkle en 1979. Su poder está en una propiedad simple: si cualquier byte de los datos originales cambia, la cascada de hashes hace que la raíz también cambie. Resultado: podés verificar la integridad de gigabytes de información comparando apenas 32 bytes.

Cómo se construye

Supongamos que tenemos cuatro bloques de datos: A, B, C y D. La construcción funciona en niveles, de abajo hacia arriba:

• Paso 1 — calcular el hash de cada bloque: H(A), H(B), H(C), H(D). Esas son las hojas.
• Paso 2 — agrupar de a pares y hashear las concatenaciones: H(H(A)+H(B)) y H(H(C)+H(D)).
• Paso 3 — repetir hasta que quede un único hash: la raíz, también llamada Merkle root.

La función de hash suele ser SHA-256 (Bitcoin, IPFS, Git moderno) o SHA-1 (Git histórico). Cada hash tiene tamaño fijo, sin importar cuántos datos representa: un árbol con 4 bloques o con 4 millones produce una raíz de los mismos 32 bytes.

Implementación en Python

Construir un Merkle Tree es sorprendentemente simple. Acá va una implementación funcional en menos de 20 líneas:

import hashlib

def sha256(data: str) -> str:
    return hashlib.sha256(data.encode()).hexdigest()

def merkle_root(blocks):
    # Nivel 0: hashear cada bloque (las hojas)
    layer = [sha256(b) for b in blocks]

    # Subir nivel por nivel hasta que quede un solo hash
    while len(layer) > 1:
        if len(layer) % 2 == 1:
            layer.append(layer[-1])  # duplicar el ultimo si es impar
        layer = [sha256(layer[i] + layer[i+1])
                 for i in range(0, len(layer), 2)]

    return layer[0]

bloques = ['Alice paga 1 BTC', 'Bob paga 0.5 BTC',
           'Carol paga 2 BTC', 'Dave paga 0.1 BTC']
print(merkle_root(bloques))
# -> un unico hash de 64 caracteres que representa TODO

Si cambiás un solo carácter en cualquier bloque (por ejemplo, '1 BTC' por '10 BTC'), la raíz resultante será completamente distinta. Esa es la propiedad de cascada que hace imposible alterar los datos sin que se note.

Pruebas de inclusión: la magia real

La verdadera utilidad aparece cuando querés demostrar que un dato específico está en el árbol sin descargar el árbol completo. Eso se llama Merkle proof o prueba de inclusión.

Para probar que el bloque B existe en un árbol con 1.000.000 de bloques, no necesitás el millón entero: solo log₂(1.000.000) ≈ 20 hashes. El verificador recibe la cadena de hermanos desde la hoja hasta la raíz, reconstruye el camino y compara con la raíz pública. Si coincide, la prueba es válida; si no, los datos fueron alterados.

Esto es exactamente lo que permite a un wallet ligero de Bitcoin (modo SPV) verificar que tu transacción está en un bloque sin descargar los cientos de gigabytes de toda la blockchain.

Cómo lo usa Git

Git es, en esencia, un sistema de archivos basado en Merkle Trees. Cada commit apunta a un objeto 'tree' que representa el snapshot del directorio en ese momento. Ese tree contiene los hashes SHA-1 (o SHA-256 en repos modernos) de cada archivo y subdirectorio. Si un solo byte cambia en cualquier archivo, el hash sube por la cadena hasta modificar el hash del commit.

Por eso la documentación de Git Internals describe a Git como un 'content-addressable filesystem': los archivos se direccionan por su hash, no por su nombre. Y por eso reescribir un commit antiguo invalida automáticamente todos los commits posteriores: cada commit incluye el hash del padre.

Cómo lo usa Bitcoin

Cada bloque de Bitcoin contiene cientos o miles de transacciones. En vez de meterlas todas en el header del bloque, Bitcoin construye un Merkle Tree con todas las transacciones y guarda solo la raíz (32 bytes) en el header del bloque.

Eso le da dos cosas a la red: bloques pequeños y rápidos de propagar entre nodos, y la posibilidad de que un cliente liviano verifique la inclusión de una transacción específica pidiendo apenas el camino de hashes hasta la raíz. Con 20-25 hashes alcanza para validar una transacción dentro de un bloque con millones de operaciones.

Cómo lo usa IPFS

IPFS lleva el concepto un paso más allá con los Merkle DAGs (grafos acíclicos dirigidos basados en Merkle). Cada archivo se trocea en bloques, cada bloque tiene un hash y los hashes se enlazan formando un grafo. El identificador del archivo en IPFS, el famoso CID, es la raíz de ese DAG.

Como dos archivos idénticos producen exactamente el mismo CID, IPFS deduplica de forma automática: subir la misma película mil veces ocupa el espacio de una sola. Y como el identificador depende del contenido y no de la ubicación, los datos pueden moverse entre nodos sin cambiar la dirección que los referencia.

Otros usos en producción

• Cassandra y DynamoDB — usan Merkle Trees para detectar diferencias entre réplicas durante el anti-entropy repair. Solo se transfieren los segmentos cuyos hashes difieren.
• Certificate Transparency — Google publica todos los certificados SSL emitidos en un árbol de Merkle público y append-only. Cualquiera puede auditar que un certificado realmente fue emitido.
• BitTorrent v2 — desde 2020 reemplazó SHA-1 por SHA-256 dentro de Merkle Trees, lo que permite verificar piezas individuales sin descargar el archivo entero.
• ZFS y Btrfs — sistemas de archivos modernos que usan árboles de hashes para detectar y reparar la corrupción silenciosa de bits en discos.

Por qué importa

Los Merkle Trees resuelven uno de los problemas más viejos de la computación distribuida: cómo confiar en datos que no controlás. Con un solo hash de 32 bytes podés verificar que un terabyte de información no fue alterado, y con log(n) hashes adicionales podés demostrar la inclusión de cualquier dato puntual.

Esa eficiencia matemática es la razón por la que una idea de 1979 sigue siendo, casi medio siglo después, la columna vertebral invisible de Git, las criptomonedas, los sistemas de archivos distribuidos y la web descentralizada que apenas está empezando.