432 lines
19 KiB
JavaScript
432 lines
19 KiB
JavaScript
/**
|
|
* BLS != BLS.
|
|
* The file implements BLS (Boneh-Lynn-Shacham) signatures.
|
|
* Used in both BLS (Barreto-Lynn-Scott) and BN (Barreto-Naehrig)
|
|
* families of pairing-friendly curves.
|
|
* Consists of two curves: G1 and G2:
|
|
* - G1 is a subgroup of (x, y) E(Fq) over y² = x³ + 4.
|
|
* - G2 is a subgroup of ((x₁, x₂+i), (y₁, y₂+i)) E(Fq²) over y² = x³ + 4(1 + i) where i is √-1
|
|
* - Gt, created by bilinear (ate) pairing e(G1, G2), consists of p-th roots of unity in
|
|
* Fq^k where k is embedding degree. Only degree 12 is currently supported, 24 is not.
|
|
* Pairing is used to aggregate and verify signatures.
|
|
* There are two modes of operation:
|
|
* - Long signatures: X-byte keys + 2X-byte sigs (G1 keys + G2 sigs).
|
|
* - Short signatures: 2X-byte keys + X-byte sigs (G2 keys + G1 sigs).
|
|
* @module
|
|
**/
|
|
/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
|
|
import { abytes, notImplemented, randomBytes } from "../utils.js";
|
|
import {} from "./curve.js";
|
|
import { createHasher, } from "./hash-to-curve.js";
|
|
import { getMinHashLength, mapHashToField } from "./modular.js";
|
|
import {} from "./weierstrass.js";
|
|
// prettier-ignore
|
|
const _0n = BigInt(0), _1n = BigInt(1), _2n = BigInt(2), _3n = BigInt(3);
|
|
// Signed non-adjacent decomposition of the spec-defined Miller-loop parameter.
|
|
// BN254 benefits most because `6x+2` has multiple adjacent `11` runs, but BLS12-381's
|
|
// stored `|x|` still starts with `11`, so the Miller loop must also handle one `-1` digit there.
|
|
function NAfDecomposition(a) {
|
|
const res = [];
|
|
// a>1 because of marker bit
|
|
for (; a > _1n; a >>= _1n) {
|
|
if ((a & _1n) === _0n)
|
|
res.unshift(0);
|
|
else if ((a & _3n) === _3n) {
|
|
res.unshift(-1);
|
|
a += _1n;
|
|
}
|
|
else
|
|
res.unshift(1);
|
|
}
|
|
return res;
|
|
}
|
|
function aNonEmpty(arr) {
|
|
// Aggregate helpers use this to reject empty variable-length inputs consistently.
|
|
// Without the guard, each caller would fall through into a different empty-input / identity
|
|
// case and hide missing inputs behind outputs that still look structurally valid.
|
|
if (!Array.isArray(arr) || arr.length === 0)
|
|
throw new Error('expected non-empty array');
|
|
}
|
|
// This should be enough for bn254, no need to export full stuff?
|
|
function createBlsPairing(fields, G1, G2, params) {
|
|
const { Fr, Fp2, Fp12 } = fields;
|
|
const { twistType, ateLoopSize, xNegative, postPrecompute } = params;
|
|
// Applies sparse multiplication as line function
|
|
let lineFunction;
|
|
if (twistType === 'multiplicative') {
|
|
lineFunction = (c0, c1, c2, f, Px, Py) => Fp12.mul014(f, c0, Fp2.mul(c1, Px), Fp2.mul(c2, Py));
|
|
}
|
|
else if (twistType === 'divisive') {
|
|
// NOTE: it should be [c0, c1, c2], but we use different order here to reduce complexity of
|
|
// precompute calculations.
|
|
lineFunction = (c0, c1, c2, f, Px, Py) => Fp12.mul034(f, Fp2.mul(c2, Py), Fp2.mul(c1, Px), c0);
|
|
}
|
|
else
|
|
throw new Error('bls: unknown twist type');
|
|
const Fp2div2 = Fp2.div(Fp2.ONE, Fp2.mul(Fp2.ONE, _2n));
|
|
function pointDouble(ell, Rx, Ry, Rz) {
|
|
const t0 = Fp2.sqr(Ry); // Ry²
|
|
const t1 = Fp2.sqr(Rz); // Rz²
|
|
const t2 = Fp2.mulByB(Fp2.mul(t1, _3n)); // 3 * T1 * B
|
|
const t3 = Fp2.mul(t2, _3n); // 3 * T2
|
|
const t4 = Fp2.sub(Fp2.sub(Fp2.sqr(Fp2.add(Ry, Rz)), t1), t0); // (Ry + Rz)² - T1 - T0
|
|
const c0 = Fp2.sub(t2, t0); // T2 - T0 (i)
|
|
const c1 = Fp2.mul(Fp2.sqr(Rx), _3n); // 3 * Rx²
|
|
const c2 = Fp2.neg(t4); // -T4 (-h)
|
|
ell.push([c0, c1, c2]);
|
|
Rx = Fp2.mul(Fp2.mul(Fp2.mul(Fp2.sub(t0, t3), Rx), Ry), Fp2div2); // ((T0 - T3) * Rx * Ry) / 2
|
|
// ((T0 + T3) / 2)² - 3 * T2²
|
|
Ry = Fp2.sub(Fp2.sqr(Fp2.mul(Fp2.add(t0, t3), Fp2div2)), Fp2.mul(Fp2.sqr(t2), _3n));
|
|
Rz = Fp2.mul(t0, t4); // T0 * T4
|
|
return { Rx, Ry, Rz };
|
|
}
|
|
function pointAdd(ell, Rx, Ry, Rz, Qx, Qy) {
|
|
// Addition
|
|
const t0 = Fp2.sub(Ry, Fp2.mul(Qy, Rz)); // Ry - Qy * Rz
|
|
const t1 = Fp2.sub(Rx, Fp2.mul(Qx, Rz)); // Rx - Qx * Rz
|
|
const c0 = Fp2.sub(Fp2.mul(t0, Qx), Fp2.mul(t1, Qy)); // T0 * Qx - T1 * Qy == Ry * Qx - Rx * Qy
|
|
const c1 = Fp2.neg(t0); // -T0 == Qy * Rz - Ry
|
|
const c2 = t1; // == Rx - Qx * Rz
|
|
ell.push([c0, c1, c2]);
|
|
const t2 = Fp2.sqr(t1); // T1²
|
|
const t3 = Fp2.mul(t2, t1); // T2 * T1
|
|
const t4 = Fp2.mul(t2, Rx); // T2 * Rx
|
|
// T3 - 2 * T4 + T0² * Rz
|
|
const t5 = Fp2.add(Fp2.sub(t3, Fp2.mul(t4, _2n)), Fp2.mul(Fp2.sqr(t0), Rz));
|
|
Rx = Fp2.mul(t1, t5); // T1 * T5
|
|
Ry = Fp2.sub(Fp2.mul(Fp2.sub(t4, t5), t0), Fp2.mul(t3, Ry)); // (T4 - T5) * T0 - T3 * Ry
|
|
Rz = Fp2.mul(Rz, t3); // Rz * T3
|
|
return { Rx, Ry, Rz };
|
|
}
|
|
// Pre-compute coefficients for sparse multiplication
|
|
// Point addition and point double calculations is reused for coefficients
|
|
// pointAdd happens only if bit set, so wNAF is reasonable. Unfortunately we cannot combine
|
|
// add + double in windowed precomputes here, otherwise it would be single op (since X is static)
|
|
const ATE_NAF = NAfDecomposition(ateLoopSize);
|
|
const calcPairingPrecomputes = (point) => {
|
|
const p = point;
|
|
const { x, y } = p.toAffine();
|
|
// prettier-ignore
|
|
const Qx = x, Qy = y, negQy = Fp2.neg(y);
|
|
// prettier-ignore
|
|
let Rx = Qx, Ry = Qy, Rz = Fp2.ONE;
|
|
const ell = [];
|
|
for (const bit of ATE_NAF) {
|
|
const cur = [];
|
|
({ Rx, Ry, Rz } = pointDouble(cur, Rx, Ry, Rz));
|
|
if (bit)
|
|
({ Rx, Ry, Rz } = pointAdd(cur, Rx, Ry, Rz, Qx, bit === -1 ? negQy : Qy));
|
|
ell.push(cur);
|
|
}
|
|
if (postPrecompute) {
|
|
const last = ell[ell.length - 1];
|
|
postPrecompute(Rx, Ry, Rz, Qx, Qy, pointAdd.bind(null, last));
|
|
}
|
|
return ell;
|
|
};
|
|
function millerLoopBatch(pairs, withFinalExponent = false) {
|
|
let f12 = Fp12.ONE;
|
|
if (pairs.length) {
|
|
const ellLen = pairs[0][0].length;
|
|
for (let i = 0; i < ellLen; i++) {
|
|
f12 = Fp12.sqr(f12); // This allows us to do sqr only one time for all pairings
|
|
// NOTE: we apply multiple pairings in parallel here
|
|
for (const [ell, Px, Py] of pairs) {
|
|
for (const [c0, c1, c2] of ell[i])
|
|
f12 = lineFunction(c0, c1, c2, f12, Px, Py);
|
|
}
|
|
}
|
|
}
|
|
if (xNegative)
|
|
f12 = Fp12.conjugate(f12);
|
|
return withFinalExponent ? Fp12.finalExponentiate(f12) : f12;
|
|
}
|
|
// Calculates product of multiple pairings
|
|
// This up to x2 faster than just `map(({g1, g2})=>pairing({g1,g2}))`
|
|
function pairingBatch(pairs, withFinalExponent = true) {
|
|
const res = [];
|
|
for (const { g1, g2 } of pairs) {
|
|
// Mathematically, a zero pairing term contributes GT.ONE. We still reject it here because
|
|
// this API mainly backs BLS verification, where ZERO inputs usually mean broken hash /
|
|
// wiring. Silently skipping them would turn those failures into a neutral pairing product.
|
|
// Callers that want the algebraic neutral-element behavior can filter ZERO terms first.
|
|
if (g1.is0() || g2.is0())
|
|
throw new Error('pairing is not available for ZERO point');
|
|
// This uses toAffine inside
|
|
g1.assertValidity();
|
|
g2.assertValidity();
|
|
const Qa = g1.toAffine();
|
|
res.push([calcPairingPrecomputes(g2), Qa.x, Qa.y]);
|
|
}
|
|
return millerLoopBatch(res, withFinalExponent);
|
|
}
|
|
// Calculates bilinear pairing
|
|
function pairing(Q, P, withFinalExponent = true) {
|
|
return pairingBatch([{ g1: Q, g2: P }], withFinalExponent);
|
|
}
|
|
const lengths = {
|
|
seed: getMinHashLength(Fr.ORDER),
|
|
};
|
|
const rand = params.randomBytes === undefined ? randomBytes : params.randomBytes;
|
|
// Seeded calls deterministically reduce exactly `lengths.seed` bytes into `1..Fr.ORDER-1`;
|
|
// omitting `seed` just fills that input buffer from the configured RNG first.
|
|
const randomSecretKey = (seed) => {
|
|
seed = seed === undefined ? rand(lengths.seed) : seed;
|
|
abytes(seed, lengths.seed, 'seed');
|
|
return mapHashToField(seed, Fr.ORDER);
|
|
};
|
|
Object.freeze(lengths);
|
|
return {
|
|
lengths,
|
|
Fr,
|
|
Fp12, // NOTE: we re-export Fp12 here because pairing results are Fp12!
|
|
millerLoopBatch,
|
|
pairing,
|
|
pairingBatch,
|
|
calcPairingPrecomputes,
|
|
randomSecretKey,
|
|
};
|
|
}
|
|
function createBlsSig(blsPairing, PubPoint, SigPoint, isSigG1, hashToSigCurve, SignatureCoder) {
|
|
const { Fr, Fp12, pairingBatch, randomSecretKey, lengths } = blsPairing;
|
|
if (!SignatureCoder) {
|
|
SignatureCoder = {
|
|
fromBytes: notImplemented,
|
|
fromHex: notImplemented,
|
|
toBytes: notImplemented,
|
|
toHex: notImplemented,
|
|
};
|
|
}
|
|
function normPub(point) {
|
|
return point instanceof PubPoint ? point : PubPoint.fromBytes(point);
|
|
}
|
|
function normSig(point) {
|
|
return point instanceof SigPoint ? point : SigPoint.fromBytes(point);
|
|
}
|
|
// Sign/verify here take points already hashed onto the signature subgroup.
|
|
// Raw bytes and points from the other subgroup must fail this constructor-brand
|
|
// check before later validity checks run.
|
|
function amsg(m) {
|
|
if (!(m instanceof SigPoint))
|
|
throw new Error(`expected valid message hashed to ${!isSigG1 ? 'G2' : 'G1'} curve`);
|
|
return m;
|
|
}
|
|
// What matters here is what point pairing API accepts as G1 or G2, not actual size or names
|
|
const pair = !isSigG1
|
|
? (a, b) => ({ g1: a, g2: b })
|
|
: (a, b) => ({ g1: b, g2: a });
|
|
return Object.freeze({
|
|
lengths: Object.freeze({ ...lengths, secretKey: Fr.BYTES }),
|
|
keygen(seed) {
|
|
const secretKey = randomSecretKey(seed);
|
|
const publicKey = this.getPublicKey(secretKey);
|
|
return { secretKey, publicKey };
|
|
},
|
|
// P = pk x G
|
|
getPublicKey(secretKey) {
|
|
let sec;
|
|
try {
|
|
sec = PubPoint.Fn.fromBytes(secretKey);
|
|
}
|
|
catch (error) {
|
|
// @ts-ignore
|
|
throw new Error('invalid private key: ' + typeof secretKey, { cause: error });
|
|
}
|
|
return PubPoint.BASE.multiply(sec);
|
|
},
|
|
// S = pk x H(m)
|
|
sign(message, secretKey, unusedArg) {
|
|
if (unusedArg != null)
|
|
throw new Error('sign() expects 2 arguments');
|
|
const sec = PubPoint.Fn.fromBytes(secretKey);
|
|
amsg(message).assertValidity();
|
|
return message.multiply(sec);
|
|
},
|
|
// Checks if pairing of public key & hash is equal to pairing of generator & signature.
|
|
// e(P, H(m)) == e(G, S)
|
|
// e(S, G) == e(H(m), P)
|
|
verify(signature, message, publicKey, unusedArg) {
|
|
if (unusedArg != null)
|
|
throw new Error('verify() expects 3 arguments');
|
|
signature = normSig(signature);
|
|
publicKey = normPub(publicKey);
|
|
const P = publicKey.negate();
|
|
const G = PubPoint.BASE;
|
|
const Hm = amsg(message);
|
|
const S = signature;
|
|
// This code was changed in 1.9.x:
|
|
// Before it was G.negate() in G2, now it's always pubKey.negate
|
|
// e(P, -Q)===e(-P, Q)==e(P, Q)^-1. Negate can be done anywhere (as long it is done once per pair).
|
|
// We just moving sign, but since pairing is multiplicative, we doing X * X^-1 = 1
|
|
try {
|
|
const exp = pairingBatch([pair(P, Hm), pair(G, S)]);
|
|
return Fp12.eql(exp, Fp12.ONE);
|
|
}
|
|
catch {
|
|
return false;
|
|
}
|
|
},
|
|
// https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407
|
|
// e(G, S) = e(G, SUM(n)(Si)) = MUL(n)(e(G, Si))
|
|
// TODO: maybe `{message: G2Hex, publicKey: G1Hex}[]` instead?
|
|
verifyBatch(signature, items) {
|
|
aNonEmpty(items);
|
|
const sig = normSig(signature);
|
|
const nMessages = items.map((i) => i.message);
|
|
const nPublicKeys = items.map((i) => normPub(i.publicKey));
|
|
// NOTE: this works only for exact same object
|
|
const messagePubKeyMap = new Map();
|
|
for (let i = 0; i < nPublicKeys.length; i++) {
|
|
const pub = nPublicKeys[i];
|
|
const msg = nMessages[i];
|
|
let keys = messagePubKeyMap.get(msg);
|
|
if (keys === undefined) {
|
|
keys = [];
|
|
messagePubKeyMap.set(msg, keys);
|
|
}
|
|
keys.push(pub);
|
|
}
|
|
const paired = [];
|
|
const G = PubPoint.BASE;
|
|
try {
|
|
for (const [msg, keys] of messagePubKeyMap) {
|
|
const groupPublicKey = keys.reduce((acc, msg) => acc.add(msg));
|
|
paired.push(pair(groupPublicKey, msg));
|
|
}
|
|
paired.push(pair(G.negate(), sig));
|
|
return Fp12.eql(pairingBatch(paired), Fp12.ONE);
|
|
}
|
|
catch {
|
|
return false;
|
|
}
|
|
},
|
|
// Adds a bunch of public key points together.
|
|
// pk1 + pk2 + pk3 = pkA
|
|
aggregatePublicKeys(publicKeys) {
|
|
aNonEmpty(publicKeys);
|
|
publicKeys = publicKeys.map((pub) => normPub(pub));
|
|
const agg = publicKeys.reduce((sum, p) => sum.add(p), PubPoint.ZERO);
|
|
agg.assertValidity();
|
|
return agg;
|
|
},
|
|
// Adds a bunch of signature points together.
|
|
// pk1 + pk2 + pk3 = pkA
|
|
aggregateSignatures(signatures) {
|
|
aNonEmpty(signatures);
|
|
signatures = signatures.map((sig) => normSig(sig));
|
|
const agg = signatures.reduce((sum, s) => sum.add(s), SigPoint.ZERO);
|
|
agg.assertValidity();
|
|
return agg;
|
|
},
|
|
hash(messageBytes, DST) {
|
|
abytes(messageBytes);
|
|
const opts = DST ? { DST } : undefined;
|
|
return hashToSigCurve(messageBytes, opts);
|
|
},
|
|
Signature: Object.freeze({ ...SignatureCoder }),
|
|
}) /*satisfies Signer */;
|
|
}
|
|
// NOTE: separate function instead of function override, so we don't depend on hasher in bn254.
|
|
/**
|
|
* @param fields - Tower field implementations.
|
|
* @param G1_Point - G1 point constructor.
|
|
* @param G2_Point - G2 point constructor.
|
|
* @param params - Pairing parameters. See {@link BlsPairingParams}.
|
|
* @returns Pairing-only BLS helpers. The returned pairing surface rejects infinity inputs, while
|
|
* empty `pairingBatch(...)` calls return the multiplicative identity in GT. This keeps the
|
|
* low-level pairing API fail-closed for BLS-style callers, where identity points usually signal
|
|
* broken hash / wiring instead of an intentionally neutral pairing term. This also eagerly
|
|
* precomputes the G1 base-point table as a performance side effect.
|
|
* @throws If the pairing parameters or underlying curve helpers are inconsistent. {@link Error}
|
|
* @example
|
|
* ```ts
|
|
* import { blsBasic } from '@noble/curves/abstract/bls.js';
|
|
* import { bn254 } from '@noble/curves/bn254.js';
|
|
* // Pair a G1 point with a G2 point without the higher-level signer helpers.
|
|
* const gt = bn254.pairing(bn254.G1.Point.BASE, bn254.G2.Point.BASE);
|
|
* ```
|
|
*/
|
|
export function blsBasic(fields, G1_Point, G2_Point, params) {
|
|
// Fields are specific for curve, so for now we'll need to pass them with opts
|
|
const { Fp, Fr, Fp2, Fp6, Fp12 } = fields;
|
|
// Point on G1 curve: (x, y)
|
|
// const G1_Point = weierstrass(CURVE.G1, { Fn: Fr });
|
|
const G1 = { Point: G1_Point };
|
|
// Point on G2 curve (complex numbers): (x₁, x₂+i), (y₁, y₂+i)
|
|
const G2 = { Point: G2_Point };
|
|
const pairingRes = createBlsPairing(fields, G1_Point, G2_Point, params);
|
|
const { millerLoopBatch, pairing, pairingBatch, calcPairingPrecomputes, randomSecretKey, lengths, } = pairingRes;
|
|
G1.Point.BASE.precompute(4);
|
|
Object.freeze(G1);
|
|
Object.freeze(G2);
|
|
return Object.freeze({
|
|
lengths: Object.freeze(lengths),
|
|
millerLoopBatch,
|
|
pairing,
|
|
pairingBatch,
|
|
G1,
|
|
G2,
|
|
fields: Object.freeze({ Fr, Fp, Fp2, Fp6, Fp12 }),
|
|
params: Object.freeze({
|
|
ateLoopSize: params.ateLoopSize,
|
|
twistType: params.twistType,
|
|
}),
|
|
utils: Object.freeze({
|
|
randomSecretKey,
|
|
calcPairingPrecomputes,
|
|
}),
|
|
});
|
|
}
|
|
// We can export this too, but seems there is not much reasons for now? If user wants hasher, they can just create hasher.
|
|
function blsHashers(fields, G1_Point, G2_Point, params, hasherParams) {
|
|
const base = blsBasic(fields, G1_Point, G2_Point, params);
|
|
// Missing map hooks intentionally fail closed via notImplemented on first hash use.
|
|
const G1Hasher = createHasher(G1_Point, hasherParams.mapToG1 === undefined ? notImplemented : hasherParams.mapToG1, {
|
|
...hasherParams.hasherOpts,
|
|
...hasherParams.hasherOptsG1,
|
|
});
|
|
const G2Hasher = createHasher(G2_Point, hasherParams.mapToG2 === undefined ? notImplemented : hasherParams.mapToG2, {
|
|
...hasherParams.hasherOpts,
|
|
...hasherParams.hasherOptsG2,
|
|
});
|
|
return Object.freeze({ ...base, G1: G1Hasher, G2: G2Hasher });
|
|
}
|
|
// G1_Point: ProjConstructor<bigint>, G2_Point: ProjConstructor<Fp2>,
|
|
// Rename to blsSignatures?
|
|
/**
|
|
* @param fields - Tower field implementations.
|
|
* @param G1_Point - G1 point constructor.
|
|
* @param G2_Point - G2 point constructor.
|
|
* @param params - Pairing parameters. See {@link BlsPairingParams}.
|
|
* @param hasherParams - Hash-to-curve configuration. See {@link BlsHasherParams}.
|
|
* @param signatureCoders - Signature codecs.
|
|
* @returns BLS helpers with signers. The inherited pairing surface still rejects infinity inputs,
|
|
* and empty `pairingBatch(...)` calls still return the multiplicative identity in GT. Aggregate
|
|
* verification still requires proof of possession or another rogue-key defense from the caller.
|
|
* @throws If the pairing, hashing, or signature helpers are configured inconsistently. {@link Error}
|
|
* @example
|
|
* ```ts
|
|
* import { bls } from '@noble/curves/abstract/bls.js';
|
|
* import { bls12_381 } from '@noble/curves/bls12-381.js';
|
|
* const sigs = bls12_381.longSignatures;
|
|
* // Use the full BLS helper set when you need hashing, keygen, signing, and verification.
|
|
* const { secretKey, publicKey } = sigs.keygen();
|
|
* const msg = sigs.hash(new TextEncoder().encode('hello noble'));
|
|
* const sig = sigs.sign(msg, secretKey);
|
|
* const isValid = sigs.verify(sig, msg, publicKey);
|
|
* ```
|
|
*/
|
|
export function bls(fields, G1_Point, G2_Point, params, hasherParams, signatureCoders) {
|
|
const base = blsHashers(fields, G1_Point, G2_Point, params, hasherParams);
|
|
const pairingRes = {
|
|
...base,
|
|
Fr: base.fields.Fr,
|
|
Fp12: base.fields.Fp12,
|
|
calcPairingPrecomputes: base.utils.calcPairingPrecomputes,
|
|
randomSecretKey: base.utils.randomSecretKey,
|
|
};
|
|
const longSignatures = createBlsSig(pairingRes, G1_Point, G2_Point, false, base.G2.hashToCurve, signatureCoders?.LongSignature);
|
|
const shortSignatures = createBlsSig(pairingRes, G2_Point, G1_Point, true, base.G1.hashToCurve, signatureCoders?.ShortSignature);
|
|
return Object.freeze({ ...base, longSignatures, shortSignatures });
|
|
}
|
|
//# sourceMappingURL=bls.js.map
|