Learn what is a Bitcoin Merkelized Abstract Syntax Tree?
Original title: "Dry goods | What is the Bitcoin Merkelization Abstract Syntax Tree? ", by David A. Harding
Merklized Abstract Syntax Trees (MAST) is a proposed upgrade for Bitcoin that enables smaller transaction sizes, better privacy, and larger smart contracts. In this article, we explain the rationale for MAST, explain its potential benefits, and summarize some current proposals that incorporate this technology.
Problem: Unused script data
Satoshi Nakamoto gave Bitcoin an interesting feature that he did not write in the Bitcoin white paper. In addition to receiving bitcoins through public keys and spending bitcoins with private key digital signatures, users can also write programs (called "scripts") that can be used as dynamic public keys and signatures.
When you specify a script -- which is a basic operation in every Bitcoin wallet -- the Bitcoin protocol, enforced by the Bitcoin network, will not allow anyone to spend the Bitcoins controlled by the script unless the script Return True. This allows you to specify conditions under which funds can be spent, called "encumbrances" (property conditions), such as requiring transactions to be spent to be signed by your private key.
More complex property conditions are also possible, such as the following example, which we will use throughout this article: Alice wants to be able to spend her bitcoins at any time, but if she does not spend her bitcoins for three consecutive months (possibly death or incapacity), she wants her siblings, Bob and Charlie, to own their bitcoins and use them wherever they can agree.
The following conditional script achieves the above goal, it not only includes Alice's public key (need to verify a signature from her private key), but also adds the following conditional logic: a timeout condition, and Bob and Charlie's public key.
In the current Bitcoin protocol, all the above-mentioned data must be added to the blockchain, and when Alice’s Bitcoin is spent, it also includes parts of the script that are completely irrelevant in the specific spending behavior, which must also be exposed. For example, when Alice spends her bitcoins, the public keys of Bob and Charlie will also be exposed.
Unused conditional data increases the size of transactions and exposes users to more privacy than necessary. At the same time, it also makes size rather than verification cost the main limiting factor for smart contract size. MAST aims to improve these situations by removing the need to include unused parts of scripts directly on the blockchain.
MAST initial idea
The ideas behind MAST 1 come from two long-standing concepts, abstract semantic trees and Merkle trees. Abstract Semantic Tree (AST) is a way to describe a program by breaking it into independent small pieces, which makes the program easier to analyze and optimize. To generate an AST, you need to connect all equations with their premises with arrows until all premises are found. The figure below is the AST of the example script above.
On the other hand, a Merkle tree can be used to verify whether an element belongs to a set without knowing the full picture of the set. For example, Bitcoin's Simple Payment Verification Wallet (SPV wallet) uses a Merkle tree to verify whether a certain transaction exists in a certain block, so that there is no need to download the complete block, which can save bandwidth.
To generate a Merkle tree, first hash each element once to generate its own unique identifier; then these identifiers are paired and hashed again to generate the identifier of the pair of identifiers; and so on Repeat until there is only one identifier left, called the "Merkel root", which is a short identifier that marks the entire collection.
When verifying that an element belongs to a set, someone who owns the entire set can give you all the identifiers on the path from that element to the Merkle root. This proves that the element is indeed in the set.
In short, the technology behind AST allows you to divide a program into small pieces, and Merkle tree allows us to verify that these small pieces are indeed part of a complete program without exposing the entire program. This is the basic principle of MAST, which allows consumers to replace conditions that are not used in a single transaction with a Merkle proof - reducing transaction size, improving privacy, and supporting larger contracts.
An example of MAST
Let's take the property condition above as an example, and divide it into two subscripts for the two possible scenarios we want:
Alice can spend her bitcoins at any time (subscript on the left)
Or, if Alice's signature is used to spend for three consecutive months, Bob's and Charlie's signatures are required to spend the bitcoins (subscript on the right in the figure below)
Create a Merkle tree based on these two separate subscripts:
The root of this Merkle tree finally identifies Alice's complete property conditions, and it only has a size of 32 bytes. Thereafter, Alice can use an alternative conditional script, stating that a spend transaction is only valid if one of the subscripts is provided with proof that it is connected to the Merkle root, and the subroutine returns True.
The Merkle proof of the subscript will be drawn visually like the following figure, depending on which subscript is used:
Benefit #1 - Smaller Transactions
Let's first look at how MAST enables users with complex property conditions to create smaller transactions. This is the first benefit that MAST brings us.
In the example above, we used a property bar with two subscripts: either Alice spends her own money, or Bob and Charlie spend her money together after waiting three months. Let's imagine an infinitely stretched version where the third subscript specifies that after three months and one day, Dan and Edith can spend the funds; the fourth subscript specifies that after three months and two days, Fred and George can use the funds; etc. etc.
This thought experiment leads us to the graph below, which shows the relationship between the number of subscripts and the amount of conditional data that needs to be added to a block, with and without MAST.
Here is a logarithmic plot, meaning the same:
Although the size of the MAST transaction will be larger than the same condition transaction without MAST at the beginning, such as the conditions of our two sub-scripts, the non-MAST transaction size will increase linearly (with the number of sub-scripts), while the volume of the MAST transaction will only increase logarithmically.
If saving data volume is the main goal, we can further optimize it. For many property conditions, consumers may use one of them more frequently. For example, Alice wants to live a long life, so the Merkle tree she constructs puts her spending conditions closer to the top, and all other conditions are placed at the bottom of the tree:
It can be seen that when Alice uses the funds, the amount of transaction data is always the optimal situation, no matter how many beneficiaries there are in her property conditions; and when her beneficiaries use the funds, the amount of transaction data is also the same. Only a few bytes more than the aforementioned standard constructed Merkle tree.
No matter what arrangement Alice chooses, it can be seen that MAST can make multi-subscript property conditional transactions smaller, so users can pay less fees, and more advanced transactions can be loaded into blocks.
Benefit #2 - Greater Privacy
In the above explanation, we exposed all of Alice’s property scripts, but you can imagine that if Alice spends her own bitcoins, you only see the data on the left side of the figure below on the blockchain:
Only with this information, you have no way of knowing whether anyone other than Alice can spend the funds here, and what constraints they need to face when spending. You can guess from the MAST that there might be some other conditions, but that's just a guess - Alice might just pretend her Merkle tree has other spendable parts.
Correspondingly, if you see another branch (that is, the sub-script on the right in the above picture), you will not know whether the funds can be spent before the timeout, and you will not know whether it is possible to spend with only a private key. can spend it. You can also guess that there are other spending conditions, but you can't confirm this on the blockchain.
It is very useful to ensure that unused property conditions are not exposed. For example, some merchants may want their smart contracts to be as confidential as possible and not to be seen by potential competitors. This is in contrast to some altcoins that claim to be designed for smart contracts, but in fact cannot provide privacy for these contracts.
Privacy can also provide additional benefits to all Bitcoin users, even if some users simply don't care about privacy in terms of property. Assume that from the beginning of this article, Alice is the only person using a non-MAST conditional template. Because all conditions are public, anyone can track Alice's spending behavior, just observe the usage of this template on the blockchain, so Alice's privacy is gone.
Any design that makes it easier to identify a particular user will also make it easier for people to treat their bitcoins differently from other people's bitcoins, which is called "lack of homogeneity". If someone knows what Alice's property conditions look like, they can bribe or force the miners not to package these people's transactions, so as to prevent Alice from using her own bitcoin.
MAST cannot fully solve this problem, because Alice (or Bob and Charlie) still need to reveal some encumbrances, but many otherwise complex property conditions can be resolved into a small number of simple MAST-type conditions.
For example, Alice's default spending behavior looks like any other ordinary payment behavior that only needs to provide a single signature, so Alice's MAST-based transaction is no different from other MAST-based single-signature transactions. This in turn improves Alice's privacy, as well as the homogeneity of her funds, and monetary homogeneity for all users using MAST-based single-signature conditions.
This benefit of MAST is also likely to be combined with other proposals to improve Bitcoin's privacy and homogeneity. There are proposals to make certain complex property conditions available with a single signature, such as Pieter Wuille and Gregory Maxwell's "Universal Threshold Tree", Andrew Poelstra's "Scriptless Script", and Thaddeus Dryja's "Discrete Logarithm Contract ”; MAST can be combined with these schemes.
But even if none of these solutions can be implemented on Bitcoin, MAST itself can provide more privacy and interchangeability for users with complex property conditions, whether it is compared with the current one, or with support for user-defined smart contracts Altcoins compared.
Benefit #3 - Larger Smart Contracts
Bitcoin now sets three different size limits for individual scripts: naked scripts cannot exceed 10,000 bytes in size, introduced in July 2010; P2SH scripts cannot exceed 520 bytes; and segwit scripts cannot exceed 10,000 bytes. We show these sizes in the above figure:
It can be seen that even for the extreme case of infinite extension, MAST supports more conditional branches than all current mechanisms. In fact, MAST scales so well that even if you have all the energy in the observable universe, if you only use it to create a standard (balanced) Merkle tree, its Merkle evidence is only 8448 bytes. Even for such a large Merkle proof, any modern laptop can verify it in under 1 millisecond.
MAST can also help Bitcoin Script bypass some other hard restrictions by freeing full nodes from the task of processing unused subscripts. In this regard, MAST has well preserved and extended the long-term design goal of Bitcoin smart contracts, that is, the burden of the contract should be borne by the participants of the contract as much as possible, while the nodes pay for bandwidth, memory and processing power, but cannot are compensated and should therefore be liable for as little as possible.
So, the real achievement of MAST is not to allow Bitcoin users to create (than ever) more advanced contracts, but that it opens up this possibility without adding new burdens to Bitcoin nodes.
Implementing MAST: Existing Multiple Proposals
So far, two methods of enabling MAST in the Bitcoin protocol have been proposed on the bitcoin-dev mailing list, both of which are still in draft stages and are subject to change.
The first proposal is BIP114 proposed by Johnson Lau (pseudonym "jl2012"), which uses an extended feature based on segregated witness, so that the original segregated witness address (bech32) can become a Merkle root commitment to MAST property conditions. A spend transaction can thus select a child script from the tree.
The second proposal, two unnamed BIPs (1, 2) by Mark Friedenbach (alias "maaku"), increases the flexibility of the scripting language, allowing programmers to write scripts to verify MAST-based property conditions. Implemented the way Friedenbach prefers, that would make Merkle proofs available to all three script types that Bitcoin currently supports (naked scripts, P2SH, and Segregated Witness scripts).
These several proposals have their own advantages and disadvantages, but all provide the benefits of MAST mentioned above (the number of bytes may be increased or decreased). Each can be activated with a soft fork.
Conclusion: When can we use MAST?
Above we explained the benefits of MAST, and briefly mentioned two proposals to implement MAST on Bitcoin. You may also be curious about when we can use MAST. Sadly, I don't know either.
From idea, to proposal, to complete implementation, to proposing soft fork, to activating soft fork, the road is long and difficult. This has been made abundantly clear by the two-year drama surrounding the Segregated Witness upgrade.
thank you
further reading
BIP114: Merklized Abstract Syntax Tree by Johnson Lau
Tail Call Sematics by Mark Friedenbach
MerkleBranchVerify opcode by Mark Friedenbach
Discussion at core.tech meetup by Mark Friedenbach (transcribed by Bryan Bishop)
Merklized Abstract Syntax Trees by Jeremy Rubin, Manali Naik, Nitya Subramanian
An explanation and justification of the tail-call and MBV approach to MAST by Mark Friedenbach
Making MAST Meaningful by Brian Deery
The next step to improve Bitcoin by Aaron van Wirdum
thank you
footnote
footnote
Russell O'Connor is credited with being the first to describe the prototype of MAST, and some sources add Pieter Wuille. Sources: Peter Todd, Gregory Maxwell (cited in Jeremy Rubin et al.), and Mark Friedenbach (in personal communication).
Thanks John Newbery.
Original link:
(over)
(There are many hyperlinks in this article, you can click "Read the original text" on the lower left to get it from the EthFans website)
Original link:
https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f
Translation: A Jian
Translation: A Jian
