Un arbre de Merkle organise les hashes de données en arbre. Le hash supérieur, appelé racine de Merkle, résume la collection engagée. Chaque parent est calculé à partir de ses enfants selon des règles précises. Modifier une feuille change généralement les hashes sur son chemin jusqu’à la racine.
Vérifier un élément
Une preuve d’inclusion fournit les hashes voisins nécessaires pour recalculer ce chemin, au lieu de tous les éléments. Dans un arbre binaire équilibré à huit feuilles, prouver une feuille nécessite généralement trois hashes frères et les informations de position. Le vérificateur a aussi besoin de l’élément ou de son hash et d’une racine fiable.
Utilisation dans Bitcoin
Bitcoin engage les identifiants de transactions dans une racine de Merkle inscrite dans chaque en-tête de bloc. La construction précise leur ordre, le hachage par paires et la duplication lorsqu’un niveau comporte un nombre impair d’entrées. D’autres systèmes peuvent employer des structures et encodages différents.
Ce que la preuve établit
Une preuve valide montre qu’un élément appartient à la collection représentée par la racine de référence, sous les hypothèses de sécurité du hachage. Elle ne prouve pas seule la validité d’une transaction, l’état actuellement non dépensé d’une sortie ou la finalité de la chaîne. La racine ne révèle pas non plus toutes les données : celles-ci doivent rester disponibles ailleurs pour une vérification complète.