Un árbol de Merkle organiza hashes de datos en una estructura cuyo hash superior, la raíz de Merkle, resume el conjunto comprometido. Cada nodo padre se calcula a partir de sus hijos según reglas definidas. Cambiar una hoja suele modificar los hashes de su ruta hasta la raíz.
Verificar un elemento
Una prueba de inclusión aporta los hashes vecinos necesarios para recalcular esa ruta, sin entregar todos los elementos. En un árbol binario balanceado con ocho hojas, probar una hoja suele requerir tres hashes hermanos y su información de posición. Quien verifica también necesita el elemento o su hash y una raíz confiable.
Uso en Bitcoin
Bitcoin compromete los identificadores de transacción mediante una raíz de Merkle en cada encabezado de bloque. La construcción define el orden, el hash por pares y la duplicación cuando un nivel tiene un número impar de entradas. Otros sistemas pueden usar estructuras y codificaciones diferentes.
Qué demuestra la prueba
Una prueba válida muestra que un elemento pertenece al conjunto representado por la raíz de referencia, bajo los supuestos de seguridad del hash. No demuestra por sí sola la validez de la transacción, su estado actual no gastado ni la finalidad de la cadena. La raíz tampoco revela todos los datos originales: deben seguir disponibles por otra vía para una revisión completa.