The Schnorr Signature & Taproot Softfork Proposal

Abstract: We summarise and provide context for a recent Bitcoin softfork upgrade proposal, which includes a new digital signature scheme (Schnorr), as well as a complementary upgrade called Taproot, which adds new capabilities that extend Bitcoin’s smart contracting capability. The upgrades are structured to ensure that they simultaneously improve both scalability and privacy. Other than increased complexity, there are no significant downsides to the proposal, and the most controversial aspect of it is likely to be the lack of other anticipated features. We conclude that although many will be enthusiastic about the upgrade and keen to see it rolled out, patience will be important.

(Source: Pexels)

Overview

On 6th May 2019, Bitcoin protocol developer Pieter Wuille posted a softfork upgrade proposal to the Bitcoin developer mailing list, called “Taproot”. If this proposal is accepted, it is likely to complement the Schnorr signature softfork upgrade, which Pieter posted in July 2018. The benefits of these proposals are related to both scalability (efficiency) and privacy. Scalability and privacy enhancements now appear somewhat interrelated and inseparable. Removing details about transactions, ensures both that transactions are smaller (improving scalability) and that they reveal less information and are therefore potentially indistinguishable from transactions of different types, thereby improving privacy.

Schnorr Signatures

The Schnorr signature scheme was patented in 1991 by Claus Schnorr and the patent expired in 2008. Although the Schnorr scheme is said to be stronger, a variant of it, the Digital Signature Algorithm (DSA) scheme was more widely adopted, as the patent for this scheme was made available worldwide royalty free. However, Dr Schnorr himself always maintained that DSA should be covered under his patent.

When Bitcoin was launched, in 2009, it therefore used a variant of DSA, Elliptic Curve Digital Signature Algorithm (ECDSA) for its digital signature scheme, due to its widespread adoption. However, the original Schnorr signature scheme was always more simple and efficient than DSA, with less burdensome security assumptions. After 10 years of experience of Bitcoin usage, it is becoming more apparent that these efficiency advantages could be important. Therefore it seems sensible that Bitcoin should migrate over to the Schnorr signature scheme.

The main benefit with Schnorr signatures, is that multi-signature transactions appear onchain as a normal single signature transaction. Using Schnorr signatures, multiple signers can produce a joint public key and then jointly sign with one signature, rather than publishing each public key and each signature separately on the blockchain. This is a significant scalability and privacy enhancement. This implies that Schnorr signatures result in significant space savings and savings to verification times, with the comparative benefits getting larger as the number of signatories on a traditional multi-signature transaction increase.

Schnorr signature space saving estimates

We have tried to calculate the potential Bitcoin network capacity increase this aggregation feature of Schnorr multisig can provide. However, due to the large number of assumptions involved, our 13.1% capacity increase figure below should be considered as a very approximate estimate.

Savings estimates based on UTXO count

Estimated current multi-signature usage by UTXO count
5.9%
Effective network capacity increase assuming 100% Schnorr adoption
13.1%

(Source: BitMEX Research calculations and estimates, p2sh.info)

(Notes: The estimates ignore the impact of Schnorr’s smaller signature size and only include the benefits of joining the public keys and signatures. The capacity increase was estimated by using p2sh.info related to multi-signature usage and applying a savings multiple to each multi-signature type (ranging from 50% to 85%). A network wide capacity increase was estimated by assuming the UTXO usage proportion was typical of blockchain usage and applying a higher weight to larger multi-signature transactions. Unspent P2SH outputs were allocated to multi-signature types in proportion to the spent outputs. This figure should only be considered as a very approximate estimate. Data as at 07 May 2019 )

The above estimated capacity increase can be considered as small, however one should consider the following:

  • Economic usage of multi-signature technology is far more prevalent than by merely looking at the UTXO count. Around 21.5% of all Bitcoin is stored in multi-signature wallets, a far higher figure than the 5.9% adoption by UTXO count
  • Multi-signature adoption is growing rapidly, as the below chart indicates. While at the same time new systems like the lightning network require multi-signature adoption and with Schnorr signature making multi-signature systems more powerful, adoption is likely to increase

Bitcoin stored by P2SH address type – chart shows strong growth of multi-signature technology

(Source: p2sh.info)

Therefore, although based on the current usage of the network, according to our basic calculation, even 100% Schnorr adoption only results in a 13.1% network capacity increase, in the long term the potential space savings and network capacity gains are likely to be far higher than this.

Merkelized Abstract Syntax Tree (MAST)

MAST was an idea worked on by Bitcoin protocol developer Dr Johnson Lau in 2016. Dr Lau has written for BitMEX Research in the past, in his February 2018 piece entitled The art of making softforks: Protection by policy rule. The MAST idea is that transactions can contain multiple spending conditions, for example a 2 of 2 multi-signature condition, in addition to a time lock condition. In order to avoid putting all these conditions and scripts into the blockchain, the spending scripts can be structured inside a Merkle tree, such that they only need to be revealed if they are used, along with the necessary Merkle branch hashes.

Graphical illustration of MAST spending conditions

(Source: BitMEX Research)
(Notes: The diagram is trying to illustrate a transaction structure assuming MAST was used in conjunction with Schnorr. In the above construction funds can be redeemed the cooperative way if both Bob and Alice sign, or in an uncooperative way after a timelock. The above is supposed to illustrate the type of structure which could be required when opening and closing lightning network channels)

Based on the above design, it can be assumed that only one spending condition will need to be revealed. For example, to spend the output, all the signers need to do is provide one Schnorr multi-signature and the hash at the top of the right hand side of the Merkle tree (Hash (1 & 2)). Therefore despite the existence of a Merkle tree, in the majority of cases, where everything goes as planned, only a single signature and 32-byte hash is required. More concisely, in order to verify a script, you need to prove that it is part of the Merkle tree by revealing other branch hashes.

However, the disadvantage of this structure is that even in normal optimal circumstances, when the single key and script on the top left of the Merkle tree is provided, one still needs to publish another hash to the blockchain (Hash (1 & 2) in the above diagram), using up 32 bytes of data. This weakness also reduces privacy, since third parties can always determine if more complex spending conditions exist, as the top branch of the Merkle tree is always visible.

Taproot

As far as we can tell, the origins of the Taproot idea are from an email from Bitcoin developer Gregory Maxwell in January 2018. Taproot is similar in construction to MAST, except at the top of the Merkle tree. In the case of Taproot, in the cooperative or normal scenario, there is an option for only a single public key and single signature to be published, without the need to publish evidence of the existence of a Merkle tree. An illustration of the Taproot transaction structure is provided below.

Graphical illustration of Taproot spending conditions

(Source: BitMEX Research)

(Notes: The diagram attempts to illustrate the same spending criteria as the MAST diagram above)

The tweaked public key on the left (or address) can be calculated from the original public key and the Merkel root hash. In the event of a normal or cooperative payment, on redemption, the original public key is not required to be onchain and the existence of the Merkle tree is not revealed, all that needs to be published is a single signature. In the event of a lack of cooperation or abnormal redemption, the original public key is revealed along with information about the Merkle tree.

The benefits of Taproot compared to the original MAST structure are clear, in the cooperative case, one is no longer required to include an extra 32-byte hash in the blockchain or the script itself, improving efficiency. In addition to this, the transactions looks “normal”, just a payment with a public key and signature, the existence of the other spending conditions do not need to be revealed. This is a large privacy benefit, for example when opening a lightning channel or even doing a cooperative lightning channel closure, to an external third party observer, the transaction would look exactly like a regular spend of Bitcoin. The transaction could be structured such that only in an uncooperative lightning channel closure would the existence of the Merkle tree need to be revealed. The more different types of transactions look the same, the better it is for privacy, as third parties may be less able to determine which types of transactions are occurring and establish the flow of funds. A long term objective from some of the Bitcoin developers may be to ensure that, no matter what type of transaction is occurring, at least in the so-called cooperative cases, all transactions look the same.

The confusion over Signature aggregation

The potential scalability benefits of reducing the number of signatures needed on the blockchain are large and therefore the concept tends to generate a lot of excitement. Schnorr signatures do provide the capability to aggregate signatures in multi-signature transactions, which should be a significant benefit to Bitcoin. However, the inclusion of this and the existence of other signature aggregation related ideas, has lead to some unrealistic expectations about the potential benefits, at least with respect to this upgrade proposal. As far as we can tell, for this particular upgrade proposal, the only aggregation benefits are in the form of joining signatures in multi-signature schemes, not for multiple inputs or multiple transactions.

Summary table of signature aggregation ideas


Included in softfork proposal
Combined public key and signatures in multi-signature transactions – Included as part of Schnorr
Yes
Joint signature for multiple inputs in a transaction
No
Joint signature for multiple inputs in multiple transactions (Grin coin has some capabilities in this area, using Mimblewimble)
No

(Source: BitMEX Research)

Conclusion

In our view, the benefits associated with this softfork are not likely to be controversial. This softfork appears to be a win-win-win for capability, scalability and privacy. The largest area of contention is likely to be the absence of the inclusion of other ideas or arguments over why to do it this particular way.

That being said, many are likely to be excited about the potential benefits of these upgrades and keen to see these activated on the network as fast as possible. However, when it comes to Bitcoin, and in particular changes to consensus rules, the need for patience cannot be overstated.