MAST concept in Bitcoin
In this article we will talk about the concept of MAST and its application to the Bitcoin protocol. We consider the properties that MAST allows, as well as the benefits of its application. The article will be interesting to readers who are interested in the Bitcoin protocol and other innovative payment systems. A separate lecture is also devoted to this topic in the online blockchain course “ MAST in Bitcoin ”.
The concept of MAST implies the use of Merkle trees and abstract syntax trees to define the conditions of spending coins at the outputs of transactions. Consider in order how it works.
So you can schematically depict Merkle Tree.
There are pieces of data for which you need to get a checksum, i.e., calculate the hash value of all the pieces. But instead of concatenating them all and giving hash functions to the input with one value, Merkle Tree offers a different approach. Each piece of data is hashed separately. Then the resulting hash values are concatenated in pairs and then hashed again. And so on until a single hash value is obtained that covers all portions of the data. This value is called Merkle Root.
Merkle Tree allows you to check the occurrence of a separate piece of data in Merkle Root, while not having all the other pieces of data. This is a valuable property.
Suppose a user has Merkle Root and data from a single transaction (in the diagram above, it is indicated in red). Then the user can take a chain of missing hash values (in the diagram they are marked in blue) in order to verify that this transaction is included in Merkle Root. Missing hash values are called Merkle Branch. For a specific transaction, they can be requested from the node that stores the full block.
This method of hashing multiple pieces of data is used in many protocols. The best-known examples are hashing transactions that are included in a block, and hashing parts of files that are transferred in the BitTorrent network to form a torrent file.
Now let's take a look at abstract syntax trees. The diagram below shows a syntax tree that describes a very simple loop. Here, the blue color indicates tree nodes, which mean operations, green indicates variables, and red - constants. Edges of a tree designate transitions between operations.
Thus, a cycle is described that is executed in a specific sequence. First, the equality of the variable A and the constant 32 is checked. If it is not fulfilled, then we go to the loop body, where the variable A is assigned the sum of two values: the variable A itself and the constant 2. This is the abstract syntax tree in general terms.
We have prepared the theoretical ground, now we will define what MAST is and what its benefits are. MAST is the Merkelized Abstract Syntax Tree, where the ideas of the Merkle tree and the abstract syntax tree are used to define mutually exclusive conditions for spending coins. At the same time, Bitcoin Script acts as a language for describing conditions. The concept of MAST allows you to increase confidentiality and reduce the size of transactions.
People like Russell O'Connor, Pieter Wuille, Peter Todd and Johnson Lau started to develop and promote the idea of MAST in the Bitcoin community. At the beginning of 2016, a proposal to improve the Bitcoin protocol under number 114 (BIP114) was published, where the specification of one of the options for implementing this approach using witness programs, which in turn were introduced with the update of SegWit, was described. BIP114 also offers a software implementation that adds new consensus rules to the Bitcoin protocol.
Later, in 2017, they proposed an alternative implementation of the MAST concept, which is described in BIP117. It is based on BIP114 and makes some modifications. At the time of 2018, both proposals remain at the stage of consideration.
Note that MAST can be integrated into Bitcoin using softfork protocol updates. And this is perhaps the most important feature of this concept.
Sketchy Merkelized Abstract Syntax Tree will look like this.
Here MAST Root is the root hash value that will be placed in the output of the transaction. Blue color indicates the hash values of tree branches, which lead to the conditions of spending coins. Thus, these branches contain mutually exclusive conditions under which coins can be spent. Therefore, the one who spends coins will use either one branch or the other.
Yellow color indicates conditions that are set using Bitcoin Script. Moreover, the conditions under which the coins are most likely to be spent are recommended to be placed as close as possible to the root of the tree — this will make the proof of ownership of the coins smaller.
Let's identify the problems that arise during the usual setting of conditions for spending coins using Bitcoin Script. The first, and most important of them, is that the recipient needs to describe or transmit the conditions on which he wants to receive the payment so that the sender specifies them in the output of his transaction. MAST and P2SH solve this problem.
The second problem: complex conditions occupy a large amount of memory in the output of the transaction. As a result, the sender must pay a fee for establishing such difficult conditions for obtaining coins, although they are dictated by the recipient. P2SH and MAST also cope with this by shifting the need to include large amounts of data in the transaction that will be spent, and accordingly the recipient will pay the increased commission, and not the sender.
The third problem is that ScriptPubKey, which fits in the output of a transaction, is limited in size and number of operations, i.e. OP_CODEs. The concept of MAST allows you to almost completely get away from these restrictions without compromising reliability due to mutually exclusive conditions.
The fourth problem: when sending coins, everyone immediately sees the conditions of their spending. MAST allows you to hide the conditions of spending until the moment of the most waste. Moreover, only those conditions that are actually used will be disclosed, and not all possible options.
One of them is to increase the level of user privacy by hiding the conditions of waste that were not used in the end. This property is achieved by proving that only certain conditions are included in MAST Root and satisfying these conditions.
Another positive feature is the ability to set more voluminous and difficult coin spending conditions. For example, using MAST, you can specify hundreds of thousands of different multi-signature options for a single transaction output. In this case, the conditions of spending coins and the corresponding proof of ownership of coins will be very compact.
In addition, it becomes possible to record data of arbitrary size in the blockchain without increasing the size of the transaction.
This diagram shows a variant of the MAST structure in accordance with BIP114. Hash values are marked in blue, Bitcoin Script in yellow, and arbitrary data in red as an additional message. The version value is included at the top of the tree.
Here are two mutually exclusive conditions for spending coins. In the first case, coins can be spent by giving one signature and waiting for a certain time to arrive, and in the second case you need to provide several signatures. Users can resort to one of the options, while the conditions of the second will not be disclosed.
In the first case, MAST can be applied to a more optimized implementation of HTLC (Hashed Time-Lock Contracts), which are used in the Lightning Network protocol. In the other - for a more optimized implementation of Escrow.
MAST makes it possible to implement very large constructions using multisignature. This will help solve such pressing problems as the theft or loss of bitcoins, and in some cases even allow you to give up cold storage.
Thanks to MAST, in many cases, you can opt out of the OP_RETURN operation to add data to the Bitcoin blockchain. Instead, you can include this data in the tree and, if necessary, prove that the specific data were recorded in the Bitcoin blockchain. You do not need to increase the size of the blockchain itself.
Pay attention to the optimization of the amount of data that eventually fall into the blockchain. Take a close look at the chart below. The vertical axis indicates the amount of data in bytes, while the scale itself is logarithmic. The horizontal axis indicates the number of alternative coin spending conditions.
The blue line indicates the dependence of the amount of data on the number of conditions without using MAST. The red line indicates the dependence of the amount of data on the number of conditions using MAST. The blue line is the Bitcoin Script size limit for P2SH. The green line is the Bitcoin Script size limit in the witness structure.
The conclusion is simple. The concept of MAST allows you to store a much smaller amount of data with the same reliability of verification and much greater functionality.
And now we come to the frequently asked questions on this topic.
- Will MAST Root be asked in the witness structure or where will it be listed?
MAST Root, along with the data that defines it, will be indicated in the ScriptPubKey at the exit of the transaction. This data will occupy 25-35 bytes and, most likely, they will be easily encoded into the usual Bitcoin address. And in the witness structure, where the possession of coins is proved, Merkle Branch and data that meet the conditions of the waste, such as electronic signatures, will be indicated.
- Will the many available OP_CODEs be extended in Bitcoin Script?
At the moment, it is not yet clear, because the proposal is under consideration and additional amendments and improvements can be made. It is likely that OP_CODE, such as OP_MERKLEBRANCHVERIFY, will be added for the flexibility of using MAST. Perhaps they will offer something else useful, but this is not yet accurate.
- Is there a chance of integrating MAST in the near future?
The probability of course is, but it is small. After all, this update is important, but not urgent, so it can wait until the developers think about other protocol improvements. Later they can integrate several improvements in one update at once, as was the case with SegWit.
The concept of MAST implies the use of Merkle trees and abstract syntax trees to define the conditions of spending coins at the outputs of transactions. Consider in order how it works.
Merkle tree
So you can schematically depict Merkle Tree.
There are pieces of data for which you need to get a checksum, i.e., calculate the hash value of all the pieces. But instead of concatenating them all and giving hash functions to the input with one value, Merkle Tree offers a different approach. Each piece of data is hashed separately. Then the resulting hash values are concatenated in pairs and then hashed again. And so on until a single hash value is obtained that covers all portions of the data. This value is called Merkle Root.
Merkle Tree allows you to check the occurrence of a separate piece of data in Merkle Root, while not having all the other pieces of data. This is a valuable property.
Suppose a user has Merkle Root and data from a single transaction (in the diagram above, it is indicated in red). Then the user can take a chain of missing hash values (in the diagram they are marked in blue) in order to verify that this transaction is included in Merkle Root. Missing hash values are called Merkle Branch. For a specific transaction, they can be requested from the node that stores the full block.
This method of hashing multiple pieces of data is used in many protocols. The best-known examples are hashing transactions that are included in a block, and hashing parts of files that are transferred in the BitTorrent network to form a torrent file.
Abstract Syntax Tree
Now let's take a look at abstract syntax trees. The diagram below shows a syntax tree that describes a very simple loop. Here, the blue color indicates tree nodes, which mean operations, green indicates variables, and red - constants. Edges of a tree designate transitions between operations.
Thus, a cycle is described that is executed in a specific sequence. First, the equality of the variable A and the constant 32 is checked. If it is not fulfilled, then we go to the loop body, where the variable A is assigned the sum of two values: the variable A itself and the constant 2. This is the abstract syntax tree in general terms.
What is MAST?
We have prepared the theoretical ground, now we will define what MAST is and what its benefits are. MAST is the Merkelized Abstract Syntax Tree, where the ideas of the Merkle tree and the abstract syntax tree are used to define mutually exclusive conditions for spending coins. At the same time, Bitcoin Script acts as a language for describing conditions. The concept of MAST allows you to increase confidentiality and reduce the size of transactions.
Concept development and current position
People like Russell O'Connor, Pieter Wuille, Peter Todd and Johnson Lau started to develop and promote the idea of MAST in the Bitcoin community. At the beginning of 2016, a proposal to improve the Bitcoin protocol under number 114 (BIP114) was published, where the specification of one of the options for implementing this approach using witness programs, which in turn were introduced with the update of SegWit, was described. BIP114 also offers a software implementation that adds new consensus rules to the Bitcoin protocol.
Later, in 2017, they proposed an alternative implementation of the MAST concept, which is described in BIP117. It is based on BIP114 and makes some modifications. At the time of 2018, both proposals remain at the stage of consideration.
Note that MAST can be integrated into Bitcoin using softfork protocol updates. And this is perhaps the most important feature of this concept.
MAST on the diagram
Sketchy Merkelized Abstract Syntax Tree will look like this.
Here MAST Root is the root hash value that will be placed in the output of the transaction. Blue color indicates the hash values of tree branches, which lead to the conditions of spending coins. Thus, these branches contain mutually exclusive conditions under which coins can be spent. Therefore, the one who spends coins will use either one branch or the other.
Yellow color indicates conditions that are set using Bitcoin Script. Moreover, the conditions under which the coins are most likely to be spent are recommended to be placed as close as possible to the root of the tree — this will make the proof of ownership of the coins smaller.
Problems with transactions in Bitcoin
Let's identify the problems that arise during the usual setting of conditions for spending coins using Bitcoin Script. The first, and most important of them, is that the recipient needs to describe or transmit the conditions on which he wants to receive the payment so that the sender specifies them in the output of his transaction. MAST and P2SH solve this problem.
The second problem: complex conditions occupy a large amount of memory in the output of the transaction. As a result, the sender must pay a fee for establishing such difficult conditions for obtaining coins, although they are dictated by the recipient. P2SH and MAST also cope with this by shifting the need to include large amounts of data in the transaction that will be spent, and accordingly the recipient will pay the increased commission, and not the sender.
The third problem is that ScriptPubKey, which fits in the output of a transaction, is limited in size and number of operations, i.e. OP_CODEs. The concept of MAST allows you to almost completely get away from these restrictions without compromising reliability due to mutually exclusive conditions.
The fourth problem: when sending coins, everyone immediately sees the conditions of their spending. MAST allows you to hide the conditions of spending until the moment of the most waste. Moreover, only those conditions that are actually used will be disclosed, and not all possible options.
Properties, which gives the use of MAST in Bitcoin
One of them is to increase the level of user privacy by hiding the conditions of waste that were not used in the end. This property is achieved by proving that only certain conditions are included in MAST Root and satisfying these conditions.
Another positive feature is the ability to set more voluminous and difficult coin spending conditions. For example, using MAST, you can specify hundreds of thousands of different multi-signature options for a single transaction output. In this case, the conditions of spending coins and the corresponding proof of ownership of coins will be very compact.
In addition, it becomes possible to record data of arbitrary size in the blockchain without increasing the size of the transaction.
This diagram shows a variant of the MAST structure in accordance with BIP114. Hash values are marked in blue, Bitcoin Script in yellow, and arbitrary data in red as an additional message. The version value is included at the top of the tree.
Simplified MAST Scheme
Here are two mutually exclusive conditions for spending coins. In the first case, coins can be spent by giving one signature and waiting for a certain time to arrive, and in the second case you need to provide several signatures. Users can resort to one of the options, while the conditions of the second will not be disclosed.
Application of MAST in practice
In the first case, MAST can be applied to a more optimized implementation of HTLC (Hashed Time-Lock Contracts), which are used in the Lightning Network protocol. In the other - for a more optimized implementation of Escrow.
MAST makes it possible to implement very large constructions using multisignature. This will help solve such pressing problems as the theft or loss of bitcoins, and in some cases even allow you to give up cold storage.
Thanks to MAST, in many cases, you can opt out of the OP_RETURN operation to add data to the Bitcoin blockchain. Instead, you can include this data in the tree and, if necessary, prove that the specific data were recorded in the Bitcoin blockchain. You do not need to increase the size of the blockchain itself.
Optimization of data volume
Pay attention to the optimization of the amount of data that eventually fall into the blockchain. Take a close look at the chart below. The vertical axis indicates the amount of data in bytes, while the scale itself is logarithmic. The horizontal axis indicates the number of alternative coin spending conditions.
The blue line indicates the dependence of the amount of data on the number of conditions without using MAST. The red line indicates the dependence of the amount of data on the number of conditions using MAST. The blue line is the Bitcoin Script size limit for P2SH. The green line is the Bitcoin Script size limit in the witness structure.
The conclusion is simple. The concept of MAST allows you to store a much smaller amount of data with the same reliability of verification and much greater functionality.
And now we come to the frequently asked questions on this topic.
Frequently asked Questions
- Will MAST Root be asked in the witness structure or where will it be listed?
MAST Root, along with the data that defines it, will be indicated in the ScriptPubKey at the exit of the transaction. This data will occupy 25-35 bytes and, most likely, they will be easily encoded into the usual Bitcoin address. And in the witness structure, where the possession of coins is proved, Merkle Branch and data that meet the conditions of the waste, such as electronic signatures, will be indicated.
- Will the many available OP_CODEs be extended in Bitcoin Script?
At the moment, it is not yet clear, because the proposal is under consideration and additional amendments and improvements can be made. It is likely that OP_CODE, such as OP_MERKLEBRANCHVERIFY, will be added for the flexibility of using MAST. Perhaps they will offer something else useful, but this is not yet accurate.
- Is there a chance of integrating MAST in the near future?
The probability of course is, but it is small. After all, this update is important, but not urgent, so it can wait until the developers think about other protocol improvements. Later they can integrate several improvements in one update at once, as was the case with SegWit.