Arbre de Merkle

En informatique et en cryptographie, un arbre de Merkle ou arbre de hachage est une structure de données contenant un résumé d'information d'un volume de données, généralement grand (comme un fichier).

Les arbres de hachage ont été inventés par Ralph Merkle en 1979^[1].

Fonctionnement

Le principe d'un arbre de hachage est de pouvoir vérifier l'intégrité d'un ensemble de données sans les avoir nécessairement toutes au moment de la vérification.

Construction de l'arbre

Dans la figure, l'ensemble de données est représenté par les blocs^[Quoi ?] L1 à L4. L'arbre est constitué par un ensemble de valeurs de hash^[Quoi ?] interdépendantes. Les feuilles de l'arbre sont les valeurs de hash de chacun des blocs de données initiales. Dans un arbre de Merkle binaire, ces hashs sont alors concaténés deux à deux pour pouvoir calculer un nouveau hash parent. Ainsi de suite jusqu'au sommet de l'arbre où on obtient un hash-sommet. Si le nombre de blocs, ou les hashs intermédiaires ne forment pas un arbre binaire, on complète la base avec suffisamment de blocs vides.

Exploitation

Pour garantir l'intégrité d'un bloc téléchargé par rapport à l'ensemble des données, il suffit de posséder les hashs des frères, les hashs des oncles et le hash-sommet. De plus, seul le hash-sommet doit être récupéré de manière sûre pour garantir l'intégrité de l'ensemble des données représentées par l'arbre.

Par exemple, si on veut vérifier l'intégrité du bloc L2, il suffit d'avoir récupéré le hash0-0 (son frère), le hash1 (son oncle) et le hash-sommet.

Utilisations

Actuellement, les arbres de hachage sont très utilisés dans les réseaux pair à pair, car ils permettent de vérifier l'intégrité d'une partie d'un fichier. En effet, il suffit alors de connaître le bon nœud se situant à la hauteur nécessaire dans l'arbre, sans nécessairement devoir posséder tout le fichier.

La fonction de hachage cryptographique MD6 utilise un arbre de Merkle, ce qui permet de tirer parti du parallélisme présent dans les ordinateurs modernes.

Les arbres de Merkle sont aussi utilisés dans le système de fichiers ZFS^[2], dans le protocole Google Wave^[3], dans le protocole de la cryptomonnaie Bitcoin^[4] ou dans le logiciel de versionnement Git^[5].

Références

↑ R. C. Merkle, A digital signature based on a conventional encryption function, Crypto '87
↑ Jeff Bonwick's Blog ZFS End-to-End Data Integrity
↑ « General Verifiable Federation - Google Wave Federation Protocol », sur web.archive.org, 8 avril 2018 (consulté le 18 novembre 2021)
↑ (en) Satoshi Nakamoto, « Bitcoin: A Peer-to-Peer Electronic Cash System », Cryptography Mailing List,‎ 31 octobre 2008, p. 9 (lire en ligne [PDF])
↑ Jill-Jênn Vie, « Arbres de Merkle : la structure de données à l'origine de git, BitTorrent, Bitcoin, Ethereum, The DAO et autres blockchains », sur tryalgo.org

[1] R. C. Merkle, A digital signature based on a conventional encryption function, Crypto '87

[2] Jeff Bonwick's Blog ZFS End-to-End Data Integrity

[3] « General Verifiable Federation - Google Wave Federation Protocol », sur web.archive.org, 8 avril 2018 (consulté le 18 novembre 2021)

[4] (en) Satoshi Nakamoto, « Bitcoin: A Peer-to-Peer Electronic Cash System », Cryptography Mailing List,‎ 31 octobre 2008, p. 9 (lire en ligne [PDF])

[5] Jill-Jênn Vie, « Arbres de Merkle : la structure de données à l'origine de git, BitTorrent, Bitcoin, Ethereum, The DAO et autres blockchains », sur tryalgo.org

[1]

[2]

[3]

[4]

[5]

v · m Fonctions de hachage cryptographiques
Algorithmes	APR1 AR Boognish FFT-hash HAS-160 Haval MD2 MD4 MD5 MD6 N-hash PANAMA RadioGatún RIPEMD RIPEMD-128 RIPEMD-160 RIPEMD-256 Scrypt SHA-0 SHA-1 SHA-2 SHA-224 SHA-256 SHA-384 SHA-512 SHA-3 Snefru StepRightUp Streebog Tiger VSH Whirlpool
Cryptanalyse	Attaque des anniversaires Paradoxe des anniversaires Linéaire Différentielle Attaque par force brute Effet avalanche Pseudo-collision Attaque de collisions Attaque de préimage Attaque par extension de longueur
Architecture	Remplissage Fonction de compression Construction de Merkle-Damgård Construction de Miyaguchi-Preneel Construction de Matyas-Meyer-Oseas Construction de Davies-Meyer Construction de l'éponge

v · m Arbre enraciné
Arbre binaire	Arbre binaire de recherche Arbre de fouille Arbre cartésien MVP Tree (en) Top tree (en) T-tree (en)
Arbre équilibré	AA tree (en) Arbre AVL LLRB tree (en) Arbre bicolore Arbre bouc-émissaire Arbre splay Treap
Arbre B	B*-tree (en) Bx-tree (en) UB-tree (en) 2-3 tree (en) Arbre 2-3-4 (a,b)-tree (en) Dancing tree Htree (en)
Trie	Arbre des suffixes Arbre radix Arbre ternaire de recherche X-fast trie (en) Y-fast trie (en)
Partition binaire de l'espace trees	Quadtree Octree Arbre kd (relaxé) Implicit k-d tree (en) Vp-tree
Arbres non binaires	Arbre exponentiel Fusion tree (en) arbre d'intervalles arbre PQ arbre de portée (range tree) arbre SPQR arbre de Van Emde Boas
Arbre de base de données spatiales	R-arbre R+ tree (en) R* tree (en) X-tree (en) M-tree (en) arbre de segments Hilbert R-tree (en) Priority R-tree (en)
Autres arbres	Arbre de Merkle Arbre couvrant de poids minimal Arbre syntaxique Arbre de la syntaxe abstraite Finger tree (en) Order statistic tree (en) Arbre métrique Cover tree (en) BK-tree (en) Doubly chained tree iDistance (en) Link-cut tree (en) Fenwick tree (en) Tas Binaire Binomial Fibonacci Arbre cousu

Arbre de Merkle

Fonctionnement

Utilisations

Références

€4.95