The soon-to-be proposed SegregatedWitness soft fork is set to extend Bitcoin’s potential in several ways. One potentially promising innovation enabled by “SegWit” is MAST, an abbreviation for Merkelized Abstract Syntax Trees. While mainly designed to increase smart contract flexibility, MAST would increase scalability and privacy on the platform at the same time. The idea of MAST originates from Blockstream developer Russell O’Connor, Blockstream and Bitcoin Core developer, Dr. Pieter Wuille, and Bitcoin Core developer, Peter Todd. It was recently drafted into an initial Bitcoin Improvement Proposal (BIP) by Bitcoin Core developer Dr. Johnson Lau. Given its potential, MAST is surprisingly straightforward.
P2SH: A Primer
One part of the MAST puzzle is based on P2SH, which has been used in certain Bitcoin transactions for several years now.
All Bitcoin transactions in effect “lock bitcoins up” in outputs, which typically refer to Bitcoin addresses. These bitcoins are locked to be unlocked (and then locked again) in a later transaction; that’s how bitcoins effectively move from address to address.
This locking-up is really done with a script — a couple lines of code. For standard transactions, the script is included in the output and defines the requirement to spend bitcoins in a later transaction.
Most non-standard Bitcoin transactions, like multisig or CheckLockTimeVerify, 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 itself not included in the transaction-output. Rather, the script is hashed; it’s scrambled and condensed into a short and seemingly random string of numbers. This string of numbers cannot be used to reproduce the original script. But with the original script, the string of numbers can be reproduced by simply hashing it again. The hash of the script is what’s included in the transaction-output.
To unlock a P2SH-output in a next transaction, it’s not sufficient to meet the requirements as defined in the script. After all, Bitcoin nodes on the network only know the hash of the script; not the actual script. These nodes, therefore, cannot verify that the requirements as defined in the script are met. They cannot confirm the transaction.
That’s why the next transaction, which spends the bitcoins, must include the whole script, as well as the requirements as defined in that script: the lock (script) itself, as well as the key (requirements) to unlock it.
By hashing the actual script, Bitcoin nodes can verify that the included script matches the script hash that was included in the previous output. If it matches, nodes know that the bitcoins were indeed locked into that specific script. Then they can verify that the requirements as defined in the script were met, and the transaction can be confirmed.
Merkle Trees: A Primer
The other part of the MAST puzzle is a cryptographic trick called Merkle tee.
A Merkle tree is basically a mathematical structure that hashes different sets of data into a single, compact hash: the Merkle root. Much like any other hash, this Merkle root cannot be used to recreate the data in the Merkle tree.
But Merkle trees offers a unique benefit. If any of the data in the Merkle tree is known, the Merkle root can be used to verify that that specific data is really somewhere in the Merkle tree — even if not all data in the Merkle tree is known.
As a simplified example, let’s say Alice made a Merkle tree by combining the data sets “123” and “456,” and that Merkle tree’s Merkle root turns out to be “789.” Alice then tells Bob that data package “123” is somewhere in this Merkle tree. Now, with just the Merkle root (“789”), Bob can verify that “123” is indeed included somewhere in the Merkle tree, even though he has no idea that “456” is in there as well. In fact, for all he knows, there could be thousands of data packages in the Merkle tree — and he couldn’t decipher any of them.
MAST: P2SH + Merkle Trees
MAST essentially merges the potential of P2SH with that offered by Merkle trees.
Instead of locking bitcoins up into a single script, with MAST the same bitcoins can be locked up in a series of different scripts. In other words, the same bitcoins can be locked up under a set of different and mutually exclusive conditions. (For example, requiring a cryptographic signature from only Alice, or a signature from Bob and Carol each, or a signature from only Carol after a certain amount of time has passed, and so forth.)
Whichever of these conditions is met in a (confirmed) transaction first determines how the bitcoins are spent. (If Alice is the first to sign a transaction spending the output, that transaction is valid. If Bob and Carol beat Alice to it, that’s the valid transaction. Or if a certain amount of time has passed and Carol is the first to sign, that is the valid one.)
Much like P2SH, all these different scripts are hashed. But this time, they’re combined into a Merkle tree. And it’s the Merkle root of this Merkle tree that’s included in a transaction-output, as a sort of ultimate lock.
Spending funds, then, resembles P2SH as well. To create a transaction that unlocks funds from the Merkle root, the whole script used must be included in the new transaction, as well as the requirement to unlock that script. (The lock and the key.)
But importantly: not all potential scripts (locks) must be included. Only the one that is actually used. (If Alice spends the funds first, she does not need to include the script that lets Bob and/or Carol spend the funds. In fact, Alice doesn’t even need to know that Bob and/or Carol could have also spent the funds.)
Bitcoin nodes can verify that the included script checks out by utilizing the Merkle tree trick. They use the Merkle root included in the output to check if the script used is really included in the Merkle tree. If it is, these nodes know that the included script checks out as one of the options to spend the bitcoins and can validate the new transaction.
Benefits
MAST improves Bitcoin in three main ways: it extends smart contract flexibility; improves scalability; and increases privacy.
The type of smart contract flexibility offered by MAST is not entirely new — there were already some “either/or” constructs possible with only P2SH. (Requiring a signature from only Alice, or a signature from Bob and Carol, etc.) But there is a currently protocol-imposed size limit on different options to prevent DoS attacks.
MAST extends smart contract flexibility since it removes any such limit. Whether there are two possible ways to spend bitcoins or 20 or 1000, it makes no difference to the network, only one script is included in the required transaction. This also enables new and complex possibilities, like 1-of-1000 multisig transactions, that would currently be too big. Or long lists of users that can spend specific bitcoins at different points in time.
Furthermore, these types of “either/or” constructs could, with P2SH, only be unlocked by ultimately publishing all of the scripts — not just the one used. This makes for big transactions, data-wise, and for expensive transactions, fee-wise. By only requiring users to include the script that is actually used in the end, MAST improves scalability. It reduces the amount of data that must be transmitted, validated and stored by all nodes on the network.
As an additional bonus, MAST improves privacy, again by the virtue of keeping unused scripts hidden forever. This could, for example, hide arbitrators from escrow transactions if they never come into play (because both trading parties use their 2-of-2 multisig-script, instead of the 2-of-3 version). Or it could hide never-used time-out safeguards from the public.
Authors note: MAST is still a work in progress; implementation details may differ from the explanation in this article.