SegWit: Bob, Alice and Trent meet Schnorr
SegWit: Bob, Alice and Trent meet Schnorr
Let’s say we have a transaction, and Bob, Alice and Trent must authorise it. In a Bitcoin network, this is defined as a “multisig” setup. Bob, Alice and Trent must then go away and create their own new “aggregated” signature, which will be their new public key for transactions. This is not efficient, and also reveals the Bob, Alice and Trent are working together. In an improved setup, we can define an n-from-m setup, where we can merge Bob, Alice and Trent’s keys into one public key, and then use that. The public key will then not reveal that Bob, Alice and Trent are working together, but they will create a new public key which will validate the transaction.
If we wanted just any two of them to validate it, we could ask for a 2-from-3 multisig. So if Bob, Alice and Trent are directors in a company, they could define that any two of them could validate a transaction.
The Bitcoin network could have found a way to enable this type of signature merging of public keys, and it all points to the Schnorr method. In illustration below, we can see that the current method involves Bob, Alice and Trent getting together and creating a new public key (and an associated private). With Schnorr’s key aggregation method, we can take Bob, Alice and Trent’s public keys and then merge into a new transaction key. It will then not be possible to see the parties who created the transaction key.
The ECDSA bottleneck
Bitcoin is a bit of a hotch-potch of cryptography, but it all seems to work. Unfortunately, it is having trouble scaling up, and one of the bottlenecks is the signature. For this we create a private key, and then use the Elliptic Curve DSA method to produce a signature of this key:
In this way, the Bitcoin infrastructure knows that the person with the correct private key has signed the transaction. Unfortunately, ECDSA is not an efficient method.
Schnorr’s method of signature aggregation
This method, though, suffers from performance issues. In a paper by Maxwell etc at, they describe a way to bunch Schnorr’s multi-signatures (multisig) data into a signature which improves performance and transaction privacy (paper). It will support one person sending a transaction from multiple sources, and which will produce a single signature.
At the present time, multisig is trademarked, but the patent has elapsed. It also lacks standardisation, but this new application is likely to accelerate this process.
Schnorr this allows multiple signatures to be merged into a single valid signature, by just summing the keys of the inputs. In a performance analysis, Schnorr is slightly faster than ECDSA, but it provides several significant performance improvements. A major advantage is that each of the input signatures do not need to be checked, as only the overall signature is checked. The output also provides a signature of the same size, no matter the number of users who provide their inputs. Another advantage is that this reduction in data will improve the capacity of the Bitcoin infrastructure.
For privacy, Schnorr’s method the transaction signatures will not be observable, and thus user privacy will be preserved. All that will be available is an overall signature for aggregated transactions. For many participants, it will not be possible to determine which of them was actually responsible for a transaction.
I have produced a demo here.
Fixing the cancellation problem
A current challenge is related to the cancellation problem, and where a group of users could possibly create a validate transaction signature from the summation of their keys.
For example, if we have two public keys (K1 and K2). Normally they would advertise their keys as K1 and K2, but an adversary then maliciously advertises the keys as K2-K1 and K1. When summated we get the key of the adversary (K2) — see the diagram below. Now the funds which are sent to this joint public key will be associated to the owner of the K2 key (and the owner of the K1 key will not know about the transaction). The two key process is defined as a 2-of-2 multisig. The solution is now to multiple all of the keys when the summation of the keys is created, and then taking a hash of it. The transactions can then be signed.
It is likely that Schnorr’s signatures could be used in OP_CHECKSIG (which checks the ECDSA signature on a transaction against the public key) and OP_CHECKMULTISIG. With spend request with multiple signatures, the Bitcoin networks are currently required to call OP_CHECKMULTISIG, and this would be replaced by a signal call to OP_CHECKSIG (and thus improving privacy). Thus for a spend where n-of-m signatures are required to authorize a signature, OP_CHECKMULTISIG checks all of the public keys and their signatures (for up to n signatures), but now it can be checked by a single signature (and which combines all of the associated public keys).
A hard fork?
But, I hear you say, “How can you just change over, surely you will need to create a hard fork of the Blockchain?”. Well with Segregated Witness (SegWit), we move all the signature data for the blockchain to a separate part of the transaction (“the witness”), and not embedding it into the transaction. This only required a soft fork of the blockchain.
SegWit went into operation with a soft fork on 21 July 2017 — with miners adding the software upgrade named Bitcoin Improvement Proposal (BIP) 91. It first operation was on 23 August 2017, and appeared in Block 477,120:
Conclusion
As Bitcoin grows, we find new ways of fixing its core problems, and at each stage, we allow it to scale, where improving security.