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.

Schnorr Signatures

Signature Schemes

To explain Schnorr, we must first go back to the basics, Signature Schemes. Bitcoin relies on public key cryptography, a cryptographic system with two components a public key and a private key, you can easily calculate a public key from a private key but the opposite is impossible, to prove you can spend funds you must prove that your private key corresponds to the public key the funds were sent to without releasing your private key, this is done through a cryptographic signature. Anyone can verify that a signature came from a private key that corresponds to this public key.

Bitcoin currently uses Elliptic Curve Digital Signature Algorithm (ECDSA) with a secp256k1 curve parameters and has been since it started. While this worked so far, there are reasons to believe that Schnorr signatures can help Bitcoin’s scalability and privacy. It is relatively faster to verify and it has multisignature support baked in. In the past, changing the Signature Algorithm used to require a hard fork but since Segregated Witness ¹ moved all the signature data (Witness data) into a separate part of the transaction it currently only requires a software fork.

Schnorr Signature Scheme

While Schnorr sounds mathematically sound, it had a patent that expired in 2008² and so it still hasn’t been standardized and due to the lack of documentation and specifications makes it challenging to implement.

In a nutshell, Alice wants to sign a message \(m\) , with a hash function \(H\) , for instance SHA256 , a private key \(x\) , a group generator \(G\) and a public key \(X = x \ast G\) ,a Schnorr signature is generated by the following equations³:

• \(e = H(R || m)\)
• \(sG = R + eX\)

Where \(||\) denotes concatenation; \(e\) and \(s\) integers picked by the signer with:

• \(s = r - e \ast x\)
• \(r\) is a randomly picked private nonce and \(R = r \ast G\) is the public nonce.
• And the pair \((R,s)\) is the Schnorr Signature.

Bitcoin is going to use the same eliptical curve parameters that it used with the older signing algorithm (Secp256k1).

Advantages

One of the key advantages of Schnorr signatures is its native support for multisignature transactions or signature aggregation, the older process to do this had many flaws like increasing the size of the transaction linearly with the amount of participants, longer and more computationally expensive validation and lack of privacy.

Schnorr has a constant size irrespective of the number of participants so the size of a n-of-n transaction is the same as one that uses a single pubkey and signature, this greatly improves the performance as it doesn’t need to validate every signature individually, it aggregates multiple signatures and their keys into a single one cryptographically, so any multisignature payment on the blockchain will look like it came from a single address ⁴, with no way of being distinguishable, additionally, using batch validation, the verification of Schnorr is slightly faster than ECDSA.

Even though they might not be used as often by the average user, if we look closely at the usage of multisig transactions we can observe it has been almost exponentially increasing for the past few years and due to the diminished size of the data produced by Schnorr, this greatly decreases the validation and transmission cost across the network.

If this signature process was implemented since the genesis block, analysis shows that the current chain size could have been reduced by more than 25% and with the current trend in multisig transactions this can likely be translated into more savings in the future.

There is an other promising benefit to Schnorr signatures and that is Scriptless Scripts. They are a kind of smart contracts that can be deployed off block chain, and only calculated by the two, or more, users participating in the smart contract. see scriptless scripts.

Problems

However, due to the unstandardized nature of Schnorr, its implementation does not come without challenges, mainly the “cancellation” problem which can be explained with a simple example.

Lets say we want to create a 2-of-2 multisig scheme with public keys from Alice and Bob (Pub1 and Pub2). Rather than combining the two public keys, Alice can provide the difference between the two keys (Pub1-Pub2) during the interaction and cancel out Bob’s key. Any funds sent to the address is now only spendable by Alice and Bob is out of the picture.

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) ⁴, 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.

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.

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 we only wrote about a couple of them, if there are other technologies you want us to cover, don’t hesitate to each out or offer your contribution.

Resources

Schnorr

• BitcoinCore.org Update on Schnorr
• BIP Schnorr
• Deep technical details and the math behind Schnorr
• The Power of Schnorr

Mast

• BIP 114
• Bitcoin Scripts
• Merkle Trees
• Abstract Syntax Trees