The Schnorr signature method supports the merging of public keys to produce a single public key to check the signature of a transaction [Schnorr aggregate]. Unfortunately it is not secure and suffers from the cancellation problem. As a more secure method we can use the MuSig method [1]. We will simplify the method in order to illustrate how it works. We will use NIST P-256 for the key generation, and the curve.
Using the MuSig signature method to aggregate signers (P-256) |
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\)
We compute:
\(L=H(X_1 || X_2)\)
Now we can merge their public keys (\(X\)) to give:
\(X = H(L || X_1) X_1 + H(L || X_2) 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 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 || R || msg) H(L,X_1) x_1\)
and where \(H(X || R || msg)\) is a hash of the merged public key (\(X\)), \(R\) and the message. Alice computes her value of:
\(s_2 = r_2+H(X || R || msg) H(L,X_2) 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 || R || M) X\)
If the two values match, the merged signature has been proven.
Code
The code used is:
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:
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!
References
[1] Maxwell, G., Poelstra, A., Seurin, Y., & Wuille, P. (2019). Simple schnorr multi-signatures with applications to bitcoin. Designs, Codes and Cryptography, 87(9), 2139-2164. [paper]