Unlocking MAST: From Bitcoin Roots to Polygon Miden’s Scalable Future
Merklized Abstract Syntax Trees (MAST) are an innovative data structure combining the principles of abstract syntax trees (AST) and Merkle trees and first appeared in 2013 in the early days of Bitcoin.
The idea to combine Merkle trees and abstract syntax trees together comes out of the goal to enhance security, efficiency, and verifiability in program execution, particularly within blockchain environments. MAST structures provide a method to hash the logic of a program into a unique and compact representation, facilitating efficient verification without requiring access to the entire program code. Sounds cool, right?
The Origins: MASTs in Bitcoin
The concept of Merklized Abstract Syntax Trees (MAST) was first introduced in Bitcoin as a method to enhance the privacy, scalability, and flexibility of Bitcoin script execution. Initially proposed in 2013, MASTs allow bitcoin scripts to store various user-selected conditions that must be fulfilled in order to “unlock” the Bitcoin in the associated UTXO (unspent transaction output).
By using a MAST, this enables a spender of a Bitcoin UTXO to reveal and fulfill only the specific condition required for a transaction, while keeping other conditions hidden from the blockchain. This selective disclosure not only improves privacy but also reduces the amount of data that needs to be included in a transaction, thereby saving space on the blockchain and lowering transaction fees.
BIP114, one of the earliest formal proposals for MAST, aimed to address several drawbacks in Bitcoin’s original script system, such as the difficulty in specifying complex conditions, the large size of scripts, and the exposure of unexecuted branches.
Polygon Miden and MAST: An In-Depth Application
Polygon Miden, a rollup-based blockchain platform focused on scalability and privacy, adopts and extends the concept of MASTs through its Miden Virtual Machine (Miden VM).
Just like with Bitcoin scripts, on Polygon Miden, the MAST is a binary tree, where each node represents a specific code block. The execution begins at the root of the tree, with the Miden VM processing each node recursively according to its semantics. If the execution of a code block fails, the VM halts at that point, reverting the transaction.
However, unlike Bitcoin’s use of MASTs primarily for on-chain script execution with enhanced privacy, Polygon Miden uses MASTs in conjunction with zero-knowledge proofs, specifically Zero-Knowledge Scalable Transparent ARguments of Knowledge (ZK-STARKs), to enable the possibility of private off-chain computation.
When executing a program, the Miden VM processes the program’s MAST structure by recursively evaluating each MAST node based on its semantics. Upon completion of the program’s execution, the Miden VM generates a ZK-STARK proof attesting to the correctness of the execution of a program with the given MAST root, without revealing any specific details about the program’s computation or data. This ZK proof can then be submitted on-chain, and attest to the validity of the state change of an account or smart contract on Miden.
By using MASTs, Polygon Miden enables the ability to create highly scalable privacy preserving applications. Since the computation of the state change of a smart contract can be computed off-chain, then the proof that the state change was correct can be validated quickly on-chain, this opens the door for massive scaling opportunities and innovative financial applications, one of which we are building at Composability Labs.
Conclusion
Merklized Abstract Syntax Trees represent a significant advancement in computer science, particularly in cryptography, verifiable computation, and privacy, by enabling the efficient execution and verification of complex programs within the constraints of computationally limited blockchain virtual machines.
This article was written by Alexander John Lee, a researcher and engineer at Composability Labs.
