Bitcoin’s Merkelized Abstract Syntax Tree (MAST) Explained!!

Last week if you remember we discussed Pay To Script Hash (P2SH), a fundamental concept in Bitcoin transactions that improves the scalability of Bitcoin.

But as discussed in that previous article on P2SH that more complicated scripts or conditions can create data-heavy Bitcoin transactions for the owners of P2SH addresses.

That’s why a new and more optimized way of transactions is proposed for Bitcoin to improve the scalability, flexibility, and privacy of Bitcoin.

It is called Merklized Abstract Syntax Trees (MAST).

But before jumping on it, I want to talk some basics.

If you don’t know, bitcoins are essentially locked in a script (a couple of lines of codes), and when that script returns true or is satisfied, the bitcoins are unlocked.

You can look at this script as a smart contract also which is again merely a couple of lines of code which executes itself when fed with relevant inputs.

A similar thing happens when someone is trying to spend bitcoins from a P2SH address, where they need to produce the whole script (conditions), the script hash and the requirements to unlock it on the blockchain.

But what if the script (conditions) are too many?

This can make the transaction too heavy if too many conditions are present while transacting through a P2SH address.

But Bitcoin’s MAST (Merklized Abstract Syntax Trees) provides a solution to it.

What Is Mast In Bitcoin?

MAST (Merklized Abstract Syntax Trees) is an amalgamation of two concepts called Merkle Trees and Abstract Syntax Trees.

Don’t get overwhelmed by these technical terms as I am going to make it as simple as possible.

MAST is like pay to the Merkle root’s hash as in Pay To Script Hash (P2SH) we have “pay to a script matching this hash.”

Still not making sense?

Well, stick around as I am going peel the onion layers one by one.

MAST technique allows us to create a hash tree of individual scripts (or conditions) that are present in a complicated condition set.

And all these conditions can be condensed in a single hash called the Merkle root. But one would say, how this Merkle root is different from the pay to script hash?

Well, it is different, and you will understand this by reading, how a Merkle root is formed?

To generate a Merkle root, a Merkle tree is formed, and for that, each condition (or script) is individually hashed, and then the resultant hashes are again paired with the nearby hashes to make a set of new hashes again. This process is continued untill only one hash is remained, and this is called as the Merkle root.

For example, have a look at this set of 4 conditions that are first hashed individually, and then two pairs are formed from these four hashes to be hashed again. This generates two more hashes respectively from those two pairs which are again combined to create the final hash. This is called as the Merkle root.

And just like in P2SH we can convert scripts (or conditions) in payable Bitcoin addresses or Bitcoin PubKeys, in MAST too we can turn this Merkle root into a valid and payable Bitcoin address.

This Merklized Bitcoin address that we derive through MAST technique has several benefits, and one of these benefits is the ability to verify an individual script (or condition) that is encapsulated somewhere in the Merkle tree without know all the individual scripts (or conditions)

This trick is called Merkle Proof and here is a simple example to understand it:

Let say there are two data sets (or conditions) that are Merklized into a Merkle root. We have a one set as ’11’ which lets Bob spend the bitcoins and other is ’12’ which lets Alice spend the bitcoins. And now these two conditions make a Merkle root which is ‘121’.

Now anyone with the root ‘121’  and the presented condition ’11’ can verify that condition ’11’ is somewhere present in the Merkle tree even when they have no knowledge of condition ’12’.

Similarly, anyone with the root ‘121’ and the presented condition ’12’ can verify that condition ’12’ is somewhere present in the Merkle tree even when they have no knowledge of condition ’11’.

This enables a Bitcoin transaction to have several conditions and yet it is easy to verify.

Also, while using MAST enabled addresses you need not include the whole script (or conditions) in the UTXO for spending it because even a part of the entire script (or an individual condition) can be verified against the hash of the whole script, i.e., Merkle root.

This way instead of locking bitcoins in a single complicated script, MAST can be used to lock up bitcoins in small individual scripts (or conditions) that are mutually exclusive.

For example, these mutually exclusive conditions could be:

  • Alice’s signatures are needed to unlock these bitcoins.
  • Or Bob’s signature is required when a certain amount of time is passed to unlock the coins
  • Or apart from a valid signature of Harry, he needs to provide a password to unlock the coins.

So whichever condition is satisfied the bitcoins will become spendable for that person !!

I know some of you might be thinking, how this works on the blockchain?

Spending Of Transaction

The spending of bitcoins is much like we have in P2SH, but here in MAST, the bitcoins are locked in the Merkle root which is derived as I have explained in the previous section by hashing individual conditions and stacking them in a Merkle tree.

So to spend this Bitcoin output from the Merklized address one needs to produce the script, the script hash (Merkle root) and other requirements like the signatures to unlock the coins.

Sound like the P2SH?

Well, but in MAST, one need not include the whole set of the script (or conditions) and instead can only produce the script that is actually being used.

Now using the Merkle proof trick, Bitcoin clients can execute and produce the hash of the actual script being used which can be verified against the Merkle root.

Now because the hash of the condition being used and the Merkel root are enough to check whether the condition was part of the original condition set, you now have a compact transaction.

And when this is verified the blockchain gets to know that the coins were locked in this script only and the transaction gets successful.

This construct of hiding unexpected script branches allows you to have complicated redemption conditions where each of the condition is a leaf on the Merkle tree. When you are spending, you only need to present the branch plus a proof that it was part of the Merkle tree without showing any other information or branches and this is what MAST enables.

Benefits Of Bitcoin MAST

Bitcoin Mast improves the flexibility of Bitcoin smart contracts, increases privacy, and helps a great deal in scalability.

Since many complex types of conditions can be expressed using MAST to lock up bitcoins, one can easily have multisig contracts like 1 of 1000 or 20 of 200 types easily.

Also, since MAST requires you to include only that condition in the transaction that you are using instead of the whole set has data benefits. This way your transaction becomes much smaller while simultaneously giving you the capability to engage with complex unlocking conditions. This also reduces the transaction fee that you would otherwise pay while using P2SH.

Lastly, with MAST you get the additional privacy because one can only guess by looking at a MAST transaction that there are conditions involved, but one would never come to know what those conditions were or are !!

But the fact that one can make out by looking at a transaction that someone is trying to achieve privacy by using Mast itself is a privacy loophole, and Bitcoin developers are trying to fix this problem by another technique known as Bitcoin Taproot.

We are going to discuss Bitcoin Taproot in detail in our next article so stay tuned and let us know your feedback on this article in the comments below 🙂

Further Suggested Readings…

Sudhir Khatwani

Contents

Leave a Reply

Your email address will not be published. Required fields are marked *