What is MAST and How Does it Improve Bitcoin?

While bitcoin is the most popular and largest cryptocurrency by market capitalization, it has a relatively simple blockchain which is unable to support some of the features that have made some of its successors popular.

Introducing MAST

In an effort to increase speeds as well as reduce the fees associated with transactions, the Segregated Witness (SegWit) update was added to the Bitcoin blockchain in August 2017. While SegWit was a much-publicized addition, there are a number of other Bitcoin Improvement Proposals (BIPs) that endeavor to improve the digital currency. A number of these focus on MAST.

MAST is an acronym for Merkelized Abstract Syntax Tree. This protocol is an amalgamation of Merkle trees and Abstract Syntax Trees algorithms. Merkle trees are a cryptographic tool that facilitates the reduction of the size of data within a block. Using a Merkle root, it is possible to confirm whether the data within a Merkle tree is true without the need to download all of the data.

Abstract Syntax Trees (ASTs) are an algorithm that function by splitting a program into its constituent parts in order to understand and categorize it easier. This split helps to access all relevant data faster as well. The combination of Merkle trees and ASTs make it possible for more complex data sets to be added to transactions within the Bitcoin blockchain while still allowing for smaller transaction data due to the use of Merkle proofs.

Bitcoin developer Luke-jr wrote in November 2016, “The idea of Merkelized Abstract Syntax Tree (MAST) is to use a Merkle tree to encode the operations in a script. When spending, users may provide only the branches they are executing and hashes that connect the branches to the fixed size Merkle root. This reduces the size of redemption stack from O(n) to O(log n) (n as the number of operations).”

Currently, the Bitcoin blockchain requires for all the data that is associated with a transaction to be included in the transaction data. This is true even for data that was not used during the transaction. This makes transactions on its ledger data heavy, and as a result, the process is slower than it should be. The inclusion of MAST would lead to improvements in the bitcoin transaction process.

Bitcoin lead developers have been researching and fine-tuning the possibility of MAST. There are three ways through which MAST can be added to Bitcoin’s blockchain.

BIP114

Johnson Lau, a bitcoin lead developer submitted a pull request on GitHub, naming the proposal BIP 114. Defining BIP114, he states:

“This BIP defines a new witness program type that uses a Merkle tree to encode mutually exclusive branches in a script. This enables complicated redemption conditions that are currently not possible, improves privacy by hiding unexecuted scripts, and allows inclusion of non-consensus enforced data with very low or no additional cost.”

Lau explains the motivation behind the proposal is borne out of Bitcoin’s secure yet somewhat inadequate and cumbersome script system. If implemented, the proposal would enable native SegWit addresses to use a Merkle root to witness transactions. Lau further explains that while BIP114 is based on MAST, it has a few distinctions and is better referred to as Merkelized Script. “This proposal is a simplified and special case MAST. Instead of encoding individual operations, the Merkle root encodes mutually exclusive conditional script branches. Although this is not a full implementation of MAST, it provides the same level of privacy and O(log n) scalability.”

The Mark Friedenbach Proposals

Another bitcoin developer Mark Friedenbach has set forth two proposals that when working together would allow for the introduction of MAST into bitcoins blockchain. The first of these is BIP 116 that seeks to allow “script writers to commit to a set of data elements and have one or more of these elements be provided at redemption without having to reveal the entire set.” He calls this opcode MERKLEBRANCHVERIFY.

The second BIP is number 117, which is titled Tail Call Semantics. Friedenbach explains how it would work to achieve MAST stating: “This BIP, in conjunction with BIP 116, allows for a script to commit to a practically unbounded number of code pathways, and then reveal the actual code pathway used at spend time. This achieves a form of generalized MAST enabling decomposition of complex branching scripts into a set of non-branching flat execution pathways, committing to the entire set of possible pathways, and then revealing only the path used at spend time.”

While Laus’ proposals can only function within the SegWit script, Friedenbachs proposals can be implemented within the three scripts currently in use in the Bitcoin blockchain. These are bare, P2SH, and SegWit. “By using modularity and composition of powerful but simple tools like MERKLEBRANCHVERIFY and single tail-call recursion to construct MAST we enable a complex and desirable feature while minimizing changes to the consensus code, review burden, and acquired technical debt.”

Gregory Maxwell’s Taproot

While Lau and Friedenbach are focused on MAST because of the efficiency the protocol can introduce, Gregory Maxwell is looking at the increased privacy that can be facilitated by its implementation.

Maxwell is developing a protocol named Taproot that aims to preserve the privacy of transactions. Due to the fact that transactions with conditions are easily distinguishable from those that are simple spends, Maxwell proposes a construction that would allow complex smart contracts to look like simple payments.

Taproot is a special kind of Merkle root which functions as a delegating CHECKSIG. This tool makes it impossible to distinguish between smart contract fulfillments and other simpler transactions as “the verification computational complexity of signature path is obviously the same as any other plain signature (since its indistinguishable). Verification of the branch redemption requires a hash and a multiplication with a constant point which is strictly more efficient than a signature verification and could be efficiently fused into batch signature validation.”

What Are the Advantages of Implementing MAST?

The greatest advantage offered by the addition of MAST is the possibility of smart contract functionality as well as scalability. Using MAST, it is possible to write a long list of conditions within a spend without a proportionate growth in data. Due to this, it is possible to create complex smart contract on the Bitcoin blockchain. Furthermore, MAST can also help address scalability concerns. The upgrade is quite unique, in the respect that there is no trade-off between efficiency, functionality and privacy.

Moreover, MAST would lead to a greater level of privacy associated with transactions on Bitcoin’s blockchain because only the information used while the transaction is process is included in the transaction data. Data that may be attached to a bitcoin but is unused in a transaction, such as a timelock or a condition, is not included in the transaction data. This protects the privacy of those included in the conditions because data related to them is not made publicly visible. In addition, MAST can also restore fungibility as it would make it impossible to ascertain which units were attached to a smart contract and which were simple spends.

Lastly, the use of MAST would lead to much less data per transaction because of the use of Merkle trees. Merkle roots and Merkle proofs would remove the need to include the whole data set. As a result of this, transactions on the blockchain would also be faster.

While it remains to be seen when MAST will be added into Bitcoin’s blockchain, it would definitely augur well for the digital currency and its functionalities if it does happen.