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
So how do Bob and Wendy sign a message for Alice? With the Schnorr signature method we can simply perform an add operation. With this, Bob will generate his private key (\(sk_1\)) and derive his public key from:
\(P_1=sk_1.G\)
He will then generate:
\(R_1=k_1.G\)
\(s_1=k_1+H(P || M || R).sk_1\)
and where \(H()\) is the hash of the associated byte values, and (\(P || M || R\)) is appended byte values from \(M\) and \(R\). The overall public key (\(P\)) will be computed by the adding of Bob and Wendy's public key. Wendy will generate her private key (\(sk_2\)) and derive her public key from:
\(P_2=sk_2.G\)
She will then generate:
\(R_2=k_2.G\)
\(s_2=k_2+H(P || M || R) . sk_2\)
and where the public key to sign the message will be:
\(P=P_1+P_2\)
Bob then sends the message (\(M\)) and the signature (\(R,s\)) to Alice. The signature becomes:
\(R=R_1 + R_2\)
\(s=s_1 + s_2\)
When Alice received the signature (\(R,s\)) and the message (\(M\)), she checks:
\(R+H(P || M || R).P = sG\)
If they are the same, the signature checks out.
Here is a doodle on the maths:
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!