Merkalized Abstract Syntax Tree (Part 2)

In a previous article, we covered the basics of MAST. This article will highlight some of the benefits of this development.

An example of MAST

We take the case from the previous article (the one with Alice, Bob and Charlie) and break the problem into separate sub-scripts for each of the two outcomes:

  1. Alice can spend her bitcoins at any time (lower left in the image below)
  2. After three months in which Alice hasn’t spent her bitcoins, Bob and Charlie can decide together what Alice should spend her bitcoins on (bottom right in the image below)

The Merkle tree based on the results looks like this:

The Merkle root for this tree identifies the full encumbrances in just 32 bytes. Subsequently, a Merkle proof must be shown by anyone who wants to spend the bitcoins. The Merkle proof links the Merkle root and the scripts where the encumbrances of the scripts will have to return ‘correct’. Only then can it be proven that the initiator should be allowed to execute the sub-script.

The Merkle proof with the sub-script could be visualized depending on which sub-script to use:

Advantage 1: smaller transactions

One of the benefits of MAST is the ability to make certain transactions smaller. In the example above we assumed two sub-scripts; Alice sends her bitcoins, or Bob and Charlie decide where Alice’s bitcoins can go. If we apply this option even further, Daan and Ella would decide together again the following month what the bitcoins are spent on, followed by Fred and Gert who can do that again a month later.

These functionalities would entail an enormous amount of data. After all, every condition must be included in the transaction, even if there is a good chance that many of the later conditions will not be used.

Below is a graph in which the size of the script with and without MAST is indicated, with an increasing number of sub-scripts.

The same graph on a logarithmic scale:

As can be seen on the graph above, the MAST transaction starts slightly larger and therefore more expensive than the transaction that does not use MAST. However, the non-MAST transaction scales linearly where the MAST transaction scales logarithmically. This means that the MAST transaction becomes exponentially more efficient as more sub-scripts are used, compared to the regular transaction.

If saving data in a transaction is the main goal, this can be further optimized. With most encumbrances, senders will use one condition more often than another.

An example: Alice assumes that she has a long time to live. She therefore ensures that the condition in which she is allowed to spend the bitcoins herself is at the top of the Merkle tree. Any later conditions do not have to be called as long as Alice is still alive, so the transaction does not contain the extra data of the later conditions every time.

As a result, the MAST Merkle proofs have two different sizes. One of the transactions when Alice is alive and alone can send the bitcoins, the other in the cases where Alice is no longer alive (or hasn’t shown any sign of life for a long time) allowing Bob and Charlie to send the bitcoins. Based on the previous graph on the size of the MAST and non-MAST transactions, the graph below applies to this case.

In the best case scenario it can be seen that Alice always uses the same number of bytes for the transaction, regardless of the number of additional beneficiaries included in the encumbrance. Any later senders, such as Bob and Charlie, only need to add a few extra bytes to the transaction when they want to send the bitcoins.

No matter how Alice arranges it with the beneficiaries who could possibly send the bitcoins later, the savings per added sub-script proves to be significant.

Advantage 2: more privacy

Since we’ve covered Alice’s entire story in great detail, you should know all the details of the encumbrance. Now imagine that only the data that is actually needed for the transaction to be sent is added to the blockchain when Alice sends her bitcoins (the example below on the left), without all of the following conditions:

With just this information, you wouldn’t know if anyone other than Alice would have access to the bitcoins or what terms might limit their spending. You could guess from the MAST that other conditions exist, but that would only be a guess; Alice could pretend that she herself has to meet several conditions in order to be able to send her own bitcoins.

On the other hand, if you only saw the other conditions (right example above), you wouldn’t know that the bitcoins before the timeout could be spent ‘after 3 months’ or that a single person (Alice) could spend them. So you could guess that there were other circumstances, but you cannot draw a certain conclusion based on the data in the blockchain.

The ability to keep all terms of the encumbrance unknown can be very important to some users, such as companies that want to keep their smart contracts confidential from potential competitors. This is in contrast to some altcoins that are specifically designed for smart contracts, which provide no privacy for the smart contract data at all.

Privacy can also provide another benefit that applies to all bitcoin users, even those who are not concerned with the privacy of the encumbrance itself. Imagine Alice being the only person ever to use the non-MAST encumbrance. Because the full encumbrance is made public here, anyone can track all of Alice’s releases just by looking for instances where the same kind of encumbrance is used. This completely destroys Alice’s privacy.

Everything that makes it easy to identify certain users also makes it easy to treat their bitcoins differently from other people’s bitcoins; a lack of fungibility. Fungibility implies the replaceability of an object; one bitcoin should be no different than the other. If someone knows what Alice’s assets look like, he or she can bribe miners or force them not to mine those transactions to prevent Alice from spending her bitcoins.

MAST alone cannot solve this completely, as Alice (or Bob and Charlie) still has to reveal some of the encumbrance when the bitcoins are spent. However, it is possible for a large number of complex encumbrances to be merged into a smaller number of MAST encumbrances.

For example, Alice’s normal transactions look like the normal transactions that require only one digital signature, so Alice’s MAST-based transactions look like all other MAST-based transactions with only one signature. This returns Alice’s privacy and increases both her fungibility and the fungibility of everyone else using the same form of transaction.

This particular advantage of MAST is likely to work well with other proposed features that improve privacy and fungibility for bitcoin users by allowing certain complex encumbrances to conform to a single digital signature. Examples of this are the generalized threshold trees of Pieter Wuille and Gregory Maxwell, scriptless scripts of Andrew Poelstra scripts and the discrete log contracts of Thaddeus Dryja.

But even if none of these developments ever become possible on the bitcoin network, MAST itself already offers users more privacy and fungibility for the complex encumbrances than is currently possible.

Advantage 3: larger smart contracts

Bitcoin has three different byte limits that apply to scripts depending on how an encumbrance is set up: a 10,000-byte limit for regular scripts, a 520-byte limit for P2SH (pay-to-script hash), and a 10,000 byte limit. limit for SegWit.

The chart below shows these limits on the previously used chart.

It can be seen that MAST makes it possible to add a large number of extra conditional conditions as a script compared to the other methods.

There are even more limits regarding the bitcoin scripts that MAST manages to circumvent. After all, full nodes on the network do not have to validate and forward unused sub-scripts across the entire network. In this way, the amount of all data contained in the scripts mainly remains with the user, and the network is not burdened with it. This saves the nodes bandwidth, memory and computing power.

The actual advantage of MAST is therefore not only the fact that one can create more extensive smart contracts with increased privacy, but if one does, this is possible without putting an extra burden on the network.

This article is based on an article published by David A. Harding. David publishes documentation of free software and has been focused on Bitcoin since 2014.

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

© 2024 Cryptocoin