Wet Signatures and the Wonderful World of Schnorr …
Wet Signatures and the Wonderful World of Schnorr …
Signatures are at the core of our world of trust. For centuries we have used them as a legal way of proving our identity and in confirming our approval of something:
But, in this modern world, our usage of wet signatures is flawed, and have very little credibility. Few of us have to sign for things these days, and thus our signature is often difficult to properly verify. Along with this we often just sign the last page of a document, and where a malicious entity could replace all the other pages. Wet signatures, too, are often scanned and added to documents as GIF files, and then converted into PDF format. All these methods have virtually zero credibility.
In a digital age, we thus need to move to methods which are almost 100% certain, and where we create signatures which cannot be forged, and which validate that the contents of a message/document have not been changed. For this we need digital signatures, and one of the most widely used methods is based on elliptic curve cryptography (ECC): ECDSA.
With ECDSA we create a public and a private key, and then sign a message with the private key, and where the public key is then used to check the validity of the signature. For this we generate a private key, and then, through ECDSA, we can produce the associated public key [demo]:
In this way, the Bitcoin infrastructure knows that the person with the correct private key has signed the transaction.
But what happens if two or more people sign a document? Can we produce a single signature for them, so that they both bring their signatures together to sign a document?
Let’s say two people want to purchase a new car. How do we create a single signature that proves that it has been signed by both people? Also, how can we make sure that if we get them to sign the same document, that the signature is not the same? Well, that is where the Schnorr signature — created by Claus P. Schnorr — method comes in, and where we can aggregate signers into a single signature.
Schnorr signatures
With the Schnorr signature, we create a signature (R,s) for a hash of the message (MM). We first generate a private key (x) and then derive the public key from a point on the elliptic curve (G) to get:
P=x⋅G
Next we select a random value (k) to get a signature value of R:
R=k⋅G
The value of s is then:
s=k−Hash(M,R)⋅x
Our signature of M is (s,R) and the public key is P.
To check the signature we calculate
P⋅Hash(M,R)+s⋅G
This becomes x⋅G⋅Hash(M,R)+(k−Hash(M,R)⋅x)⋅G
which is:
x⋅G⋅Hash(M,R)+k⋅G−Hash(M,R)⋅x⋅G=k⋅G
The value of k⋅G is equal to R, and so if the result is the same as R, the signature checks out.
A sample run with the message of “Hello” is (and where “BN” is “Big Number”) [here]:
Message:Hello
Private Key: dce71358bf6d57dffaf8ac422ea972dca65badd2ce21b585803ea3075b7de388
Public key: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27
Signature [s]: BN: 18573f5212373b51022b00cbe12276b8099a351526b3384ccd1f02ad71761ff1
Signature [r]: BN: 3d96504afbe3beec97a753c38d614ec5fa68cf8219df36d7cce891319058d5db
Public key recover: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27
Signature verified: true
In this case we have 256-bit private key (dce7 … 388), and produce a 512-bit public key (03 96e … 827) — the “03” part identifies that we are using a Bitcoin public key. Thus, if we know the message — and which will be stored on the blockchain in the case of Bitcoin — and the key, we can see that we can recover the public key from the signature.
One of the great advantages of the Schnorr signature is that we can sign more than one message.
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 the 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.
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 does 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. Its 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. Some time — SOON! — we need to stop using wet signatures, and start using digital signatures. Only then will we have fully trusted digital world.