Merklized Abstract Syntax Tree

Compress a Smart Contract Logarithmically

Merklized Abstract Syntax Tree MAST (aka, Merklized Alternative Script Trees) is a technique to compress Bitcoin smart contracts using Merkle tree. We have implemented MAST on Bitcoin SV. Different from all other implementations, ours leverages the original Bitcoin protocol, without any consensus change.

Problem

There are generally more than one way to spend coins locked in a Bitcoin smart contract. In sCrypt, each way is modelled as a public function, representing a conditional spending branch. For example, in contract TimeCommit, the contract can be unlocked either by Alice’s preimage and her signature, or by Alice and Bob’s signatures.

TimedCommit Contract

As contracts becomes more complex, there may be tens of public functions/branches, if not hundreds, in a single contract. Only one of them is eventually called, but all of them must be included in the blockchain, even though they are not executed at all. This bloats on-chain footprint and increases transaction fees.

MAST

MAST removes unreached branches from the blockchain. A uncompressed contract (the original) is split into individual branches and organized into a Merkle tree, where each branch’s script is a leaf. The compressed contract only stores a merkle root, which is used to verify a specific branch belongs to the original contract, without storing it in entirety.

MAST brings enormous benefits, especially when the number of branches n is large.

• Scalable: deployed contract size scales at log(n)¹, as only the chosen branch and its merkle path are needed, instead of all branches. In the example below, when branch Tc is called, only its merkle path in yellow is needed.
• Private: unused branches are not published on chain. In the example below, only Tc is revealed, all other branches are hidden.

A Merkle Tree and a Merkle Path

Implementation

We have implemented MAST in Bitcoin. When a branch is executed, itself and its merkle path are used to unlock. In the compressed contract, we first verify the branch is from the original contract, using its merkle root. Next, using a technique simulating P2SH, the new locking script in the current spending transaction is set to be this branch’s script, which is spent in a subsequent transaction.

MAST Contract

[1] Assume all branches are of similar size.