What Is a Merkle Tree?

By Kurt Wuckert Jr.

A Merkle tree is a way of organizing data so you can quickly prove that a specific item is part of a larger set without having to scan everything. It does this by using hash functions to turn data into fixed-length digital fingerprints, then combining those fingerprints layer by layer into a single “root” value that represents the whole set.

In Bitcoin, Merkle trees sit at the heart of how nodes prove that particular transactions belong in a block.

Hash Functions in the Background

Merkle trees rely on cryptographic hash functions. A hash function takes any digital input - a string, a file, a transaction - and produces a fixed-length output that behaves like a fingerprint for that input.

Modern cryptographic hash functions, such as SHA-256, have three key properties that make Merkle trees work:

  • Preimage resistance (one way):Given a hash output, it is computationally infeasible to figure out the original input that produced it.

  • Second preimage resistance (deterministic uniqueness):The same input always produces the same output, and it should be infeasible to find a different input that gives that exact output.

  • Collision resistance:It should be extraordinarily unlikely for two distinct inputs to produce the same hash. For SHA-256, the probability of a random collision is so small that for practical purposes it can be treated as impossible.

Because hash outputs are fixed in length and behave like unique identifiers for arbitrary data, they are ideal building blocks for tree structures.

Building a Merkle Tree: From Leaves to Root

To build a Merkle tree, you start with a list of data items. For clarity, imagine items labeled A through P.

  1. Leaf layer (layer 0):Each data item is passed through a hash function.

    • A becomes H(A)

    • B becomes H(B)

    • … and so on, up to H(P)

    These hashed values are called the leaf nodes of the tree.

  2. Interior layers:To build the next layer up, you take the leaf hashes in order, concatenate them in pairs, and hash the result. For example:

    • H(A) and H(B) are concatenated as H(A) || H(B) and then hashed to form a new node.

    • H(C) and H(D) are combined in the same way, and so on.

    Each of these new hashes is an interior node in the tree.

  3. Repeat until you reach the root:You continue this process layer by layer. At each step, you take hashes from the current layer in pairs, concatenate them, and hash again to form the next layer up. Eventually, you end up with a single hash at the top. This is the Merkle root. It serves as a compact representation of all the data items below it.

By convention, the leaf layer is called layer 0. The next layer up is layer 1, and the numbering continues until you reach the root.

Tree Depth and Number of Layers

Each additional layer in a Merkle tree summarizes twice as many data items as the one below it.

  • A tree with 4 leaf nodes will have 3 layers:layer 0 (leaves), layer 1 (two interior nodes), and the root.

  • A tree with 8 leaf nodes will have 4 layers.

  • A tree with 16 leaf nodes will have 5 layers.

In general, whenever the number of leaves doubles, you add one more layer to the tree.

This structure is powerful because it allows a verifier to prove that a single data item is part of the tree using only:

  • The hash of that item,

  • A handful of sibling hashes along the path to the root,

  • And the known Merkle root at the top.

Why Use a Merkle Tree?

Merkle trees exist to make data verification fast and efficient. Because hash functions are deterministic, a single bit flip anywhere in the underlying data will change the hash at that position and every hash above it on that branch, all the way up to the root. That means a particular Merkle root can only come from one specific set of leaf values in one specific order. If the root matches, you know the entire set matches.

Merkle Proofs: Verifying a Single Entry

To check that a specific piece of data is included in a Merkle tree, you do not need the whole dataset. You only need:

  • The data you care about, and

  • A short list of hashes called the Merkle path.

For example, suppose you want to verify that element K is part of a tree with Merkle root R. You hash K to get H(K), then combine it with the hashes on its path: H(L), H(IJ), H(MNOP), and H(ABCDEFGH). At each step you concatenate the appropriate values in order and hash again, climbing up the tree until you recompute a candidate root R′. If R′ equals the known root R, you have proven that K is in the set. This is a Merkle proof.

The power of this approach is that you only need a number of hashes proportional to log₂(n), where n is the number of leaves. You also do not have to reveal the underlying data for the other leaves; their hashed values are enough to complete the proof, which is helpful when some data is sensitive.

Efficiency in Distributed and Peer-to-Peer Systems

In distributed and peer-to-peer systems, many copies of similar data live on different machines. Verifying every object directly would be slow and bandwidth heavy. Hashing those objects and organizing them in a Merkle tree lets participants work with compact hash values instead.

If two peers want to confirm they have the same dataset, they can first compare Merkle roots. If the roots match, the sets match. If the roots differ, they walk down the tree together. For instance, if both sides agree on H(ABCDEFGH) but disagree on HIJKLMNOP, they know the inconsistency is only in the right-hand branch. They can keep drilling down until they isolate exactly which element differed.

When there are multiple mismatches, more steps are required, and proofs that once passed may fail if a leaf value changes, such as a new value Q replacing L.

Where Merkle Trees Are Used

This pattern is not unique to Bitcoin. Git uses Merkle trees to track versions of files. BitTorrent uses similar structures to verify file pieces. Bitcoin uses them to summarize transactions in each block and to support efficient verification by lightweight clients.