Taptree

What Is a Taptree?

A taptree is the data structure at the heart of Taproot script spending. It organizes multiple spending conditions into a binary Merkle tree, where each leaf contains a single script. When a user spends via one of these scripts (known as a script-path spend), they reveal only the leaf they are using and provide a compact Merkle proof. Every other spending condition remains invisible to the blockchain.

Before Taproot activated in November 2021, Bitcoin transactions that required complex spending logic (multisig with fallbacks, timelocked recovery, escrow) had to reveal every possible condition on-chain, even the ones never exercised. Taptrees solve this by letting a single P2TR output commit to an arbitrary number of scripts while revealing only what is actually needed. This improves privacy, reduces transaction size, and makes complex contracts look identical to simple single-key spends when the cooperative key path is used.

How It Works

Constructing a taptree involves three stages: building the tree from script leaves, computing the Merkle root, and tweaking the internal public key so the output commits to the entire tree.

Building the Tree

Each spending condition is placed in a leaf. A leaf is hashed using the tagged-hash scheme defined in BIP-341:

TapLeaf = hash_TapLeaf(leaf_version || compact_size(script_len) || script)

The leaf version byte identifies the script execution rules. Version 0xc0 signals TapScript rules as defined in BIP-342. Other even values are reserved for future script upgrades, giving Bitcoin a built-in versioning mechanism for new opcodes.

Internal (branch) nodes are computed by sorting the two child hashes lexicographically, then hashing them together:

TapBranch = hash_TapBranch(sorted(left_hash, right_hash))

Sorting the children eliminates the need to store direction bits in the Merkle proof: the verifier can reconstruct the correct pairing by comparing hash values at each level.

Tagged Hashes

All hashes in taptree construction use domain-separated tagged hashes to prevent collisions between different protocol contexts:

hash_tag(x) = SHA256(SHA256(tag) || SHA256(tag) || x)

Three tags are used: TapLeaf for leaf nodes, TapBranch for internal nodes, and TapTweak for the final key derivation. This ensures that a leaf hash can never be confused with a branch hash, even if they happen to share the same byte content. The SHA-256 prefix of the tag is computed once and reused, so the overhead is negligible.

Key Tweaking

Once the Merkle root (km) is computed, it is combined with the internal public key (P) to produce the output key that appears on-chain:

t = hash_TapTweak(P || km)
Q = P + t * G

Here G is the secp256k1 generator point. The resulting output key Q looks like any other public key. An observer cannot tell whether Q hides a complex taptree with dozens of scripts or no scripts at all. This is what makes Taproot outputs fungible: cooperative key-path spends and script-path spends produce outputs that look identical before they are spent.

Script-Path Spending

To spend via a taptree leaf, the spender provides a control block containing the internal public key, the leaf version, and the Merkle proof (one 32-byte sibling hash per tree level). The full witness structure:

witness: <script_args> <script> <control_block>

control_block:
  <control_byte>       // leaf_version | output_key_y_parity
  <internal_key>       // 32 bytes
  <merkle_path>        // 32 * depth bytes

The verifier reconstructs the Merkle root from the leaf hash and the proof, then checks that the tweaked internal key matches the output key. If both checks pass, the script is executed. The entire verification is performed without revealing any other leaf in the tree.

Tree Depth and Proof Size

BIP-341 caps taptree depth at 128 levels. The control block size is 33 + 32m bytes, where m is the Merkle path length (0 to 128). In practice, even a tree with millions of leaves only requires around 20 levels, so the 128-level cap is a safety bound rather than a practical constraint.

Each additional level of depth adds 32 bytes to the witness. This means leaf placement directly affects transaction cost: a script at depth 2 requires 64 bytes of proof, while a script at depth 6 requires 192 bytes. The deeper a script sits, the more expensive it is to use.

Huffman Encoding for Optimal Trees

When the probabilities of different spending paths are known, the taptree should be constructed as a Huffman tree. High-probability scripts (like a cooperative 2-of-2 multisig) are placed closer to the root with shorter proofs. Low-probability scripts (like a timelock recovery after one year) are placed deeper where their larger proofs only matter if they are actually used.

The expected witness weight across all possible spending paths is:

expected_weight = sum(probability_i * witness_weight_i) for each leaf i

For equal-probability scripts, a balanced binary tree minimizes the worst-case proof size. For unequal probabilities, Huffman encoding can reduce expected costs significantly.

Example: 2-of-3 Multisig with Timelock Fallback

Consider a wallet controlled by three parties (Alice, Bob, Carol) where any two can spend cooperatively, and after one year Alice alone can recover funds. Using MuSig2 for key aggregation, this taptree would be structured as follows:

Internal key: MuSig2(Alice, Bob, Carol)  // 3-of-3 key-path spend

Taptree:
            [root]
           /      \
      [branch]    [branch]
       /    \       /    \
  Leaf 0  Leaf 1  Leaf 2  Leaf 3

Leaf 0: <Alice> <Bob> OP_CHECKSIGVERIFY OP_CHECKSIG
Leaf 1: <Alice> <Carol> OP_CHECKSIGVERIFY OP_CHECKSIG
Leaf 2: <Bob> <Carol> OP_CHECKSIGVERIFY OP_CHECKSIG
Leaf 3: <locktime> OP_CHECKLOCKTIMEVERIFY OP_DROP <Alice> OP_CHECKSIG

The internal key is the MuSig2 aggregate of all three parties. If all three cooperate, they spend via the key path: no scripts are revealed, the transaction looks like an ordinary single-signature spend, and fees are minimal.

If only two parties are available, they use the corresponding taptree leaf. Leaves 0, 1, and 2 (the 2-of-2 combinations) are placed at equal depth because they are roughly equally likely. Leaf 3 (the timelock fallback) could be placed deeper if the tree is unbalanced, since it is the least likely path.

Using TapScript rules, each leaf uses the more efficient Schnorr OP_CHECKSIG instead of legacy ECDSA verification, and no dummy bytes are needed for OP_CHECKMULTISIG workarounds.

Why Taptrees Matter

Taptrees fundamentally change how complex Bitcoin contracts work. Before Taproot, a P2SH or P2WSH output revealed every spending path at spend time, regardless of which one was used. A 10-path contract paid for all 10 paths even when only 1 was exercised. Taptrees flip this: you pay only for the path you use.

For protocols like Spark, taptrees enable compact representation of complex ownership and exit conditions in a single UTXO. A virtual UTXO can encode cooperative exits, unilateral exits with timelocks, and penalty conditions all within one taptree, keeping the common cooperative path cheap and private.

The privacy benefit extends beyond individual users. When cooperative spends are indistinguishable from simple payments, chain analysis cannot differentiate a multisig spend from a single-key spend. This improves fungibility across the entire network.

Relationship to MAST

Taptrees are Bitcoin's concrete implementation of MAST (Merkelized Abstract Syntax Trees). The MAST concept was proposed as early as 2013 and went through several iterations (BIP-114, BIP-116/117) before being incorporated into BIP-341. The key innovation of Taproot's approach is combining MAST with Schnorr key tweaking, allowing a single output format to serve both simple key-path spends and complex script-path spends.

Earlier MAST proposals required separate output types for script trees, making them distinguishable on-chain. Taptrees avoid this by embedding the script commitment inside a standard public key, achieving the privacy benefits that previous proposals lacked. For a deeper technical walkthrough of how Taproot and Schnorr signatures work together, see the Taproot and Schnorr signatures explained research article.

Use Cases

• Complex custody arrangements: corporate treasuries can encode board-level multisig, executive-level multisig, and emergency recovery paths in a single output, paying only for the path exercised
• Lightning Network channels: channel outputs can commit to cooperative close, force close, and penalty paths using taptrees, as described in the simple Taproot channels specification
• Inheritance planning: time-locked recovery scripts for heirs sit in deeper taptree leaves, invisible during normal use
• Escrow and trade: atomic swap contracts with multiple refund and claim conditions fit naturally into a taptree structure
• Miniscript policies: spending policies compiled through Miniscript can be automatically decomposed into optimal taptree layouts

Risks and Considerations

Script-Path Fingerprinting

While taptrees hide unused scripts, a script-path spend does reveal the executed script and its position in the tree (via the Merkle proof length). Observers can infer approximate tree size from the proof depth and potentially fingerprint specific contract templates. The privacy benefit is strongest when the key path is used for the common case.

Complexity in Construction

Designing an optimal taptree requires estimating the probability of each spending path. Poorly balanced trees waste witness space on common paths. Tools like Miniscript and output descriptors help automate taptree construction, but developers working with raw scripts need to carefully consider leaf ordering.

Leaf Version Compatibility

Currently only leaf version 0xc0 (TapScript) is defined. Scripts using reserved leaf versions will be treated as "anyone can spend" by current nodes. Future soft forks can activate new leaf versions, but until they do, only 0xc0 leaves enforce meaningful spending conditions.

Key-Path Preference

Taptrees are most effective when the key path handles the majority of spends. If every spend goes through a script-path leaf, the taptree still reveals one script per transaction and pays the Merkle proof overhead. Protocols should be designed so cooperative cases use the key path, with taptree leaves reserved for dispute resolution and fallback scenarios.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.