With the Schnorr signature scheme we can merge public keys together to create a single signature [Multi sig].
Merging Public Keys in Schnorr signatures |
Theory
Signatures are at the core of our world of trust. For centuries we have used them as a legal way of proving our identity and our confirmation of something.
But, in this modern world, our usage of wet signatures is flawed, and have very little credibility. Few of us have to sign for things these days, and thus our signature is often difficult to properly verify. Along with this we often just sign the last page of a document, and where a malicious entity could replace all the other pages. Wet signatures, too, are often scanned and added to documents as GIF files, and then converted into PDF format. All these methods have virtually zero credibility.
In a digital age, we thus need to move to methods which are almost 100% certain, and where we create signatures which cannot be forged, and which validate that the contents of a message/document have not been changed. For this we need digital signatures, and one of the most widely used methods is based on elliptic curve cryptography (ECC): ECDSA.
With ECDSA we create a public and a private key, and then sign a message with the private key, and where the public key is then used to check the validity of the signature. For this we generate a private key, and then, through ECDSA, we can produce the associated public key:
In this way, the Bitcoin infrastructure knows that the person with the correct private key has signed the transaction.
But what happens if two or more people sign a document? Can we produce a single signature for them, so that they both bring their signatures together to sign a document?
Let's say two people want to purchase a new car. How do we create a single signature that proves that it has been signed by both people? Also, how can we make sure that if we get them to sign the same document, that the signature is not the same? Well, that is where the Schnorr signature method comes in, and where we can aggregate signers into a single signature.
With the Schnorr signature, we create a signature \((R,s)\) for a hash of the message (\(M\)). We first generate a private key (\(x\)) and then derive the public key from a point on the elliptic curve (\(G\)) to get:
\(P = x \cdot{G}\)
Next we select a random value (\(k\)) to get a signature value of \(R\):
\(R = k \cdot{G}\)
The value of \(s\) is then:
\(s= k - \text{Hash}(M,R)\cdot{x}\)
Our signature of \(M\) is \((s,R)\) and the public key is \(P\).
To check the signature we calculate
\(P \cdot \text{Hash}(M,R) + s \cdot{G}\)
This becomes \(x \cdot{G} \cdot \text{Hash}(M,R) + (k - \text{Hash}(M,R) \cdot{x})\cdot{G}\).
which is:
\(x \cdot{G} \cdot \text{Hash}(M,R) + k \cdot{G} - \text{Hash}(M,R) \cdot x \cdot G = k \cdot G\)
The value of \(k \cdot{G}\) is equal to \(R\), and so if the result is the same as \(R\), the signature checks out.
A sample run with the message of "Hello" is (and where "BN" is "Big Number") and where we merge the public keys together, and where the signature still checks to be valid:
--Signature 1--- --Signature 1--- Message:Hello Private Key: 74014dec35a33f8b09e7d1fc4f4fdba19de6a498c8bd9daed43eb3d73f99deb7 Public key: Buffer 03 b4 cd 8a 35 00 d5 cb 6f 0a a9 98 83 0b fe 83 b3 4e b9 a9 ab ea 06 ab f5 cb e7 90 4b fd 33 4d 19 Signature1 [s]: BN: 501d0bd1acbea82481d20767e556ffafd496e82d3a41653eb254361e74507c1f B Signature1 [r]: BN: e22a81f9ca8689aadc26387a9d766ae9e86752dc8546e7274475bf317962e722 --Signature 2--- Message:Hello Private Key: 209632ee8f758dbd9bd78ca10d782a7e63c17fa0296ef34183bb5fd0a346e86e Public key: Buffer 02 e2 6b 45 25 f6 81 6e 97 26 89 9e 1c 96 93 aa ad 78 41 31 f4 d5 9e c5 19 bc 10 e1 c7 40 c7 28 a7 Signature2 [s]: BN: 97efdec94c288dcbd552ca1738a193554e3098c055267f4ed68936d3804eba87 Signature2 [r]: BN: ca20518c2305c4148f0649931340c27c570c4be562fb00a0d2c48a084509a14d --Combined key--- Combined Public key: Buffer 02 3e 41 f2 e2 8e 57 ce 12 6a 78 21 43 39 ca 1a fd 20 b4 9a d2 7c 2a 5e fa fe f2 6a f4 e6 a5 4d c4 Merged Signature verified: true -----
The following is the code [code]:
'use strict'; const assert = require('./util/assert'); const secp256k1 = require('bcrypto/lib/secp256k1'); const hash256 = require('bcrypto/lib/hash256'); const schnorr = require('../'); const Signature = require('bcrypto/vendor/elliptic/lib/elliptic/ec/signature'); describe('Schnorr', function() { let LAST_PARAM = process.argv[process.argv.length-1] let PARAM_NAME = LAST_PARAM.split("=")[0].replace("--","") let m = LAST_PARAM.split("=")[1] console.log("\n--Signature 1---"); const key = secp256k1.privateKeyGenerate(); const pub = secp256k1.publicKeyCreate(key, true); const msg = hash256.digest(Buffer.from(m, 'ascii')); const sig = schnorr.sign(msg, key); const sig1 = new Signature(sig); console.log("Message:"+m); console.log("Private Key:",key.toString('hex')); console.log("Public key:",pub); console.log("\nSignature1 [s]:",sig1.s); console.log("\nSignature1 [r]:",sig1.r); console.log("\n--Signature 2---"); const key2 = secp256k1.privateKeyGenerate(); const pub2 = secp256k1.publicKeyCreate(key2, true); const sig2 = schnorr.sign(msg, key2); const sig21 = new Signature(sig2); console.log("Message:"+m); console.log("Private Key:",key2.toString('hex')); console.log("Public key:",pub2); console.log("\nSignature2 [s]:",sig21.s); console.log("\nSignature2 [r]:",sig21.r); var pub3 = []; pub3.push(pub); pub3.push(pub2); const pub4 = schnorr.combineKeys(pub3); console.log("\nCombined Public key:",pub4); const rtn=schnorr.verify(msg, sig, pub); console.log("\nMerged Signature verified:",rtn); console.log("\n-----"); });
The schnorr.js file is:
/*! * schnorr.js - schnorr signatures for bcoin * Copyright (c) 2014-2017, Christopher Jeffrey (MIT License). * https://github.com/bcoin-org/bcoin */ 'use strict'; const assert = require('bsert'); const elliptic = require('bcrypto/vendor/elliptic'); const Signature = require('bcrypto/vendor/elliptic/lib/elliptic/ec/signature'); const BN = require('bcrypto/lib/bn.js'); const DRBG = require('bcrypto/lib/drbg'); const sha256 = require('bcrypto/lib/sha256'); const curve = elliptic.ec('secp256k1').curve; const POOL64 = Buffer.allocUnsafe(64); const schnorr = exports; /** * Hash (r | M). * @param {Buffer} msg * @param {BN} r * @returns {Buffer} */ schnorr.hash = function hash(msg, r) { const R = r.toArrayLike(Buffer, 'be', 32); const B = POOL64; R.copy(B, 0); msg.copy(B, 32); return new BN(sha256.digest(B)); }; /** * Sign message. * @private * @param {Buffer} msg * @param {BN} priv * @param {BN} k * @param {Buffer} pn * @returns {Signature|null} */ schnorr.trySign = function trySign(msg, prv, k, pn) { if (prv.isZero()) throw new Error('Bad private key.'); if (prv.gte(curve.n)) throw new Error('Bad private key.'); if (k.isZero()) return null; if (k.gte(curve.n)) return null; let r = curve.g.mul(k); if (pn) r = r.add(pn); if (r.y.isOdd()) { k = k.umod(curve.n); k = curve.n.sub(k); } const h = schnorr.hash(msg, r.getX()); if (h.isZero()) return null; if (h.gte(curve.n)) return null; let s = h.imul(prv); s = k.isub(s); s = s.umod(curve.n); if (s.isZero()) return null; return new Signature({ r: r.getX(), s: s }); }; /** * Sign message. * @param {Buffer} msg * @param {Buffer} key * @param {Buffer} pubNonce * @returns {Signature} */ schnorr.sign = function sign(msg, key, pubNonce) { const prv = new BN(key); const drbg = schnorr.drbg(msg, key, pubNonce); const len = curve.n.byteLength(); let pn; if (pubNonce) pn = curve.decodePoint(pubNonce); let sig; while (!sig) { const k = new BN(drbg.generate(len)); sig = schnorr.trySign(msg, prv, k, pn); } return sig; }; /** * Verify signature. * @param {Buffer} msg * @param {Buffer} signature * @param {Buffer} key * @returns {Buffer} */ schnorr.verify = function verify(msg, signature, key) { const sig = new Signature(signature); const h = schnorr.hash(msg, sig.r); if (h.gte(curve.n)) throw new Error('Invalid hash.'); if (h.isZero()) throw new Error('Invalid hash.'); if (sig.s.gte(curve.n)) throw new Error('Invalid S value.'); if (sig.r.gt(curve.p)) throw new Error('Invalid R value.'); const k = curve.decodePoint(key); const l = k.mul(h); const r = curve.g.mul(sig.s); const rl = l.add(r); if (rl.y.isOdd()) throw new Error('Odd R value.'); return rl.getX().eq(sig.r); }; /** * Recover public key. * @param {Buffer} msg * @param {Buffer} signature * @returns {Buffer} */ schnorr.recover = function recover(signature, msg) { const sig = new Signature(signature); const h = schnorr.hash(msg, sig.r); if (h.gte(curve.n)) throw new Error('Invalid hash.'); if (h.isZero()) throw new Error('Invalid hash.'); if (sig.s.gte(curve.n)) throw new Error('Invalid S value.'); if (sig.r.gt(curve.p)) throw new Error('Invalid R value.'); let hinv = h.invm(curve.n); hinv = hinv.umod(curve.n); let s = sig.s; s = curve.n.sub(s); s = s.umod(curve.n); s = s.imul(hinv); s = s.umod(curve.n); const R = curve.pointFromX(sig.r, false); let l = R.mul(hinv); let r = curve.g.mul(s); const k = l.add(r); l = k.mul(h); r = curve.g.mul(sig.s); const rl = l.add(r); if (rl.y.isOdd()) throw new Error('Odd R value.'); if (!rl.getX().eq(sig.r)) throw new Error('Could not recover pubkey.'); return Buffer.from(k.encode('array', true)); }; /** * Combine signatures. * @param {Buffer[]} sigs * @returns {Signature} */ schnorr.combineSigs = function combineSigs(sigs) { let s = new BN(0); let r, last; for (let i = 0; i < sigs.length; i++) { const sig = new Signature(sigs[i]); if (sig.s.isZero()) throw new Error('Bad S value.'); if (sig.s.gte(curve.n)) throw new Error('Bad S value.'); if (!r) r = sig.r; if (last && !last.r.eq(sig.r)) throw new Error('Bad signature combination.'); s = s.iadd(sig.s); s = s.umod(curve.n); last = sig; } if (s.isZero()) throw new Error('Bad combined signature.'); return new Signature({ r: r, s: s }); }; /** * Combine public keys. * @param {Buffer[]} keys * @returns {Buffer} */ schnorr.combineKeys = function combineKeys(keys) { if (keys.length === 0) throw new Error(); if (keys.length === 1) return keys[0]; let point = curve.decodePoint(keys[0]); for (let i = 1; i < keys.length; i++) { const key = curve.decodePoint(keys[i]); point = point.add(key); } return Buffer.from(point.encode('array', true)); }; /** * Partially sign. * @param {Buffer} msg * @param {Buffer} priv * @param {Buffer} privNonce * @param {Buffer} pubNonce * @returns {Buffer} */ schnorr.partialSign = function partialSign(msg, priv, privNonce, pubNonce) { const prv = new BN(priv); const k = new BN(privNonce); const pn = curve.decodePoint(pubNonce); const sig = schnorr.trySign(msg, prv, k, pn); if (!sig) throw new Error('Bad K value.'); return sig; }; /** * Schnorr personalization string. * @const {Buffer} */ schnorr.alg = Buffer.from('Schnorr+SHA256 ', 'ascii'); /** * Instantiate an HMAC-DRBG. * @param {Buffer} msg * @param {Buffer} priv * @param {Buffer} data * @returns {DRBG} */ schnorr.drbg = function drbg(msg, priv, data) { const pers = Buffer.allocUnsafe(48); pers.fill(0); if (data) { assert(data.length === 32); data.copy(pers, 0); } schnorr.alg.copy(pers, 32); return new DRBG(sha256, priv, msg, pers); }; /** * Generate pub+priv nonce pair. * @param {Buffer} msg * @param {Buffer} priv * @param {Buffer} data * @returns {Buffer} */ schnorr.generateNoncePair = function generateNoncePair(msg, priv, data) { const drbg = schnorr.drbg(msg, priv, data); const len = curve.n.byteLength(); let k = null; for (;;) { k = new BN(drbg.generate(len)); if (k.isZero()) continue; if (k.gte(curve.n)) continue; break; } return Buffer.from(curve.g.mul(k).encode('array', true)); };
To implement this we install the following:
npm install bcrypto npm install secp256k1 npm install hash256