What is a Merkle tree and how does it work?

A Merkle tree, or hash tree, is a tree data structure in which every leaf node is labelled with a cryptographic hash of a data block, and non-leaf nodes are labelled with the cryptographic hash of their children. It allows for efficient and secure verification of large data structures. Named after Ralph Merkle who patented it in 1979, it serves as a generalization of hash lists and hash chains.

What we know

• Every leaf node in a Merkle tree is labelled with the cryptographic hash of a data block, and inner nodes are labelled with the cryptographic hash of their child nodes. [1, 2]
• Demonstrating that a leaf node is part of a binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes. [2]
• The concept of a hash tree is named after Ralph Merkle, who patented it in 1979. [2]
• A hash tree functions as a generalization of a hash list and a hash chain. [2]

Where to go next

• whoWho was Ralph Merkle?
• compared withWhat is a hash list?
• how it workedHow does cryptographic commitment work?
• the bigger pictureWhat are common tree data structures?
• an unexpected connectionWhat is the Merkle-Damgard construction?

Sources

• [1]hash tree (Wikidata Q14746) · CC0 1.0
• [2]Merkle tree · CC BY-SA 4.0
• [3]List of data structures · CC BY-SA 4.0
• [4]Merkle–Damgård construction · CC BY-SA 4.0
• [5]Hash tree · CC BY-SA 4.0