Merkle tree
Named after its inventor, Ralph Merkle, a Merkle tree, also known as a hash tree, is a data structure that ensures the integrity of data verification in Bitcoin. Its tree-like structure enables lightweight nodes to verify transactions without having to download the entire block by encoding all transactions in a block into a single hash, known as the Merkle root, which is then included in the block header.
Below is an example of how a Merkle tree might look for a block with four transactions:
Merkle Root
|
_______|_______
| |
Hash 01 Hash 23
| |
___|___ ___|___
| | | |
Hash0 Hash1 Hash2 Hash3
| | | |
Tx0 Tx1 Tx2 Tx3
- Tx0, Tx1, Tx2, Tx3: the individual transactions included in a Bitcoin block.
- Hash0, Hash1, Hash2, Hash3: the hashes of the individual transactions.
- Hash 01: the hash of the concatenation of Hash0 and Hash1.
- Hash 23: the hash of the concatenation of Hash2 and Hash3.
- Merkle root: This is the hash of Hash 01 and Hash 23 concatenation embedded into the block header.
If someone wants to verify that a particular transaction is included in a block, they do not have to download every transaction. Instead, they can download the top part of the Merkle tree (the root) along with a Merkle path (the set of hashes needed to reconstruct the Merkle root from a single transaction).