TERM_DEF // SCRIPT_AUTHORIZATION / MAST_MERKELIZED_ABSTRACT_SYNTAX_TREE
MAST (MERKELIZED ABSTRACT
SYNTAX TREE)
SYNTAX TREE)
MAST (Merkelized Abstract Syntax Tree). A Merkle tree of script alternatives; only the chosen branch is revealed at spend time.
This page sits in the Script & Authorization section — The stack VM that decides whether a UTXO is spendable — opcodes, templates, and modern script trees. Read on for what it is, why it exists, how it works under the hood, and what to watch out for.
This page sits in the Script & Authorization section — The stack VM that decides whether a UTXO is spendable — opcodes, templates, and modern script trees. Read on for what it is, why it exists, how it works under the hood, and what to watch out for.
WHAT_MAST_MERKELIZED_ABSTRACT_SYNTAX_TREE_IS
MAST (Merkelized Abstract Syntax Tree) — at a glance
SCRIPT
MAST (Merkelized Abstract Syntax Tree) is part of Bitcoin Script, the small stack-based programming language that decides whether any given output can be spent. A Merkle tree of script alternatives; only the chosen branch is revealed at spend time. Script is intentionally simple — no loops, no recursion, no global state — because every node/">full node must execute every script in every transaction, and any complexity becomes a denial-of-service vector.
Why it exists
DESIGN
Bitcoin needed programmable money. A flat "pay address X" rule would have been too rigid — no multisig, no time-locks, no hashed commitments, no Lightning. Script is the answer: a tiny, deterministic, non-Turing-complete bytecode that lets coins be locked behind arbitrary spending conditions while keeping validation cheap and predictable.
HOW_IT_WORKS
Mechanism
HOW IT WORKS
Every UTXO is locked by a scriptPubKey — the output's locking script. To spend it, you provide a scriptSig (or witness) containing data that satisfies the lock. The node concatenates them, runs the combined script on a stack machine, and accepts the spend if and only if execution finishes with a single truthy value on the stack. MAST (Merkelized Abstract Syntax Tree) contributes a specific stack effect within that process — opcodes either push, pop, copy, hash, branch, or verify, and they do so left-to-right deterministically.
1. The script is parsed into a sequence of opcodes and push-data items.
2. Execution starts with an empty stack and an empty alt-stack.
3. Each opcode runs in order — push opcodes add to the stack, others consume the top items and may push results.
4. Conditional opcodes (OP_IF/OP_NOTIF/OP_ELSE/OP_ENDIF) branch execution.
5. Final state: a single non-zero (truthy) value on top → the spend is authorised. Anything else (empty stack, false, error) → the script fails and the tx is rejected.
WORKED_EXAMPLE
A canonical P2PKH script — the most common locking script in Bitcoin
EXAMPLE
scriptPubKey (locking script — sits in the output):
OP_DUP OP_HASH160 <20-byte pubkey hash> OP_EQUALVERIFY OP_CHECKSIG
scriptSig (unlocking script — provided by the spender):
<signature> <pubkey>
Combined execution, left to right:
push signature → [sig]
push pubkey → [sig pubkey]
OP_DUP → [sig pubkey pubkey]
OP_HASH160 → [sig pubkey hash160(pubkey)]
push expected_hash → [sig pubkey hash160(pubkey) expected]
OP_EQUALVERIFY → [sig pubkey] (fails if hashes differ)
OP_CHECKSIG → [1] (true if signature is valid)
End state: single truthy value on top → spend authorised.
KEY_PROPERTIES
STACK-BASED
Every operation reads and writes the top of a single shared LIFO stack. No registers, no variables, no heap.
DETERMINISTIC
No randomness, no clocks. Every node executes the same script the same way — divergence would fork the network.
NON-TURING-COMPLETE
No loops, no recursion. Every script halts in bounded time, so validation cost is predictable.
CONSENSUS-CRITICAL
A misbehaving Script implementation forks its node off the network. The reference implementation is the de-facto spec.
COMMON_PITFALLS
Things that catch people out
PITFALLS
- OP_RETURN makes an output provably unspendable — useful for data commitments, ruinous if used accidentally.
- Several opcodes were disabled in 2010 after security incidents (OP_MUL, OP_DIV, OP_SUBSTR, …) and have never been re-enabled.
- Number encoding (CScriptNum) is sign-magnitude, not two's complement. -1 is 0x81, not 0xff — a frequent source of bugs.
- OP_CHECKMULTISIG has a historical off-by-one bug — it pops one extra dummy item from the stack. Always prefix the sigs with an OP_0.
RELATED_CONCEPTS
Other terms from Script & Authorization — click any to read its page:
TERMINOLOGY_INDEX
TERMINOLOGY
MAST (Merkelized Abstract Syntax Tree)
A Merkle tree of script alternatives; only the chosen branch is revealed at spend time.
Script
Bitcoin's purpose-built stack language; every locking and unlocking script is a script program.
Stack
The single LIFO data structure all script execution operates on; no variables, no registers.
Locking Script
The scriptPubKey on an output; specifies the spending conditions.
Unlocking Script
The scriptSig/witness in an input; provides the data that satisfies the lock.
Redeem Script
Witness Script
In P2WSH, the script whose SHA256 is committed in the output; placed at the end of the witness stack.
Script Execution
Sequential stepping through opcodes, mutating the stack until either a valid truthy stack remains or the script fails.