Merkle Roots et Merkle Trees expliqués.

Le Merkle Tree, à ne pas confondre avec çà  …

merkELtree

… est une structure que les programmeurs Bitcoin utilisent tous les jours. Elle vient de son inventeur Ralph Merkle, qui a publié l’algorithme dans cet article en 1979.

merkeltree_explLes transactions bitcoin qui arrivent sans cesse l’une après l’autre sont regroupées a l’intérieur d’un bloc avant d’être enregistrées à jamais dans la blockchain.

Supposons que nous ayons 8 transactions (de T1 à T8). On appelle ces feuilles initiales qui fournissent l’input les feuilles (leaves) de l’arbre de Merkle. Ces transactions  sont traitées  deux à deux de manière récursive :

On fait le hash de  T1 avec T2,   T3 avec T4 ,   T5 avec T6,   T6 avec T8
et on obtient 4 hash (de H1 à H4), qui forment la première branche

On refait le hash de  H1 avec H2  et de  H3 avec H4
et on obtient 2 hash (de K1 à K2),  qui forment la deuxième branche.

On fait le hash final entre K1 et K2 et on obient ainsi le Merkle Root.

Le root est fondamental parce que c’est lui qui assure l’intégrité et la véridicité d’un bloc. N’importe qui peut contrôler  les Merkel Roots d’un bloc. Toutes les dix minutes un nouveau bloc est enregistré dans la blockchain. Il contient l’ensemble des transactions (ventes/achats + mining de nouveaux blocs) survenues dans cet intervalle.

Prenons par exemple le bloc numéro: 392458 et analysons le via le site blockchain.info  On voit que son Merkle Root vaut:

9998e9174144512e0a36865b877d169d6ab3fc5565f8bd4d8e49e6560ac9f1b0

En vérifiant le même bloc sur un autre site qui sonde la blockchain et retourne ses informations, par exemple  blockexplorer, on constate que la racine est strictement la même.

Le bloc de notre exemple contient 2869 transactions. Puisque les hashes de toutes les transactions sont liés entre eux, on ne peut pas changer un seul bit d’une quelconque transaction sans altérer le Merkle Root. La construction pyramidale voulue par le Merkle Tree garantit que le Merkle Root dépend des hashes de toutes les opérations sous-jacentes.

C’est pour cette raison aussi que la blockchain est infalsifiable et qu’on peut lui faire confiance sans avoir recours à une tierce partie pour en assurer le bon fonctionnement.

Laisser un commentaire