How to maximize Bitcoin's resilience, scalability, and privacy? The answer lies in this new improved protocol MAST

The upcoming Segregated Witness (SegWit) soft fork can tap into the potential of Bitcoin in many ways. One of the potential innovations brought by Segregated Witness is MAST ( Merkelized Abstract Syntax Trees , there is no unified translation method yet, readers are welcome to contribute to the forum). The main goal of MAST is to improve the flexibility, scalability and privacy of smart contracts.

The MAST scheme was jointly proposed by Blockstream developer Russell O'Connor, Blockstream and Core developer Pieter Wuille, and Core developer Peter Todd. Recently, the MAST draft has been written into the Bitcoin Improvement Protocol (BIP) by Core developer Johnson Lau.

The potential of MAST is endless.

P2SH

To understand MAST, you must first understand脚本哈希支付方式（P2SH，Pay to script hash） . P2SH has been operating in Bitcoin transactions for many years.

All Bitcoin transactions ultimately involve "locking Bitcoin" to a certain address when outputting. These locked Bitcoins will be unlocked (and then locked again) in subsequent transactions; this is the process of transferring Bitcoin between addresses (that is, the transaction process).

This locking process is done by a script, which is a few lines of code. In a standard transaction, this script is included in the output to specify how bitcoins are transferred in subsequent transactions.

Non-standard Bitcoin transactions using多重签名（multisig） or CheckLockTimeVerify require a relatively complex mechanism, namely P2SH. In this mode, Bitcoin is still locked by a script language. But this script language will not appear in the transaction output. This script language will be hashed, appear in a disordered form, and shortened in length, and look like a string of random numbers. This string of random numbers cannot be used to copy the initial script, but once the initial script is available, this string of random numbers can be copied by hashing again. What appears in the transaction output is only the hash of this script language.

To unlock a P2SH output in a subsequent transaction, it is not enough to simply comply with the requirements of the scripting language. After all, the Bitcoin nodes in the network only see the hashed script, not the original script. Therefore, the nodes cannot verify and confirm the transaction.

Therefore, the next transaction must contain the entire script and its prescribed transfer method, i.e. the key responsible for locking (script language) and the key responsible for unlocking (transfer method).

After hashing the correct script, the Bitcoin node can verify whether the script matches the script hash in the previous output. If it matches, the node knows that the Bitcoin is indeed locked in a specific script. Then they can verify whether the transaction conforms to the transfer method specified in the script, and finally the transaction can be confirmed.

Merkle Tree

Another key to unlocking the mystery of MAST is梅克尔树（Merkle tree also known as a binary hash tree).

Essentially, a Merkle tree is a mathematical structure that can hash several different sets of data into a single compact hash:梅克尔树根（Merkle root a binary hash root). Like other hashes, the Merkle root cannot be used to recreate the data in the Merkle tree.

However, the Merkle tree has a unique advantage. If any data in the Merkle tree is known, the specific location of the data in it can be confirmed by simply using the Merkle tree root.

Let's take a simple example. Xiaohong creates a Merkle tree, combining the data sets "123" and "456" together, and the resulting Merkle root is "789". Xiaohong then tells Xiaoming that the data "123" is at a certain position in the Merkle tree. Through the Merkle root ("789"), Xiaoming can verify whether "123" is really at the position Xiaohong said, even if he doesn't know the existence of "456". In fact, even if he knows that there may be tens of thousands of data sets in the Merkle tree, he cannot decipher any of them.

MAST = P2SH + Merkle Tree

MAST actually combines the advantages of P2SH and Merkle tree.

MAST does not lock Bitcoin in a single script, but locks the same Bitcoin in different scripts. In other words, the same Bitcoin can be locked in a series of different, even mutually exclusive conditions. The transaction that matches the conditions first can use the Bitcoin first.

For example, if the transaction condition requires Xiaohong's signature, or requires Xiaoming and Xiaohua's signatures, or requires Xiaohua's signature after a certain time, etc. Assuming Xiaohong is the first to sign, then the output will be generated and the transaction will take effect. If Xiaoming and Xiaohua sign before Xiaohong, then their transaction will take effect. And so on.

Like P2SH, the scripts involved in the above transactions are all hashed. But at the same time, they exist in the Merkle tree. The corresponding Merkle tree root is in the transaction output and can be finally locked.

To create a transaction that unlocks a transaction in the Merkle root, the entire script and the corresponding unlocking requirements must be included in the new transaction (equivalent to the lock and key).

But the important thing is: the transaction does not have to include all potential scripts. Only the useful ones are left. Going back to the above example, if Xiaohong wants to use the bitcoin first, then her transaction does not need to include the scripts that Xiaoming or Xiaohua need. In fact, Xiaohong does not need to know the scripts of others.

With MAST, Bitcoin nodes can use Merkle trees to verify scripts. They can use the Merkle tree root included in the output to check whether a certain script actually exists in the corresponding Merkle tree. If the result is positive, the transaction can be confirmed.

Advantages

MAST can improve the Bitcoin network in three main ways: improving the resilience, scalability, and privacy of smart contracts .

The smart contract resiliency that MAST enables is not entirely new. P2SH already has some usable “either/or” instructions (for example, requiring Alice’s signature或Bob and Bob’s signature). However, P2SH instructions have protocol-level limitations when it comes to responding to DoS attacks.

MAST can get rid of this limitation while increasing the flexibility of smart contracts. Are there two feasible ways to use 20 or 1000 bitcoins? This question makes no difference to the network, no matter what, a certain script will always correspond to a specific transaction requirement. This also brings new and more complex possibilities, such as 1-of-1000 multi-signature transactions (current systems cannot accommodate such a large capacity), or listing a long list of user addresses and setting different times to send bitcoins.

In addition, the "either/or" instruction of P2SH can only be successfully unlocked after all scripts appear. This can easily cause problems such as excessive transaction information and high handling fees. MAST only requires users to provide scripts that are valid for it, thereby achieving the purpose of improving scalability. Therefore, MAST can reduce the data transferred, confirmed and stored by nodes across the entire network.

MAST can also improve privacy by hiding unavailable scripts (i.e. scripts involved in other people's transactions). For example, if a transaction is not valid, users will not be able to know the information in it. MAST can also hide some security improvements that have never been used and have expired.

Author's Note: The MAST scheme is still under development, and subsequent improvements may differ from the content of this article.
Translator's note: Since the translator is not a professional developer, if there are any misunderstandings in the translation, please feel free to correct them.