MAST - Hiding Unexecuted Script Branches
9. MAST — Hiding Unexecuted Script Branches
MAST stands for Merkelized Abstract Syntax Trees (or Merkelized Alternative Script Trees, depending on who you ask). It is the mechanism by which Taproot allows multiple spending conditions to be committed to in a single output while revealing only the condition being used at spend time.
The Problem MAST Solves
Before MAST, complex multi-condition scripts had to be expressed as a single script using OP_IF/OP_ELSE trees:
// Legacy multi-condition script (all conditions visible on-chain):
OP_IF
// Condition A: 2-of-2 multisig
OP_2 <pubkeyA1> <pubkeyA2> OP_2 OP_CHECKMULTISIG
OP_ELSE
OP_IF
// Condition B: Timelock + single sig
<timelock> OP_CHECKLOCKTIMEVERIFY OP_DROP
<pubkeyB> OP_CHECKSIG
OP_ELSE
// Condition C: Hash preimage
OP_SHA256 <hash> OP_EQUAL
OP_ENDIF
OP_ENDIF
Problems with this approach:
-
All conditions are visible on-chain, even if only one is ever used
-
Script size grows with every condition, increasing transaction fees
-
Privacy is poor — observers can see all possible spending conditions
-
P2SH/P2WSH limit script size to 520/10,000 bytes
How MAST Works
MAST organizes spending conditions as leaves of a Merkle tree. The Merkle root is committed to in the output. To spend, you reveal only the one leaf you are using, plus the Merkle path proving its inclusion.
Script tree with 3 conditions:
Root (32 bytes)
/ \
Branch (32 bytes) Leaf C (32 bytes)
/ \
Leaf A Leaf B
(2-of-2) (timelock) (hash preimage)
On-chain, only the tweaked pubkey is visible.
To spend via Leaf A, you reveal: Leaf A script + Branch hash + Leaf C hash
To spend via Leaf B, you reveal: Leaf B script + Branch hash + Leaf C hash
To spend via Leaf C, you reveal: Leaf C script + Root hash computation only needs Branch
Privacy Properties
When spending via Leaf A:
-
The blockchain records: Leaf A script (executed) + two 32-byte hashes
-
Nobody can determine: What Leaf B or Leaf C contain
-
Nobody even knows: How many other leaves exist (the tree could be larger)
This is a massive privacy improvement. A complex financial contract (escrow, inheritance, DLC) looks identical on-chain to a simple single-key spend, as long as the key path is used. Even script path spends reveal only the executed branch.
Constructing a MAST Tree
def build_tap_tree(scripts):
"""
Build a Taproot script tree from a list of (script, weight) tuples.
Weight determines how deep in the tree a script is placed.
Frequently-used scripts should be shallow (lower fee to execute).
"""
# Create leaf hashes
leaves = []
for script, weight in scripts:
leaf_hash = tagged_hash(
"TapLeaf",
bytes([0xc0]) + compact_size(len(script)) + script
)
leaves.append((leaf_hash, weight))
# Build tree using Huffman-like algorithm (heavier weights = shallower)
# Sort by weight descending
leaves.sort(key=lambda x: -x[1])
# Combine leaves into branches
while len(leaves) > 1:
left = leaves.pop()
right = leaves.pop()
# Combine using sorted hash order
if left[0] <= right[0]:
branch_hash = tagged_hash("TapBranch", left[0] + right[0])
else:
branch_hash = tagged_hash("TapBranch", right[0] + left[0])
leaves.append((branch_hash, left[1] + right[1]))
return leaves[0][0] # The Merkle root
MAST and Fee Optimization
The depth of a leaf in the MAST tree determines how many 32-byte hashes must be included in the control block. A leaf at depth 1 needs 1 hash (32 bytes). A leaf at depth 10 needs 10 hashes (320 bytes).
The optimal strategy is to place the most likely spending path at the shallowest depth:
For a 2-of-3 multisig with a 6-month recovery:
Optimal tree:
Root
/ \
Leaf A Leaf B
(2-of-3) (recovery)
Leaf A (common case) is at depth 1 — minimal control block overhead
Leaf B (rare recovery) is at depth 1 as well
For 4 conditions with probabilities 70%, 20%, 7%, 3%:
Root
/ \
70% Branch1
/ \
20% Branch2
/ \
7% 3%
Technical Insight
This topic covers essential mechanics for Chapter 11. Understanding these details is key to mastering advanced Bitcoin script constructions like Taproot and specialized covenants.
TeachMeBitcoin is an ad-free, open-source educational repository curated by a passionate team of Bitcoin researchers and educators for public benefit. If you found our articles helpful, please consider supporting our hosting and ongoing content updates with a clean donation: