tw-rl

[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 --- https://fr.wikipedia.org/wiki/Arbre_de_Merkle https://en.wikipedia.org/wiki/Ralph_Merkle (plus complet que la version en français)

https://www.gemini.com/cryptopedia/merkle-tree-blockchain-merkle-root#section-merkle-roots-in-blockchain-why https://www.investopedia.com/terms/m/merkle-root-cryptocurrency.asp https://medium.com/blockchain-stories/merkle-tree-a-beginners-guide-5c53a7defeb9 https://techjd.medium.com/build-a-whitelisted-mint-in-react-using-merkletreejs-7b165ac9f9d7 https://medium.com/@ItsCuzzo/using-merkle-trees-for-nft-whitelists-523b58ada3f9 https://medium.com/coinmonks/merkle-trees-concepts-and-use-cases-5da873702318 https://www.webopedia.com/definitions/merkle-proof/ https://www.geeksforgeeks.org/blockchain-merkle-trees/

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

- Thread incroyable sur de l'optimisation de gas autour des preuves de Merkle (merci @cleminso) : --- SOURCES ---