Goodbye To Multiple Wet Signatures on Documents … and Hello To A More Trusted and Verifiable World

Goodbye To Multiple Wet Signatures on Documents … and Hello To A More Trusted and Verifiable World

Here is a message for the future:

We are two million citizens, and we believe that the government should eradicate poverty within our villages, towns and cities.

-- Signed:
[s]:3a0ae4e78cde038b3ff368c0d5739ed4bcec1354ecdf81cc089ae6f48ccd3737

[r]:964b5691268baccd780302266b38984649920276af8bf4c4ecfb6190f073b16

This signature would include the verified identity of the two million citizens who had signed the message.

What a crazy 19th Century world we live in, and where we add our wet signatures to co-sign documents? It might be for an application for a loan where the company directors need to sign the last page of the loan agreement. The validity of the document is that each director signs the last page with a scribble. In the 21st Century, how can this even have any legal standing? Unbelievably, I see GIF signatures pasted into PDF documents for legal documents and then being seen as being acceptable for a signature on a document.

And so with digital signatures we can each sign with our private key, and which will verify both what we are signing and our identity. Our public key is then used to prove our identity. But each party will then sign their own document, and we thus end up with a whole lot of signed documents, and where we would have to check the signature on each one against the public key of each party. So how do we allow the directors to get together, and to sign the whole document with a single signature, and where none of the directors can fake any other signature?

Meet the wonderful Schnorr method …

Meet Schnorr

Every so often, a research paper arrives and it just takes your breath away and changes your thinking on things. For me the most recent example of this is [here]:

In the paper, the authors define how the Schnorr signature method can be used to take a number of public keys and merge them together into a single signature. They have a magical way of making sure that no party in the signing can fake any other party.

The scope of this work provides another piece of the puzzle in creating a new trusted world, and it has been almost immediately adopted within the Bitcoin network (in order to address the scaling problem). But it’s scope is much greater than in cryptocurrency scaling, as it provides a new way of bringing together signatures, without those involved having to each produce their own signature for a transaction.

So let’s say that million people want to sign a petition for a new Blockchain Act in Europe. In the traditional way, they would each view the petition, and then sign it with their private key. In this way we would end up with a million signatures, and we would have to store all the signers.

But let’s say they all get together and agree to sign the petition. They would thus all have public keys (Xi). In the Schnorr method each of the signers will then generate a random number (ri), and then communicate it to the rest of the signing group with (where g is a generator value):

Ri = g ^{ri}

Each signer then communicates their random value as a public value (Ri), along with their public key (Xi), to the rest of the signing group.

Each signer can then compute R as the multiplication of all the Ri values. They will also compute X which is the multiplication of all the public keys of the group. All of these operations are with the mod of p (a shared prime number). Next, they compute c for a message (M):

c = Hash (R,X,M)

Each party computes their own si value:

si = ri + c xi

and shares it. The signature element(s) is then the summation of all the si values.

The signature then becomes (R,s). To check the signature, we take g and raise to the power of s, and then take R and multiply it by X to the power of c:

g^{s} = R X^{c}

If they are the same — due to the magic of logarithms (which John Napier invented) — the signature checks.

Magic!!!!!!! We can now have consensus politics, where groups can come together and sign for things, and then everyone can openly check the signers with a single signature. If we scale it up — for open voting systems — we could have a way to tally all the votes for something, and then openly show where the votes have come from, with a single result … and no more crosses on a ballet paper.

Example

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.

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 al, 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 with 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).

Conclusion

And there you go! Why do we create documents with wet signatures that we all co-sign? With the Schnorr method we can now all agree to sign something, and share our public key and a random value, and then we can compute a signature on a document that shows that we have all contributed to the signatures. Magic!