Nivel 5

Árbol de Merkle

Resumir miles de transacciones en 32 bytes. La estructura que hace posible la verificación ligera.

El concepto

Un árbol de Merkle es una estructura de datos que permite resumir una lista de elementos en un solo hash (la Merkle root) de forma que:

  1. Cualquier cambio en cualquier elemento cambia la root
  2. Puedes probar que un elemento está en la lista proporcionando solo O(log n) hashes

En Bitcoin, los elementos son los txids de las transacciones del bloque.

Construcción del árbol

Dado un bloque con transacciones T1, T2, T3, T4: Merkle Root / \ H(AB) H(CD) / \ / \ H(A) H(B) H(C) H(D) | | | | T1 T2 T3 T4

Paso a paso:

  1. Nivel 0 (hojas): Hashear cada transacción
  • H(A) = SHA256(SHA256(T1))
  • H(B) = SHA256(SHA256(T2))
  • H(C) = SHA256(SHA256(T3))
  • H(D) = SHA256(SHA256(T4))
  1. Nivel 1: Concatenar pares y hashear
  • H(AB) = SHA256(SHA256(H(A) || H(B)))
  • H(CD) = SHA256(SHA256(H(C) || H(D)))
  1. Nivel 2 (root): Concatenar y hashear
  • Root = SHA256(SHA256(H(AB) || H(CD)))

Bitcoin usa doble SHA256 en cada paso, igual que en otras partes del protocolo.

Número impar de elementos

Si hay un número impar de elementos en algún nivel, el último se duplica:

Con 3 transacciones (T1, T2, T3): Merkle Root / \ H(AB) H(CC) / \ / \ H(A) H(B) H(C) H(C) | | | T1 T2 T3

H(C) se concatena consigo mismo para formar H(CC).

Merkle proof (prueba de inclusión)

Para probar que T3 está en el bloque, no necesitas todas las transacciones. Solo necesitas:

  1. El txid de T3 → H(C)
  2. Su hermano en el árbol → H(D) (o H(C) duplicado si era impar)
  3. El hash del subárbol hermano → H(AB)
  4. La Merkle root (del header del bloque)

Con estos datos, cualquiera puede:

  1. Calcular H(CD) = SHA256(SHA256(H(C) || H(D)))
  2. Calcular Root' = SHA256(SHA256(H(AB) || H(CD)))
  3. Verificar que Root' == Merkle root del bloque

Si coincide, T3 está definitivamente en el bloque.

Eficiencia logarítmica

Para un bloque con n transacciones:

  • La prueba requiere log₂(n) hashes
  • Un bloque con 4096 transacciones solo necesita 12 hashes (~384 bytes) para probar cualquier transacción

Esto hace viable la verificación ligera (SPV) en dispositivos con recursos limitados.

SPV (Simplified Payment Verification)

Los clientes SPV (como muchas wallets móviles) no descargan bloques completos. Solo descargan:

  1. Headers de todos los bloques (80 bytes cada uno)
  2. Merkle proofs de las transacciones que les interesan

Un cliente SPV puede verificar que una transacción está en un bloque válido sin tener todas las transacciones del bloque.

Limitaciones de SPV

SPV confía en que los mineros no incluyen transacciones inválidas. Un full node verifica cada transacción independientemente; un cliente SPV solo verifica la inclusión.

Para máxima seguridad, ejecuta tu propio nodo completo. Pero SPV es un compromiso razonable para muchos casos de uso móvil.

Representación visual

Un bloque con 8 transacciones: Root ┌───────────┴───────────┐ ABCD EFGH ┌──────┴──────┐ ┌──────┴──────┐ AB CD EF GH ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ A B C D E F G H │ │ │ │ │ │ │ │ T1 T2 T3 T4 T5 T6 T7 T8

Para probar T5:

  • Proporcionar: H(F), H(GH), H(ABCD)
  • El verificador calcula: H(EF), H(EFGH), Root
  • Compara con la Merkle root del header

Aplicaciones más allá de Bitcoin

Los árboles de Merkle se usan en muchos sistemas:

  • Git (para verificar integridad de repositorios)
  • Sistemas de archivos distribuidos (IPFS)
  • Bases de datos verificables
  • Otros protocolos blockchain

La idea de resumir datos en un hash raíz con pruebas de inclusión eficientes es fundamental en sistemas distribuidos.