Comment implémenter un arbre Merkle dans Solidity

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 2^N , 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.

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 H2 est présent dans l'arborescence. La preuve sera un tableau de données : H1 , H3-4 , H5-6-7-8 . Grâce à ces hachages, nous pouvons reconstruire le hachage racine :

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 H2 est présent dans l'arborescence.

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 keccak256 intégrée, qui renvoie un hachage de 32 octets, le type de données du tableau de hachages sera bytes32 . 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 public chacun de ces tableaux et lire les hachages des transactions.

Nous produirons hashes dans le constructeur. La première étape consiste à compter les hachages des blocs avec transactions 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 abi.encodePacked 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.

Nous avons donc construit l'arbre, mais l'intérêt consiste à valider les données. Pour ce faire, écrivons une fonction validateTransaction qui prend une transaction et son index. Malheureusement, Solidity n'a pas de méthode find pour les tableaux, il est donc plus facile de simplement transmettre l'index de transaction.

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 proofsIndexes . 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 hashes . 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.

Application

Il existe plusieurs applications d'un arbre Merkle dans la blockchain.

• Stockage des transactions : 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.
• Minage : 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é.
• Vérification : 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.

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.