Home › Glossary › Merkle tree

Merkle tree

Also called: Merkle root, hash tree, Merkle proof, Merkle branch, hashMerkleRoot.

A Merkle tree hashes many items into one 32-byte root, so any single item can be proven to be included with a short proof instead of the whole list.

A Merkle tree, named after Ralph Merkle, is a way of hashing a list of items into a single fingerprint, the Merkle root, so that you can later prove one item is in the list without revealing the rest. Each item is hashed, then the hashes are paired and hashed together, level by level, until one hash remains.

Merkle trees in Bitcoin blocks

Every block header contains a 32-byte Merkle root of all the block's txids, computed with double SHA-256. To prove a transaction is in a block you only need the hashes along its path to the root, about log2(n) of them: for a block of 4,000 transactions that's 12 hashes, or 384 bytes. This is what makes SPV light clients possible, and BIP 37 merkleblock messages carry exactly such partial trees. SegWit added a second tree over wtxids, whose root is committed in the coinbase transaction (BIP 141).

Known quirks

Satoshi's design duplicates the last hash when a level has an odd number of entries, which lets two different transaction lists share one root (CVE-2012-2459). And because an inner node is 64 bytes of data, a 64-byte transaction can be passed off as an inner node to forge an inclusion proof. BIP 54 and BIP 53 propose making 64-byte transactions invalid, and BIP 98 describes a faster tree without these problems.

Merkle trees in scripts

Taproot (BIP 341) commits to a tree of alternative scripts using tagged hashes (TapLeaf and TapBranch). Spending reveals one script plus its path, up to 128 levels deep. This idea is known as MAST and was earlier proposed in BIP 114 and BIP 116.

BIPs that define Merkle tree

  • BIP 141 (SegWit): Segregated Witness (Consensus layer): Deployed. Defines Segregated Witness (SegWit), which moves signatures into a separate "witness" section of each transaction while remaining compatible with older nodes. This fixed transaction malleability,…
  • BIP 341: Taproot: SegWit version 1 spending rules: Deployed. Taproot introduces a new kind of Bitcoin output that can be spent either with a single signature or by revealing just one of many possible alternative spending conditions, kept hidden in a tree…
  • BIP 98: Fast Merkle Trees: Draft. Specifies a faster and safer version of the Merkle tree, the data structure Bitcoin uses to summarize many items in one fingerprint so that any single item can be proven to be included. The design…
  • BIP 54: Consensus Cleanup: Complete. Bundles fixes for several long-standing protocol weaknesses: the timewarp attack (manipulating block timestamps to speed up coin issuance), blocks that take extremely long to validate, Merkle tree…
  • BIP 53: Disallow 64-byte transactions: Draft. Proposes making transactions that are exactly 64 bytes long (excluding signature data) invalid. Such transactions can be confused with internal pieces of a block's Merkle tree, the structure…
  • BIP 37: Connection Bloom filtering: Deployed. Lets lightweight wallets hand a full node a Bloom filter (a compact, approximate summary of what they care about) so they receive only relevant transactions. This made phone wallets practical,…

Related terms

  • MAST: MAST commits to many alternative spending scripts in a Merkle tree so only the branch actually used is revealed; Taproot implements it as script trees.
  • SPV (Simplified Payment Verification): SPV (Simplified Payment Verification) is how light wallets check payments using only block headers and Merkle proofs, without downloading full blocks.
  • Taproot: Taproot is the 2021 Bitcoin soft fork (BIPs 340, 341, 342) that added Schnorr signatures and P2TR outputs which hide unused spending conditions.
  • TXID: A TXID (transaction ID) is the 32-byte hash that identifies a Bitcoin transaction, shown as 64 hex characters in wallets and block explorers.

Learn more

Guides