Merkle Trees: Construction, Inclusion Proofs, and Variants

Summary

A Merkle tree summarizes a dataset with a single cryptographic root hash.

It makes it possible to verify that an item belongs to the dataset using only a logarithmic number of hashes, without downloading or reprocessing everything.

Introduction

A Merkle tree is a hash-based structure for efficiently verifying the integrity of a dataset. Each leaf commits to one data block, while each internal node commits to its children. The final node, the Merkle root, commits to the entire ordered dataset.

Changing a block changes its leaf hash and every ancestor up to the root. A trusted root can therefore be used to detect tampering and to verify individual items.

Merkle trees are a useful building block in distributed storage, version control, blockchains, and append-only transparency logs.

What problem do Merkle trees solve?

Suppose a client knows the correct digest of a very large dataset and receives one item from an untrusted server. Rehashing or transferring the complete dataset just to validate that item would be wasteful.

A Merkle tree separates two costs:

Building the commitment requires hashing the dataset.
Verifying one item requires only the item and one sibling hash per tree level.

For a balanced binary tree containing n leaves, the second cost is O(log n) in both proof size and hashing work. The proof establishes inclusion relative to a particular root; trusting that root is a separate problem, usually handled by a signature, consensus protocol, or trusted distribution channel.

Constructing a binary Merkle tree

Given four data blocks D1, D2, D3, and D4, define separate hash functions for leaves and internal nodes:

leaf(data)        = SHA-256(0x00 || data)
node(left, right) = SHA-256(0x01 || left || right)

The distinct prefixes provide domain separation: a raw data block cannot be confused with the encoding of an internal node.

The tree is then constructed bottom-up:

L1 = leaf(D1)                 L2 = leaf(D2)
L3 = leaf(D3)                 L4 = leaf(D4)
 
N1 = node(L1, L2)            N2 = node(L3, L4)
 
Root = node(N1, N2)

graph TD
    Root["Root = node(N1, N2)"]
    N1["N1 = node(L1, L2)"]
    N2["N2 = node(L3, L4)"]
    L1["L1 = leaf(D1)"]
    L2["L2 = leaf(D2)"]
    L3["L3 = leaf(D3)"]
    L4["L4 = leaf(D4)"]

    Root --> N1
    Root --> N2
    N1 --> L1
    N1 --> L2
    N2 --> L3
    N2 --> L4

The order and encoding rules are part of the tree definition. Two implementations can use the same hash algorithm and data but produce different roots if they serialize nodes differently or handle incomplete levels differently.

In the implementation below, an unpaired final node is duplicated at each level. This is a common convention, notably in Bitcoin transaction trees, but it is not universal. Certificate Transparency, for example, defines a different splitting rule.¹ A protocol must specify its convention precisely.

Minimal Python implementation

The following example computes a root, constructs an inclusion proof, and verifies it. Each proof step records both the sibling hash and whether that sibling belongs on the left or right.

import hashlib
import hmac
from typing import Literal, TypeAlias
 
Side: TypeAlias = Literal["left", "right"]
Proof: TypeAlias = list[tuple[Side, bytes]]
 
 
def hash_leaf(data: bytes) -> bytes:
    return hashlib.sha256(b"\x00" + data).digest()
 
 
def hash_node(left: bytes, right: bytes) -> bytes:
    return hashlib.sha256(b"\x01" + left + right).digest()
 
 
def next_level(nodes: list[bytes]) -> list[bytes]:
    current = nodes.copy()
    if len(current) % 2 == 1:
        current.append(current[-1])
 
    return [
        hash_node(current[i], current[i + 1])
        for i in range(0, len(current), 2)
    ]
 
 
def merkle_root(data_blocks: list[bytes]) -> bytes | None:
    if not data_blocks:
        return None
 
    nodes = [hash_leaf(data) for data in data_blocks]
    while len(nodes) > 1:
        nodes = next_level(nodes)
    return nodes[0]
 
 
def merkle_proof(data_blocks: list[bytes], index: int) -> Proof:
    if not data_blocks:
        raise ValueError("cannot prove inclusion in an empty tree")
    if index < 0 or index >= len(data_blocks):
        raise IndexError("leaf index out of range")
 
    nodes = [hash_leaf(data) for data in data_blocks]
    position = index
    proof: Proof = []
 
    while len(nodes) > 1:
        if len(nodes) % 2 == 1:
            nodes.append(nodes[-1])
 
        sibling_index = position ^ 1
        side: Side = "left" if sibling_index < position else "right"
        proof.append((side, nodes[sibling_index]))
 
        nodes = next_level(nodes)
        position //= 2
 
    return proof
 
 
def verify_proof(
    data: bytes,
    proof: Proof,
    expected_root: bytes,
) -> bool:
    current = hash_leaf(data)
 
    for side, sibling in proof:
        if side == "left":
            current = hash_node(sibling, current)
        elif side == "right":
            current = hash_node(current, sibling)
        else:
            raise ValueError(f"invalid proof side: {side}")
 
    return hmac.compare_digest(current, expected_root)

An empty dataset has no root in this API, so merkle_root([]) returns None. Proof construction rejects an empty dataset or an invalid index. A one-leaf tree has the leaf hash as its root and an empty inclusion proof.

This is intentionally a teaching implementation. A production protocol must also define serialization, maximum input sizes, hash agility, proof encoding, and resource limits.

Inclusion proof example

To prove that D3 belongs to the four-leaf tree, the verifier does not need D1, D2, or D4. It needs only two sibling hashes:

Level	Sibling hash	Position
Leaf pair	`L4 = leaf(D4)`	Right of `L3`
Subtree pair	`N1 = node(L1, L2)`	Left of `N2`

Starting with L3 = leaf(D3), the verifier reconstructs:

N2   = node(L3, L4)
Root = node(N1, N2)

The proof is valid only if the reconstructed root equals the trusted root. For a balanced tree, doubling the number of leaves adds only one proof element, which explains the logarithmic proof size.

The implementation can be exercised as follows:

blocks = [b"D1", b"D2", b"D3", b"D4"]
root = merkle_root(blocks)
assert root is not None
 
proof = merkle_proof(blocks, 2)
assert verify_proof(b"D3", proof, root)
assert not verify_proof(b"tampered", proof, root)
 
wrong_side: Proof = [("left", proof[0][1]), *proof[1:]]
assert not verify_proof(b"D3", wrong_side, root)
 
wrong_hash: Proof = [(proof[0][0], b"\x00" * 32), *proof[1:]]
assert not verify_proof(b"D3", wrong_hash, root)
 
assert merkle_root([]) is None
assert merkle_root([b"only"]) == hash_leaf(b"only")
 
odd_blocks = [b"D1", b"D2", b"D3", b"D4", b"D5"]
odd_root = merkle_root(odd_blocks)
assert odd_root is not None
assert verify_proof(b"D5", merkle_proof(odd_blocks, 4), odd_root)

Major variants

Binary Merkle tree

The form used above is well suited to ordered batches and append-only logs. Its simple structure gives compact inclusion proofs, but key lookup requires an external index. Update cost depends on the layout: changing a known leaf requires rehashing its path to the root, while inserting data may also require restructuring or a protocol-specific append algorithm.

Merkle Patricia trie

A Merkle Patricia trie combines a cryptographic commitment with a compressed prefix trie. Keys determine paths, so the structure supports verifiable key-value lookup rather than only positional lookup.

Ethereum’s execution-layer state is encoded in a modified Merkle Patricia trie, with branch, leaf, and extension nodes and protocol-specific encodings.² This is substantially more complex than the binary example and should not be treated as a drop-in variant of it.

Sparse Merkle tree

A sparse Merkle tree represents a very large, fixed key space—often one path per possible key hash. Most empty subtrees are implicit and represented by precomputed default hashes.

Its fixed paths make both inclusion and non-inclusion proofs natural: reaching the protocol-defined empty value proves that a key is absent relative to the root. The trade-off is a fixed logical depth and more hashing unless implementations use caching, compression, or batching.

Merkle DAG

A Merkle directed acyclic graph allows a node to be referenced by multiple parents. Each node identifier commits to its payload and links, making nodes immutable and content-addressed.³

IPFS uses Merkle DAGs to support content addressing and partial retrieval. Git uses related content-addressed graph ideas, although its object model and hashing rules are its own rather than a generic binary Merkle tree.

Comparison

Structure	Best suited to	Key strength	Main trade-off
Binary Merkle tree	Ordered batches and logs	Simple, compact inclusion proofs	Needs an external key index
Merkle Patricia trie	Verifiable key-value state	Lookup and integrity in one structure	Encoding and update complexity
Sparse Merkle tree	Large fixed key spaces	Natural non-inclusion proofs	Fixed logical depth
Merkle DAG	Storage and versioned graphs	Content addressing and deduplication	Traversal and garbage collection

Real-world uses

Certificate Transparency uses Merkle trees for efficient inclusion and consistency proofs over append-only certificate logs.¹
Ethereum commits to execution-layer state using modified Merkle Patricia tries.²
IPFS links immutable, content-addressed objects in Merkle DAGs.³
Distributed storage and databases can compare subtree hashes to locate differences without retransmitting identical regions.

Guarantees and limitations

Merkle trees provide useful guarantees, but only under explicit assumptions:

Integrity, not authenticity: a root detects changes relative to itself, but it must come from a trusted source.
Collision resistance: security depends on the selected hash function and unambiguous node encoding.
Protocol-specific ordering: positional trees commit to order; key-addressed variants derive paths from keys.
Variant-specific absence proofs: ordinary positional trees do not automatically prove that an arbitrary key is absent.
Update costs: updating a leaf rehashes its ancestor path, but insertion and deletion behavior depends on the tree design.
Metadata leakage: a proof can reveal a leaf’s position or surrounding structure, depending on its encoding.

Conclusion

A Merkle tree turns a large collection into a small cryptographic commitment. Its central benefit is not merely detecting that something changed, but proving which data is consistent with a trusted root using a compact witness.

The binary tree is the simplest expression of that idea. Patricia tries add key-based navigation, sparse trees make absence proofs practical, and Merkle DAGs extend content addressing to shared graphs. In every case, the root is meaningful only together with precise rules for hashing, encoding, ordering, and trust.

IETF, RFC 9162: Certificate Transparency Version 2.0, sections 2.1 and 2.1.3. ↩ ↩²
Ethereum.org, Merkle Patricia Trie. ↩ ↩²
IPFS Docs, Merkle Directed Acyclic Graphs. ↩ ↩²

Fabien Joubert

Explorer

Merkle Trees: Construction, Inclusion Proofs, and Variants

Introduction

What problem do Merkle trees solve?

Constructing a binary Merkle tree

Minimal Python implementation

Inclusion proof example

Major variants

Binary Merkle tree

Merkle Patricia trie

Sparse Merkle tree

Merkle DAG

Comparison

Real-world uses

Guarantees and limitations

Conclusion

Table of Contents

Fabien Joubert

Explorer

Merkle Trees: Construction, Inclusion Proofs, and Variants

Introduction

What problem do Merkle trees solve?

Constructing a binary Merkle tree

Minimal Python implementation

Inclusion proof example

Major variants

Binary Merkle tree

Merkle Patricia trie

Sparse Merkle tree

Merkle DAG

Comparison

Real-world uses

Guarantees and limitations

Conclusion

Footnotes

Table of Contents