[Thread] Les arbres de Merkle Dans ce thread seront détaillés les éléments suivants : l'arbre (tree), la racine (root), les branches ou noeud (branch, inner node, et parfois inode), les feuilles (leaf/leaves) et les preuves (proof) de Merkle.

Je vous présenterai également un exemple concret que vous pourrez utiliser pour créer votre propres whitelist (ou blockchain si vous en avez le courage :D ) en utilisant Javascript et la librairie merkletreejs.

--- CULTURE --- Revenons un peu aux fondamentaux dans ce thread, c'est légèrement technique mais compréhensible par tous et toutes. Vous en avez forcément entendu parler sur un medium, Youtube, dans vos cours ou bien lors d'une discussion.

Parfois appelé arbre de hachage, dont le créateur est Ralph Merkle en 1979 (il est toujours vivant), qui avait auparavant co-inventé le "Merkle–Hellman knapsack cryptosystem".

Aujourd'hui considéré comme non sécurisé ainsi que le "Merkle–Damgård hash function", son œuvre la plus célèbre reste donc l'arbre de Merkle très largement répondu et s'imposant comme un standard.

A la fin du thread je donne les sources utilisées afin décrire ce thread, ce qui vous amènera à creuser le sujet si vous souhaitez aller plus loin. --- CULTURE ---

--- BITCOIN --- Le monde de la cryptomonnaie et particulièrement le projet Bitcoin ne saurait vivre sans. C'est un des grands principes utilisé de manière générale en cryptographie.

Il aurait été possible de base de s'en passer, par exemple au lieu d'utiliser l'arbre de Merkle, tous les TXID pourraient être hachés par lots.

Cependant, si vous souhaitez le faire pour valider une transaction particulière, vous devez connaître tous les id de transaction du bloc associé et c'est là tout le problème.

Cela nécessite une grande quantité de mémoire pour stocker et envoyer sur le réseau. L'arbre de Merkle vous permet d'utiliser la racine de Merkle afin de vérifier l'id de transaction sans connaître tous les id de transaction du bloc.

Vous l'aurez compris c'est là toute la force et la subtilité du principe. Il en découle 2 caractéristiques intéressantes : - réduction de la mémoire (place sur le disque) - réduction du temps de traitement (Je vous laisse creuser par vous-même concernant les performances)

Cela fait partie intégrante de notre blockchain préférée. --- BITCOIN ---

--- SCHEMA --- Un schéma issu de Wikipédia donne une représentation d'un Arbre de Merkle

Un schéma vaut mille mots, vous retrouvez en légende les notions présentées plus haut, ici les "Data Nodes" sont les données en elles-mêmes (une transaction, un smart contract, etc...). --- SCHEMA ---

--- EXEMPLE --- Passons par l'exemple : Je voudrais vérifier si mon adresse est bien en liste blanche (whitelist). Pour cela j'ai utilisé pour l'exemple Javascript, en utilisant la librairie merkletreejs côté Javascript.

Vous pouvez utiliser ce que bon vous semble, là c'est pour l'exemple. A l'origine j'avais déployé un smart contract (NFT) en utilisant Solidity sur Ethereum qui est un cas pratique mais pour l'exemple j'ai simplifié au maximum.

On va retrouver les principes expliqués plus haut, à savoir le Merkle Tree, Markle Root, Merkle Node, Merkle Leaf et les Merkle Proof et la donnée (ici les adresses)

Tout d'abord les adresses sur la liste blanche. La première adresse (la mienne) surlignée en jaune est donc sur la liste blanche.

Les différents éléments de l'

La racine

Les nœuds ou branches

les feuilles de l'arbre

Le test ici réside dans le fait de déterminer si les adresses sont sur la liste blanche ou non.

En imprimant le résultat on voir que la première adresse retourne une preuve de Merkle tandis que la seconde non, savez-vous pourquoi ?

Parce qu'elle n'est pas dans la liste des adresses sur liste blanche, tout simplement ! Il ne reste plus qu'à vérifier dans l'arbre avec la commande suivante ici (en Javascript) tree.verify(proof, leaf, root) qui donne "true" pour le premier et "false" pour le second.

En regardant un peu plus loin on remarque quelque chose qui a été expliqué plus haut, c'est la preuve nécessaire et suffisante qui permet de valider l'adresse :

Ici l'adresse "0x28f794C0F4D685CF7a9Faa37AAc6d2150f2b568d" dont le hash (il y a un peu plus qu'un hash en réalité) est "fbe9...c491" entourée en bleu, c'est la preuve représenté dans le tweet au dessus ci vous regardez bien (éléments en jaune) :

Pour aller plus loin dans la technique Si je passe cette preuve à mon smart contract, il me retournera une erreur (si j'ai bien géré cela) car je ne suis pas whitelist (je l'utilise à nouveau, la liste blanche c'est la traduction française). En Solidity vous trouverez ceci :

L'adresse (qui est la feuille ici) sera déterminée par l'adresse de l'appelant (celui ou celle qui mint), on vérifie ensuite si l'adresse est bien incluse dans la liste des adresses autorisées en utilisant la racine, la preuve et la feuille (l'adresse).

On ne passe en paramètre que la preuve car la racine est stockée sur le smart contract, c'est aussi un aspect sécuritaire (on ne fournit que ce qui est nécessaire au calcul). --- EXEMPLE ---

--- MOT DE LA FIN --- Ca fait un moment que j'ai commencé à écrire ce thread, je l'ai fini ce soir car on m'a pas mal sollicité pour que je le sorte, à ma manière, un peu moins léger que d'habitude.

Je vous remercie de m'avoir lu jusqu'ici. Ce fut un peu technique sur la fin mais il est difficile de vulgariser une notion aussi essentielle du cœur de l'écosystème blockchain/crypto. --- MOT DE LA FIN ---

--- SOURCES --- fr.wikipedia.org/wiki/Arbre_de_… en.wikipedia.org/wiki/Ralph_Mer… (plus complet que la version en français)

gemini.com/cryptopedia/me… investopedia.com/terms/m/merkle… medium.com/blockchain-sto… techjd.medium.com/build-a-whitel… medium.com/@ItsCuzzo/usin… medium.com/coinmonks/merk… webopedia.com/definitions/me… geeksforgeeks.org/blockchain-mer…

- bon résumé sur l'utilité de l'arbre de Merkle dans la blockchain bitcoin : cryptoast.fr/arbres-merkle-… : - Pour les devs : soliditydeveloper.com/merkle-tree merkletree.js.org

- Thread incroyable sur de l'optimisation de gas autour des preuves de Merkle (merci @ιπ$øʍπιακ✨🐺(🌸, 🌿)) : twitter.com/krzKaczor/stat… --- SOURCES ---

DISCLAIMER : J'ai eu un souci lors de la mise en page j'ai dû faire sauter un ou deux tweets assez importants

Chaque (nœud) feuille est un hash de données transactionnelles où un nœud (ou branche) non feuille est un hash de ses hashs précédents soit un hash de la somme des hash sous ce nœud.

Ici on voit bien que Hash 0est un hash de la somme des hash 0-0 + hash 0-1 soit : Hash 0 = Hash (hash 0-0 + hash 0-1) (source Wikipedia citée plus haut)

Les arbres de Merkle sont dans un arbre binaire ce qui signifie qu'il faut donc un nombre pair de nœuds feuilles, si ce n'est pas le cas, le dernier hachage sera dupliqué une fois pour créer un nombre pair de nœuds feuilles. (source coinmonks citée plus haut)

Ici on voit que le Hash 5 est dupliquée pour palier au nombre impair de nœuds feuilles :

Dernier chose. Parfois on lit feuille ou noeud feuille, noeud sans enfant, c'est en fait la même chose, et sont les données hachées. Juste au dessous il y a les données elles-mêmes (dernier niveau).

Vous l'aurez donc compris l'arbre de Merkle est utilisé dans le monde de la cryptographie et donc sur toutes nos blockchains préférées (ou presque), pour sa robustesse, sa vitesse d'exécution et sa quantité de mémoire utilisée.

J'en ai fini avec les arbres de Merkle, j'aurai pu en ajouter bien plus mais un Medium serait plus adapté dans ce cas là (je dois être à pas loin de 40 tweets). Sur ce bon vent !