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 BN 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.
Bellare-Neven (BN) multi-signature scheme 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 then compute the hash of all the public keys involved:
\(L=H(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 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 || X_1 || R || msg) x_1\)
and where \(H(X || X_1 || 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 || X_2 || R || 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(L || X_1 || R || M) X_1 + H(L || X_2 || R || M) X_2 \)
If the two values match, the merged signature has been proven.
Code
The code used is:
import 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 ("BN 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() hasher=hashlib.sha256() hasher.update(L + X1.W.x.to_bytes(32,'big') +R.W.x.to_bytes(32,'big') + msg) h = hasher.digest() h = int.from_bytes(h,'big') H1 = h hasher=hashlib.sha256() hasher.update(L + X2.W.x.to_bytes(32,'big') +R.W.x.to_bytes(32,'big') + msg) h = hasher.digest() h = int.from_bytes(h,'big') H2 = h # si = ri + H(L,Xi,R,m)xi s1 = (r1.d+H1*x1.d)% curve.order s2 = (r2.d+H2*x2.d)% curve.order s=(s1+s2) % curve.order # sG = R + H(L,X1,R,m)X1 + H(L,X2,R,m)X2 + ... v1 = s * curve.generator v2 = R.W + H1*X1.W + H2*X2.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"\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 BN with NIST P-256 Bob Private key (x1) = 462120788799923564447829271909662496086207634262627810760054925865813576716 Bob Public key (X1) = (40235184919608415225604262248995783664938969420966882261119625569503186180891,29962648730796713463805521723492334715342479607527342802002285125168885433079) Alice Private key (x2) = 110921558973028998945223046881828921954228139493473821575353318227414547336099 Bob Public key (X2) = (92996928295234219084742643225523846572086057607360033040836868527658293840325,49629787472834635994935210252019488113657888410793576939796497728525668673760) Bob s1 =97450526126185614740512555982713378183843166089451454947623361147979391042464 Alice s2 =95541569019641104158904339107633223112562683610616971347561006193678702849983 Merged s =77200005935470470136719448140939027766408894475932665952762108280589581848078 Merged R =24089476977508910549351169991279131233329755604840086432916785722042811018889 sG=(0xc68f8c72364c3dc53c8eaa60773d090b3d97005725dd403ea437f534991d6c74 , 0x7fbe33d97fce04563948aed5f0adc36fdeabc66dfda62371268e70ca390bbfe4) R+H(X || M) X =(0xc68f8c72364c3dc53c8eaa60773d090b3d97005725dd403ea437f534991d6c74 , 0x7fbe33d97fce04563948aed5f0adc36fdeabc66dfda62371268e70ca390bbfe4) Verified!
Reference
[1] Bellare, M., & Neven, G. (2006, October). Multi-signatures in the plain public-key model and a general forking lemma. In Proceedings of the 13th ACM conference on Computer and communications security (pp. 390-399). [paper]