12. MAST (Merklized Abstract Syntax Tree)
back to table of contents
Merklized Abstract Syntax Trees (MAST) is an additional proposal proposed in the Bitcoin protocol that enables the implementation of the following:
- Smaller deal size
- More privacy
- Larger Smart contract.
Issue: Script data not used.
- Satoshi Nakamoto gives Bitcoin a feature that allows users to write programs (called scripts) that can be used as dynamic public keys and signatures.
- When you specify a script - which is the default of every wallet - Consensus on the Bitcoin Protocol will not allow anyone to spend on your bitcoin until a predetermined script justifies the process.
- Currently, all scripts must be written on the Blockchain (as a whole).
The origin of MAST
The idea of MAST comes from two pre-existing concepts, namely Abstract Syntax Trees (AST) and Merkle Trees.
- AST - is a way to describe a program by dividing it into separate parts so that it is easier to analyze and also optimize the functions of each.
- Merkle Tree - allows a node to copy some information without having to copy all transactions.
Example of Abstract Syntax Tree
Example of Merkle Tree
Example of MAST
Allice can use up BTC (left picture), or after three months, Bob and Charlie can spend BTC (right image) - you only need to save completely from encumbrance (Merkle root) to get all the subscripts.
Benefits of Implementing MAST
1. Smaller transactions
You can add as many subscripts as you want.
2. More privacy
The benefits of this MAST are likely to work more optimally in improvising privacy when combined with other methods such as generalized threshold trees (Pieter Wuilles & Gregory Maxwell), scriptless scripts (Andrew Poelstra) and discrete log contracts (Thaddeus Dryja).
3. Larger Smart Contract
Bitcoin has three different byte sizes that apply to each script depending on the development of the encumbrance.
With MAST, you cannot exceed the limit of bytes
Ten thousand bytes limit for empty scripts, 520 bytes limit for P2SH, and 10,000 bytes limit for SegWit.
Reference:
- https://github.com/jl2012/bips/blob/mast/bip-mast.mediawiki
- https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki
- http://www.mit.edu/~jlrubin/public/pdfs/858report.pdf
- https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f
- https://www.youtube.com/watch?v=Phn_Im2K_PY
- https://bitcoinops.org/en/topics/mast/
- https://themoneymongers.com/merkelized-abstract-syntax-tree-mast/
- https://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2017-09-07-merkleized-abstract-syntax-trees/
- Bitcoin Developer Guide - https://bitcoin.org/en/developer-guide#transaction-data (D.A. Harding - 2015, 12 Januari 2016)
https://bitcoin.org/en/glossary/simplified-payment-verification
- Other references look at post #1
back to table of contents
Merklized Abstract Syntax Trees (MAST) is an additional proposal proposed in the Bitcoin protocol that enables the implementation of the following:
- Smaller deal size
- More privacy
- Larger Smart contract.
Issue: Script data not used.
- Satoshi Nakamoto gives Bitcoin a feature that allows users to write programs (called scripts) that can be used as dynamic public keys and signatures.
- When you specify a script - which is the default of every wallet - Consensus on the Bitcoin Protocol will not allow anyone to spend on your bitcoin until a predetermined script justifies the process.
- Currently, all scripts must be written on the Blockchain (as a whole).
The origin of MAST
The idea of MAST comes from two pre-existing concepts, namely Abstract Syntax Trees (AST) and Merkle Trees.
- AST - is a way to describe a program by dividing it into separate parts so that it is easier to analyze and also optimize the functions of each.
- Merkle Tree - allows a node to copy some information without having to copy all transactions.
-snip-
Images of Merkle Tree
There are advantages to using the Merkle tree in terms of verifying a block.
For example, in the Merkle tree structure in the picture above, to verify transaction D, a node does not need to copy all transactions A, B, C, D, and E, but enough to copy C, AB, and EEEE information to produce the Merkle root. It has led to the emergence of nodes that do not have a complete copy of the blockchain, which is then called simplified payment verification (SPV).
Reference: Bitcoin Developer Guide - https://bitcoin.org/en/developer-guide#transaction-data (D.A. Harding - 2015, 12 Januari 2016) - https://bitcoin.org/en/glossary/simplified-payment-verification.
Images of Merkle Tree
There are advantages to using the Merkle tree in terms of verifying a block.
For example, in the Merkle tree structure in the picture above, to verify transaction D, a node does not need to copy all transactions A, B, C, D, and E, but enough to copy C, AB, and EEEE information to produce the Merkle root. It has led to the emergence of nodes that do not have a complete copy of the blockchain, which is then called simplified payment verification (SPV).
Reference: Bitcoin Developer Guide - https://bitcoin.org/en/developer-guide#transaction-data (D.A. Harding - 2015, 12 Januari 2016) - https://bitcoin.org/en/glossary/simplified-payment-verification.
Example of Abstract Syntax Tree
Example of Merkle Tree
Example of MAST
Allice can use up BTC (left picture), or after three months, Bob and Charlie can spend BTC (right image) - you only need to save completely from encumbrance (Merkle root) to get all the subscripts.
Benefits of Implementing MAST
1. Smaller transactions
You can add as many subscripts as you want.
2. More privacy
The benefits of this MAST are likely to work more optimally in improvising privacy when combined with other methods such as generalized threshold trees (Pieter Wuilles & Gregory Maxwell), scriptless scripts (Andrew Poelstra) and discrete log contracts (Thaddeus Dryja).
3. Larger Smart Contract
Bitcoin has three different byte sizes that apply to each script depending on the development of the encumbrance.
With MAST, you cannot exceed the limit of bytes
Ten thousand bytes limit for empty scripts, 520 bytes limit for P2SH, and 10,000 bytes limit for SegWit.
Reference:
- https://github.com/jl2012/bips/blob/mast/bip-mast.mediawiki
- https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki
- http://www.mit.edu/~jlrubin/public/pdfs/858report.pdf
- https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f
- https://www.youtube.com/watch?v=Phn_Im2K_PY
- https://bitcoinops.org/en/topics/mast/
- https://themoneymongers.com/merkelized-abstract-syntax-tree-mast/
- https://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2017-09-07-merkleized-abstract-syntax-trees/
- Bitcoin Developer Guide - https://bitcoin.org/en/developer-guide#transaction-data (D.A. Harding - 2015, 12 Januari 2016)
https://bitcoin.org/en/glossary/simplified-payment-verification
- Other references look at post #1