Schnorr Signatures

Improving Bitcoin’s privacy and scalability

Back in September 2013, an anonymous author wrote a bitcointalk.org post suggesting there may be ways to improve privacy and scalability by aggregating or combining signatures. Multiple inputs can share a signature authorizing the collective movement of the coins. In doing so, people have an economic incentive to combine transactions which results in less precious blockchain space and more ambiguity as to the payer and payee within a transaction, improving privacy.

Since then, the Bitcoin developer community has been abuzz with this idea and a relatively obscure method of cryptographic signatures has been thrust to the forefront of this movement. The method is known as Schnorr Signatures. They were created by cryptographer Claus Schnorr, and first released to the public in a 1989 paper. It’s unknown whether Satoshi considered this method for signatures, but it likely wouldn’t have mattered as Schnorr held a patent on this method until 2008.

Background

Each block within the Bitcoin blockchain contains one or more transactions. Transactions are composed of a list of existing inputs which are to be consumed, a list of outputs to be created, and proof that the owners of the inputs approve of the transaction which will transfer their bitcoins.

credit: Satoshi Nakamoto

In Bitcoin, the majority of inputs need a cryptographic proof in the form of a digital signature to be spent. It’s possible to have many different types of spending criteria that must be satisfied, including no criteria at all, which are known as anyone-can-spend outputs.

Quick intro to digital signatures

The most popular signature algorithms in use today are Rivest–Shamir–Adleman (RSA) and Digital Signature Algorithm (DSA). RSA was built for both encryption and signatures, while DSA was originally built only for signatures, but has since been adapted to support encryption as well. The two algorithms rely on different cryptographic assumptions: RSA relies on factoring being hard, while DSA relies on the discrete log problem being hard.

Both techniques require public and private key pairs. The private key is needed to sign the message while the public key is used to verify the signature. Keys are technically very large numbers that we use to conduct discrete math. The set of numbers that are possible values in these computations are known as a field or group.

Currently, Bitcoin uses Elliptic Curve Digital Signature Algorithm (ECDSA), a modification of the Digital Signature Algorithm (DSA) to work on elliptic curves. The curve defines the mathematical group used for computations, which dictates the key format and the set of values the cryptography operates on. The advantages of ECDSA is that thanks to the efficiencies of elliptic curve cryptography, you can achieve the same security as RSA with smaller key sizes. This has made ECDSA an astute choice for Bitcoin since smaller keys make for a smaller footprint overall for the system, resulting in less data and faster operation.

Schnorr Signatures

Schnorr signatures can be adapted to any mathematical group that satisfies the discrete log problem. Luckily the elliptic curve in Bitcoin, secp256k1, fits this property. This means that the same private and public keys can be used with Schnorr signatures in Bitcoin. Schnorr signatures have many advantages over ECDSA signatures:

1. Schnorr signatures are smaller. Most ECDSA signatures are 71 or 72 bytes. All Schnorr signatures will be 64 bytes.
2. They allow for more compact multisig. Current m-of-n signature schemes in Bitcoin require the presentation and verification of m signatures. Schnorr multisig needs just one signature to account for all m parties.
3. Signature aggregation across inputs! Not only can we condense a multisig input’s signatures into a single signature, we can aggregate signatures from multiple inputs into a single signature. When combined with CoinJoin, this can make transactions cheaper and more private. Even without CoinJoin, this can greatly reduce the size and cost of a transaction. Pieter Wuille, the primary engineer behind bringing Schnorr signatures to Bitcoin, estimates that just by having users aggregate signatures across inputs, the Bitcoin blockchain could shrink by 25–30%.
4. Scriptless Scripts! By using Schnorr signatures in clever ways that are well beyond the scope of this post, we can actually implement different spending conditions just by using a special process to create the required signatures. Scriptless scripts exploit the linear nature of Schnorr signatures so that partial signatures must be combined in specific ways to satisfy the spending criteria. Blockstream’s Andrew Poelstra has done some great research into the possibilities here.
5. Schnorr Signatures are provably immalleable. ECDSA signatures can be changed without having access to the private key that created them. This was a big problem for Bitcoin when the signatures were included in generating the transaction id. Segregated Witness made this less of an issue by splitting out the signatures (also known as witnesses), but it is still nice to have consistent signatures.

Any downsides?

Schnorr signatures accentuate a weakness that already exists with the current ECDSA system. These signature schemes utilize a nonce, a value intended to be used only once, that must be selected at random or at least be unpredictable or an attacker can reverse engineer the private keys. This famously happened to Sony in 2011 when the ECDSA scheme used on the PS3 was revealed to not choose this nonce randomly at all. The result was a group publishing Sony’s private keys allowing users to install their own OS and/or pirate PS3 games.

With ECDSA, the nonce can be deterministic based on what is being signed since there is no signature aggregation. This is what Bitcoin does without issue. However, when aggregation is introduced, we will need a real source of random entropy in order to create signatures. The problem is that with multiple parties joining to create signatures, malicious parties can start the request for two multisignatures with the same nonce and the same inputs. They would abort the requests before completion, but may have created just the right conditions to reverse engineer a victim’s private key.

What’s next?

One obstacle to Schnorr signatures being implemented is that they are not yet standardized. Bitcoin Core developers, led by Pieter Wuille, have a draft proposal offering a standardization for the implementation of single signatures. The draft is currently being peer reviewed by the Bitcoin community.

Signature aggregation is another layer of complexity due to possible attacks with crafted nonces. Blockstream has been doing some fascinating work on this problem and their proposed solution has been dubbed MuSig. MuSig currently solves the problem by adding more rounds to the signature creation process to ensure that nobody is able to harm others by manipulating the nonce selection. Currently the MuSig protocol requires three rounds of coordination with the co-signers. The first round requires everybody produce unique input that will be hashed together to ensure that the same nonce is never used to sign the same message.

There is ongoing research into optimizing signature aggregation. Blockstream’s hope is that they will be able to reduce the rounds of communication from three to two by utilizing zero knowledge proofs to ensure proper entropy. It seems unlikely that Schnorr signatures will enter Bitcoin this year, but they are well on their way and with any luck we can hope to see them introduced around the next block reward halving in 2020.