In recent weeks, developer Pieter Wuille has released the sources of two new BIPs for the implementation of Schnorr and Taproot on Bitcoin. The latter consists of a possible evolution of MAST, a protocol aimed at improving privacy and Bitcoin scripts.
MAST is a BIP – short for Bitcoin Improvement Proposal – initially proposed by Dr Johnson Lau in 2016.
There are several proposals for MAST, each with different implementation mechanisms. Precisely for this reason, there is no single BIP but rather different codes. There is BIP114, and the second branch of development of MAST, behind BIP116 and 117. The 117 was updated last February/January 2018, while the 114 was updated in September 2017.
What is MAST?
An acronym for Merkelized Abstract Syntax Trees, this protocol is the result of the union of Merkle Tree and AST, or abstract syntax trees. The merkle tree can be seen as a cryptographic tool to reduce the use of data within a block. It allows confirming whether data within a Merkle tree is true without having to re-download all of it.
Abstract Syntax Trees (AST), on the other hand, consist of a series of algorithms that divide a program or set of data into its constituent parts with the aim of understanding and classifying it more easily. This subdivision helps to access all important data more quickly, by easily excluding superfluous data.
Combining the Merkle trees and AST allows adding more complex data sets to the transactions that will be inserted in the bitcoin blockchain, while also allowing for the reduction of the transaction data size thanks to the use of Merkle Proofs.
Using this concept, in fact, those who carry out transactions can replace the unused data of the transaction itself with a merkle proof, so as to allow the reduction of the size of transactions, in order to increase privacy and make possible the creation of very complex smart contracts without affecting the network.
One clarification is necessary. In reality, MAST itself does not enable smart contracts on Bitcoin. It simply allows, through the features listed above, to reduce the size of data required for bitcoin scripts, thus allowing to insert complex sets within transactions and thus in the blocks of the blockchain.
The problem with Bitcoin scripts
When Satoshi Nakamoto created Bitcoin it was possible to use programs (called scripts) that could act as dynamic public keys and digital signatures. This way it was possible to spend bitcoins according to the behaviour determined by the constraints (a time constraint of expense for example) imposed in the script itself. It was a real first approach to smart contracts.
However, this approach has some limitations for more complex uses. The example proposed in the whitepaper reads as follows:
“Alice wants to be able to spend her bitcoins at any time, but if her bitcoins aren’t spent within three months (maybe because she’s dead or incapacitated), she wants her siblings Bob and Charlie to have her bitcoins as long as they can agree on where to spend them”.
In this case, the script in which the policy described above is specified includes not only Alice’s public key (necessary to verify the signature from her private key) but also a condition, a timeout and the public keys of Bob and Charlie.
In the current Bitcoin protocol, all the above data must be entered on the blockchain when Alice’s bitcoins are spent. However, parts of the script that are not used should also be included, such as Bob and Charlie’s public keys, which are useless if Alice herself spends her bitcoins.
All this unused data increases the size of the transactions. Not only that, but they also reduce privacy by publicly disclosing more information than necessary. In addition, they limit smart contracts based on their size rather than transaction validation costs.
MAST: a possible solution
The MAST protocol attempts to significantly improve the current situation by eliminating the need to directly include unused parts of a script on the blockchain. This not only reduces the size of transactions but also improves privacy and makes it possible to create complex smart contracts in bulk.
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)”.
In summary, MAST using AST allows splitting a script into its individual parts, while the Merkle trees allow verifying that these parts belong to a complete script without having to own the entire code, which therefore will not have to be included in its entirety every time on the blockchain.
Applying this idea to the example above, with Alice who can spend her bitcoins whenever she wants, but if she doesn’t spend them for three months they are sent to the brothers Bob and Charlie (a kind of virtual will), it is necessary to first create a Merkle tree.
The root of the Merkle tree uniquely identifies Alice’s and the participants’ script using only 32 bytes of data. To do this, each node in the tree has its own unique hash identifier. Each of these identifiers is then coupled to the identifier of another node.
A unique hash identification is then generated again, this time referring to that pair of nodes. This step is repeated until only one identifier remains, i.e. the Merkle root. It uniquely identifies the entire set in a few bytes of data, in this example only 32 Bytes.
At this point, Alice adds a constraint in which she imposes that a Spender must provide a proof of Merkle linking the Merkle root to one of the subscripts. This subscript must return the value “True” to allow the actual spending.
It is, therefore, possible to obtain considerable memory savings within the transactions, which, by exploiting this system, will include only what is strictly necessary.
Optimisation of the use of the blockchain
The first thing that stands out is the saving of data within the blocks. In the previous example, we used a rather simple Bitcoin script, but it is also possible to add several subscripts with new conditions and constraints. It follows that, by using MAST, it is possible not only to have a considerable reduction in the size of the data but also to allow the creation of more and more extensive and complex scripts.
The Merkle tree approach also further optimises memory usage, resulting in better data reduction in the case of actual usage. In simple terms, referring to the previous example of the “digital will”, the most realistic scenario is that Alice continues to spend her bitcoins, because she continues to live. The pessimistic one, on the other hand, is the case in which Alice dies, and therefore her bitcoins pass to her brothers.
The tree structure rewards – in terms of memory usage – the most realistic case, namely that Alice does not die (in yellow), allowing her to carry out her transactions with the least memory usage compared to all other more unlikely cases (red/purple).
In any case, the advantage with respect to the Bitcoin protocol is at least one order of magnitude better, especially with complex scripts.
More privacy for bitcoin
Among other advantages, it also improves the privacy of Bitcoin. The reason is quite simple: only essential data is entered in the blockchain and not superfluous data.
In the original scenario – without MAST -, all script data would be uploaded to the blockchain. Among them there would also be the public keys of Bob and Charlie, so an attacker could trace who will inherit Alice’s bitcoins. With MAST, on the other hand, it would not be possible to trace the conditions imposed and the heirs solely with the information shared.
There are also other advantages in terms of privacy, but they involve mass adoption of MAST to become truly effective. To avoid that an attacker recognises the use of a specific script by Alice, a “mass” script could be created that is the same for all MAST users, with the aim of making individual cases indistinguishable from others.
But this is a very special case, which is not due to MAST itself but to a possible implementation.
On the privacy front, further progress has been made with Taproot, a true evolution of MAST which, combined with Schnorr’s signatures, offers a tangible improvement in Bitcoin’s privacy.
More complex Bitcoin scripts
The most interesting feature of MAST is the possibility of creating increasingly complex smart contracts (scripts). To date, Bitcoin has three different byte size limits that can be used by individual scripts depending on the constraints. There is a limit of 10,000 bytes, added in July 2010, for Bare scripts. A limit that drops to 520 bytes for P2SH scripts. Segwit, on the other hand, has a limit of 10,000 bytes.
Looking at the graph it is possible to notice that with MAST you can have much more complex scripts (more reiterations, subscripts, conditions etc) than with other mechanisms. All this within the P2SH limit.
There are also other limits that apply to Bitcoin scripts which MAST allows to bypass since it does not require unused scripts to be processed by a full node. Overall, MAST maintains and significantly improves the scalability of Bitcoin scripts, maximising the use of resources, shifting the bulk of the burden of contract management to the participants themselves, so as to have minimal impact on the network.
So, the actual result of MAST is not to allow Bitcoin users to create scripts that are more advanced than before (it could already be done but using a lot of resources), but to allow such operation without weighing down the Bitcoin network.
Taproot: the possible implementation of MAST
At the moment the BIP that is most likely to be implemented in the Bitcoin protocol is the one recently proposed by Pieter Wuille, which provides for the integration of MAST in the most recent evolution: Taproot.
It is difficult to assume when the actual fork for upgrading Bitcoin will occur (a soft fork may not be enough). However, the recent release on Github of the very first source codes will allow the community to check and test the proposed BIPs, evaluating together any changes as well as the definitive confirmation for the final upgrade.
