Arbre de Merkle

Un eixemple d'arbre de Merkle binario. Els hashes 0-0 i 0-1 són els valors dels hash dels blocs de senyes 1 i 2 respectivament, i 0 és el hash de la concatenació de hashes 0-0 i 0-1.

Un arbre hash de Merkle (en inglés: Merkle hash tree) o arbre de Merkle o arbre hash és una estructura de senyes en arbre, binario o no, en el que cada nodo que no és un full està etiquetat en el hash de la concatenació de les etiquetes o valors (per a nodos full) dels seus nodos fill. Són una generalisació de les llistes hash i les cadenes hash.

Permet que gran número de senyes separades puguen ser lligats a un únic valor de hash, el hash del nodo raïl de l'arbre. D'esta forma proporciona un método de verificació segura i eficient dels continguts de grans estructures de senyes. En les seues aplicacions pràctiques, normalment el hash del nodo raïl va firmat per a assegurar la seua integritat i que la verificació siga totalment fiable. La demostració de que un nodo full és part d'un arbre hash dau requerix una cantitat de senyes proporcional al logaritmo del número de nodos de l'arbre.

Va ser patentat en 1979 per Ralph Merkle.

Aplicacions

Actualment el major us dels arbres de Merkle és fer segurs els blocs de senyes rebudes d'atres parells en les rets peer-to-peer, assegurar que estos són rebuts sense danys i sense ser alterats. Ademés permeten que les senyes d'un bloc puguen ser entregats per parts: un nodo pot descarregar solament la capçalera d'un bloc (arbre) des d'una font, i una atra chicoteta part de l'arbre rellevant per a ell, des d'una atra font, i encara assegurar que les senyes són correctes. La raó per lo que açò funciona és perque els hashes es propaguen cap a dalt: si un usuari malintencionat intenta fer un canvi en una transacció falsa en la part inferior de l'arbre de Merkle, este canvi provocarà un canvi en el nodo superior i seguidament un atre canvi en el nodo per damunt d'est, fins que finalment, es produïxca un canvi en la raïl de l'arbre i per tant en el hash del bloc, fent que el protocol tinga que registrar-ho com un bloc completament diferent (i casi en tota seguritat en una prova de treball inválida).

Referències

• Mastering Bitcoin. Unlocking Digital Cryptocurrencies. Andreas M. Antonopoulos. O'Reilly 2014
• Bitcoins. ¿Revolució o Història? Jaime Sánchez de Diego Martínez-Cabrera. Universitat Pontifícia de Comillas. Juny 2014
• Estructures de Senyes Autenticadas per a gestionar. Senyes de Revocació en VANETs. Carlos Gañán et al.