The soon-to-be proposed Segregated Witness 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.)
Source/More: The Next Step to Improve Bitcoin’s Flexibility, Scalability and Privacy Is Called MAST — Bitcoin Magazine
