How will Schnorr Signatures Benefit Bitcoin?
In this first part of our series explaining Bitcoin’s highly anticipated upgrade (BIPs 340–342), we’ll explain how bitcoin transactions work as well as the benefits and mechanics of Schnorr signatures (BIP 340).
On January 21st 2020, protocol developer Pieter Wuille submitted a pull request for Bitcoin’s next soft fork upgrade. A pull request means more developers will examine the code — which is significant for Bitcoin since the upgrade is another step closer to inclusion into the protocol. Formally known as Bitcoin Improvement Protocols 340, 341, and 342, these updates include Schnorr signatures, Taproot and Tapscript.
The three-part BIP represents the biggest upgrade to Bitcoin yet, and the first since the activation of Segregated Witness (or SegWit) over two years ago. As a bundle, these proposals have significant advantages for Bitcoin’s functionality, scalability and privacy.
The activation method for this soft fork is being debated. BIPs do not specify the exact method of deployment of an upgrade to the network. The upgrades described by BIPs 340–342 could be implemented as early as winter 2020, although it may take longer.
In this first part of our series, we’ll explain how bitcoin transactions work, introduce the scripting system used, outline Schnorr signatures and the advantages of BIP 340. The following two parts in our series will look at Taproot (BIP 341) and Tapscript (BIP 342).
If you already have a good understanding of Bitcoin’s script system, you can skip the following section and go straight to Schnorr Signatures (BIP 340).
How Bitcoin Transactions Work
Bitcoin transactions are not based balances as you may be familiar with, e.g., your bank account.
Instead, transactions revolve around unspent transaction outputs (UTXOs), which comprise inputs and outputs. Each UTXO is associated with a private key and its associated transaction data. When you transfer bitcoins, you are transferring the ownership of a UTXO, of which you can prove with a cryptographic signature.
UTXOs are labelled by Bitcoin Script which describes the spending policy and these scripts are a list of instructions that are included with each transaction outlining how the new owner of some coins can spend them. Through the use of the Script programming language, transactions can contain many conditions, which include things like multi-signature (multi-sig) schemes.
Inputs are UTXOs consumed by a transaction, while outputs refer to the UTXOs created by a transaction. For example, when you create a new bitcoin transaction, you use the set of UTXOs you own and provide a witness that attests you own those coins. To sign and authorise the transaction, you provide your digital signature associated with your private key to prove you are the owner.
Transaction outputs have two elements: the amount of bitcoin and a locking script (or scriptPubKey) that locks the amount by outlining certain conditions to spend the output. The locking script will lock the output to a particular bitcoin address, which transfers ownership of those bitcoins to the new owner.
The new owner can unlock the output by providing an unlocking script (or scriptSig) along with their signature that’s associated with their private key and then spend those coins. Unlocking scripts are part of every transaction input.
To ensure you cannot spend UTXOs you do not own, Bitcoin clients confirm transactions by executing a script. The unlocking script in each input is executed alongside the corresponding locking script to see if satisfies the spending condition. Full nodes track and verify UTXO sets, which ensures that each person can only spend the coins they own.
An Example
The diagram below illustrates how bitcoin transactions work.
Alice wants to pay Bob 1 BTC, and to do so, she creates a transaction using Bob’s public address. To transfer the coins, Alice provides her digital signature (which is a product of the private key and transaction data history) to prove she owns at least 1 BTC in her UTXO set — without revealing her private key.
As part of the transaction, there is a locking script that only Bob can unlock. The UTXOs are transferred once the transaction has been submitted, and it is added to the Bitcoin blockchain. By providing his signature, Bob can remove a locking script (or scriptPubKey) and he can use the UTXO as an input into a transaction.
The most common and basic form of bitcoin transactions utilise the Pay-to-Public-Key Hash (P2PKH) script. Bitcoin’s script language uses commands (or functions) that determine the instructions recorded with each transaction with more complicated transactions. Known as OP_CODEs, they enable us to set up certain conditions to transfer the ownership of coins.
For example, a multi-signature scheme (multi-sig for short) may specify that 3-of-5 participants must provide their signatures to spend the coins. Another example is the use of timelocks (such as nLockTime) to lock coins until a specified point in the future.
Another advanced type of transaction is Pay-to-Script-Hash (P2SH), which allows the sender to commit funds to a hash of an arbitrary valid script. The use cases for P2SH include multi-signature and non-native SegWit transactions. Also, several spending conditions can be combined to create complex smart contracts.
The locking script in a P2SH transaction is replaced by the ‘redeem script’. All scripts are revealed when the owner of the coins spends them as well as the solution to the script that locks up the bitcoins. Using the hash of the script included in the blockchain, anyone can check the conditions of the script to spend those bitcoins were met.
P2SH addresses start with a ‘3’, unlike P2PKH addresses which start with a ‘1’. As a result, a drawback with P2SH transactions is that they reveal all possible conditions and identities within the multi-sig.
Since P2SH transactions reveal the entire script once coins are spent, network participants can uncover of all the different ways they could have met the conditions (enabling the distinction between multi-signature transactions and P2PKH transactions). Network participants may also be able to deduce what type of wallet was used.
There’s also a disadvantage for scalability: complicated scripts have higher transaction sizes requiring more space on the blockchain (resulting in higher transaction fees).
Schnorr Signatures (BIP 340)
The first of the three-part BIP put forward by Pieter Wuille, BIP 340, lays out the specification of a more efficient digital signature scheme for Bitcoin: Schnorr signatures.
What are Schnorr Signatures?
As explained in the preceding section on how bitcoin transactions work, a scripting language controls the spending of coins and involves the use of digital signatures to transfer ownership of coins. Bitcoin checks cryptographic signatures using the Elliptic Curve Digital Signature Algorithm (ECDSA) (which doesn’t provide native support for multi-sig transactions and led to the standardisation of P2SH transactions in 2012).
In short, the Schnorr signature scheme (hereafter referred to as ‘Schnorr’) is a more efficient signature scheme. Developed by Claus-Peter Schnorr in 1989, this signature scheme was patented up until 2008. Bitcoin relied on OpenSSL for its cryptography, as ECDSA had become the standard and is the main reason for its use.
Schnorr builds on top of Segregated Witness, which was activated on Bitcoin to fix malleability problems in August 2017. With SegWit, it moves all scripts and signature data to the ‘witness’. The witness is a part of the transaction that is appended as a separate structure and no longer included in the list of inputs.
Let’s look at the main properties of Schnorr and the benefits for Bitcoin. First, we look at key aggregation, which follows on from the linear property.
Key Aggregation
The main benefit of Schnorr relates to multi-signature transactions.
Schnorr signatures are linear in that they can be subject to addition (or subtraction). The result is a valid signature corresponding to the same addition (or subtraction) of the public keys. The same does not hold with ECDSA and adding or subtracting these types of digital signatures is meaningless.
From its linearity, Schnorr enables key and signature aggregation. Aggregation means that we can combine several public keys into one, so that one signature is required for all parties. By summing the keys of the inputs, they are aggregated into a single signature where each signer contributes a partial signature.
The equations below illustrate aggregation with Schnorr thanks to its linear property. No one (apart from the participants) knows that there are three people behind the public key/signature.
With M-of-n multi-sig transactions, partial signatures are called threshold signatures. As shown by the diagram below, in a 3-of-5 multi-sig at the moment, you have M=3 signatures (out of n=5) as part of the inputs of the transaction.
M-of-n multi-sig transactions need M signers at the very least (and each signature needs to be verified) and to prove ownership of a UTXO of a multi-signature key, the scriptSig (or Unlocking Script), would have to contain M number of ECDSA signatures. The size of scriptSigs grows linearly according to M number of signatures, which increases the size of these transactions (and increases transaction fees).
Also, an observer will know that A, B, and C signed a transaction and they can also identify the multi-sig setup used.
But, with Schnorr, M signatures are aggregated into a single signature. Once the threshold public keys and threshold signatures are provided, the transaction is authorised and looks like a normal P2PKH transaction to an observer.
Schnorr enables us to produce only one signature for all M parties. The unlocking script would have one signature representing an aggregate of the participant’s signatures. An observer can no longer link a transaction’s signature to one person, many people or a threshold of people.
While the addresses and transaction amounts are still publicly visible, Schnorr by itself makes wallet/use-case fingerprinting more difficult (which are both used in taint analysis).
Going further with Schnorr’s ability to be added or subtracted opens up new and interesting applications. One example is Scriptless Scripts, a method of executing smart contracts on Bitcoin. Scriptless Scripts relies on Schnorr’s linear property to create adaptor signatures, enabling atomic swaps.
The table below shows the advantages of Scriptless Script atomic swaps.
Reduction in Transaction Sizes and Faster Verification
Schnorr signatures are 11% smaller than existing signatures, which take up around 70–72 bytes per transaction. Since Schnorr signatures take up less room in a transaction/on the blockchain (they are fixed at 64 bytes), smaller transaction sizes and lower fees are possible.
Also, if a bitcoin transaction contains many inputs, they each need their own signature. Remember, inputs refer to addresses you have received bitcoin from. For any amount of bitcoins controlled by many signers, each signer must post their separate ECDSA signature to the transaction. These signatures are verified individually and to verify a batch of signatures efficiently, we have to rely on some mathematical tricks.
All inputs will only need one combined signature with Schnorr, as the different signatures are aggregated. With the inclusion of one signature into a transaction, there’s more capacity for other transactions. Smaller transaction sizes for multi-sig transactions translates into lower fees. With key aggregation, we do not have to check each individual input, and verification is faster.
A compact multi-signature with ECDSA is also more difficult to produce as they are encoded using DER (Distinguished Encoding Rules), while Schnorr signatures will be encoded in a more space efficient way.
Schnorr is At Least as Secure, If Not More Secure, than ECDSA
Both the ECDSA and Schnorr digital signature schemes rely on the discrete logarithm problem. But the upside of Schnorr is that it uses fewer assumptions as compared to ECDSA and has a formal proof that is secure.
ECDSA lacks a formal security proof and relies on extra assumptions to achieve this. As a result, Schnorr should be a clearer framework to work with for cryptographers and is at least as secure (if not more secure) than ECDSA.
Summary
In short, Schnorr has several implications for scalability and spending policy privacy (not transaction linkage privacy). The efficiency gains open up the use of more complex multi-sig transactions, allowing very large M-of-n schemes and more advanced contracts. When combined with Taproot and Tapscript, Schnorr lays the foundation for many more benefits in terms of privacy and scalability.
BIP 340 is the standardisation for Schnorr signatures to integrate them into the Bitcoin protocol. The proposal will go under thorough review to ensure that there are no problems within the parameters outlined in BIP 340. The upgrade itself is not controversial. There’s wide agreement that Schnorr is one of the best digital signature schemes and is beneficial for Bitcoin. Bitcoin Cash developers have seen value in Schnorr signatures, and have implemented it into their protocol.
The average user who does not use complicated spending policies will not notice the new Schnorr signature scheme (apart from one character in SegWit addresses). They will not replace ECDSA signatures in Bitcoin (both signature schemes will exist side-by-side). Much like SegWit, wallet developers/users will have to adopt Schnorr — once implemented — to realise the benefits.
In the next installment, we will look at how Schnorr signatures combined with Taproot (BIP 341), enables even greater privacy and scalability for Bitcoin.
Have any questions or thoughts about Schnorr/BIP 340? Leave them in the comments below.
Read part 2 ‘What is Taproot and How will it Benefit Bitcoin?’ here.
About Interdax:
Interdax — the first competitive crypto trading platform. Trade crypto derivatives with up to 100x leverage while competing to win big prizes in matches and tournaments. Built by former NYSE / Nasdaq engineers.
