There is much talk about Smart Contract on Ethereum, and indeed they have led to several innovations on the cryptocurrencies world. But now, this will also be possible on Bitcoin, when MAST (Merkel Abstract Syntax Trees) protocol will be integrated.
MAST allows the creation of algorithms with different functionalities and conditions within the Bitcoin Blockchain, enabling only a relatively small amount of data to be inserted in the transaction block.
MAST combines functionalities of Merkle Trees and Abstract Syntax Trees (AST) algorithms to represent programs in a compact and secure way. The data structure of Merkle Trees can be used to efficiently verify the integrity of the stored data.
The data blocks are stored in the leaf nodes, while each non-leaf node is the hash of the labels of their child nodes. In the Bitcoin Blockchain, Merkle Trees are currently used to efficiently store transactions history. ASTs, on the other hand, represent the syntactic structure of the programs. Primitives are in the ASTs leaf nodes and the non-foliar nodes represent programmatic operations and flow control mechanisms.
They work by taking a program and dividing each conditional part of it into a separate segment, and then placing each of these segments in a Merkle Tree.
A minimum set of conditions that must be used for final validation can be revealed to all complete validation nodes, but the code that is not executed can be replaced by a simple hash as part of a partial Merkle branch, allowing all parts of the script to be linked to the Merkle root used used in such a way that the validation can be completed. This not only saves space, but can also help improve privacy.
For example, if Alice wants to be able to spend her bitcoins normally every day, but she also wants that her lawyer, Bob, is able to spend her bitcoins if they have been inactive for a year, she can put both conditions into branches separated. When Alice is doing normal expenses, no one can know it, but just looking at the transaction will see the second condition.
The enabling of MAST can be performed using the version control of Bitcoin Script enabled by SegWit; this next step improves Bitcoin’s flexibility, scalability and privacy.
MAST essentially fuses the P2SH potential with that offered by Merkle Trees. Most non-standard Bitcoin transactions, such as Multi-Sig or Check Lock Time Verify, use a slightly more complex scheme, called “P2SH” (which stands for Pay to Script Hash). With P2SH, bitcoins are still locked up in a script. But this script is not included in the transaction output. Just like P2SH, all these different scripts are subjected to hashes. But this time, they are combined in a Merkle tree. And it is the Merkle root of this Merkle tree that is included in a transaction output, as a kind of definitive block.
Instead of blocking bitcoins in a single script, with MAST the same bitcoins can be locked up in a series of different scripts. In other words, same bitcoins can be locked in a series of different and mutually exclusive conditions. Whatever of these conditions is satisfied in a (confirmed) transaction first determines how bitcoins are spent.
To create a transaction that unlocks funds from Merkle roots, it is necessary to include the entire script used in the new transaction, as well as the requirement to unlock that script.
But above all: not all potential scripts should be included, but only the one actually used, considering that there is a size limit currently imposed by the protocol on different options to prevent DoS attacks.
MAST extends the smart contract flexibility as it removes any such limit. This also allows for new and complex possibilities, such as 1 in 1000 Multi-Sig transactions, which are currently too large. Or long lists of users who can spend specific bitcoins at different times.
MAST can be used to represent in a compact way the contractual programs that will be executed remotely and, using some properties of Merkle Trees, which can also be used to verify the integrity of the code in execution.
A MAST node is constructed with strings contents and father pointers. The content of the string is a code that can be executed. A MAST node can have any number of sons, each of which represents a different branch of program execution, and new branches can be added via the “addBr” method.
By combining all the string content from each node along a path into a MAST, then it possible to get the code for a possible run path for a program. Since the branches in a MAST should not be added in a particular order, maintaining consistency during tree building would be cumbersome.
Instead of that, the hash function of a MAST node calculates the correct Merkle hash using the current state of the tree. It does this at first by forming a binary tree of all direct son nodes. As this tree is built, hashes are concatenated and a new hash is added to each Merkel Tree binary level.
To verify the code integrity, the MAST function generates a list of tests on a given Merkle root hash from the current node. It does this by crossing the tree upwards, generating a list of Merkle hashes and the content of the code it parses. Logic becomes more complicated due to the Merkle hashes are calculated using a binary tree.
As a result, the test list generator scans this binary tree until it reaches the Merkle root of the branch (the main MAST node), then repeats the process until the destination node is reached.
MAST allows to create complicated smart contracts on the blockchain without clogging. Normally all smart contracts would be easily visible on the blockchain and would take up a lot of space. MAST protects privacy by revealing only the smart contracts that have been completed and saves space on the chain because the nodes will only read the upper level of Merkle Tree.
For example, at this time Lightning Network transactions are easily identifiable due to the P2SH hash they use. In light of this, nodes are able to censor LN transactions if they decide to do so. MAST would be able to hide LN transactions making them indistinguishable from other Blockchain transactions.