MuSig: A Secure Method of Merging Public Keys with a Single Signature

The Schnorr signature method supports the merging of public keys to produce a single public key to check the signature of a transaction…
Photo by DocuSign on Unsplash

MuSig: A Secure Method of Merging Public Keys with a Single Signature

The Schnorr signature method supports the merging of public keys to produce a single signature for a transaction [Schnorr aggregate]. Unfortunately, it is not secure and suffers from the cancellation problem [here], but which can be overcome with the MuSig method or the BN Method [here]. In this article, we will simplify the method in order to illustrate how it works, and use just two signers (Bob and Alice). The MuSig method is outlined by Greg Maxwell et al in this paper [1][here]:

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 (and where X_1 is a point on the curve). Alice will generate her private key (x_2) and a public key of:

X_2=x_2 G

We compute the hash of the merged public keys with:

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:

R1=r_1 G

and Alice computes a point on the curve of:

R2=r_2 G

We can then merge these values to get R with:

R=R1+R2

Bob then computes an s value of:

s_1=r_1+H(X||R||msg) H(L || x1) x1

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 || x1) x2

We can then merge s_1 and s_2 to give:

s=s1+s2

The merged signature of the message is the (R,s). To check we compute the merged signature we compute:

v_1=sG

v_2=R+H(X||R||M)X

If the two values match, the merged signature has been proven. Note that only Bob can produce the correct value of s_1 (as he knows the private key of x_1), and only Alice can produce the correct value of s_2 (as he knows the private key of x_2).

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!

And there you go. If we had a transaction with many signers, we can merge these into a single signature, and then be able to check with the public keys of the entities involved.

Reference

[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 [here].