Générateur et visualiseur d'arbre de Merkle

Un arbre de Merkle est un arbre binaire d'hachages cryptographiques. Les feuilles sont des hachages des données d'entrée, et chaque nœud parent est l'hachage de la concaténation de ses deux enfants. La seule hachage au sommet — la racine de Merkle — fait servir l'ensemble des données : tout changement dans une feuille modifie la racine. Les arbres de Merkle permettent de prouver qu'une valeur spécifique appartient à un ensemble en partageant uniquement un nombre logarithmique de hachages de frères (la preuve de Merkle), ce qui est la raison pour laquelle ils alimentent les en-têtes de Bitcoin, l'état d'Ethereum, les commits Git et les journaux de Transparence des Certificats.

Pour maintenir la construction strictement binaire, Bitcoin complète les niveaux à nombre impair en dupliquant la dernière hachage afin qu'il puisse être apparié avec lui-même. Cela est facile à implémenter mais introduit un défaut connu de deuxième préimage (CVE-2012-2459) où un attaquant peut parfois concevoir une liste de feuilles différente produisant la même racine. Les nouvelles conceptions préfèrent une règle de « promotion » — porter le nœud non apparié vers le haut sans le modifier — ou des étiquettes de domaine entre les hachages internes et les hachages de feuilles afin de réduire cette lacune.

Keccak-256 est la construction initiale de la pompe qui a remporté la compétition NIST SHA-3. Avant la standardisation, NIST a modifié la règle de padding, produisant SHA3-256, incompatible byte pour byte avec le Keccak-256 pré-standardisation. Ethereum a fixé le Keccak-256 original avant ce changement, donc la fonction 'keccak256' en Solidity n'est pas la même que SHA3-256. SHA-256 fait partie de la famille SHA-2 indépendante et utilise une construction Merkle–Damgård ; elle partage seulement le nom de la structure.

En triant les hachages gauche et droit avant concaténation, la hachage du parent devient indépendant de laquelle des deux est « gauche » ou « droite ». Cela signifie qu'une preuve de Merkle n'a besoin que des hachages de frères, sans bits de direction, ce qui rend les preuves environ 30% plus petites sur la chaîne et simplifie considérablement le contrat vérificateur. La bibliothèque MerkleProof.sol d'OpenZeppelin utilise cette convention ; les en-têtes classiques de Bitcoin et d'Ethereum ne le font pas. La variante triée est principalement utilisée dans les listes d'airdrop, les snapshots de gouvernance et d'autres engagements hors chaîne.