The Schnorr signature method supports the merging of public keys to produce a single public key to check the signature of a transaction. We will simplify the method in order to illustrate how it works. We will use secp256k1 for the key generation, and the curve. Unfortunately the Schnorr method is insecure, but can be enhanced with [MuSig].
Using the Schnorr signature method to aggregate signers (secp256k1) |
Theory
To sign a message, Bob takes his private key, a random value (\(r_i\)) and a message (\(msg\)), and produces a signature: (\(R,s\)). Initially Bob generates a private key of \(x_1\) and a public key of:
\(X_1 = x_1 G\)
and where \(G\) is the base point on the curve. Alice will generate her private key (\(x_2\)) and a public key of:
\(X_2 = x_2 G\)
Now we can merge their public keys (\(X\)) to give:
\(X = X_1 + X_2\)
For Bob's signature, he generates a random value \(r_1\) and computes a point on the curve of:
\(R_1 = r_1 G\)
and Alice computesand computes a point on the curve of:
\(R_2 = r_2 G\)
We can then merge these values to get \(R\) with:
\(R = R_1 + R_2\)
Bob computes an \(s\) value of:
\(s_1 = r_1+H(X || msg) x_1\)
and where \(H(X || msg)\) is a hash of the merged public key (\(X\)) and the message. Alice computes her value of:
\(s_2 = r_2+H(X || msg) x_2\)
We can then merge \(s_1\) and \(s_2\) to give:
\(s = s_1 + s_2\)
The merged signature of the message is the (\(R,s\)). To check we compute:
\(v_1=sG\)
\(v_2=R+H(X || M) X\)
If the two values match, the merged signature has been proven.
This works because \(sG = (s_1 + s_2) G = (r_2+H(X || msg) x_1 + r_2+H(X || msg) x_2) G = (r_1+r_2) G + H(X || msg) (x_1 + x_2) G = rG + H(X || msg) X = R+H(X || M) X\)
Code
The code used is:
import hashlib from ecpy.keys import ECPublicKey, ECPrivateKey from ecpy.curves import Curve import secrets import sys print ("Schnorr with secp256k1") curve = Curve.get_curve('secp256k1') x1 = ECPrivateKey(secrets.randbits(32*8), curve) X1 = x1.get_public_key() x2 = ECPrivateKey(secrets.randbits(32*8), curve) X2 = x2.get_public_key() msg = 'Hello' if (len(sys.argv)>1): msg=str(sys.argv[1]) print("Message: ",msg) msg=msg.encode() 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) X = ECPublicKey(X1.W+X2.W) hasher=hashlib.sha256() 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') s1 = (r1.d+H*x1.d)% curve.order s2 = (r2.d+H*x2.d)% curve.order s=(s1+s2) % curve.order v1 = s * curve.generator v2 = R.W + H*X.W 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.W.x},{X.W.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:
Schnorr with NIST P-256 Message: Hello Bob Private key (x1) = 106845362583985020054903306033834870233127847329445482955853733185703498467930 Bob Public key (X1) = (108850805131909999653962539019941416455063507729008368830201603194889370037069,63860899170722904600169709630176780543373441430279215078029829753650834388433) Alice Private key (x2) = 72261135823387549290070942746942676681134083835832805048072332754162376491325 Bob Public key (X2) = (86830578128013360615411914972906975245363901188663711370367420184129444271257,65229405188415618342771011262407379032784006010207317586930245530635329511837) Merged Public key (X) = (81896342855807749757524301193503930162797532117174173396121303757060543881980,65945161807122072819279674341584565737335309478478410033575403769642190314665) Bob s1 =34350450799518316374301784996428393495182913975852174621567378094009080754768 Alice s2 =63034502782467967743143665588985804527901815755867434152463367099622224001732 Merged s =97384953581986284117445450585414198023084729731719608774030745193631304756500 Merged R =104095141705636762283402378026445635383407564023610492441348593673734110639644 sG=(0xdb8d6f446c4d79fd69f68a19275eea5364a4ee910140e7238000c2ba3819c01a , 0x97e6aaeb49f33369ab18992105b6900605851f8729372e817e172c06fc6afe51) R+H(X || M) X =(0xdb8d6f446c4d79fd69f68a19275eea5364a4ee910140e7238000c2ba3819c01a , 0x97e6aaeb49f33369ab18992105b6900605851f8729372e817e172c06fc6afe51) Verified!