Timechain Wiki

Merkle trees

11 min read

A Merkle tree is a binary tree of hashes: the leaves contain hashes of individual data items, every internal node contains the hash of its two children concatenated together, and the Merkle root at the top is a single hash that commits to the entire dataset. The structure was introduced by Ralph Merkle in his 1979 PhD thesis and has become a foundational primitive across cryptographic systems. Bitcoin uses Merkle trees in two principal places: every block contains a Merkle root in its header committing to all the transactions in the block; and Taproot (BIP-341, 2021) uses a Merkle-like structure (the TapTree) to commit to alternative spending scripts. The structural property that makes Merkle trees useful is efficient inclusion proofs — to prove that a specific transaction is in a block, you only need the transaction itself plus log₂(n) sibling hashes along the path to the root. A 4000-transaction block requires only ~12 hashes (~400 bytes) to prove inclusion of any specific transaction, rather than the full ~1-2 MB block. This efficiency is what enables SPV (Simplified Payment Verification) light-client architecture.

Why this note matters

Merkle trees are the load-bearing primitive for two distinct Bitcoin capabilities: commitment and efficient verification of inclusion. The Merkle root in a block header is a tamper-evident commitment to the entire transaction set — change any byte of any transaction, and the root changes. The inclusion-proof property is what makes SPV light clients viable: a wallet running on a phone, holding only block headers (80 bytes each, ~4 MB per year), can verify that a specific payment was confirmed by requesting a Merkle proof rather than the full block.

The Taproot upgrade (2021) extended the Merkle-tree primitive to script-level commitments: a Taproot output commits via Merkle tree to multiple alternative spending paths, and a spender reveals only the path they actually used. This is one of Taproot’s load-bearing efficiency and privacy properties.

This note is the structural reference for both uses; the operational implications surface in Full nodes vs pruned vs SPV and Bitcoin Script and opcodes.

The construction

A Merkle tree is built bottom-up from a set of data items:

  1. Leaves. Hash each data item individually: leaf_i = H(data_i). In Bitcoin’s main Merkle tree, the data items are transaction IDs (themselves double-SHA-256 hashes of serialized transactions). The “hash of a hash” sequence is conventional.
  2. Pair leaves into nodes. Take adjacent leaves in pairs; hash the concatenation: node = H(leaf_left || leaf_right). This produces the next level up, with half as many nodes.
  3. Repeat upward. Pair nodes at each level, hashing the concatenation, until exactly one node remains.
  4. That final node is the Merkle root — a single hash committing to the entire input set.

If the number of items at any level is odd, the last item is duplicated (Bitcoin’s specific quirk; see Tradeoffs) so that pairing always works out.

For n input items, the tree has roughly log₂(n) levels and computes roughly 2n - 1 hashes total. The root is exactly one hash regardless of n.

The inclusion-proof property

The structural advantage of a Merkle tree is that proving any single item is in the tree requires only log₂(n) hashes, not the full tree.

To prove that item x is in a tree with root R:

  1. The prover provides x plus the siblings of every node on the path from x’s leaf up to the root (~log₂(n) hashes).
  2. The verifier hashes x to get the leaf; pairs it with the first sibling; hashes; pairs with the next sibling; etc.; arrives at a candidate root.
  3. If the candidate root equals R, the proof is valid: x must be in the tree.

This is the Merkle proof (or “Merkle branch” or “inclusion proof”). For a 4096-transaction block, the proof requires ~12 hashes — roughly 400 bytes — compared to the megabyte-scale full block. The asymmetry is what makes SPV viable.

Where Bitcoin uses Merkle trees

1. Block-level transaction commitment. Every Bitcoin block header includes a 32-byte Merkle root field. The root commits to all transactions in the block, in their canonical order. The leaves are transaction IDs (double-SHA-256 of each serialized transaction); internal nodes apply double-SHA-256 to the concatenation of children. See Blocks and the blockchain for the block-header structure.

The Merkle root in the header is what miners actually hash for Proof of Work. A miner trying nonces is hashing an 80-byte block header whose Merkle root has already been committed to. If the miner wants to modify the transaction set (e.g., to insert a transaction), they must rebuild the Merkle tree, generating a new root, and start the PoW search over from scratch. This binds transaction selection to the PoW expenditure.

2. SPV (Simplified Payment Verification). A light client that does not store the full blockchain can still verify that a transaction was confirmed by:

  • Obtaining all block headers (a chain of 80-byte headers, ~4 MB/year of growth)
  • Querying a server for the Merkle proof connecting a specific transaction to its block’s Merkle root
  • Hashing through the proof to confirm the computed root matches the header’s root
  • Confirming the header is in the longest chain at sufficient depth

The trust model: SPV trusts the longest chain (work-based), but does not trust the server providing the proofs about the transaction set itself — the proof either verifies or it doesn’t. This is the formal mechanism behind Full nodes vs pruned vs SPV.

3. Taproot script trees (TapTree). BIP-341 Taproot extends Merkle-tree commitment to alternative spending scripts. A Taproot output can commit to a tree of alternative script branches; at spend time, the spender reveals which branch they’re using plus the Merkle proof connecting that branch to the committed root.

The TapTree uses tagged hashes (a domain-separation construction over SHA-256 — see SHA-256) rather than double-SHA-256, providing cleaner cryptographic separation between hashing contexts. The tree is also explicitly hash-sorted at each level (the smaller hash always goes left), preventing certain malleability attacks.

The privacy property: only the spent branch is revealed; the other branches stay hidden. A multisig setup using 10 alternative quorum combinations can use a TapTree to commit to all 10 while only revealing the specific combination actually used at spend time.

4. Compact Block Filters (BIP-157/158). Modern light clients (alternatives to BIP-37 SPV) use compact block filters instead of Merkle proofs for transaction-of-interest detection. Filters are not Merkle-tree-based, but Merkle proofs remain available for full inclusion verification when needed.

The “duplicate the last leaf” quirk

Bitcoin’s specific Merkle tree construction handles odd-numbered levels by duplicating the last item before pairing. If a level has, say, 7 nodes, the 7th is duplicated to form an 8th, then pairs of 4 are hashed normally.

This quirk introduced the CVE-2012-2459 vulnerability: an attacker could construct a malicious block where a transaction at the tail of the tree could be silently duplicated without changing the Merkle root. The bug was fixed in 2012; current node implementations check for this pattern explicitly and reject blocks containing it. The quirk itself remains in the protocol’s Merkle root computation (a hard fork would be required to change it), but the validation rules catch the abuse pattern.

Taproot’s TapTree avoided this design entirely by using a different construction: pairs are sorted by hash value, and the tree handles odd-counts via a different mechanism (essentially treating an unpaired node as “its own sibling” at a higher level rather than duplicating).

Properties the primitive provides

What Merkle trees give Bitcoin:

  • Tamper-evidence. Any change to any leaf data cascades to a different root. The block header’s Merkle root is a cryptographic commitment to the exact transaction set.
  • Compact commitment. A single 32-byte hash commits to arbitrary-many transactions. Block headers stay 80 bytes regardless of how many transactions a block contains.
  • Efficient inclusion proofs. O(log n) hashes prove membership; this is the structural enabler of SPV.
  • Selective revelation. In Taproot’s TapTree, only the used branch is revealed; others stay hidden. Useful for privacy and for representing complex spending policies compactly.

What Merkle trees do NOT give Bitcoin:

  • Non-inclusion proofs by default. Proving that a transaction is not in a block requires either a different structure (e.g., a sorted Merkle tree) or scanning the full set. Bitcoin’s mainline Merkle tree is unsorted; non-inclusion is asserted by scanning headers and finding the relevant transactions.
  • Privacy of the tree contents. The tree commits to the set, but a node that has the full block can see every transaction. Merkle commitment is not encryption.
  • Order-independence. Bitcoin’s Merkle tree is sensitive to leaf order; transactions in different orders produce different roots. Taproot’s TapTree is sort-based at each level, which decouples the canonical structure from leaf ordering.

Tradeoffs and design choices

Why pair-based (binary) trees specifically? Higher-arity trees (e.g., 4-ary, 8-ary) would reduce tree depth but increase the number of sibling hashes needed at each level for proofs. Binary trees are the optimal balance for hash-based inclusion proofs and are the default across cryptographic systems.

Why double-SHA-256 as the internal hash function? Consistent with the rest of Bitcoin’s hashing. See SHA-256 for the rationale for double-application. Modern Bitcoin (Taproot) shifts to tagged hashes, which are cleaner cryptographically but were not available in 2008.

The duplicate-last-leaf vulnerability. As discussed above. The protocol has lived with this quirk since 2009 through validation-side fixes; the structural issue would require a hard fork to address cleanly.

Merkle-Mountain Ranges and successor structures. Several proposed extensions to Bitcoin (e.g., UTREEXO accumulators, MMR-based commitments) replace the per-block Merkle tree with rolling commitments that span the chain. These are research-stage as of 2026; the main protocol’s per-block Merkle tree remains the production primitive.

Privacy limits of the TapTree commitment. While unspent branches stay hidden, the structure of the tree (the number of branches, the depth) leaks information. A TapTree with 256 branches reveals “the spender had 256 alternatives” even if only one was used. For most use cases this is acceptable; for high-privacy applications it can be a fingerprint.

For substantive engagement with the limits of light-client architecture that Merkle proofs enable, see Full nodes vs pruned vs SPV; for the Taproot-specific TapTree implications, see Bitcoin Script and opcodes.

Open questions for further development

  • Should Bitcoin migrate the legacy block-level Merkle tree to a structure without the duplicate-last-leaf quirk? Doing so requires a hard fork; the pragmatic argument is to leave the legacy structure alone since validation rules already catch the abuse pattern.
  • How will UTREEXO and similar accumulator structures interact with Merkle-based block commitments if they’re eventually deployed?
  • Does the TapTree’s branch-count leak (revealing the total number of alternatives even when only one is spent) become a substantive privacy concern as Taproot adoption grows?
  • For SPV clients specifically, is the bandwidth saved by Merkle proofs sufficient to justify the trust model, or has the rise of efficient compact-block-filter clients made Merkle-proof SPV obsolete? Operational consensus in 2026 is leaning toward compact filters for new wallets.

Canonical sources for this note

Original sources

  • Ralph C. Merkle, Secrecy, Authentication, and Public Key Systems (Stanford PhD thesis, 1979) — the foundational source where Merkle trees were introduced.
  • Ralph C. Merkle, “Protocols for Public Key Cryptosystems,” 1980 IEEE Symposium on Security and Privacy.

Bitcoin engineering references

  • Mastering Bitcoin, Andreas Antonopoulos (chapter 7: “The Blockchain”, section on “Merkle Trees”) — the canonical engineering treatment. See Mastering Bitcoin - Andreas Antonopoulos.
  • Programming Bitcoin, Jimmy Song (chapter 11: “Merkle Tree”) — working-programmer treatment, including the construction and inclusion-proof verification code.
  • Bitcoin Wiki entry on Merkle trees — Bitcoin-specific notes.

Bitcoin Improvement Proposals

  • BIP-37 — original SPV with bloom filters (Mike Hearn et al.). Largely deprecated in favor of compact block filters.
  • BIP-157 / BIP-158 — compact block filters (the modern light-client alternative to BIP-37 SPV).
  • BIP-340 — Schnorr signatures and tagged-hash construction (relevant for TapTree).
  • BIP-341 — Taproot, including TapTree script-tree commitment.

Cryptographic foundations

  • Handbook of Applied Cryptography, Menezes et al. (chapter 9.4: “Data Integrity and Message Authentication”) — covers hash-tree constructions in the broader cryptographic context.
  • SHA-256 — The hash function underlying Bitcoin’s Merkle tree (double-SHA-256 for the main tree; tagged-SHA-256 for TapTree).
  • Public key cryptography — Companion foundational primitive; Merkle trees commit to data; signatures authorize spends.
  • Signature schemes in Bitcoin — Taproot (Schnorr) introduces the TapTree construction; this note links to those mechanisms.
  • Blocks and the blockchain — Block headers contain the Merkle root field; this note is the deferral target for how that root is computed.
  • UTXO model and Bitcoin transactions — Transactions are the leaves of the block-level Merkle tree; their TXIDs are what the tree commits to.
  • Full nodes vs pruned vs SPV — SPV is the principal application of Merkle inclusion proofs; this note is the upstream mechanism reference.
  • Bitcoin Script and opcodes — TapTree commits to alternative script branches; spending mechanics reference this note.
  • Pieter Wuille — Co-author of BIP-341 Taproot, including the TapTree construction.

Graph View

Backlinks