Merkle Tree o Árbol de Merkle en PHP

Merkle Tree o Árbol de Merkle en PHP

En esta entrada voy a hablar de una implementación en PHP de un «Merkle Tree«, un árbol de Merkle, una implementación en árbol binario para conseguir un hash de un conjunto de datos. En anteriores artículos ya hablé de (o usé) árboles binarios, como en el artículo sobre la cola de prioridad en PHP (un buen ejemplo de árbol binario).

Esta estructura de datos fue originalmente propuesta en 1979 por Ralph Merkle, y de ahí su nombre.

Puedes ver la implementación de este Merkle Tree en mi github.

Usos más destacados

Los árboles de Merkle tienen una finalidad básica: obtener un hash, llamado Merkle Root, que identifique clara y unívocamente el conjunto original de datos. Por esta razón su uso está muy extendido en la comunicación entre ordenadores. A modo de ejemplo, cuando se descarga una gran cantidad de ficheros de un servidor podemos «calcular» si su contenido ha sido modificado/dañado comprobando que el Merkle Root original coincide con el que hemos calculado durante la descarga.

En el mundo de las criptomonedas también se aplica el algoritmo de Merkle Tree para comprobar que las transacciones no han sido modificadas. La primera criptomoneda del mundo, Bitcoin, incluye un Merkle Root en cada bloque.

Funcionamiento de un Merkle Tree

El funcionamiento de un árbol de Merkle es bastante simple. Se trata, en primer lugar, de asignar un hash a cada elemento del conjunto de datos. Cuando todos los datos estás hasheados, hay que concatenar esos mismo hashes y volver a aplicar la misma función de hash por parejas. Esta operación se repite hasta que sólo queda un nodo que, obviamente, contiene la raíz de Merkle.

Keep reading →