How Merkle Trees Work in Bitcoin

A Merkle tree compresses commitments to many items into one root hash. Leaves represent items. Pairs of child hashes are combined into parent hashes until one root remains. A proof can then show that one leaf contributes to that root without transmitting every other leaf.

Bitcoin uses this pattern in more than one place, but the constructions are not interchangeable. The transaction Merkle tree, witness Merkle tree, BIP 37 partial Merkle tree, and Taproot script tree use different leaves, commitments, and validation rules.

This guide was researched on July 25, 2026 against BIPs 37, 141, 341, and 342 and Bitcoin Core 31.1 at tag v31.1, commit 9be056a8a72b624dae9623b2f7bded92c2a21c91. Historical mutation behavior is described from Bitcoin Core’s current consensus Merkle implementation and its tests.

The transaction Merkle root

Every Bitcoin block header includes a 32-byte hashMerkleRoot field. That value commits to the ordered list of transaction identifiers in the block.

Bitcoin Core constructs the root by:

1. computing or taking each transaction’s txid;
2. preserving block order, beginning with the coinbase transaction;
3. pairing adjacent 32-byte hashes;
4. concatenating each pair in the algorithm’s internal byte order;
5. applying double SHA-256 to create the parent;
6. repeating until one hash remains.

The leaf is the txid itself. The transaction is not hashed a third time as a special “leaf hash.” Its identifier is already the double SHA-256 of the non-witness serialization.

The resulting Merkle root is placed in the block header. Because the block identifier and proof of work hash the serialized header, proof of work indirectly commits to that transaction root.

Order matters

The tree commits to an ordered transaction list. Swapping two leaves generally changes parent hashes and the root.

A proof must therefore include not only sibling hashes but enough position information to determine whether each sibling belongs on the left or right. Hashing left || right is different from hashing right || left.

Human-facing transaction and block identifiers are usually displayed with reversed byte order relative to their serialized internal bytes. Merkle documentation must be explicit about whether a diagram shows conventional display hex or bytes fed into the hashing routine.

Odd-node duplication

When a level has an odd number of nodes, Bitcoin duplicates the final node and hashes the pair:

parent = double_sha256(last || last)

This is a historical Bitcoin rule. It is not a universal property of Merkle trees and should not be copied into a new design without understanding its consequences.

The duplication repeats at any odd level, not only at the transaction-leaf level. Bitcoin Core’s ComputeMerkleRoot appends the final hash when the level size is odd and then performs pairwise double-SHA-256.

A small example

Suppose a block has transaction leaves A, B, and C, where each letter represents a 32-byte txid in internal byte order.

The first level is:

• P1 = H(A || B)
• P2 = H(C || C)

The root is:

• Root = H(P1 || P2)

where H means double SHA-256.

A proof for B needs:

• A, because B is the right child paired with A;
• P2, because the A/B parent is the left child at the root level;
• the position information indicating these left/right relationships.

The verifier computes P1, then the root, and compares it with the header’s Merkle root.

What an inclusion proof establishes

If a verifier already trusts or has validated a block header, a correct Merkle branch can establish that a given txid is included in the transaction list committed by that header, assuming the hash construction’s relevant security properties.

That statement has boundaries.

A Merkle proof does not by itself prove:

• the transaction is valid under Bitcoin consensus;
• the block is valid under all consensus rules;
• the block belongs to the best valid chain;
• the transaction’s inputs were unspent;
• the transaction has a particular number of confirmations;
• the transaction cannot be reorganized out;
• the recipient controls an output;
• the transaction remains economically final.

A fully validating node checks the transaction, scripts, amounts, lock rules, block structure, proof of work, chain history, and UTXO transitions. A Merkle branch is only one commitment proof inside that larger process.

Proof size

For a balanced binary tree with N leaves, an inclusion branch needs roughly one sibling hash per tree level, so proof size grows logarithmically with N.

For example, doubling the number of transactions generally adds only one additional 32-byte sibling to a simple branch. This is the efficiency benefit: a verifier can connect one transaction to a root without receiving the full block.

The actual message also needs position data, the transaction or txid being proved, and the block header or another trusted root. BIP 37 partial Merkle trees may include more hashes than a single branch because they can prove multiple matched transactions together.

Inclusion, confirmation, and finality

A transaction is included when it appears in a block’s committed transaction list.

It has one confirmation when that valid block is part of the best chain as evaluated by a node. Each valid descendant block increases the confirmation count.

“Finality” in Bitcoin is economic and probabilistic rather than a Merkle-tree property. A chain reorganization can remove a previously included transaction from the best chain. The practical cost and likelihood of a reorganization generally change with accumulated proof of work and circumstances, but no Merkle branch turns a confirmation into an irreversible guarantee.

A proof anchored to an orphaned or invalid block header can remain mathematically correct for that header while no longer demonstrating inclusion in the node’s active chain.

The historical mutation issue

Bitcoin’s odd-node duplication creates an ambiguity when duplicate transaction identifiers appear in specific positions. Bitcoin Core’s source documents the historical issue associated with CVE-2012-2459.

Consider a level ending in two identical real child hashes. That pair can produce the same parent as a shorter level where the final child is duplicated by the odd-node rule. Under certain transaction-list patterns, distinct lists can therefore produce the same root without requiring a break of double SHA-256.

The practical historical danger involved invalid-block caching. A node could receive a mutated version with the same header hash and Merkle root, mark that block invalid, and then incorrectly reject the unmutated version.

This is a structural ambiguity in the tree algorithm, not a discovered SHA-256 collision.

Bitcoin Core mutation detection

Bitcoin Core 31.1 detects mutation while reducing each level. Before duplicating a final odd node, it checks whether any actual adjacent pair at that level contains identical hashes. If so, it marks the tree as mutated.

Block validation checks the computed root and the mutation flag. A mutated transaction tree is rejected.

The detection rule distinguishes:

• an identical pair that actually appeared in the list before odd duplication;
• the normal artificial duplicate added solely because a level had odd length.

Bitcoin Core’s source notes that, assuming no double-SHA-256 collisions, this detects the known transaction-list changes that preserve the root through the duplicate-node ambiguity.

The warning remains relevant to implementers. Reimplementing only the root calculation without mutation detection can reproduce the commitment but omit a consensus-critical validation boundary.

Duplicate transactions and other validity rules

Mutation detection is not the only protection around duplicate data. Bitcoin consensus and transaction rules impose other constraints, and a block containing duplicate transactions or duplicate-spend behavior can fail for reasons independent of the Merkle tree.

The Merkle root function should not be expected to enforce all transaction validity. It consumes identifiers and produces a commitment plus mutation information. Block validation applies the rest.

This separation illustrates a recurring rule: a cryptographic commitment does not validate the semantics of what was committed.

The witness Merkle tree

SegWit introduced a separate commitment to witness data. The ordinary transaction Merkle root still uses txid leaves, which exclude witness data. A witness tree uses wtxid leaves, which commit to witness-inclusive transaction serialization when witness data exists.

Bitcoin Core’s BlockWitnessMerkleRoot uses:

• a 32-byte zero value for the coinbase transaction’s witness leaf;
• each non-coinbase transaction’s wtxid for the remaining leaves;
• the same pairwise double-SHA-256 and odd-duplication tree algorithm.

The coinbase’s actual wtxid is not used as its leaf. BIP 141 explicitly defines the coinbase witness transaction identifier as all zeroes for this tree.

The witness commitment

The witness Merkle root is not placed directly in the block header. Instead, it is combined with a 32-byte witness reserved value from the coinbase input’s witness:

commitment = double_sha256(witness_root || witness_reserved_value)

The commitment is placed in a coinbase output script beginning with:

OP_RETURN 0x24 aa21a9ed

followed by the 32-byte commitment. If multiple outputs match the pattern, the highest-index matching output is used. A witness commitment is required when the block contains any transaction with nonempty witness data. If every transaction has empty witness data, the commitment output is optional; when a matching commitment is present, the commitment and coinbase witness rules still apply. When a witness commitment is required, the coinbase input’s witness must contain exactly one 32-byte reserved value.

Because the coinbase transaction’s txid is a leaf of the ordinary transaction Merkle tree, the block header commits to the coinbase transaction, which contains the witness commitment. This links witness data to the header without placing another root directly in the header.

The reserved value provides an extension point in the commitment construction. In currently deployed BIP 141 validation, it is included exactly as specified; it should not be described as arbitrary unused padding.

Why there are two roots

The transaction Merkle root preserves the pre-SegWit block-header structure and commits to transaction identifiers that exclude witness data. The witness commitment separately binds the witness-inclusive identifiers.

This separation supports SegWit’s compatibility design. It also means:

• a transaction’s txid and wtxid may differ;
• the transaction Merkle root and witness Merkle root are different;
• witness-only changes affect the wtxid and witness commitment, not the legacy txid;
• a transaction inclusion proof using the header Merkle root proves inclusion of the txid, not a standalone proof of its witness bytes.

A verifier that needs the witness must validate the witness commitment and relevant transaction data, not rely only on a txid Merkle branch.

Partial Merkle trees under BIP 37

BIP 37 introduced Bloom-filtered block serving and the merkleblock message for simplified payment verification clients. A merkleblock includes:

• a block header;
• the total transaction count;
• a depth-first list of selected hashes;
• packed flag bits describing which branches are expanded.

The partial tree lets the receiver reconstruct the full transaction Merkle root while extracting txids that matched the peer’s Bloom filter. Branches unrelated to matches can be represented by a single interior hash.

BIP 37 parsing rejects a partial tree when two explicitly provided child hashes are identical in a position that would reproduce the mutation ambiguity. Bitcoin Core’s partial-tree implementation also checks structural limits and whether all supplied hashes and bits were consumed appropriately.

BIP 37 privacy limitations

BIP 37’s Bloom filters can have false positives, which were intended to trade bandwidth for some uncertainty. However, a serving peer observes the filter, matched transactions, filter updates, connection metadata, and repeated queries. Accurate filters can reveal wallet-related keys, scripts, and transactions; broader filters consume more bandwidth without guaranteeing privacy.

BIP 37 also permits lying by omission. A peer can omit a relevant transaction even if it cannot fabricate a valid inclusion proof for a transaction absent from the block.

An SPV client that checks header proof of work and Merkle inclusion still does not reproduce full validation. It relies on assumptions about chain selection, peers, and the validity of blocks and transactions it does not independently verify.

Bitcoin Core’s current support and default service policy for BIP 37 are implementation- and configuration-specific. The deployed BIP remains useful for understanding partial Merkle trees, but current wallet protocols should not be assumed to use it.

The Bitcoin paper’s SPV model

The Bitcoin paper describes a simplified verification model that keeps block headers, follows the chain with the most proof of work, and obtains a Merkle branch linking a transaction to a block.

The model provides evidence that a transaction was accepted into a proof-of-work chain under the client’s assumptions. It does not give the same guarantees as validating every block and transaction. An attacker who can isolate the client, withhold information, or present an invalid high-work chain can exploit what the client does not check.

Modern lightweight-client designs may use other filters and peer strategies, but a Merkle proof alone never fills the full-validation gap.

Taproot script trees

Taproot can commit to optional scripts in a tree often called a tap tree. The construction differs from the block transaction tree.

A Taproot leaf commits to:

• a leaf version;
• the compact-size length of the script;
• the script bytes.

The tapleaf hash is:

TapLeaf = tagged_hash("TapLeaf", leaf_version || compact_size(script_length) || script)

A branch parent is:

TapBranch = tagged_hash("TapBranch", min(a, b) || max(a, b))

where the two 32-byte child hashes are ordered lexicographically before concatenation. Because of this sorting, left-versus-right position is not carried in the same way as a transaction Merkle branch.

The final script-tree root is included in the Taproot tweak applied to an internal x-only public key. The output key therefore commits to both the internal key and the optional script tree.

Control blocks and revealed branches

A Taproot script-path spend reveals:

• the tapscript;
• the control block;
• the witness data needed by the script.

The control block contains:

• a leaf version combined with the output-key parity bit;
• the 32-byte internal x-only public key;
• zero or more 32-byte sibling hashes forming the Merkle path.

The verifier recomputes the tapleaf hash, combines it with each branch sibling using lexicographic ordering and the TapBranch tag, computes the Taproot tweak, and confirms that the resulting output key matches the witness program and parity.

Only the executed leaf and its branch need to be revealed. Unused leaves can remain hidden, subject to what can be inferred from the revealed path, tree shape, wallet behavior, and other transaction information.

Taproot trees are not block transaction trees

The differences are structural:

| Property | Block transaction tree | Taproot script tree | |---|---|---| | Leaves | txids | Tagged leaf-version-and-script hashes | | Parent hash | Double SHA-256 | Tagged single SHA-256 | | Child order | Positional left then right | Lexicographically sorted | | Odd rule | Duplicate final node | Tree is constructed from chosen binary branches; no block-style odd duplication rule | | Root commitment | Direct field in block header | Included in tweak of an x-only output key | | Proof purpose | Transaction inclusion in a block | Reveal one committed script path | | Mutation handling | Bitcoin-specific duplicate-pair detection | Different construction; block mutation rule does not apply |

Calling both “Merkle trees” is useful at a high level, but implementations must use the exact construction for the exact context.

Merkleized scripts versus transaction inclusion

A Taproot control block proves that a revealed script leaf was committed by the output key, assuming the tweak and hash construction. It does not prove that a transaction containing that output was confirmed.

Conversely, a block Merkle branch can prove that a transaction identifier was included under a block root. It does not reveal or prove an unused Taproot script path.

A complete script-path spend validation may involve both layers:

• the transaction must be valid and included in a block;
• the input witness must reveal a valid Taproot path and satisfy the tapscript;
• the block and chain must satisfy consensus and proof-of-work rules.

The transaction root does not commit to the UTXO set

The block header’s transaction Merkle root commits to the ordered transactions in that block. It does not directly commit to:

• the UTXO set before the block;
• the UTXO set after the block;
• account balances;
• address balances;
• wallet ownership labels;
• spent-status proofs for arbitrary outputs.

A fully validating node derives its UTXO state by processing valid blocks in order and applying spends and creations. Bitcoin Core maintains implementation-specific databases and caches for this state, but the current UTXO set is not the leaf set of the block transaction Merkle tree.

Proposals and research have considered UTXO commitments and accumulators, but they should not be described as deployed merely because Bitcoin already uses Merkle trees elsewhere.

Confirmation proofs require chain context

To claim that a transaction has a certain number of confirmations, a verifier needs more than one Merkle branch. It needs:

• the block header containing the committed root;
• evidence that the header is part of a valid chain;
• descendant headers or validated blocks;
• the node’s chain-selection result;
• awareness of reorganizations and competing branches.

Header proof of work is necessary but not sufficient for full validation. Invalid blocks can have valid proof of work. A fully validating node also checks version and target rules, timestamps, Merkle mutation, witness commitment, transaction validity, scripts, subsidy and fees, and all applicable consensus rules.

Endianness and proof serialization

A Merkle proof implementation frequently fails not because of SHA-256 but because of byte-order assumptions.

Common distinctions include:

• displayed txid hex versus internal 32-byte hash order;
• little-endian integer serialization inside transactions and headers;
• direct byte concatenation of 32-byte hash objects;
• reversal for human display;
• left/right branch order for block trees;
• lexicographic byte comparison for Taproot branches.

Test vectors should be reproduced byte for byte. A diagram that reverses hashes for readability should say so.

Test and fuzz evidence

Bitcoin Core’s Merkle unit tests cover roots, branches, odd leaf counts, duplicate-child mutation cases, and path reconstruction. Partial Merkle-tree tests cover serialization, extraction, malformed structures, and duplicate-branch rejection. Fuzz targets exercise Merkle-block parsing and branch behavior with generated inputs.

Witness-commitment functional tests cover coinbase reserved values, matching output selection, malformed commitments, and witness data. Taproot functional and wallet vectors cover tapleaf, branch, tweak, control-block, and script-path validation.

Tests provide reproducible evidence that an implementation follows specified cases. They do not prove the entire implementation or construction is free from defects.

A Merkle-proof checklist

When evaluating a “Merkle proof,” ask:

• Which tree is this: transaction, witness, partial transaction, or Taproot script?
• What exactly are the leaves?
• Which hash construction is used for leaves and parents?
• Are child hashes positional or sorted?
• Is there an odd-node duplication rule?
• What root is trusted, and how is it committed?
• Does the proof establish inclusion only, or is separate script and transaction validation performed?
• Is the header in the active valid chain?
• How many confirmations are established, and under which node’s chain view?
• Does the claim incorrectly infer UTXO state, ownership, or irreversibility?
• Which implementation version and tests reproduce the proof?

Merkle trees make compact commitments possible. They do not collapse Bitcoin’s validation system into one root hash.