Un arbre Merkle est un arbre binaire qui permet de vérifier de manière efficace et sécurisée le contenu de grandes structures de données. Le concept de cet arbre a été proposé et breveté en 1982 par Ralph Merkle, un cryptographe américain. La longueur du hachage reste la même quelle que soit la quantité de données d'entrée. Les sommets feuilles contiennent des hachages de blocs de données, tandis que les sommets internes incluent des hachages issus de l'ajout de valeurs dans deux sommets enfants. À son tour, le sommet racine comprend le hachage de l’ensemble des données. Théorie Initialement, il existe un ensemble de données qui ne sont en aucun cas liées les unes aux autres. Pour chaque bloc de données (dans le contexte d'une blockchain de transaction), nous devons calculer un hachage du bloc. Le nombre de blocs de données doit être de , car au fur et à mesure que l'arborescence est construite, les blocs précédents sont hachés par paires à chaque itération. Une paire de hachages est ensuite regroupée et un nouveau hachage est créé sur cette base. Le hachage continuera tant qu'il y aura quelque chose à regrouper à chaque niveau, et il s'arrêtera lorsqu'il ne restera qu'une seule paire à partir de laquelle le hachage racine – la racine de Merkle – est obtenu. 2^N H(1-2) = keccak256(H(1) + H(2)) H(3-4) = keccak256(H(3) + H(4)) H(5-6) = keccak256(H(5) + H(6)) H(7-8) = keccak256(H(7) + H(8)) H(1-2-3-4) = keccak256(H(1-2) + H(3-4)) H(5-6-7-8) = keccak256(H(5-6) + H(7-8)) H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8)) Une fois que nous avons la racine, nous pouvons valider les données. Si le hachage racine correspond au hachage d'origine, tout va bien, les données sont valides. Il est également possible de vérifier efficacement si certaines données sont présentes dans l’arborescence. Disons que nous voulons vérifier que le hachage est présent dans l'arborescence. La preuve sera un tableau de données : , , . Grâce à ces hachages, nous pouvons reconstruire le hachage racine : H2 H1 H3-4 H5-6-7-8 H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8)) Ensuite, nous comparons le hachage obtenu avec celui d'origine. S'ils correspondent, cela signifie que le hachage est présent dans l'arborescence. H2 Pratique Voyons maintenant comment implémenter un arbre Merkle et une validation des données dans Solidity. Pour plus de simplicité, nous écrirons le tableau des transactions directement dans la blockchain, ainsi que le tableau des hachages. Puisque nous utiliserons la fonction intégrée, qui renvoie un hachage de 32 octets, le type de données du tableau de hachages sera . Le tableau aura également une longueur dynamique. En général, la longueur du tableau de hachages ne sera pas la même que la longueur du tableau de transactions, car il contiendra les hachages produits. Nous pourrions calculer la longueur à l’avance, mais par souci de simplification du code, nous ne le ferons pas. Si vous le souhaitez, vous pouvez rendre chacun de ces tableaux et lire les hachages des transactions. keccak256 bytes32 public Nous produirons dans le constructeur. La première étape consiste à compter les hachages des blocs avec dans la boucle. Ensuite, à chaque niveau de l'arborescence, le nombre de hachages est réduit d'un facteur 2. Puisque nous allons stocker les hachages dans le tableau de hachages, les décalages d'index doivent être stockés séparément. L'itérateur dans la boucle interne est incrémenté de 2 car nous prendrons quelques éléments lors du calcul et de l'ajout de hachages. Dans cette fois, nous ajouterons 2 hachages chacun auxquels nous définirons correctement les indices : pour l'élément de gauche – la valeur du décalage de décalage actuel + l'index au niveau de l'arborescence actuel, et pour l'élément de droite – la même chose + 1. hashes transactions abi.encodePacked Nous avons donc construit l'arbre, mais l'intérêt consiste à valider les données. Pour ce faire, écrivons une fonction qui prend une transaction et son index. Malheureusement, Solidity n'a pas de méthode pour les tableaux, il est donc plus facile de simplement transmettre l'index de transaction. validateTransaction find Tout d’abord, calculons le hachage de la transaction et créons un tableau de preuves. Nous trouvons le nombre de preuves en fonction de la longueur du tableau de transactions et définissons la longueur des . Après cela, à chaque niveau de l'arborescence, on retrouve l'élément nécessaire, selon l'index, en prenant l'élément droit ou gauche, en tenant compte des décalages dans les . Ensuite, nous parcourons le tableau des indices de preuve, vérifions la parité de l'indice et calculons le hachage selon que l'élément est à gauche ou à droite dans la paire. Enfin, nous comparons le hachage résultant avec le hachage racine et renvoyons le résultat. proofsIndexes hashes Application Il existe plusieurs applications d'un arbre Merkle dans la blockchain. : Dans Bitcoin par exemple, un bloc de transaction stocke uniquement la merkle_root de ses transactions. Cela réduit la taille du bloc et la charge sur le réseau. Après avoir accumulé un certain nombre de transactions, il est possible de supprimer les anciennes transactions pour gagner de la place, mais les blocs eux-mêmes restent inchangés car ils ne stockent que la racine de l'arborescence. Stockage des transactions : Un bloc Bitcoin se compose de deux parties : l’en-tête du bloc et la liste des transactions. Pour éviter d'avoir à recalculer les hachages de transaction à chaque fois, ils sont alignés dans un arbre Merkle, après quoi l'en-tête du bloc est haché plutôt que le bloc entier, et un nombre occasionnel aléatoire est pris. Lorsque le bloc est envoyé à d'autres nœuds, la racine de la liste de transactions est calculée et si elle ne correspond pas à la racine de l'en-tête, le bloc est rejeté. Minage : L'essence de la vérification est l'audit sans avoir à télécharger l'intégralité de la blockchain. Le processus est grandement simplifié et permet également de confirmer l'existence de données sans divulguer d'informations sur les données, ce qui peut être utile pour vérifier des informations sensibles. Vérification Résumé Sans les arbres Merkle, les blockchains seraient trop lourdes et les preuves Merkle permettent une vérification rentable de l'authenticité des données. Les arbres Merkle sont activement utilisés dans les blockchains (par exemple, Bitcoin, Ethereum) pour stocker efficacement les transactions, mais ce n'est pas la seule application. Par exemple, après l'effondrement de la bourse FTX, de nombreuses bourses ont mis en œuvre un mécanisme de preuve de réserve, qui utilise un arbre Merkle.
