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?
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ærgeOct 25, 2020 at 17:07
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. en.wikipedia.org/wiki/Abstract_syntax_tree– Michael FolksonOct 25, 2020 at 17:19
The idea of Merklized Alternative Script Trees (or previously Merklized Abstract Syntax Trees) dates back to an idea Russell O'Connor had in 2012. 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 and BIP 116 and the most recent proposal is of course Taproot (BIP 341). 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 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.
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) 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 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 Michael's answers, which goes into more detail on that.
MAST is mentioned as Merkelized Alternative Script Tree in the mailing list archive link I got from bitcoinops
MAST -- provides alternative scripts, doesn't affect sigs
I think I'm going to claim "MAST" stands for "merkelized alternative script tree" these days, since they're not "abstract syntax trees"
Only part that I understood about MAST from a medium post that it will improve privacy:
Taproot uses MAST to include the merklized hash as the public key, thereby then includes making a complex script transaction indistinguishable from a standard P2PKH transaction.