Merkalized Abstract Syntax Tree (MAST, part 1)

What is a Merkalized Abstract Syntax Tree (MAST)?

Merkalized Abstract Syntax Tree (MAST) is a proposed addition to the Bitcoin protocol that allows for smaller transaction size, improved privacy, and the ability to create larger smart contracts. This article will explain the basics of MAST.

The problem: unused script data

Satoshi Nakamoto presented Bitcoin with an interesting feature that was not described in the original white paper. Instead of only being able to receive bitcoins on a public key and then send them back based on a digital signature, Satoshi has also created the possibility to write programs (scripts) that act as dynamic public keys and signatures. could serve.

When such a script is used within a transaction, the Bitcoin protocol does not allow the bitcoins to be sent until the value of the script is considered ‘correct’. For example, certain restrictions can be imposed in the script for sending bitcoins. When all restrictions are met, the script is considered ‘correct’ and the bitcoins can be sent. Such restrictions are called encumbrances . An example of this is underwriting a transaction with the private key; signing with a digital signature to be allowed to send the bitcoins.

Because these restrictions, the encumbrances, can be programmed yourself, it is also possible to create more complex conditions. An example of this is explained in this article through a case with Alice, Bob and Charlie.

The case

Alice wants to be able to spend her bitcoins at any time. If nothing happens to her bitcoins for three months, for whatever reason, then the bitcoins will go to her brothers Bob and Charlie. This with the conditions that both brothers agree together on what the bitcoins are spent on.

The aforementioned scenario is applied in the encumbrances script below. This contains Alice’s public key to verify the signature made with a private key. Also the conditional logic, a timeout and the public keys of Bob and Charlie are listed.

In the current bitcoin protocol, all of the above data is added to the blockchain when Alice’s bitcoins are sent. This includes Bob and Charlie’s public keys, which are completely irrelevant when Alice sends the bitcoins. This is therefore extra and unnecessary data that is stored worldwide. This unused encumbrance data ensures that the transaction size itself is also higher.

The privacy of others is also affected; after all, the public keys of Bob and Charlie are unnecessarily disclosed with every transaction by Alice. Because there is no infinite amount of data that can be added to Bitcoin’s scripting function, this leaves less room for other scripting functions within the transaction.

This is where MAST comes into play. MAST ensures that the unused parts of the script do not have to be included in the blockchain.

Origin MAST

The idea behind MAST stems from two separate concepts, namely abstract syntax trees (ASTs) and Merkle trees. AST is a way to describe a program by breaking it into pieces. Each separate component can thus be analyzed or modified more easily, without the entire program having to be overhauled. To generate an AST you need to connect known functions and dependencies in programming until all dependencies have been mapped.

Here is the AST based on the case:

Merkle trees, on the other hand, ensure that part of a whole can be verified without the whole itself being present. For example, SPV bitcoin wallets use Merkle Trees so that they do not have to download the entire blockchain with associated blocks, but only check whether transactions are actually included in a block.

To generate a Merkle tree, each part of the whole has to be hashed, making each part individually identifiable by a unique sequence of characters. These identifiers are then concatenated and hashed again, creating a shorter hash for the two separate strings together. This is done until there is only one identifier string for all previous parts; the brand root. So only a small amount of data is needed (the identification string is only a few bytes in size) to verify the whole thing.

Because the entire blockchain is not checked, you must rely on an external party that can provide you with the correct identification sequences. Without those series, it is impossible to check whether a part is actually part of the whole. With the identification series you can return to the brand root of the whole. Proving that a part is part of a whole is called Merkle proof.

In short, the technique behind AST allows a program to be split into individual parts. The Merkle Tree makes it possible to verify individual parts of a complete program without having to present the entire program. This is the idea behind MAST; a sender of a transaction can replace the unused portions of an encumbrance with a Merkle Proof that reduces transaction size, increases privacy, and enables larger smart contracts.

Example and benefits

In a second article, MAST will be explained by means of an example and a number of advantages of the upgrade will be discussed. 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