Merging Public Keys — Aggregated Signing with Schnorr

We live in a fake digital world, and where we have basically scaled wet signatures into a digital work with scribbles on an electronic…

Merging Public Keys — Aggregated Signing with Schnorr

We live in a fake digital world, and where we have basically scaled wet signatures into a digital world with scribbles on an electronic document. The most trusted method is to sign for a message with a private key and to prove with the associated public key. But what happens when we have many signers, we would have to add the signature for each person on the document and provide each of their public keys. This might take some time to check. So can we merge the signatures into one signature, and also merge the public keys, so that someone can check the merged signature against the merged public keys? Well, yes, we can … with the Schnorr signature method. So, let’s take a simple example, and show how it can work.

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 to give:

X=X_1+X_2

For Bob’s signature, he generates a random value r_1 and computes:

R_1=r_1 G

and Alice computes:

R_2=r_2 G

We can then merge these values 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

This works because:

sG=(s_1+s_2)G=(r_2+H(X||msg) x_1+r2+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

The code used is [here]:

import hashlib
from ecpy.keys       import ECPublicKey, ECPrivateKey
from ecpy.curves import Curve
import secrets

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 = b'Hello'

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)

xX = (X.W.x).to_bytes(32,'big') 
hasher=hashlib.sha256()
hasher.update(xX+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"Bob Private key (x1)={x1.d}")
print (f"Bob Public key (X1)=({X1.W.x},{X1.W.y})")
print (f"Alice Private key (x2)={x2.d}")
print (f"Bob Public key (X2)=({X2.W.x},{X2.W.y})")
print (f"Merged 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 ("Verified!")

A sample run [here]:

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!

The code is here:

schnorr_sign
A Python repl by billbuchananreplit.com

If the two values match, the merged signature has been proven.