Qu'est-ce qu'un arbre de Merkle et quel est son rôle dans la blockchain ?

Les arbres de Merkle sont utilisés en informatique comme structure de données pour la vérification et la synchronisation des données. Les arbres de Merkle sont également utilisés pour chiffrer de manière plus sûre et plus efficace les données de la blockchain dans Bitcoin et d'autres cryptomonnaies. 

Dans le domaine des cryptomonnaies, une base de données d'arbres de Merkle est utilisée pour diviser les données des blocs de manière sécurisée et garantir qu'elles ne soient ni perdues, ni endommagées, ni altérées. Cette méthode de gestion des données permet de valider des transactions spécifiques sans télécharger l'intégralité de la blockchain, qui pèse un téraoctet. Il s'agit d'une méthode fiable, sécurisée et cryptographique pour faire fonctionner la blockchain.

Suite à la chute du géant des plateformes d'échange centralisées (CEX) , FTX, de nombreuses CEX ont construit et mis en œuvre l'arbre de Merkle comme forme de preuve de réserves (PoR) pour assurer aux utilisateurs que leurs fonds sont en sécurité. Dans cet article, nous aborderons la question des arbres de Merkle, leur rôle dans la blockchain et la manière dont un utilisateur peut valider ses fonds à l'aide de l'arbre de Merkle.

Qui est le fondateur de Merkle Tree ?

Ralph Merkle, un informaticien renommé pour ses travaux sur la cryptographie à clé publique, a proposé les arbres de Merkle dans l'article de 1987 intitulé « Une signature numérique basée sur une fonction de chiffrement conventionnelle ». Le hachage cryptographique a également été inventé par Merkle.

Qu'est-ce qu'un arbre de Merkle ?

L'arbre de Merkle est une structure de données mathématique basée sur le hachage qui compile les résumés de toutes les transactions d'un bloc. Il s'agit d'une méthode permettant de vérifier rapidement et de manière décentralisée l'exactitude des données. Grâce à leurs fonctionnalités, les arbres de Merkle sont utilisés de manière plus efficace et plus sûre pour chiffrer les données de la blockchain. 

Les arbres de Merkle sont souvent utilisés avec les réseaux peer-to-peer (P2P) en raison de la nécessité de partager et de valider indépendamment les informations. Approfondissons notre compréhension des arbres de Merkle et de leur fonctionnement.

Structure de l'arbre de Merkle

L'arbre de Merkle, également connu sous le nom d'arbre de hachage, possède une structure d'arbre binaire, les hachages des données transactionnelles sur la ligne du bas étant appelés « nœuds feuilles », les hachages intermédiaires étant appelés « nœuds non feuilles » et le hachage en haut étant appelé « racine ». Bien que la majorité des implémentations d'arbres de hachage soient binaires (chaque nœud a deux nœuds enfants), elles peuvent également avoir beaucoup plus de nœuds enfants.

Lorsqu'on examine la structure d'un arbre de Merkle, toutes les transactions sont regroupées par paires. Chaque paire possède un hachage calculé qui est stocké directement dans le nœud parent. Ces nœuds sont également regroupés par paires, après quoi leur hachage est stocké au niveau supérieur. Ce processus se poursuit jusqu'à atteindre la racine de l'arbre Merkle.

Examinons chacun des nœuds :

Nœuds feuilles

Il s'agit des hachages de chaque transaction de cryptomonnaie dans un bloc, également appelés identifiants de transaction (TXID). Vous visualisez le hachage de la transaction lorsque vous recherchez une transaction sur un explorateur de blocs.

Nœuds non-feuilles

Ensuite, pour créer une couche de nœuds non-feuilles au-dessus des nœuds feuilles, ces nœuds feuilles sont hachés ensemble par paires. Ils sont appelés nœuds non-feuilles car, contrairement aux nœuds feuilles, ils stockent simplement le hachage des deux nœuds feuilles qu'ils représentent et ne contiennent pas d'identifiants (ou de hachages) de transaction. En conséquence, il y aura deux fois moins de hachages (ou de nœuds) dans la couche de nœuds non-feuilles au-dessus des nœuds feuilles que dans la couche de nœuds feuilles. À mesure que l'arbre se rétrécit en s'élevant, ces couches de nœuds non-feuilles continuent d'être hachées par paires, ce qui donne deux fois moins de nœuds par couche. Deux nœuds seront présents dans la couche finale de nœuds non-feuilles. Cela crée la racine Merkle et correspond à l'emplacement du dernier hachage dans un arbre Merkle.

Racine de Merkle

Avec Bitcoin, les hachages de toutes les transactions sont combinés en un seul hachage et stockés dans l'en-tête du bloc. La racine Merkle, également connue sous le nom de hash racine, est ce hash particulier. Les nœuds feuilles (identifiants/hachages de transaction) à la base de l'arbre Merkle peuvent être vérifiés à l'aide de cette racine Merkle. Lorsqu'elle est utilisée pour les cryptomonnaies, la racine Merkle garantit que les blocs de données sont intacts, non endommagés et complets.

Un arbre de Merkle est binaire, ce qui signifie que le nombre total de nœuds feuilles différents doit être pair pour que l'arbre soit correctement construit. Lorsqu'il existe un nombre impair de nœuds feuilles, le hachage précédent sera dupliqué pour fournir un nombre pair de nœuds.

Comment fonctionne un arbre de Merkle ?

Un arbre de Merkle est essentiellement conçu pour diviser de grands ensembles de données en morceaux considérablement plus petits, ce qui garantit que toutes les transactions peuvent être vérifiées rapidement. L'arbre résume chaque transaction en créant une petite empreinte digitale d'un ensemble spécifique de transactions, ce qui facilite la vérification de la disponibilité des transactions dans un bloc par les utilisateurs. 

Les arbres de Merkle sont formés en hachant différentes paires de nœuds jusqu'à ce qu'il ne reste qu'un seul hachage, appelé racine de Merkle. Ces arbres sont construits de bas en haut, chaque transaction étant constituée de hachages. Chaque nœud feuille est un hachage unique de données. Quant aux nœuds non-feuilles, il s'agit de hachages de hachages précédents.

Supposons qu'un arbre de Merkle soit composé de quatre transactions étiquetées D0, D1, D2 et D3. Chaque transaction est hachée avant que le hachage ne soit stocké directement sur le nœud feuille. Lorsque cela se produit, les hachages N0, N1, N2 et N3 sont créés. Toute paire consécutive de nœuds feuilles sera ensuite résumée dans un nœud parent via le hachage du hachage N0 et du hachage N1, ce qui donne le hachage N4. Si les hachages N2 et N3 sont hachés ensemble, le hachage N5 est créé. Ces deux hachages, N4 et N5, sont hachés une fois de plus afin de créer la racine Merkle.

Ce procédé peut être utilisé avec de vastes ensembles de données. La racine Merkle est chargée de synthétiser les données présentes dans des transactions spécifiques, lesquelles sont toutes stockées directement dans l'en-tête du bloc. Cette technique permet de préserver l'intégrité des données. Si un détail de la transaction est modifié à un moment donné, la racine Merkle sera automatiquement modifiée en conséquence.

Avantages d'un arbre Merkle

L'utilisation d'un arbre de Merkle pour vérifier les transactions présente de nombreux avantages pour la technologie blockchain et les plateformes de cryptomonnaies, notamment une vérification efficace et une détection aisée des falsifications.

Processus de vérification des données efficace

L'intégrité des transactions peut être vérifiée très facilement et en un temps record. Du fait de la structure des données, très peu de mémoire est nécessaire lors du processus de vérification et la puissance de calcul requise est considérablement réduite. 

Étant donné que les chaînes de blocs sont généralement composées de centaines de milliers de blocs, chacun pouvant contenir jusqu'à plusieurs milliers de transactions, la validation des données pose deux défis majeurs : l'espace mémoire et la puissance de calcul. Si les arbres de Merkle n'avaient pas été un concept de la blockchain, chaque nœud du réseau aurait dû conserver une copie complète de chaque transaction effectuée sur celle-ci. Lors de la vérification d'une transaction, un nœud aurait dû comparer chaque entrée ligne par ligne afin de s'assurer que ses enregistrements correspondaient exactement à ceux du réseau. La sécurité du réseau pourrait être compromise en cas de divergence quelconque entre les enregistrements. Par conséquent, pour comparer les enregistrements et s'assurer qu'il n'y avait pas eu de modifications, l'ordinateur utilisé pour valider les données aurait eu besoin d'une puissance de traitement beaucoup plus importante. 

Les arbres de Merkle, quant à eux, offrent une solution à ce problème en réduisant considérablement la quantité de données à conserver pour les besoins de vérification. Ils hachent chaque entrée du registre, séparant ainsi les données elles-mêmes des preuves qui les sous-tendent. Sans connaître chaque TXID d'un bloc, vous pouvez vérifier un TXID en utilisant la racine Merkle avec un arbre Merkle. Un arbre de Merkle est essentiellement un excellent moyen de démontrer la présence d'un élément dans un ensemble de données sans avoir à télécharger l'ensemble complet. Par conséquent, une puissance de calcul moindre est nécessaire pour valider les transactions.

Vitesse de traitement plus rapide

Du fait de la répartition des transactions du bloc entre les validateurs, chaque validateur travaille simultanément sur une transaction différente. Comparée à une méthode où chaque transaction est validée séquentiellement après l'autre, celle-ci est beaucoup plus efficace.

Utilisation d'un portefeuille crypto

La vérification simple des paiements (SPV), qui vous permet de confirmer une transaction sans télécharger un bloc ou une blockchain entière, est rendue possible par l'arbre Merkle. Cela permet l'utilisation d'un nœud client léger, plus formellement appelé portefeuille crypto, pour envoyer et recevoir des transactions.

Détection de toute falsification

La structure de hachage permet aux mineurs d'identifier facilement si des falsifications ont eu lieu au niveau des transactions. 

Une valeur de hachage distincte est générée pour chaque bloc en utilisant la racine Merkle. Le bloc relie un bloc à un autre dans la blockchain en incluant le hachage du bloc précédent. Le hachage de toute transaction change à chaque modification de cette transaction. Ce changement rend le bloc invalide car il se répercute jusqu'à la racine Merkle et en modifie la valeur. Cela provoque alors une modification du hachage du bloc suivant, rendant invalide le reste de la blockchain. De ce fait, l'arbre de Merkle crée un enregistrement immuable des transactions du bloc.

Il est ainsi possible d'éviter les doubles dépenses. Si une personne tente de dépenser deux fois sa monnaie numérique, un hachage sera généré pour cette transaction. Si ce hachage correspond aux enregistrements existants sur la blockchain, la transaction est rejetée.

Pourquoi les arbres de Merkle sont-ils importants dans les blockchains ?

Les arbres de Merkle se sont révélés essentiels pour la technologie blockchain car ils facilitent une vérification rapide et facile, ce qui est impossible avec d'autres techniques. Ces arbres de Merkle offrent aux développeurs la possibilité de compresser des ensembles de données extrêmement volumineux en éliminant toutes les données inutiles et en transformant les données restantes en hachages. Les arbres de Merkle offrent diverses caractéristiques, notamment :

• Structure très légère

• Évolutivité efficace

• consommation de carburant

• Vérification que les transactions sont incluses dans un bloc spécifique

• Authentification de paiement de base

Preuve de réserve de Merkle Tree (PoR)

Comme mentionné au début, suite à la chute de FTX, les utilisateurs se sont interrogés sur la sécurité réelle de leurs fonds dans les plateformes d'échange centralisées. En conséquence, plusieurs CEX ont développé un mécanisme de preuve de réserve basé sur l'arbre de Merkle. Dans cette section, nous allons examiner les preuves Merkle et la manière dont nos utilisateurs peuvent valider leurs fonds.

Épreuves Merkle

Une épreuve de Merkle est une coupe réalisée sur un arbre de Merkle, et non sur l'arbre lui-même. Et être représentée sous forme de tableau ou de séquence (représentée par la partie orange dans le diagramme ci-dessous).

L'ensemble des nœuds terminaux et des informations de solde pour un utilisateur particulier de notre entreprise sont représentés par les nœuds de dernier niveau de la figure. En supposant que les personnes roses sur la figure représentent les destinataires prévus des preuves, nous extrayons les parties orange de la figure niveau par niveau et présentons les documents de preuve aux utilisateurs par ordre de hauteur. Il est important de rappeler que l'épreuve Merkle comporte deux composantes principales

1. Les nœuds parents directs (c.-à-d. B et D) de cet utilisateur ne sont pas extraits.

2. Indiquez le nœud racine, c'est-à-dire la racine de Merkle.



Prenons comme exemple un volume de 10 millions d'utilisateurs, la hauteur de l'arbre peut être calculée comme Log2(10 000 000) = 23,2534966642 sur la base de la formule mathématique, ce qui donne une hauteur d'arbre de 24 niveaux. Par conséquent, les nœuds du graphe qui ne sont pas intentionnellement fournis aux utilisateurs seront 24 - 2 = 22.

L'arbre de Merkle est un arbre binaire complet, ce qui nous permet de calculer toutes les informations concernant son nœud parent en connaissant simplement les nœuds gauche et droit. Ces informations complètes se composent de deux parties : les données de solde et les données de hachage.

1. Donnéesd'équilibre  : Les données du nœud parent peuvent et ne peuvent être divisées qu'en ses nœuds inférieurs gauche et droit.

2. Donnéesde hachage : Seules les données d'équilibre, les données de hiérarchie arborescente et les données de hachage des nœuds enfants seront présentes pour chaque nœud (chaque nœud conserve les données récapitulatives des nœuds situés à sa gauche et à sa droite).

La validation de l'arbre de Merkle est calculée en dérivant B et D et en vérifiant que

1. le solde est conforme au principe de répartition ; et

2. Le haschisch est légal.

En utilisant une fonction de hachage récapitulative, l'arbre de Merkle permet aux utilisateurs de déterminer s'ils font partie de l'arbre entier sans avoir à connaître chaque nœud violet du graphique. La preuve Merkle est exclusive à cet utilisateur. Par exemple, un arbre de Merkle à 24 niveaux nécessite un tableau de 23 éléments pour vérifier les informations de solde de l'utilisateur, et ce tableau ne peut que confirmer que la preuve du solde de l'utilisateur est exacte.

L'utilisateur ne peut pas reconstituer l'arbre entier à partir de ses informations fragmentaires tant qu'il n'obtient pas plus de la moitié du nombre total d'utilisateurs. De ce fait, l'arbre de Merkle protège à la fois la vie privée des utilisateurs et la capacité de l'entreprise à empêcher la fuite d'informations concernant l'ensemble de ses actifs.

Validation de votre compte Bybit

Deux méthodes vous permettent de valider votre compte Bybit et de vérifier la validité de vos fonds.

Outil de validation de la plateforme

Cette méthode est la première et la seule de tout le réseau, et elle illustrera le processus de dérivation des nœuds de la validation de l'arbre de Merkle de manière graphique et intuitive sur la plateforme de l'entreprise.



Outil d'auto-validation

Le code source de génération d'arbres de Merkle et le code de validation de l'entreprise sont disponibles publiquement sur GitHub afin d'aider les utilisateurs à programmer leur propre validation. Le processus de calcul de l'arbre de Merkle implique une quantité considérable de calculs effectués par l'utilisateur, généralement mis en œuvre à l'aide du Big Data et de Java. 

*Un code Java ouvert signifie qu'il est accessible aux utilisateurs sans aucune restriction d'information.

Bybit a mis en open source le code suivant afin que les utilisateurs professionnels puissent valider leur propre fichier de preuve d'arbre Merkle en le copiant depuis leur page de preuve de réserves vers leur propre version « enregistrée » du système via le bouton Copier les données et en le stockant sous forme de fichier nommé myProof.json sur leur disque local.

Applications des arbres de Merkle dans la blockchain

Les structures arborescentes et racinaires de Merkle ont déjà été largement adoptées sur de nombreuses blockchains et plateformes de cryptomonnaies. Les détails suivants portent sur trois applications de ce type.

Bitcoin

Bitcoin utilise les arbres de Merkle de plusieurs manières, ce qui rend ces arbres essentiels à l'ensemble de la plateforme Bitcoin. En réalité, ces arbres sont présents dans l'en-tête de chaque bloc Bitcoin. Le hachage de chaque transaction disponible dans le bloc est placé dans l'en-tête. En ce qui concerne le Bitcoin, la racine Merkle est importante à la fois pour le minage et la vérification.

Exploitation minière

Les blocs Bitcoin sont constitués d'en-têtes contenant des métadonnées ainsi qu'une liste exhaustive de transactions. Cette liste est généralement plus longue que l'en-tête du bloc. Les mineurs hachent les données pour créer un résultat conforme à des conditions spécifiques, ce qui est nécessaire lors de la validation d'un bloc. Les mineurs peuvent effectuer des milliards de tentatives distinctes avant de trouver un bloc valide. Chaque tentative nécessite la modification d'un nombre dans l'en-tête du bloc. Même si des milliers de transactions distinctes peuvent exister dans un bloc, chacune d'elles doit être hachée.

Les racines de Merkle permettent aux mineurs de rendre ce processus beaucoup plus efficace. Lorsque le processus de minage commence, il suffit que les transactions soient organisées dans un arbre de Merkle, après quoi le hachage racine peut être placé dans l'en-tête du bloc. À ce stade, le mineur n'est tenu de hacher que l'en-tête du bloc, et non le bloc entier.

Vérification

Un autre aspect de la racine Merkle utilisée avec Bitcoin concerne l'effet de levier, qui se concentre sur les clients légers. Lorsqu'un nœud fonctionne sur un appareil relativement peu puissant aux ressources limitées, les utilisateurs ne pourront pas télécharger et hacher chaque transaction en un seul bloc. Il est possible, en revanche, de demander une preuve Merkle, qui confirme la présence d'une transaction dans un bloc. En réduisant le nombre de hachages à effectuer lors du processus de vérification, celle-ci peut être réalisée en utilisant moins de ressources informatiques.

Ethereum

Ethereum est basé sur une version légèrement modifiée de l'arbre de Merkle, c'est pourquoi on l'appelle l' arbre de Merkle Patricia. Chaque bloc de la blockchain Ethereum est composé de trois arbres de Merkle, contrairement aux blocs Bitcoin qui ne comportent qu'un seul arbre binaire. Chacune des trois racines a sa propre fonction.

La racine initiale est considérée comme la racine de chaque transaction. Quant à la seconde racine, elle indique l'état de la transaction. La racine finale est la réception de la transaction. Un utilisateur peut consulter une racine Merkle pour déterminer si une transaction se trouve sur un bloc spécifique, ainsi que pour connaître le solde de son compte.

Hyperledger Fabric

Si l'on examine plus précisément Hyperledger Fabric, cette plateforme blockchain utilise un arbre de Merkle pour calculer les données des blocs sous forme de hachage. La valeur de hachage identifie la largeur de l'arbre de Merkle. Les arbres de Merkle sur la plateforme Hyperledger Fabric fonctionnent exactement comme ceux de la plateforme Bitcoin.

Conclusion

Les arbres de Merkle se sont révélés extrêmement utiles pour les plateformes de cryptomonnaies qui souhaitent s'assurer que leur processus de vérification des transactions soit aussi simple et efficace que possible. Sans cette structure, la vérification serait un processus long et fastidieux car les données devraient être transférées sur l'ensemble du réseau pour être vérifiées. Les plateformes utilisant les arbres de Merkle bénéficient de besoins moindres en bande passante et en puissance de calcul.