Schnorr Signatures … How To Sign and Merge Public Keys (with Multiple Signers)
Schnorr Signatures … How To Sign and Merge Public Keys (with Multiple Signers)
In Feb 1989, Claus Schnorr submitted a patent which was assigned to no one. It has 11 claims, and allowed digital signatures to be merged for multiple signers [here]:
This method has the great advantage that we can have multiple signers to a message or a transaction, and end up with a single signature for all the signers. It is now being used in Bitcoin transactions so that we have an efficient signature for a transaction that involves multiple entities.
The signature
With the Schnorr signature, we create a signature (R,s) for a hash of the message (m). Initially, Peggy (the prover) has a private key r, and her public key will then be:
U=r×G
and where G is the base point on the curve. She then generates random nonce (r_t) for the signing of a message and defines a commitment to this value:
U_t=r_t×G
Next, with a message (m), she computes a challenge (c) with a hash function of:
c=H(m,U_t)
Next, Peggy computes:
r_z=r_t+c×r
Peggy then sends U_t (R) and r_z (s) to Victor (the verifier). Victor then determines if:
r_z×G=U_t+c×U
If they are the same, Peggy has proven that she that the private key that has signed the message. This works because:
r_z×G=(r_t+c×r)×G=r_t×G+(c×r)×G = U_t+c×U
The code used is [here]:
iimport hashlib
from ecpy.keys import ECPublicKey, ECPrivateKey
from ecpy.curves import Curve
import secrets
import sys
msg = 'Hello'
if (len(sys.argv)>1):
msg=str(sys.argv[1])
print("Message: ",msg)
msg=msg.encode()print ("MuSig with NIST P-256")
curve = Curve.get_curve('NIST-P256')
x1 = ECPrivateKey(secrets.randbits(32*8), curve)
X1 = x1.get_public_key()x2 = ECPrivateKey(secrets.randbits(32*8), curve)
X2 = x2.get_public_key()
r1 = ECPrivateKey(secrets.randbits(32*8), curve)
R1 = r1.get_public_key()
r2 = ECPrivateKey(secrets.randbits(32*8), curve)
R2 = r2.get_public_key()
R = ECPublicKey(R1.W + R2.W)
hasher=hashlib.sha256()
hasher.update(X1.W.x.to_bytes(32,'big') + X2.W.x.to_bytes(32,'big') )
L = hasher.digest()
# L = int.from_bytes(L,'big')
hasher=hashlib.sha256()
hasher.update(L + X1.W.x.to_bytes(32,'big') )
h = hasher.digest()
h = int.from_bytes(h,'big')
H1 = h
hasher=hashlib.sha256()
hasher.update(L + X2.W.x.to_bytes(32,'big') )
H2 = hasher.digest()
H2 = int.from_bytes(H2,'big')
H2 = h
X = ECPublicKey(X1.W+X2.W)
hasher.update(X.W.x.to_bytes(32,'big') + R.W.x.to_bytes(32,'big') + msg )
h = hasher.digest()
h = int.from_bytes(h,'big')
hXRm = h
X = H1 * X1.W + H2*X2.W
s1 = (r1.d+hXRm*H1*x1.d)% curve.order
s2 = (r2.d+hXRm*H2*x2.d)% curve.order
s=(s1+s2) % curve.order
v1 = s * curve.generator
v2 = R.W + hXRm*X
print (f"\nBob Private key (x1) = {x1.d}")
print (f"Bob Public key (X1) = ({X1.W.x},{X1.W.y})")
print (f"\nAlice Private key (x2) = {x2.d}")
print (f"Bob Public key (X2) = ({X2.W.x},{X2.W.y})")
print (f"\nMerged Public key (X) = ({X.x},{X.y})")print (f"\nBob s1 ={s1}")
print (f"Alice s2 ={s2}")
print (f"Merged s ={s}")
print (f"Merged R ={R.W.x}")print (f"\nsG={v1}")
print (f"R+H(X || M) X ={v2}")if (v1==v2):
print ("\nVerified!")
A sample run [here]:
Message: Hello
Schnorr with NIST P-256
Bob Private key (x1) = 92015617463991137548442365686753778952956999287034740088259055343049380032874
Message: Hello
Schnorr with NIST P-256
Bob Private key (x1) = 34688108133271887290701325063206608488061193406835640861168477320782977287964
Bob Public key (X1) = (109326020439392423026677926849255570629664720095786679699474236921522678675657,63676419430583299176121403301322148480638989503859763307216258413616644055254)
Alice Private key (x2) = 47525787867773303746613761912813089499036351595165669361066751526718285419407
Bob Public key (X2) = (57936753566143626402936689917919407346772474428158197284657786782549759913616,110382238360766458580266756133202986890049218247476191133297912560798771121480)
Merged Public key (X) = (67775994906596065959668663182301553414016994563661824208494767726110916424461,460214041753869314359071314478602160770393531239137834499698176980896028479)
Bob s1 =46695673382372859752331622900912175881166025910861635751904476209596366944080
Alice s2 =70917710493303404255272957422367235491305819325485817389173964965383243610854
Merged s =1821294665320015244907133373871837842474890012211692798656182113911098510565
Merged R =13745967387972357972061400169713280564003104406131320785799559075540675315655
sG=(0xd637aa261a815b0e42e0a53b7be06fc058b1cb49cd720e7222ad7fb8228e2e2a , 0xaa4f216191ea899ad64161bb9ceb2b194d81f5d8cffe0241bf5610ee5a88657d)
R+H(X || R || m) X =(0xd637aa261a815b0e42e0a53b7be06fc058b1cb49cd720e7222ad7fb8228e2e2a , 0xaa4f216191ea899ad64161bb9ceb2b194d81f5d8cffe0241bf5610ee5a88657d)
Verified!
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:
Conclusions
And so the Schnorr signature is so simple, but it failed to make a major impact because it was patented. As it is now out of patent, it is now being applied in my areas. Here’s my Schnorr signature examples: