The Schnorr signature method supports the merging of public keys to produce a single public key to check the signature of a transaction. It is used in SegWit to merge the signing of a transaction when there are more than one entity involved in the signing of a transaction. 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. Unfortunately the Schnorr method is insecure, but can be enhanced with [MuSig].
Using the Schnorr 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\)
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 || R || msg) 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 || 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 || R || 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 ("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() 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:
Bob Private key (x1)=77664663271170673620859955297191590031376319879614890096024130175852238738811 Bob Public key (X1)=(33205537830004297592692536753355413074329944357110295722573247536271516935822,35483136673364573712870651862356470178263214412106298044693643820223301937730) Alice Private key (x2)=89652975980192045565381556847798492396888680198332589948144044069692575244768 Bob Public key (X2)=(52314700046169795516310440353338851009286062572492924893420199655225375861787,99793313461811331055651099539228298455982900893174782887849276728688663511712) Merged Public key (X)=(32613327160959090234870418219181319036134300010421572408703767372617237986232,29949965415621151489514605703018985826633388176626687073567624092314768490898) Bob s1 =58523287352995947054850445709978818827618082174260032457931753496146434317118 Alice s2 =100690230142653127584181783719578152773276887952842036291802185185816439770267 Merged s =43421428258332879215461244420869063748057405848027164367128775540444712593048 Merged R =109166185492410583958809418604462912426737872331257120441714047411046250916468 sG=(0xa7f6bbab82d106837f9294cc09ff5e97e313e3167c5e10fa80e7e629c60df39d , 0x3c5434a6b00ca920e99a4fca67c8df99c0e9fd045ac44bf170f55112381507cc) R+H(X || M) X =(0xa7f6bbab82d106837f9294cc09ff5e97e313e3167c5e10fa80e7e629c60df39d , 0x3c5434a6b00ca920e99a4fca67c8df99c0e9fd045ac44bf170f55112381507cc) Verified!