This page implements the Schnorr signature, and uses Node.js. We will generate a signature, and then recover the public key from the signature and the message. The Schnorr signature is used within the Bitcoin network [theory]. With the Schnorr signature, we create a signature (R,s) for a hash of the message (h). We first generate a private key (\(x\)) and then derive the public key from a point on the elliptic curve (\(G\)) [Multi sig].
Node.js for Schnorr signature |
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"):
Message:Hello Private Key: dce71358bf6d57dffaf8ac422ea972dca65badd2ce21b585803ea3075b7de388 Public key: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27 Signature [s]: BN: 18573f5212373b51022b00cbe12276b8099a351526b3384ccd1f02ad71761ff1 Signature [r]: BN: 3d96504afbe3beec97a753c38d614ec5fa68cf8219df36d7cce891319058d5db Public key recover: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27 Signature verified: true
In this case we have 256-bit private key (dce7 ... 388), and produce a 512-bit public key (03 96e ... 827) - the "03" part identifies that we are using a Bitcoin public key. Thus, if we know the message - and which will be stored on the blockchain in the case of Bitcoin - and the key, we can see that we can recover the public key from the signature.
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] 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("\nSignature [r]:",sig1.r); const rtn=schnorr.verify(msg, sig, pub); const mypub=schnorr.recover(sig, msg) console.log("\nPublic key recover:",mypub); console.log("\nSignature verified:",rtn); });
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