Comment vérifier un morceau d'un énorme fichier sans télécharger tout le reste ?

Imagine un fichier partagé sur un million d'ordinateurs, découpé en milliers de petits morceaux. Comment vérifier qu'un seul morceau est authentique sans télécharger et hacher tous les autres ? Un arbre de Merkle résout ce problème en hachant les données par couches : chaque feuille porte l'empreinte d'un bloc de données, et chaque nœud au-dessus porte l'empreinte des empreintes de ses enfants, jusqu'à une seule empreinte au sommet, appelée racine, qui représente toute la structure.

Cette structure en couches rend la vérification peu coûteuse. Prouver qu'une feuille appartient à l'arbre demande un nombre d'empreintes proportionnel au logarithme du nombre total de feuilles, alors qu'une simple liste d'empreintes en demanderait un nombre proportionnel à toutes les feuilles elles-mêmes. En pratique, cela signifie qu'on peut télécharger une petite branche de l'arbre et vérifier son intégrité immédiatement, sans attendre que tout l'arbre soit disponible.

L'idée n'est pas récente : elle porte le nom de Ralph Merkle, qui l'a brevetée en 1979, bien avant qu'elle ne devienne une infrastructure essentielle. Aujourd'hui, on la retrouve dans les réseaux pair-à-pair de Bitcoin et d'Ethereum, parmi beaucoup d'autres systèmes, généralement construits avec une fonction de hachage cryptographique comme SHA-2 pour hacher chaque couche.

Comme toute astuce ingénieuse, elle a un point faible connu : comme la racine de Merkle à elle seule ne révèle pas la profondeur de l'arbre, un attaquant peut parfois construire un document totalement différent qui produit la même racine, une attaque dite de seconde préimage. C'est pourquoi certaines implémentations ajoutent une protection, comme marquer différemment les empreintes des feuilles et celles des nœuds internes, pour qu'un document falsifié ne puisse pas discrètement se faire passer pour l'original.