<p>The idea of Merklized <strong>Alternative Script</strong> Trees (or previously Merklized <strong>Abstract Syntax</strong> Trees) dates back to an idea Russell O'Connor had in <a href="https://diyhpl.us/wiki/transcripts/london-bitcoin-devs/2020-07-21-socratic-seminar-bip-taproot/" rel="noreferrer">2012</a>. The original idea was that you could have alternative scripts or script fragments stored as leaves in a Merkle tree and then the leaves of the tree that weren't used could be pruned away and not take up valuable space on the blockchain. Compare this to P2SH (Pay to Script Hash) where the <strong>entire</strong> script is hashed and then revealed on the blockchain at spend time. This brings block space efficiencies (and hence lower fees) as well as privacy benefits.</p>
<p>The earlier formalized proposals for MAST were <a href="https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki" rel="noreferrer">BIP 114</a> and <a href="https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki" rel="noreferrer">BIP 116</a> and the most recent proposal is of course Taproot (<a href="https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki" rel="noreferrer">BIP 341</a>). The reason why we moved away from using Merklized <strong>Abstract Syntax</strong> Tree terminology is that with Taproot (and BIP 114) only one single leaf of the Merkle tree can be executed. You cannot split one particularly long script path into multiple script fragments stored on different leaves of the tree and then satisfy a combination of these leaves. It is effectively a tree of ORs (no ANDs of different leaves and no IF, ELSEs that lead to satisfying different leaves on the tree). You can have ANDs and IF ELSEs but they are contained within leaves not between leaves. Satisfying a single leaf is sufficient to spend the UTXO. As Johnson Lau says in BIP 114:</p>
<blockquote>
<p>Only one branch is allowed for execution, and users are required to transform a complicated condition into several mutually exclusive branches.</p>
</blockquote>
<p>Pieter Wuille and Russell O'Connor discussed why this design decision was made for Taproot at <a href="https://diyhpl.us/wiki/transcripts/london-bitcoin-devs/2020-07-21-socratic-seminar-bip-taproot/" rel="noreferrer">London BitDevs</a> in July 2020. One of the reasons was that you only need a logarithmic number of Merkle branch nodes to get to any given leaf. There is a combinatorial explosion if there is the potential to have different combinations of all the leaves. Another reason is that the design space had to be limited at some stage to give the proposal the best chance of obtaining community consensus and ultimately be activated.</p>

CC BY-SA 4.0
2020-10-24T13:22:41.830Z
2020-10-25T13:41:22.160Z
2020-10-25T13:41:22.160Z
Michael Folkson
<p>You may have heard before that &quot;Bitcoin is programmable money&quot;. Bitcoin uses a simple programming language called <em>Script</em> to encode payment conditions. While today the vast majority of transactions uses standard single-sig outputs (P2PK, P2PKH, P2WPKH) or one of a small set of common scripts (wrapped segwit, 2-of-3 multisig, 2-of-2 multisig with 1-of-2 fallback), Bitcoin's script language would allow for a multitude of other applications.</p>
<p>Originally, such scripts were encoded directly in the output script that a transaction credited. <em>Pay to Script Hash (P2SH, <a href="https://en.bitcoin.it/wiki/BIP_0016" rel="nofollow noreferrer">BIP16</a>)</em> introduced locking the funds to the hash of the full <em>redeemscript</em> instead. The full script is hereby published on spending. One of the challenges of deploying more complex spending conditions with P2SH is that all possible outcomes have to be encoded into a single script which can make the script long and complicated. As the full script needs to be published upon spending, the resulting inputs are costly and reveal the full contract. Additionally, it is non-trivial to determine all possible outcomes of even moderately complex smart contracts.</p>
<p>The idea of <em>Merklized Alternative Script Trees (MAST)¹</em> is to enumerate distinct spending conditions separately and to allow funds to be spent by fulfilling any one of the scripts.  Each script is compartmentalized into the leaf of a merkle tree. On receiving, the funds are locked to the root of the merkle tree. Spending requires revealing a single leaf's script, a merkle proof to show inclusion in the tree, and fulfillment of the spending conditions encoded in the leaf. The benefits of this compartmentalization are a reduced length and complexity in each leaf, that other spending conditions remain private, and the possibility to encode a multitude of spending conditions. The downside is the added cost of the merkle proof.</p>
<p>A variant of MAST is part of the <a href="https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki" rel="nofollow noreferrer">BIP341</a> Taproot proposal which supersedes two earlier MAST proposals. <em>Pay to Taproot (P2TR)</em> output scripts are encoded in a single public key. Internally, these are composed of an inner key tweaked with the root of a MAST. A P2TR output can either be spent via the <em>key path</em> by issuing a signature satisfying the public key, or via the <em>script path</em> using one of the MAST leaves.</p>
<hr />
<p><sup>¹ Note that MAST was originally introduced as the abbreviation for Merklized Abstract Syntax Trees, but has since been backronymed to better fit the proposal's current scope. Also see <a href="https://bitcoin.stackexchange.com/a/99622/5406">Michael's answers</a>, which goes into more detail on that.</sup></p>

CC BY-SA 4.0
2020-10-25T14:50:34.810Z
2020-10-25T16:53:39.687Z
2020-10-25T16:53:39.687Z
Murch
<p>I have seen the acronym MAST floating around. I saw that it stands for Merklized Alternative Script Trees, but what does that mean? In what context do they appear and what can they be used for?</p>

CC BY-SA 4.0
2020-10-25T17:07:17.157Z
Too bad they changed the name from Merklized Abstract Syntax Tree since abstract syntax trees are a concept known to all computer scientists and would give them an understanding of the purpose of this structure.
Thorkil Værge
CC BY-SA 4.0
2020-10-25T17:19:05.467Z
They are well known to computer scientists. But leaves of a Merklized Abstract Syntax Tree aren't constrained to be mutually exclusive. So it isn't an syntax tree. https://en.wikipedia.org/wiki/Abstract_syntax_tree
Michael Folkson
<taproot><mast>
What are Merklized Alternative Script Trees?
Murch
# What are Merklized Alternative Script Trees?

(Asked by: username_0 on 2020-10-19)

I have seen the acronym MAST floating around. I saw that it stands for Merklized Alternative Script Trees, but what does that mean? In what context do they appear and what can they be used for?

**Tags:** taproot, mast

> **Comments:**
> **username_1**: Too bad they changed the name from Merklized Abstract Syntax Tree since abstract syntax trees are a concept known to all computer scientists and would give them an understanding of the purpose of this structure.  
> **username_2**: They are well known to computer scientists. But leaves of a Merklized Abstract Syntax Tree aren't constrained to be mutually exclusive. So it isn't an syntax tree. https://en.wikipedia.org/wiki/Abstract_syntax_tree  

---

## 2 answers

### Answer by username_2 on 2020-10-24. Score: 5

The idea of Merklized **Alternative Script** Trees (or previously Merklized **Abstract Syntax** Trees) dates back to an idea Russell O'Connor had in [2012](https://diyhpl.us/wiki/transcripts/london-bitcoin-devs/2020-07-21-socratic-seminar-bip-taproot/). The original idea was that you could have alternative scripts or script fragments stored as leaves in a Merkle tree and then the leaves of the tree that weren't used could be pruned away and not take up valuable space on the blockchain. Compare this to P2SH (Pay to Script Hash) where the **entire** script is hashed and then revealed on the blockchain at spend time. This brings block space efficiencies (and hence lower fees) as well as privacy benefits.

The earlier formalized proposals for MAST were [BIP 114](https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki) and [BIP 116](https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki) and the most recent proposal is of course Taproot ([BIP 341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki)). The reason why we moved away from using Merklized **Abstract Syntax** Tree terminology is that with Taproot (and BIP 114) only one single leaf of the Merkle tree can be executed. You cannot split one particularly long script path into multiple script fragments stored on different leaves of the tree and then satisfy a combination of these leaves. It is effectively a tree of ORs (no ANDs of different leaves and no IF, ELSEs that lead to satisfying different leaves on the tree). You can have ANDs and IF ELSEs but they are contained within leaves not between leaves. Satisfying a single leaf is sufficient to spend the UTXO. As Johnson Lau says in BIP 114:

> Only one branch is allowed for execution, and users are required to transform a complicated condition into several mutually exclusive branches.

Pieter Wuille and Russell O'Connor discussed why this design decision was made for Taproot at [London BitDevs](https://diyhpl.us/wiki/transcripts/london-bitcoin-devs/2020-07-21-socratic-seminar-bip-taproot/) in July 2020. One of the reasons was that you only need a logarithmic number of Merkle branch nodes to get to any given leaf. There is a combinatorial explosion if there is the potential to have different combinations of all the leaves. Another reason is that the design space had to be limited at some stage to give the proposal the best chance of obtaining community consensus and ultimately be activated.


---

### Answer by username_0 on 2020-10-25. Score: 5

You may have heard before that "Bitcoin is programmable money". Bitcoin uses a simple programming language called *Script* to encode payment conditions. While today the vast majority of transactions uses standard single-sig outputs (P2PK, P2PKH, P2WPKH) or one of a small set of common scripts (wrapped segwit, 2-of-3 multisig, 2-of-2 multisig with 1-of-2 fallback), Bitcoin's script language would allow for a multitude of other applications.

Originally, such scripts were encoded directly in the output script that a transaction credited. *Pay to Script Hash (P2SH, [BIP16](https://en.bitcoin.it/wiki/BIP_0016))* introduced locking the funds to the hash of the full *redeemscript* instead. The full script is hereby published on spending. One of the challenges of deploying more complex spending conditions with P2SH is that all possible outcomes have to be encoded into a single script which can make the script long and complicated. As the full script needs to be published upon spending, the resulting inputs are costly and reveal the full contract. Additionally, it is non-trivial to determine all possible outcomes of even moderately complex smart contracts.

The idea of *Merklized Alternative Script Trees (MAST)¹* is to enumerate distinct spending conditions separately and to allow funds to be spent by fulfilling any one of the scripts. Each script is compartmentalized into the leaf of a merkle tree. On receiving, the funds are locked to the root of the merkle tree. Spending requires revealing a single leaf's script, a merkle proof to show inclusion in the tree, and fulfillment of the spending conditions encoded in the leaf. The benefits of this compartmentalization are a reduced length and complexity in each leaf, that other spending conditions remain private, and the possibility to encode a multitude of spending conditions. The downside is the added cost of the merkle proof.

A variant of MAST is part of the [BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki) Taproot proposal which supersedes two earlier MAST proposals. *Pay to Taproot (P2TR)* output scripts are encoded in a single public key. Internally, these are composed of an inner key tweaked with the root of a MAST. A P2TR output can either be spent via the *key path* by issuing a signature satisfying the public key, or via the *script path* using one of the MAST leaves.

---

¹ Note that MAST was originally introduced as the abbreviation for Merklized Abstract Syntax Trees, but has since been backronymed to better fit the proposal's current scope. Also see [username_2's answers](https://bitcoin.stackexchange.com/a/99622/5406), which goes into more detail on that.


---

