MASTERING-BITCOIN · Interactive Practice

MAST: One Branch to Spend Them All

IKey Formulas

Formula	Name	Description
$h = \lceil \log_2 n \rceil$	Hashes revealed (balanced tree)	Sibling hashes along path to root for $n$ leaves
$B = 32 \cdot \lceil \log_2 n \rceil$	Bytes revealed	Each hash is 32 bytes (SHA-256)
$C = \sum_i p_i \cdot d_i$	Expected cost (Huffman tree)	Probability $p_i$ of using leaf at depth $d_i$
$H_{\text{parent}} = H(H_{\text{left}} \,\Vert\, H_{\text{right}})$	Merkle node hash	Each parent commits to its two children

IIVisualization 1: Building a Merkle Tree

A Merkle tree compresses many leaves (spending scripts) into a single 32-byte root. To prove that one specific leaf belongs in the tree, you only need that leaf plus the sibling hash at each level along its path to the root.

Adjust the number of leaves and pick which one is being "spent" to see the proof path.

⚙ interactive visualization — coming to this page format soon

Notice: As you double the number of leaves, the tree grows by only one extra level — so the proof grows by exactly one extra hash. That's the logarithmic scaling that makes MAST so powerful.

IIIVisualization 2: Cost Scaling — MAST vs Legacy OP_IF

A legacy Bitcoin script with OP_IF branches must include every branch on chain when spent — cost grows linearly with the number of conditions. MAST reveals only one script + log₂(n) sibling hashes — cost grows logarithmically.

Adjust the average bytes per branch and see where the two curves diverge.

⚙ interactive visualization — coming to this page format soon

Reflect: The legacy curve crashes through the 10,000-byte cap quickly — that ceiling is a hard limit. The MAST curve barely moves. Doubling $n$ adds exactly one 32-byte hash.

IVVisualization 3: Huffman Coding — Common Paths Pay Less

A balanced tree treats every spending path equally. But your daily 2-of-3 multisig might be used 90% of the time, while a 12-month timelock fallback fires almost never. Huffman coding places frequent leaves shallow (cheap) and rare leaves deep.

Adjust the probabilities and see how the expected number of revealed hashes changes.

⚙ interactive visualization — coming to this page format soon

Notice: When the daily spend dominates (probability close to 1), Huffman shaping pushes the expected reveal close to 1 hash per spend — even cheaper than a balanced tree. The tree shape itself stays hidden on chain, so this optimization has no privacy cost.

## Quiz Questions

Question 1 · Hashes Revealed for n = 8

A MAST commitment contains 8 spending conditions in a balanced tree. When you spend, how many sibling hashes must you reveal along with the chosen script?

✅ Correct! $\lceil \log_2 8 \rceil = 3$ — one sibling hash per level.

❌ Not quite. The proof size scales with the depth of the tree, not its leaf count. Use $\lceil \log_2 n \rceil$ .

Show solution

Solution:

The number of sibling hashes equals the depth of the tree: $h = \lceil \log_2 n \rceil = \lceil \log_2 8 \rceil = 3$

A balanced tree with 8 leaves has depth 3, so the path from any leaf to the root crosses 3 levels — and at each level you must reveal exactly one sibling hash to let the verifier re-hash up to the root. Total: 3 hashes = 96 bytes.

Question 2 · Privacy Property

True or False: By examining a MAST spending transaction on the blockchain, an outside observer can determine how many unused spending conditions were committed in the original output.

✅ Correct! Unused branches are committed but invisible — observers see only the revealed leaf and its proof hashes.

❌ Not quite. A core privacy benefit of MAST is that the existence of unused branches stays hidden.

Show solution

Solution:

The answer is False.

A MAST spend reveals one script and a small stack of sibling hashes. From those hashes alone, an observer cannot tell whether the tree had 2 leaves or 2 trillion leaves — every internal hash looks identical to a random 32-byte value.

A simple wallet and an enterprise vault with thousands of contingency clauses produce indistinguishable on-chain spends. The unused branches don't just stay private — even their existence stays private.

(One subtlety: the depth of the path is visible from the proof length, but Huffman shaping plus padding can be used to obscure even that.)

Question 3 · Bytes Revealed for n = 1024

A vault commits to 1,024 distinct spending conditions in a balanced MAST tree. Each SHA-256 hash is 32 bytes.

How many bytes of sibling hashes (not counting the revealed script itself) appear on chain when the vault is spent?

✅ Correct! $32 \times \log_2(1024) = 32 \times 10 = 320$ bytes.

❌ That's the linear answer ( $32 \times 1024$ ). MAST scales logarithmically — you only reveal one hash per tree level.

❌ Not quite. Use $B = 32 \cdot \lceil \log_2 n \rceil$ . For $n=1024$ , the depth is 10.

Show solution

Solution:

Compute the depth: $\lceil \log_2 1024 \rceil = 10$

Bytes revealed for the proof: $B = 32 \times 10 = 320 \text{ bytes}$

That's 320 bytes of sibling hashes to commit to 1,024 different spending conditions. For comparison, an equivalent OP_IF script with 1,024 branches at even 50 bytes per branch would need 51,200 bytes — already 5× the legacy 10,000-byte cap, making such a script impossible to construct under legacy rules.

Question 4 · Why Use Huffman Shaping?

Suppose your wallet has three spending paths with usage probabilities: daily multisig (90%), cold-key recovery (9%), and timelock fallback (1%).

What is the primary reason to use a Huffman-shaped MAST tree (placing the daily path at depth 1) instead of a balanced tree?

✅ Correct! Frequent leaves shallow, rare leaves deep — average cost drops dramatically.

❌ Not quite. Think about which path is taken most often, and what that implies for the average number of hashes revealed per spend.

Show solution

Solution:

Huffman shaping minimizes the expected proof size: $\mathbb{E}[\text{hashes}] = \sum_i p_i \cdot d_i$

With the daily path at depth 1 (used 90% of the time): $\mathbb{E} = 0.90(1) + 0.09(2) + 0.01(2) = 1.10 \text{ hashes}$

vs. a balanced 4-leaf tree where every path is at depth 2: $\mathbb{E} = 2.00 \text{ hashes}$

That's a 45% reduction in average fees, with no loss of security or privacy. The other options are wrong:

❌ Security comes from the hash function, not tree shape.
❌ Huffman shaping does not expose unused branches — they remain hidden.
❌ Bitcoin doesn't mandate balanced trees; the user chooses the shape.

Solved: 0 / 4