Plan du site  
pixel
pixel

Articles - Étudiants SUPINFO

Mast and Schnorr Signatures Part 2

Par Anis BENZIANE Publié le 05/08/2019 à 20:06:09 Noter cet article:
(0 votes)
Avis favorable du comité de lecture

Contents

Bitcoin’s development effort for the past few years has been focused on a few key concepts, privacy, scalability and efficiency. One of the first improvements was Segregated witness which is ushering in the rest, Lightning Network followed but was an effort in a different direction as it took transactions off-chain rather than optimizing the on-chain process. Some of the upcoming technologies aimed at optimizing this process are Schnorr Signatures and Merkelized Abstract Syntax Trees or MAST for short.

Merkelized Abstract Syntax Trees (MAST)

Another upcoming technology is Merkelized Abstract Syntax Trees which aims at making smaller transaction sizes while increasing the privacy of these transactions.

Bitcoin Scripts

To first understand the need for MASTs, let’s recall what are Bitcoin Scripts. Scripts (with capital “S”) are pseudo programs that are included in transactions and allow for a dynamic locking and redeeming of funds locked in transaction outputs. You can learn more on Scripts here.

One example of a commonly used Bitcoin script, overly simplified here, is the one that returns OP_TRUE if the private key is connected to the public key (signature : Pay To Public Key Hash and Mast and Schnorr SignaturesMast and Schnorr Signatures ) Once a script returns True it gives the power to spend all funds locked in a transaction unspent output (UTXO).

scriptSig: [signature] {[pubkey] OP_CHECKSIG}

scriptPubKey: OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL

This was quite a simple, bitcoin Scripts can be much more elaborate. Lets say Alice and Bob are getting married, and Bob wants to make sure that if he dies or if they get divorced half of his Bitcoin would go to Alice and the other half would go to his family. Bob makes a transaction that includes 3 conditions, each of which may be used to return TRUE and spend the transaction, the first condition is a regular spend, the second condition requires a proof of divorce to spend the money and the third condition requires the transaction to be unspent for 6 month, and we’ll just assume that if Bob doesn’t touch his money for 6 months he is dead.

Once any of these conditions gets fired and the Bitcoins are spent, all of this data must be on the blockchain. This may fill the blockchain with unnecessary data about Bob’s marriage that no body wants to know about, not even Bob.

Unused conditions increase the size of the transactions and reduces the privacy by releasing unneeded information to the public, MAST seeks to hide these conditions.

How MAST works

MAST is a two part system, the first part is an Abstract Syntax tree, an AST is a way to describe a program by splitting it into different parts, each part connected to the dependencies needed to perform its function until all dependencies are mapped. This makes the program easier to analyze, test and optimize.

The other part is a Merkel Tree. Merkle trees (also called hash trees) allow you to “verify that an element belongs to a set” without seeing the whole set. It is currently used by light (SPV) Bitcoin wallets to save bandwidth, instead of receiving a whole block to verify a transaction, it just receives the headers and uses the Merkle root to verify the transaction information. Merkle trees are created by hashing members and creating a short identifier, this identifier is then hashed again with another member’s identifier and the steps are repeated until there is no more members, the last (top) hash is the Merkle root and it identifies the set in a few bytes.

An example of a binary hash tree. Hashes 0-0 and 0-1 are the hash values of data blocks L1 and L2, respectively, and hash 0 is the hash of the concatenation of hashes 0-0 and 0-1.source: wikipedia

The basis of MAST is allowing senders to replace the unused parts of the script with a Merkle proof of its existence, reducing the transaction size making larger contracts a reality and increasing the privacy by sparing the block chain all the details.

MAST

The use of MAST in a transaction makes the increase in size and cost logarithmic, non MAST transactions increase linearly. This means that to process a large smart contract (bitcoin Script) using MAST is no longer a hard thing to do for either full nodes or light wallets.

The main proposal of MAST is currently BIP 114 by Johnson Lau that defines a new witness program type that uses a Merkle tree to encode mutually exclusive branches in scripts, the BIP requires a soft fork.

Current Status

Both MAST and Schnorr Signature requires a soft fork to be implemented and while the ideas are currently set in stone and on top of the list, it is currently unknown when will they be implemented in the main net. It took segwit almost two years and a hard fork to get implemented but we’re hoping these would be easier soft forks to implement and reach consensus.

The road to Bitcoin scalability is full with interesting and new technologies, in this article i only wrote about a couple of them.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Toeic, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels