Adam Boudjemaa

Blockchain Developer, Bitcoin & Crypto Enthusiast.

The Future of Bitcoin: Schnorr Signatures, Key Aggregation & Interactive Aggregate Signatures

Stay up to date with my latest tweets here: @BoudjemaaAdam
If you look beyond the price, you would most certainly agree that bitcoin is an amazing technology that introduced the world’s first decentralized and peer to peer electronic cash.
However, many prospects believe that bitcoin was just an experimental technology, and is still at its very early stages.
If you look closely, this argument seems to be true because bitcoin can seemingly handle 7 or 8 transactions per second and clearly lacks the foundation for what we call ‘exponential scaling’ to accommodate billions of users doing billions of transactions every single day.
However, this kind of phenomenon isn’t very new, and we have seen this many times in the past.
When any new technology is introduced, which aims to bring a completely different paradigm shift, the underlying infrastructure isn’t always ready. This happened with the internet back in the days when the bandwidth was so slow and expensive that it couldn’t even support email attachments, but now we are talking about 4K videos in virtual reality hosted on the internet.
This also happened with smartphones, where the first version of the smartphone had such less memory that it couldn’t save more than 3 or 5 songs, but now we are talking about heavy mobile gaming and Augmented Reality-based mobile applications.
The same is happening with bitcoin, and history is repeating itself one more time. Bitcoin represents an amazing potential of a decentralized financial system, but unfortunately, the infrastructure isn’t ready, and we need to make a lot of marginal improvements to ensure more privacy, more scalability, and a higher level of global adoption to accommodate billions of people with their daily transactions.
This is why the current debate for Bitcoin's improvements is turning around the two fundamental topics:

Important Breakthrough — Segregated Witness (SegWit) and Transaction Malleability

Bitcoin has an amazing community of developers and volunteers who are working very hard to solve some of the most fundamental and underlying problems to encourage the growth of a healthy ecosystem.
There have been many debates on which problems should be solved first, what approach should be taken, and what should be the priority of the updates.
It is very important to note here that we are dealing with a 'decentralized software', so the update process isn't very easy. 
In a decentralized system, updates are usually performed with either a soft-fork or a hard-fork. Right now, a hard fork is rarely an option for bitcoin because of the current scale of adoption. People also like to call bitcoin a system that has become 'hard fork averse'. However, releasing updates via a soft fork is a viable option, but it is still very different from the regular centralized software updates, and you need a vote of confidence from the community of miners, developers, users, etc. so that the soft fork gets implemented.
Soft forks are also 'backwards-compatible', which means that people could still use the older version of the software. 
When the scalability debate was happening, two solutions were proposed. One solution was to simply increase the block size (we have 1 MB block size in bitcoin), which would accommodate more transactions in a single block, thus increasing the number of transactions per second.
The second solution was to 'optimize' the existing block architecture to take full advantage of the available space. The core community members decided to go with the second option and called it an 'optimization first' strategy. 
On August 2017, an update was released with the name Segregated Witness or commonly known as SegWit. SegWit was primarily meant to solve the 'transaction malleability' problem by separating the signature information from the transaction ID.
In the past, anybody could modify the public signature (hash of the transaction) without actually changing the transaction itself, and this phenomenon is called 'transaction malleability', which didn't pose any threat to the bitcoin network, but it made the second layer networks like Lightning Network more complex. 
With the removal of transaction signature information, SegWit introduced some extra space in the block where more transactions could be included, thus increasing the number of transactions per second.
Also, by solving the problem of transaction malleability, SegWit made it easier for the second layer networks, which rely heavily on the off-chain and unconfirmed transactions for things like micro-payments.
Second layer networks are meant to solve the scalability problem of bitcoin, so we can easily say that SegWit killed two birds with one stone.
However, if you look at the SegWit blocks, you will realize that signatures still take a lot of space in a single block, which can be utilized in many other ways. This is where the 'Schnorr Signatures' come in, which we are going to discuss in the next section.

Schnorr Signatures and Cross Input Aggregation

Digital signatures are at the heart of the bitcoin architecture. These signatures allow 'ownership' of bitcoins and give you an ability to send and receive bitcoins in a transaction, thereby claiming the ownership of your bitcoins and allowing you to secure them in a wallet.
Without these signatures, you cannot send or receive bitcoins. You can think of these digital signatures as your 'digital identity'. Unlike real-world signatures, digital signatures are backed by strong cryptography, which means that it is nearly impossible to forge them or recreate them without having access to the 'Private Key'. 
When Satoshi was creating bitcoin core, there were many signature schemes available at that time. The prominent ones were RSA, ECDSA, and Schnorr signature schemes.
For Bitcoin, Satoshi wanted a signature scheme that promises higher levels of security, doesn't take a lot of space and is standardized, which means that it is widely used and adopted.
Finally, the ECDSA or Elliptic Curve Digital Signature Algorithm was chosen because of its inherent properties. It was open-source, standardized, widely adopted, and better than RSA in terms of security and space.
As a reference, a 256-bit ECDSA key has an equivalent amount of security compared to the 3,072 bit RSA key. 
Another important thing to note here is that ECDSA was included in the set of OpenSSL tools that are widely used on the internet. Schnorr signatures carried many benefits over ECDSA, but the problem with this scheme was that it was patented by Claus-Peter Schnorr, the cryptographer, and researcher who created them in the 1980s.
Due to its usage restrictions, Schnorr signatures didn't get enough popularity, and they weren't widely adopted. The patent expired in 2008, the same year when Satoshi launched bitcoin.
However, due to the lack of standardization and adoption, Satoshi didn't pick them in the first place despite all their inherent properties. 
Fast forward today, we can see a lot of standardized implementations of Schnorr signature schemes. The most famous and widely adopted Schnorr signature scheme is ed25519, which is currently being used in many cryptocurrencies today.
Discussions for the implementation of Schnorr signatures in bitcoin core started back in 2014, but after in-depth research, Pieter Wuille (one of the prominent bitcoin core developer) submitted a bitcoin improvement proposal called the Schnorr BIP.
According to this draft, Schnorr signatures would bring the following main benefits to bitcoin over ECDSA, which include: 
  • Security proof: The security of Schnorr signatures is easily provable in the random oracle model assuming the elliptic curve discrete logarithm problem (ECDLP) is hard. Such a proof does not exist for ECDSA.
  • Non-malleability: ECDSA signatures are inherently malleable; a third party without access to the private key can alter an existing valid signature for a given public key and message into another signature that is valid for the same key and message. This issue is discussed in BIP62 and BIP66. On the other hand, Schnorr signatures are provably non-malleable.
  • Linearity: Schnorr signatures have the remarkable property that multiple parties can collaborate to produce a signature that is valid for the sum of their public keys. This is the building block for various higher-level constructions that improve efficiency and privacy, such as multi-signatures and others.
Above examples are directly taken from this source: https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

Key Aggregation with Schnorr signature scheme

Traditionally, multi-sig transactions in bitcoin were made possible via a special kind of transaction called P2SH or ‘Pay to Script Hash’. With this P2SH scheme, users can specify the spending conditions which are called encumbrances for multi-sig environment in the form ‘spend the funds if m out of n people sign the message’.
This scheme has many problems but the biggest ones are that these transactions take too much space because of the number of signatures that are needed to be verified, and the multi-sig addresses start with the number ‘3’ which is a privacy problem where the intruder can not only identify a multi-sig transaction, but he can also see all the public keys of the participants.
With the Schnorr signature scheme, all the participants in the multi-sig environment can combine their keys into 'one single key'. To spend the funds, only a single key can be utilized, which is a combination of the keys of all the participants in an m-of-n scheme.
This property is called 'key aggregation'. In order to verify the sum of all the keys, a new OP code will be introduced into the bitcoin core called OP_CHECKDLS.
This new OP code includes the Discrete Log Signature (DLS) verification system, which is easier and much more efficient. With key aggregation, Schnorr signature scheme not only frees up some space by reducing the number of signatures required, but it also helps attain more privacy for the users who want to use a multi-sig scheme but don't want to leak out any kind of information for the transaction.

Cross Input Aggregation — Freeing up 25% of the space

In the previous section, we discussed the key aggregation property of Schnorr signatures and how they can be utilized in a multi-sig environment.
The same key aggregation property can be used in a single transaction environment as well, where only one signature verification is required to spend all the inputs.
A normal bitcoin transaction has more than one inputs, and each one of the input signatures is independently verified to make a successful transaction.
In the case of Schnorr signature scheme, these input signatures can be combined into a single signature called IAS or 'Interactive Aggregate Signature' which represents the sum of all the input signatures. 
This IAS or Interactive Aggregate Signature, can be used to spend all the inputs in a transaction. This new signature can be verified very easily using OP_CHECKDLS, which is a new OP code that would be introduced with the Schnorr signature scheme.
Just like a multi-sig environment, this cross input key aggregation also enhances privacy and frees up space, which was previously used to accommodate all the signatures across many different inputs.
According to some analysts, this cross input aggregation alone can free up to 25% of the space, which can be utilized to accommodate more transactions, thereby increasing the number of transactions per second. IAS will also ensure more privacy where instead of all the different signatures of every individual input, you are just using a single signature that can verify all the inputs.

Conclusion

Schnorr signatures would bring multiple benefits to the bitcoin architecture with better privacy, more optimization, and a room for scalability.
With fewer signatures and easy verification, the bitcoin architecture would be greatly improved, allowing newer possibilities for the second layer networks to build upon.
After Segregated Witness (SegWit), people are very excited to see this new update for the Schnorr signature scheme together with IAS, Key Aggregation, and new OP codes into the bitcoin network.
Once these privacy and scalability problems are solved, we will see bitcoin climbing incredible heights, building better infrastructure, and a healthy ecosystem.
Stay up to date with my latest tweets here: @BoudjemaaAdam
Follow me on Linkedin here: @AdamBoudjemaa

Tags

More by Adam Boudjemaa

Topics of interest