Boneh–Lynn–Shacham (BLS) signature method produces short signatures. They use elliptic curve pairing (and which are also known as bilinear maps):
BLS signatures and Crypto Pairing |
Background
The first main concept we need to understand is a pairing, and where we have two values (\(P\) and \(Q\)). A pairing (or bilinear map) is then defined as:
\(e(P,Q)\)
We must then find the method for \(e\) that is efficient, and for it to be bilinear it must conform to the following algebra operations:
\(a + b = b + a\)
\(a \times (b+c) = a \times b + a \times c\)
\((a \times c) + (b \times c) = (a + b) \times c\)
In our function we can operate in the same way:
\(e(P,Q+R) = e(P,Q) \times e(P,R)\))
\(e(P+S,Q) = e(P,Q) \times e(S,Q)\))
We can also swap \(\times\) for \(+\), and it should still work. We can try a pair with: \(e(x,y)=2^{xy}\), and use the values of \(x=5\) and \(y=6\):
\(e(5,6) = 2^{5 \times 6}=2^{30}\)
\(e(5,4+2) = e(5,4) \times e(5,2) = 2^{5 \times 4} \times 2^{5 \times 2}=2^{30}\)
Within pairing in elliptic curve, we take two points on a curve (or on different curves) as \(P\) and \(Q\). We then create a function (\(e\)) which returns a value:
\(e(P,Q) \rightarrow n\)
With pairing, we create a function where we can take a scalar value (\(x\)), and come up with the same result if we multiply the value by \(P\) or by \(Q\):
\(e(xP,Q) = e(P,xQ)\)
If we have two values (\(a\) and \(b\)) we can then create a function which makes these equivalent:
\(e(aP,bQ) = e(P,abQ) = e(abP,Q) = e(P,Q)^{ab}\)
Theory
We have migrated the ECDSA method of signing Bitcoin transactions as the method has been shown to be only has strong as the randomness of the random numbers used. It also requires all the public keys to be checked where there are multiple signers. This was causing Bitcoin to slow down, so the signature scheme was changed to the Schnorr scheme. With this we can merge the signing process, and aggregate the public keys together into a single signature.
But the Boneh–Lynn–Shacham (BLS) signature method is seen to be even strong for signing. It uses a bi-linear pairing with an elliptic curve group and provides some protection against index calculus attacks. BLS also products short signatures and has been shown to be secure. While Schnorr requires random numbers to generate multiple signers, BLS does not rely on these.
If Alice wants to create a BLS signature, she first generates her private key (\(a\)) and then takes a point on the elliptic curve (\(G\)) and computes her public key (\(P\)):
\(P = a G\)
She takes a hash of the message, and then map the hash value to a point on an elliptic curve. If we use SHA-256 we can convert the message into a 256-bit x-point. If we do not manage to get a point on the curve, we add an incremental value to find the first time that we reach the point. The signature of a message (\(M\)) and then computed with:
\(S = a \times H(M)\)
and where H(M) is the 256-bit hash of the message (\(M\)). Her private key is \(a\) and her public key (\(P\)) and which is equal to \(aG\). The test for the signature is then:
\(e(G,S) = e(P,H(M))\)
This can be proven as:
\(e(G,S) = e(G,a \times H(m)) = e(a \times G,H(m)) = e(P,H(M))\)
and where \(G\) is the generator point on the elliptic curve.
For the signature, we generate a new point on the elliptic curve and is 512 bits long, and use the x-point of the result. This gives us a 256-bit value, and thus our signature is 32 bytes long. This is a much smaller signatures than Schnorr and ECDSA. The signature for "Hello" is::
Message: Hello name=BN254 curve order=16798108731015832284940804142231733909759579603404752749028378864165570215949 -----Signature Test---- secretKey 3e6a4c7dae8f3563fabb9b57d04b4b21d3f2b9f4544adc7bedc6cbb36f036b10 publicKey a96fee792a1b933badbbadb9613ecd7f9903da5edfd100209622dc3402739b13df01cbb184ce620dc474d08bd83b47ac1a394e1ab652839b6232555a9be25499 signature 424d9ebf795d85e8abbbbddc264b110550afcb627dc90608e357d0cd3c2d7f08
When we look at ECDSA we see that we create an R and an S value, and which produces a longer signature:
Message: Hello Private key: Key priv: 2aabe11b7f965e8b16f525127efa01833f12ccd84daf9748373b66838520cdb7 pub: EC Point x: 39516301f4c81c21fbbc97ada61dee8d764c155449967fa6b02655a4664d1562 y: d9aa170e4ec9da8239bd0c151bf3e23c285ebe5187cee544a3ab0f9650af1aa6 Public key: EC Point x: 39516301f4c81c21fbbc97ada61dee8d764c155449967fa6b02655a4664d1562 y: d9aa170e4ec9da8239bd0c151bf3e23c285ebe5187cee544a3ab0f9650af1aa6 Signature: Signature { r: BN: 905eceb65a8de60f092ffb6002c829454e8e16f3d83fa7dcd52f8eb21e55332b, s: BN: 8f22e3d95beb05517a1590b1c5af4b2eaabf8e231a799300fffa08208d8f4625, recoveryParam: 0 }
One of the great advantages of BLS is that we can aggregate signatures together. For this we could have 100 transactions and where we had a signature for each one (Si) and each are associated with a public key of Pi (and a message Mi).
We can then just add a single signature for our 100 transactions, and the result will only have 33 bytes (rather than having to store all the signatures). In Bitcoin we can perform a single transaction with multiple addresses. This involves multiple keys, and, with BLS, we can aggregate the signatures together. With this we merge signatures into a single signature and merge the keys into a single key. The signature is then:
\(S=S1+S2… +S100\)
We can then verify with (and where we use a multiply operation):
\(e(G, S) = e(P1, H(M1))⋅e(P2, H(M2))⋅…⋅e(P100, H(M100))\)
If we have the same message - such as a cryptocurrency transaction - we can merge the public keys together (key aggregation) and check the signature (N-by-N signature):
Presentation
The following is a presentation [slides]:
Sample code
This is known as multisig and key aggregation. The basic method is defined from [here]:
(generator => { if (typeof exports === 'object') { const crypto = require('crypto') crypto.getRandomValues = crypto.randomFillSync generator(exports, crypto, true) } else { const crypto = window.crypto || window.msCrypto const exports = {} window.bls = generator(exports, crypto, false) } })((exports, crypto, isNodeJs) => { /* eslint-disable */ exports.BN254 = 0 exports.BN381_1 = 1 exports.BLS12_381 = 5 /* eslint-disable */ const getUnitSize = curveType => { switch (curveType) { case exports.BN254: case exports.BN381_1: case exports.BLS12_381: return 6; default: throw new Error(`QQQ bad curveType=${curveType}`) } } const setup = (exports, curveType) => { const mod = exports.mod const MCLBN_FP_UNIT_SIZE = getUnitSize(curveType) const MCLBN_FR_UNIT_SIZE = MCLBN_FP_UNIT_SIZE const MCLBN_COMPILED_TIME_VAR = (MCLBN_FR_UNIT_SIZE * 10 + MCLBN_FP_UNIT_SIZE) const BLS_ID_SIZE = MCLBN_FP_UNIT_SIZE * 8 const BLS_SECRETKEY_SIZE = BLS_ID_SIZE const BLS_PUBLICKEY_SIZE = BLS_ID_SIZE * 3 * 2 const BLS_SIGNATURE_SIZE = BLS_ID_SIZE * 3 const _malloc = size => { return mod._blsMalloc(size) } const _free = pos => { mod._blsFree(pos) } const ptrToAsciiStr = (pos, n) => { let s = '' for (let i = 0; i < n; i++) { s += String.fromCharCode(mod.HEAP8[pos + i]) } return s } const asciiStrToPtr = (pos, s) => { for (let i = 0; i < s.length; i++) { mod.HEAP8[pos + i] = s.charCodeAt(i) } } exports.toHex = (a, start, n) => { let s = '' for (let i = 0; i < n; i++) { s += ('0' + a[start + i].toString(16)).slice(-2) } return s } // Uint8Array to hex string exports.toHexStr = a => { return exports.toHex(a, 0, a.length) } // hex string to Uint8Array exports.fromHexStr = s => { if (s.length & 1) throw new Error('fromHexStr:length must be even ' + s.length) const n = s.length / 2 const a = new Uint8Array(n) for (let i = 0; i < n; i++) { a[i] = parseInt(s.slice(i * 2, i * 2 + 2), 16) } return a } /////////////////////////// const copyToUint32Array = (a, pos) => { a.set(mod.HEAP32.subarray(pos / 4, pos / 4 + a.length)) // for (let i = 0; i < a.length; i++) { // a[i] = mod.HEAP32[pos / 4 + i] // } } const copyFromUint32Array = (pos, a) => { for (let i = 0; i < a.length; i++) { mod.HEAP32[pos / 4 + i] = a[i] } } ////////////////////////////////// const _wrapGetStr = (func, returnAsStr = true) => { return (x, ioMode = 0) => { const maxBufSize = 3096 const pos = _malloc(maxBufSize) const n = func(pos, maxBufSize, x, ioMode) if (n <= 0) { throw new Error('err gen_str:' + x) } let s = null if (returnAsStr) { s = ptrToAsciiStr(pos, n) } else { s = new Uint8Array(mod.HEAP8.subarray(pos, pos + n)) } _free(pos) return s } } const _wrapSerialize = func => { return _wrapGetStr(func, false) } const _wrapDeserialize = func => { return (x, buf) => { const pos = _malloc(buf.length) mod.HEAP8.set(buf, pos) const r = func(x, pos, buf.length) _free(pos) if (r === 0) throw new Error('err _wrapDeserialize', buf) } } /* argNum : n func(x0, ..., x_(n-1), buf, ioMode) => func(x0, ..., x_(n-1), pos, buf.length, ioMode) */ const _wrapInput = (func, argNum, returnValue = false) => { return function () { const args = [...arguments] const buf = args[argNum] const typeStr = Object.prototype.toString.apply(buf) if (['[object String]', '[object Uint8Array]', '[object Array]'].indexOf(typeStr) < 0) { throw new Error(`err bad type:"${typeStr}". Use String or Uint8Array.`) } const ioMode = args[argNum + 1] // may undefined const pos = _malloc(buf.length) if (typeStr === '[object String]') { asciiStrToPtr(pos, buf) } else { mod.HEAP8.set(buf, pos) } const r = func(...args.slice(0, argNum), pos, buf.length, ioMode) _free(pos) if (returnValue) return r if (r) throw new Error('err _wrapInput ' + buf) } } const callSetter = (func, a, p1, p2) => { const pos = _malloc(a.length * 4) func(pos, p1, p2) // p1, p2 may be undefined copyToUint32Array(a, pos) _free(pos) } const callGetter = (func, a, p1, p2) => { const pos = _malloc(a.length * 4) mod.HEAP32.set(a, pos / 4) const s = func(pos, p1, p2) _free(pos) return s } const callShare = (func, a, size, vec, id) => { const pos = a._allocAndCopy() const idPos = id._allocAndCopy() const vecPos = _malloc(size * vec.length) for (let i = 0; i < vec.length; i++) { copyFromUint32Array(vecPos + size * i, vec[i].a_) } func(pos, vecPos, vec.length, idPos) _free(vecPos) _free(idPos) a._saveAndFree(pos) } const callRecover = (func, a, size, vec, idVec) => { const n = vec.length if (n != idVec.length) throw ('recover:bad length') const secPos = a._alloc() const vecPos = _malloc(size * n) const idVecPos = _malloc(BLS_ID_SIZE * n) for (let i = 0; i < n; i++) { copyFromUint32Array(vecPos + size * i, vec[i].a_) copyFromUint32Array(idVecPos + BLS_ID_SIZE * i, idVec[i].a_) } func(secPos, vecPos, idVecPos, n) _free(idVecPos) _free(vecPos) a._saveAndFree(secPos) } // change curveType exports.blsInit = (curveType = exports.BN254) => { const r = mod._blsInit(curveType, MCLBN_COMPILED_TIME_VAR) if (r) throw ('blsInit err ' + r) } exports.getCurveOrder = _wrapGetStr(mod._blsGetCurveOrder) exports.getFieldOrder = _wrapGetStr(mod._blsGetFieldOrder) mod.blsIdSetDecStr = _wrapInput(mod._blsIdSetDecStr, 1) mod.blsIdSetHexStr = _wrapInput(mod._blsIdSetHexStr, 1) mod.blsIdGetDecStr = _wrapGetStr(mod._blsIdGetDecStr) mod.blsIdGetHexStr = _wrapGetStr(mod._blsIdGetHexStr) mod.blsIdSerialize = _wrapSerialize(mod._blsIdSerialize) mod.blsSecretKeySerialize = _wrapSerialize(mod._blsSecretKeySerialize) mod.blsPublicKeySerialize = _wrapSerialize(mod._blsPublicKeySerialize) mod.blsSignatureSerialize = _wrapSerialize(mod._blsSignatureSerialize) mod.blsIdDeserialize = _wrapDeserialize(mod._blsIdDeserialize) mod.blsSecretKeyDeserialize = _wrapDeserialize(mod._blsSecretKeyDeserialize) mod.blsPublicKeyDeserialize = _wrapDeserialize(mod._blsPublicKeyDeserialize) mod.blsSignatureDeserialize = _wrapDeserialize(mod._blsSignatureDeserialize) mod.blsSecretKeySetLittleEndian = _wrapInput(mod._blsSecretKeySetLittleEndian, 1) mod.blsHashToSecretKey = _wrapInput(mod._blsHashToSecretKey, 1) mod.blsSign = _wrapInput(mod._blsSign, 2) mod.blsVerify = _wrapInput(mod._blsVerify, 2, true) class Common { constructor (size) { this.a_ = new Uint32Array(size / 4) } deserializeHexStr (s) { this.deserialize(exports.fromHexStr(s)) } serializeToHexStr () { return exports.toHexStr(this.serialize()) } dump (msg = '') { console.log(msg + this.serializeToHexStr()) } clear () { this.a_.fill(0) } // alloc new array _alloc () { return _malloc(this.a_.length * 4) } // alloc and copy a_ to mod.HEAP32[pos / 4] _allocAndCopy () { const pos = this._alloc() mod.HEAP32.set(this.a_, pos / 4) return pos } // save pos to a_ _save (pos) { this.a_.set(mod.HEAP32.subarray(pos / 4, pos / 4 + this.a_.length)) } // save and free _saveAndFree(pos) { this._save(pos) _free(pos) } // set parameter (p1, p2 may be undefined) _setter (func, p1, p2) { const pos = this._alloc() const r = func(pos, p1, p2) this._saveAndFree(pos) if (r) throw new Error('_setter err') } // getter (p1, p2 may be undefined) _getter (func, p1, p2) { const pos = this._allocAndCopy() const s = func(pos, p1, p2) _free(pos) return s } _isEqual (func, rhs) { const xPos = this._allocAndCopy() const yPos = rhs._allocAndCopy() const r = func(xPos, yPos) _free(yPos) _free(xPos) return r === 1 } // func(y, this) and return y _op1 (func) { const y = new this.constructor() const xPos = this._allocAndCopy() const yPos = y._alloc() func(yPos, xPos) y._saveAndFree(yPos) _free(xPos) return y } // func(z, this, y) and return z _op2 (func, y, Cstr = null) { const z = Cstr ? new Cstr() : new this.constructor() const xPos = this._allocAndCopy() const yPos = y._allocAndCopy() const zPos = z._alloc() func(zPos, xPos, yPos) z._saveAndFree(zPos) _free(yPos) _free(xPos) return z } } exports.Id = class extends Common { constructor () { super(BLS_ID_SIZE) } setInt (x) { this._setter(mod._blsIdSetInt, x) } deserialize (s) { this._setter(mod.blsIdDeserialize, s) } serialize () { return this._getter(mod.blsIdSerialize) } setStr (s, base = 10) { switch (base) { case 10: this._setter(mod.blsIdSetDecStr, s) return case 16: this._setter(mod.blsIdSetHexStr, s) return default: throw ('BlsId.setStr:bad base:' + base) } } getStr (base = 10) { switch (base) { case 10: return this._getter(mod.blsIdGetDecStr) case 16: return this._getter(mod.blsIdGetHexStr) default: throw ('BlsId.getStr:bad base:' + base) } } setLittleEndian (s) { this._setter(mod.blsSecretKeySetLittleEndian, s) } setByCSPRNG () { const a = new Uint8Array(BLS_ID_SIZE) crypto.getRandomValues(a) this.setLittleEndian(a) } } exports.deserializeHexStrToId = s => { const r = new exports.Id() r.deserializeHexStr(s) return r } exports.SecretKey = class extends Common { constructor () { super(BLS_SECRETKEY_SIZE) } setInt (x) { this._setter(mod._blsIdSetInt, x) // same as Id } deserialize (s) { this._setter(mod.blsSecretKeyDeserialize, s) } serialize () { return this._getter(mod.blsSecretKeySerialize) } share (msk, id) { callShare(mod._blsSecretKeyShare, this, BLS_SECRETKEY_SIZE, msk, id) } recover (secVec, idVec) { callRecover(mod._blsSecretKeyRecover, this, BLS_SECRETKEY_SIZE, secVec, idVec) } setHashOf (s) { this._setter(mod.blsHashToSecretKey, s) } setLittleEndian (s) { this._setter(mod.blsSecretKeySetLittleEndian, s) } setByCSPRNG () { const a = new Uint8Array(BLS_SECRETKEY_SIZE) crypto.getRandomValues(a) this.setLittleEndian(a) } getPublicKey () { const pub = new exports.PublicKey() const secPos = this._allocAndCopy() const pubPos = pub._alloc() mod._blsGetPublicKey(pubPos, secPos) pub._saveAndFree(pubPos) _free(secPos) return pub } /* input m : message (string or Uint8Array) return BlsSignature */ sign (m) { const sig = new exports.Signature() const secPos = this._allocAndCopy() const sigPos = sig._alloc() mod.blsSign(sigPos, secPos, m) sig._saveAndFree(sigPos) _free(secPos) return sig } } exports.deserializeHexStrToSecretKey = s => { const r = new exports.SecretKey() r.deserializeHexStr(s) return r } exports.PublicKey = class extends Common { constructor () { super(BLS_PUBLICKEY_SIZE) } deserialize (s) { this._setter(mod.blsPublicKeyDeserialize, s) } serialize () { return this._getter(mod.blsPublicKeySerialize) } share (msk, id) { callShare(mod._blsPublicKeyShare, this, BLS_PUBLICKEY_SIZE, msk, id) } recover (secVec, idVec) { callRecover(mod._blsPublicKeyRecover, this, BLS_PUBLICKEY_SIZE, secVec, idVec) } verify (sig, m) { const pubPos = this._allocAndCopy() const sigPos = sig._allocAndCopy() const r = mod.blsVerify(sigPos, pubPos, m) _free(sigPos) _free(pubPos) return r != 0 } } exports.deserializeHexStrToPublicKey = s => { const r = new exports.PublicKey() r.deserializeHexStr(s) return r } exports.Signature = class extends Common { constructor () { super(BLS_SIGNATURE_SIZE) } deserialize (s) { this._setter(mod.blsSignatureDeserialize, s) } serialize () { return this._getter(mod.blsSignatureSerialize) } recover (secVec, idVec) { callRecover(mod._blsSignatureRecover, this, BLS_SIGNATURE_SIZE, secVec, idVec) } } exports.deserializeHexStrToSignature = s => { const r = new exports.Signature() r.deserializeHexStr(s) return r } exports.blsInit(curveType) console.log('finished') } // setup() const _cryptoGetRandomValues = function(p, n) { const a = new Uint8Array(n) crypto.getRandomValues(a) for (let i = 0; i < n; i++) { exports.mod.HEAP8[p + i] = a[i] } } exports.init = (curveType = exports.BN254) => { exports.curveType = curveType const name = 'bls_c' return new Promise(resolve => { if (isNodeJs) { const path = require('path') const js = require(`./${name}.js`) const Module = { cryptoGetRandomValues : _cryptoGetRandomValues, locateFile: baseName => { return path.join(__dirname, baseName) } } js(Module) .then(_mod => { exports.mod = _mod setup(exports, curveType) resolve() }) } else { fetch(`./${name}.wasm`) // eslint-disable-line .then(response => response.arrayBuffer()) .then(buffer => new Uint8Array(buffer)) .then(() => { exports.mod = Module() // eslint-disable-line exports.mod.cryptoGetRandomValues = _cryptoGetRandomValues exports.mod.onRuntimeInitialized = () => { setup(exports, curveType) resolve() } }) } }) } return exports })