MAST Merkelized Alternative Script Tree
Merkelized Alternative Script Tree (MAST) was introduced in BIP 341.
For this topic, you need the following prerequisits:
MAST stands for Merkelized Abstract Syntax Tree. In the context of Bitcoin, however, it is used as Merkelized Alternative Script Tree.
The concept involves dividing a script into separate execution branches, each of which is then hashed and combined into a Merkle tree that represents the structure of the underlying code. In Bitcoin the leaves represent user-defined conditions that must be met to be able to spend a specific unspent transaction output.
Construction of a MAST
The figure below illustrates an example of a Merkelized alternative script tree (MAST) containing three scripts (conditions) in its leaves.
The construction of a MAST is similar to that of a binary Merkle tree. Leaves and nodes are hashed in pairs.
First, the scripts are individually hashed. Then, each leaf hash is concatenated with the hash of its neighbor (either the left neighbor or the right neighbor) and hashed again. This resulting hash is then concatenated with the hash of the neighbor node at the same level. The following figure illustrates a MAST.
The hashing rules may specify that certain tags or additional information be concatenated at certain levels to the pre-image before hashing.
Spending from a MAST
To spend an UTXO, the user must prove that he meets the conditions of at least one branch (leaf/script). This is done by providing the script of the chosen branch (e.g. script B), the necessary data for the script to execute correctly, and the Merkle path to the script root (=Merkle root). In this example, the user would need to provide the information in the green fields, if they wish to spend from script B. The Merkle Root (red) is provided in the transaction.
With the following tool, you can construct your own Merkelized Alternative Script Tree (MAST) by adding data to its leaves.
