The Power of Schnorr: The Signature Algorithm to Increase Bitcoin's Scale and Privacy

Segregated Witness has entered its  final testing stage before roll-out on the Bitcoin network. That is  good news, most importantly because the innovation
Segregated Witness has entered its  final testing stage before roll-out on the Bitcoin network. That is  good news, most importantly because the innovation
Privacy & security - The Power of Schnorr: The Signature Algorithm to Increase Bitcoin's Scale and Privacy

Segregated Witness has entered its  final testing stage before roll-out on the Bitcoin network. That is  good news, most importantly because the innovation introduces a capacity increase to allow for more transactions on the network, while it also solves  transaction malleability.

And, it introduces script versioning ‒ an extension to the Bitcoin protocol that allows for an entire new category of innovation.

One of these imminent innovations has been on the top of several Bitcoin developers’ wish-lists for some time: Schnorr signatures.

With the impending release of Segregated Witness, implementation of the Schnorr cryptographic signature algorithm might follow soon after, potentially improving Bitcoin's scalability, efficiency and privacy, all in one go.

Here's how.

Signatures

First, a brief re-cap: what are signatures?

At the heart of Bitcoin lies the mathematical trick called “public key cryptography,” a cryptographic system that uses two kinds of “keys” (really strings of numbers): private keys and public keys.

A private key and a public key are mathematically linked. But while it's very easy to produce a public key from a private key, it's practically impossible to produce the private key from a public key. It's a “one-way street.”

In order to spend bitcoins from a particular Bitcoin address, one must prove “ownership” (or: knowledge) of the private key that refers to the public key associated with that address. And to prove ownership of a private key, without having to reveal that private key, a cryptographic signature is used.

A signature is created by performing a calculation using the transaction data and the private key. And here's where the magic of public key cryptography comes in: Knowing the public key, anyone can see if the correct private key was used to create the signature. Without ever needing to know the private key itself.

The “owner” of the private key can therefore sign a transaction and spend bitcoins without worrying that someone else can take that private key and steal the bitcoins; the private key is never exposed, and the signature is only valid for that specific transaction.

(For a more elaborate explanation of public key cryptography in Bitcoin, see  this article. Or, just keep reading. While the basic signature concept matters, the details are not crucial for the purpose of this article.)

Schnorr

So what, then, are Schnorr signatures?

Schnorr, named after its inventor Claus-Peter Schnorr, is a signature scheme: the series of mathematical rules that link the private key, public key and signature together. Many cryptographers consider Schnorr signatures the best in the field, as they offer a strong level of correctness, do not suffer from malleability, are relatively fast to verify, and ‒ importantly ‒ support multisignature: several signatures can be aggregated into a single, new signature.

However, until now it has not been possible to utilize Schnorr in Bitcoin. Another type of signature scheme, Elliptic Curve Digital Signature Algorithm (ECDSA), is baked into the Bitcoin protocol, and changing that would require a hard fork.

That's where Segregated Witness comes in.

With Segregated Witness, all signature data is moved to a separate part of the transaction: the witness, which is not embedded in the “old” Bitcoin protocol. And thanks to script versioning, almost any rule applied in the witness can be changed through a soft fork. Including the type of signature scheme used.

This opens the door for Schnorr.

Capacity

The Schnorr property that stands to benefit Bitcoin most is multisignature aggregation.

Many Bitcoin transactions include multiple inputs, referring to the addresses bitcoins are sent from. (This can be compared to how cash payments often consist of multiple smaller bills and coins to pay a larger sum of money.) Right now, all these inputs require their own signature, which means all these signatures must be included in a transaction, all must be transmitted over the network, and all must be included in a block.

With Schnorr, however, all inputs will instead require only one combined signature to represent all these different signatures. This offers an obvious data advantage, as only one signature must be included in a transaction, only one must be transmitted over the network, and only one must be included in a block. This means there's more room for transactions.

For example:

Segregated Witness, as proposed by Bitcoin Core, offers a (roughly) 75 percent discount on all data included in the witness rather than the original block. One megabyte of witness data is therefore “weighed” as .25 megabyte, which would leave room for .75 megabyte transaction data in the original block, for a total of 1 megabyte.

If aggregated Schnorr signatures reduce the total size of witness data, say from 1 megabyte to .5 megabyte, this .5 megabyte would then be discounted to 0.125 megabyte, leaving room for up to 0.875 megabyte in the original block. (A capacity increase of about 17 percent.)

The exact amount of added room depends on the types of transactions included in blocks. But rough estimates by Bitcoin Core developer Eric Lombrozo suggest that Schnorr signatures could eventually increase total capacity 40 percent or more – that’s on top of the added 60 to 100 percent already offered by Segregated Witness.

Multisig

The capacity increase as described above is true for regular transactions, as many transactions include more than one input. But the advantage can be even greater in the case of multisig transactions ‒ transactions where a single input itself requires several signatures (typically from different people).

As with normal transactions, no more than a single signature needs to be included in any multisig transaction. No matter how many signatures are required, no matter how many people involved.

This opens the door to vastly more complex smart contract constructions, for a fraction of the data normally required. Whether it's two-of-three, three-of-fifteen or hundred-of-hundred types of multisig transactions, all will carry the same amount of signature data as a typical single-signature transaction.

Privacy

And third, Schnorr signatures could offer another interesting benefit: incentivized privacy.

As mentioned, one transaction can include multiple inputs. Most commonly, these inputs refer to addresses that are all controlled by the same person. (As per the multiple bills and coins example.)

But a privacy-enhancing trick invented by Bitcoin Core developer Gregory Maxwell,  CoinJoin, allows different users to combine all their transactions into a single transaction. That one transaction will include multiple inputs coming from different payers, which sends money to multiple outputs, belonging to different payees.

(This can be compared to a group of people throwing their bills and coins together in a basket, which they use to go shopping in different stores to buy the products all of them want. Each individual will get the goods that individual paid for, but it's unlikely any individual's “own” bill paid for the product that individual bought.)

If done right, CoinJoin is a great way to improve privacy on the Bitcoin protocol, as it becomes unclear which inputs paid which outputs exactly, let alone which person paid which person.

CoinJoin is not a new concept. But up until now CoinJoin was typically a bit of a hassle. As such, most people don't bother. And since most people don't bother, those who do bother could automatically be marked as suspicious; potentially defeating the purpose of using CoinJoin in the first place.

But Schnorr signatures can add a new advantage to CoinJoin. It enables all participants in a CoinJoin transaction to not only combine their transactions, but to also combine their signatures. And doing so means the size of the transaction would actually be smaller than all individual transactions combined. Which, in turn, means miners would typically charge a smaller fee to process the transaction.

With Schnorr, therefore, CoinJoin would not only increase privacy, but also – importantly – lower the costs for everyone involved. Indeed, there would be a cost benefit to use the most private option, which might just make it the go-to option for everyone – vastly increasing Bitcoin privacy for all.

Note: The process of implementing Schnorr signatures in Bitcoin is still in the concept phase. While most Bitcoin Core developers seem to believe Schnorr signatures can be safely deployed in Bitcoin, it is too early to say with certainty.

Thanks to Bitcoin Core developer and Blockstreamco-founder Dr. Pieter Wuille for providing information, and Bitcoin Core developer and CiphrexCEO Eric Lombrozo for proofreading and further suggestions.