Merkle trees

Understand how a Merkle tree hashes a set of items into a single root, how inclusion (and, with ordering, exclusion) proofs let a verifier confirm membership in logarithmic size, and where tamper-evident sets and light verification use this.

Track

Fundamentals

Module

2 · Applied cryptography for agents

Prerequisites

Hash functions

Suppose you have a million records and want one short value that fixes all of them, such that changing any single record changes that value — and such that you can later prove a specific record is included without sending the other 999,999. A Merkle tree (hash tree) does exactly this. Leaves are the hashes of individual items; each internal node is the hash of its two children; the single node at the top, the Merkle root, is a fingerprint of the entire set. The root is the commitment; small proofs relate any item back to it.

The security of a Merkle tree reduces to the collision resistance of its hash function: if you cannot find two inputs with the same digest, you cannot produce two different sets with the same root, nor a false proof for a non-member.

Merkle root

The single top digest committing to the whole ordered set of leaves. Publishing it commits you to every leaf and their arrangement.

Inclusion (audit) proof

The list of sibling hashes along the path from a leaf to the root — about log2(n) hashes. A verifier recomputes the root from the leaf and the siblings and checks it matches the trusted root.

Exclusion proof

A proof that an item is NOT in the set. It requires the tree to be ordered/sorted (a sorted Merkle tree or a Merkle Patricia/trie); you prove inclusion of the two adjacent leaves that would surround the item, leaving no gap for it. A plain unsorted Merkle tree cannot prove non-membership.

Construction hashes leaves, then repeatedly hashes adjacent pairs until one root remains. Verification replays only the path for the item of interest.

build root + verify an inclusion proof
# Build (n leaves; H = collision-resistant hash)
level = [ H(0x00 || item_i) for item_i in items ]     # 0x00 = leaf-domain tag
while len(level) > 1:
  next = []
  for (l, r) in pairs(level):                          # duplicate last if odd
    next.append( H(0x01 || l || r) )                   # 0x01 = node-domain tag
  level = next
root = level[0]

# Inclusion proof for leaf at index k:  path = [sibling hashes bottom->top]
Verify(item, k, path, trusted_root):
  h = H(0x00 || item)
  for (sibling, side) in path:
    h = H(0x01 || sibling || h)  if side=="left"  else  H(0x01 || h || sibling)
  return h == trusted_root

# Proof size and verify cost: ~ log2(n) hashes, not n.

Two engineering details prevent real attacks. Distinct domain tags for leaves (0x00) and internal nodes (0x01) stop second-preimage attacks that pass off an internal node as a leaf. And the leaf-vs-node distinction, plus a fixed rule for odd levels, must be specified exactly — RFC 6962 (Certificate Transparency) does this and is a good template.

1. 1Fix a canonical encoding for items and an ordering (sorted if you will need exclusion proofs).
2. 2Hash each item into a leaf using a leaf-domain tag.
3. 3Hash adjacent pairs with a node-domain tag, level by level, up to a single Merkle root.
4. 4Publish or sign the root — that one value now commits to the whole set.
5. 5To prove an item is included, send the item plus its ~log2(n) sibling hashes; the verifier recomputes the root and compares to the trusted root.
6. 6To prove an item is absent (sorted tree), prove inclusion of the two neighbors that bracket where it would sit.

synthetic — proving one audit record without the log
# An auditor trusts only the signed root of today's agent-action log.
root = signed_root_for("2026-10-17")      # e.g. commits to 1,000,000 actions

# To prove action #412,019 is in the log, the server sends ~20 hashes:
proof = merkle_path(index=412019)          # log2(1e6) ~= 20 sibling hashes
ok = Verify(action_412019, 412019, proof, root)   # recompute -> compare root

# The auditor never downloads the other ~1,000,000 records,
# yet a single altered record anywhere would change the root and fail the check.

This is "light verification": the verifier holds only a trusted root and checks membership with a proof whose size grows logarithmically. It is why Merkle proofs scale — a 20-hash proof certifies membership in a million-item set, and the same mechanism underlies light clients in distributed systems.

Merkle trees give agent systems compact, tamper-evident commitments. A fleet can commit to the day’s set of authorized actions, policy versions, or allow-lists as a single signed root, and any component can later be handed a short proof that a specific action or policy was part of that committed set — without shipping the entire set around. A lightweight verifier (a constrained worker, an external auditor) can confirm membership against only the root it trusts. Merkle roots are also how a set-commitment is anchored into the append-only, hash-chained logs covered in the next lesson, and they pair naturally with signatures: sign the root, and every proof inherits that authority.

• ▸Without distinct leaf/node domain tags, an attacker can reinterpret an internal node as a leaf (a second-preimage-style confusion); always tag leaves and nodes differently.
• ▸A plain Merkle tree proves inclusion only. Exclusion/non-membership requires a sorted tree or trie; do not assume you can prove absence from an unordered tree.
• ▸The root is only as trustworthy as how you obtained it: a proof verifies against a root, so an attacker who can feed you a false root defeats everything. Authenticate the root (sign it, or anchor it in a transparency log).
• ▸Security reduces to the hash’s collision resistance; a broken hash (MD5/SHA-1) breaks the tree.
• ▸Proofs reveal structural position and neighbor hashes; if leaves are low-entropy or sensitive, a proof may leak information — consider salting leaves.
• ▸A valid inclusion proof shows an item was committed, not that committing it was correct or authorized. Membership is not validity.

Expected direction: About 20 hashes, because the proof is one sibling per level and the tree has log2(1,048,576) = 20 levels; verify cost is ~log2(n). You cannot prove absence from a plain (unordered) Merkle tree because there is no way to show no leaf equals the item without revealing all leaves; exclusion proofs require a sorted/ordered tree (or trie), where you prove inclusion of the two adjacent leaves that bracket the missing item, leaving no room for it.

What single value commits to an entire Merkle-tree set, and what property makes it tamper-evident?

The Merkle root. Collision resistance of the hash makes it tamper-evident: changing any leaf changes the root, and you cannot find a different set with the same root.

Why is a Merkle inclusion proof only about log(n) in size?

Because it carries just one sibling hash per level along the path from the leaf to the root, and a balanced tree over n leaves has about log2(n) levels.

What extra condition is needed to prove an item is NOT in the set?

The tree must be ordered/sorted (or a trie); you then prove inclusion of the two adjacent leaves that would surround the item, showing there is no gap for it. A plain unsorted tree cannot prove non-membership.