Árbol de Merkle y wallets ligeras

Un hash que resume miles

En el capítulo 5 dijimos que la cabecera compromete todas las transacciones a través de la raíz de Merkle, y lo dejamos ahí. La forma obvia de conseguirlo sería hashear todas las transacciones seguidas: un hash, y cualquier cambio lo altera. Funciona… pero para comprobar que una transacción está dentro habría que tener todas.

El árbol de Merkle resume igual de bien y arregla eso. Se construye por niveles:

1. Se calcula el hash de cada transacción: las hojas.
2. Se emparejan de dos en dos y se hashea cada pareja. Si sobra una, se empareja consigo misma.
3. Se repite con los resultados, nivel a nivel, hasta que queda un solo hash: la raíz.

Con 8 transacciones hay 3 niveles; con 4.000, doce. La raíz va en la cabecera, así que cambiar cualquier transacción cambia una hoja, todos los hashes por encima de ella, la raíz, la cabecera y el hash del bloque.

La prueba: un camino, no un bloque

Ahora lo importante. Para demostrar que una hoja está en el árbol no hacen falta las demás hojas: basta con el hermano de cada nodo del camino hasta la raíz. Quien verifica hashea la hoja con su hermano, el resultado con el siguiente hermano, y así hasta arriba; si el hash final es la raíz de la cabecera, la transacción está en el bloque. Elige una transacción y mira qué se ilumina:

Mueve el número de transacciones y fíjate en cuántos hashes tiene la prueba: crece con el logaritmo. Con el doble de transacciones, un hash más. Un bloque de Bitcoin con 3.000 transacciones ocupa alrededor de megabyte y medio; la prueba de que una de ellas está dentro son 12 hashes, 384 bytes.

Y prueba a alterar la transacción: no hay forma de fabricar una prueba para algo que no está en el bloque, porque eso exigiría encontrar hashes que colisionen (capítulo 2).

Wallets ligeras: SPV

Con esto se puede construir una wallet que no descarga la cadena. Es lo que el documento original de Bitcoin llama verificación simplificada de pagos (SPV), y funciona así:

1. La wallet descarga solo las cabeceras: 80 bytes por bloque. Toda la historia de Bitcoin cabe en unas decenas de megas.
2. Comprueba que las cabeceras encadenan y que cada una lleva su prueba de trabajo (lo que hace handleHeaders del capítulo 8). Con eso sabe que tiene la cadena con más trabajo… sin haber visto una sola transacción.
3. Cuando alguien le dice “te han pagado en el bloque 46”, pide a un nodo completo la prueba de Merkle de esa transacción y la verifica contra la raíz de la cabecera 46, que ya tiene.
4. Y cuenta los bloques que hay encima para saber cuántas confirmaciones lleva.

Es exactamente lo que hace bin/cli proof en xavicoin: pide la prueba al nodo pero la verifica en el cliente, porque el nodo podría mentir. En la prueba real, dos hashes bastaron para demostrar que un pago estaba en el bloque 46:

$ bin/cli proof b6be90a1…
{
  "block": "…", "height": 46,
  "merkleroot": "…", "leaf": "…", "index": 1,
  "siblings": ["…", "…"]
}
prueba verificada: 2 hashes bastan para demostrar que la transacción está en el bloque 46

Lo que una wallet ligera no puede saber

SPV verifica que una transacción está en un bloque con trabajo encima. No verifica que la transacción sea válida: no tiene el conjunto de monedas sin gastar, así que no puede comprobar que las entradas existían ni que las firmas son buenas. Se apoya en que los mineros no incluirían un pago inválido en un bloque que les costó tanto minar, y en que los nodos completos lo rechazarían.

Es una confianza razonable, pero es confianza. Por eso el sistema necesita que haya nodos completos que validen todo, y por eso xavicoin es, ante todo, un nodo completo.

En el código

La raíz, la prueba y la verificación son tres funciones cortas. La verificación es la que ejecuta la wallet ligera, y no tiene nada de especial: un bucle de hashes en el que los bits del índice dicen si la hoja iba a la izquierda o a la derecha en cada nivel.

// internal/core/merkle.go

// VerifyMerkleProof recalcula la raíz desde una hoja y su prueba. El bit i
// de index indica si en el nivel i la hoja queda a la derecha.
func VerifyMerkleProof(leaf crypto.Hash, index int, proof []crypto.Hash, root crypto.Hash) bool {
	if index < 0 || index>>len(proof) != 0 {
		return false
	}
	current := leaf
	for _, sibling := range proof {
		if index&1 == 1 {
			current = hashPair(sibling, current)
		} else {
			current = hashPair(current, sibling)
		}
		index >>= 1
	}
	return current == root
}

Una trampa histórica

Ese “si sobra una hoja, se empareja consigo misma” tiene una consecuencia que a Bitcoin le costó un aviso de seguridad en 2012: la lista [a, b, c] y la lista [a, b, c, c] dan la misma raíz. Un atacante podía enviar un bloque con la última transacción duplicada: inválido (gasta dos veces lo mismo), pero con el hash de un bloque válido. Un nodo que marcase ese hash como malo rechazaría después el bloque bueno. xavicoin detecta la mutación al calcular la raíz y, si la ve, rechaza el bloque sin vetar su hash.

Fin del recorrido

Diez capítulos, y cada pieza existe por una razón que ya conoces:

• Un hash identifica datos y hace imposible retocarlos sin que se note.
• Una firma demuestra quién autoriza un gasto sin revelar el secreto.
• Una transacción destruye monedas y crea otras, y cada nodo comprueba que no crea dinero.
• Un bloque ordena transacciones y apunta al anterior, de modo que el pasado es caro de reescribir.
• La prueba de trabajo decide quién propone el siguiente bloque a base de electricidad, y la dificultad mantiene el ritmo.
• La coinbase paga a quien mina, con un calendario fijado de antemano.
• La red propaga todo de vecino en vecino, sin servidor.
• La regla del más trabajo resuelve los desacuerdos sin que nadie mande.
• Y el árbol de Merkle permite verificar pagos sin descargar la cadena.

Todo lo que has leído está implementado, con tests, en unas 5.400 líneas de Go que puedes leer entera y ejecutar en tu portátil. Si quieres seguir, el mejor siguiente paso es ese: clonar xavicoin, arrancar dos nodos, y romper algo a propósito para ver cómo lo rechazan.