TL;DR: A Merkle tree is a tree data structure that summarizes a large set of data into a single hash, called the Merkle root. In Bitcoin, every block contains a Merkle tree that summarizes all the block’s transactions: the Merkle root occupies 32 bytes of the block header (80 bytes total). This structure makes it possible to prove that a transaction is included in a block with just a few hundred bytes, without downloading the entire block. The concept was described by Ralph Merkle, who patented it in 1979.
A Merkle tree (or hash tree) is a tree data structure used to efficiently summarize and verify the integrity of large sets of data. It is named after Ralph Merkle, the computer scientist who patented the concept in 1979.
In Bitcoin, the Merkle tree is a fundamental component: every block in the blockchain contains one, organizing all of the block’s transactions and summarizing them into a single 32-byte hash known as the Merkle root.
What is a Merkle tree?
A Merkle tree is a binary tree built using hash functions. The “leaves” at the base of the tree are the hashes of individual pieces of data (in Bitcoin, transaction identifiers). Each higher level is obtained by concatenating pairs of hashes from the level below and computing the hash of the result, until a single hash remains at the top: the Merkle root.
The advantages are twofold:
- Compression: thousands of transactions are represented by a single 32-byte hash.
- Verifiability: proving that a piece of data belongs to the set requires only a small number of intermediate hashes (the Merkle proof), without transmitting the entire dataset.
If even a single bit of a transaction changes, its hash changes, all intermediate hashes along the path change, and the Merkle root changes: any tampering is immediately detectable.
How does a Merkle tree work? A step-by-step example
Imagine a block with four transactions: A, B, C, and D.
- The hash of each transaction is computed: H(A), H(B), H(C), H(D). In Bitcoin, the function used is SHA-256 applied twice (double SHA-256).
- The hashes are paired and the hash of each pair is computed: H(AB) = hash of H(A)+H(B); H(CD) = hash of H(C)+H(D).
- The process is repeated on the final level: the Merkle root is the hash of H(AB)+H(CD).
To prove that transaction C is included in the block, only two hashes are needed: H(D) and H(AB). The verifier computes H(C), combines it with H(D) to obtain H(CD), combines H(CD) with H(AB), and checks that the result matches the Merkle root in the block header. This path is called a Merkle proof (or Merkle path).
The number of hashes required grows logarithmically: for a block with over 2,000 transactions, roughly 11–12 hashes suffice — just a few hundred bytes. If the number of transactions is odd, the last hash is duplicated and paired with itself.
How Bitcoin uses the Merkle tree
The Merkle root in the block header
Every Bitcoin block consists of an 80-byte header and a body containing the transactions. The header includes six fields: the version, the hash of the previous block, the Merkle root, the timestamp, the difficulty target, and the nonce.
The Merkle root is therefore the only “summary” of the transactions that enters the block header. When miners search for a valid hash for the block, they work solely on the 80-byte header: the Merkle root ensures that header is cryptographically bound to the exact list of included transactions. Altering a transaction after the fact would require recalculating the Merkle root and redoing the proof of work for that block and all subsequent blocks.
SPV and Merkle proof: verifying without downloading everything
The Merkle tree is what makes Simplified Payment Verification (SPV) possible, as described by Satoshi Nakamoto in section 8 of the Bitcoin whitepaper. An SPV client (such as many mobile wallets) does not download the entire blockchain: it downloads only the block headers, 80 bytes each.
To verify that a payment has been received, the client requests a Merkle proof from a full node: a handful of hashes linking the transaction to the Merkle root of a header it already holds. If the path checks out, the transaction is confirmed as included in that block, and subsequently mined blocks confirm its depth. All of this without downloading and validating hundreds of gigabytes of data.
Where are Merkle trees used beyond Bitcoin?
Merkle trees are used in a variety of applications, including:
- File systems: used to verify the integrity of files within distributed file systems such as the InterPlanetary File System (IPFS).
- Database systems: used to detect inconsistencies among replicas of entire NoSQL databases such as Apache Cassandra and Amazon DynamoDB.
- Version control systems: some of the most widely used version control systems, such as Git and Mercurial, use Merkle trees to manage versions of files and directories.
Frequently asked questions
What is the Merkle root?
It is the hash at the top of the Merkle tree, summarizing all of a block’s transactions into 32 bytes. In Bitcoin, it is one of the six fields in the block header.
Who invented the Merkle tree?
American computer scientist Ralph Merkle, who patented the concept in 1979. The structure predates Bitcoin and is used in many other systems.
What is the Merkle tree used for in Bitcoin?
It cryptographically binds the list of transactions to the block header and makes it possible to prove the inclusion of a transaction using a Merkle proof, without transmitting the entire block.
What is a Merkle proof?
It is the set of intermediate hashes that links a transaction to the Merkle root. For a block with thousands of transactions, around a dozen hashes are sufficient.
What does SPV stand for?
Simplified Payment Verification: the method, described in the Bitcoin whitepaper, by which a lightweight wallet verifies payments by downloading only block headers and requesting Merkle proofs from full nodes.
