@noble/curves - npm Package Compare versions

Comparing version 1.5.0 to 1.6.0

abstract/curve.d.ts

@@ -54,2 +54,14 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 };
+/**
+ * Pippenger algorithm for multi-scalar multiplication (MSM).
+ * MSM is basically (Pa + Qb + Rc + ...).
+ * 30x faster vs naive addition on L=4096, 10x faster with precomputes.
+ * For N=254bit, L=1, it does: 1024 ADD + 254 DBL. For L=5: 1536 ADD + 254 DBL.
+ * Algorithmically constant-time (for same L), even when 1 point + scalar, or when scalar = 0.
+ * @param c Curve Point constructor
+ * @param field field over CURVE.N - important that it's not over CURVE.P
+ * @param points array of L curve points
+ * @param scalars array of L scalars (aka private keys / bigints)
+ */
+export declare function pippenger<T extends Group<T>>(c: GroupConstructor<T>, field: IField<bigint>, points: T[], scalars: bigint[]): T;
 export type BasicCurve<T> = {
@@ -56,0 +68,0 @@ Fp: IField<T>;

abstract/curve.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
 exports.wNAF = wNAF;
+exports.pippenger = pippenger;
 exports.validateBasic = validateBasic;
@@ -157,2 +158,56 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 }
+/**
+ * Pippenger algorithm for multi-scalar multiplication (MSM).
+ * MSM is basically (Pa + Qb + Rc + ...).
+ * 30x faster vs naive addition on L=4096, 10x faster with precomputes.
+ * For N=254bit, L=1, it does: 1024 ADD + 254 DBL. For L=5: 1536 ADD + 254 DBL.
+ * Algorithmically constant-time (for same L), even when 1 point + scalar, or when scalar = 0.
+ * @param c Curve Point constructor
+ * @param field field over CURVE.N - important that it's not over CURVE.P
+ * @param points array of L curve points
+ * @param scalars array of L scalars (aka private keys / bigints)
+ */
+function pippenger(c, field, points, scalars) {
+    // If we split scalars by some window (let's say 8 bits), every chunk will only
+    // take 256 buckets even if there are 4096 scalars, also re-uses double.
+    // TODO:
+    // - https://eprint.iacr.org/2024/750.pdf
+    // - https://tches.iacr.org/index.php/TCHES/article/view/10287
+    // 0 is accepted in scalars
+    if (!Array.isArray(points) || !Array.isArray(scalars) || scalars.length !== points.length)
+        throw new Error('arrays of points and scalars must have equal length');
+    scalars.forEach((s, i) => {
+        if (!field.isValid(s))
+            throw new Error(`wrong scalar at index ${i}`);
+    });
+    points.forEach((p, i) => {
+        if (!(p instanceof c))
+            throw new Error(`wrong point at index ${i}`);
+    });
+    const wbits = (0, utils_js_1.bitLen)(BigInt(points.length));
+    const windowSize = wbits > 12 ? wbits - 3 : wbits > 4 ? wbits - 2 : wbits ? 2 : 1; // in bits
+    const MASK = (1 << windowSize) - 1;
+    const buckets = new Array(MASK + 1).fill(c.ZERO); // +1 for zero array
+    const lastBits = Math.floor((field.BITS - 1) / windowSize) * windowSize;
+    let sum = c.ZERO;
+    for (let i = lastBits; i >= 0; i -= windowSize) {
+        buckets.fill(c.ZERO);
+        for (let j = 0; j < scalars.length; j++) {
+            const scalar = scalars[j];
+            const wbits = Number((scalar >> BigInt(i)) & BigInt(MASK));
+            buckets[wbits] = buckets[wbits].add(points[j]);
+        }
+        let resI = c.ZERO; // not using this will do small speed-up, but will lose ct
+        // Skip first bucket, because it is zero
+        for (let j = buckets.length - 1, sumI = c.ZERO; j > 0; j--) {
+            sumI = sumI.add(buckets[j]);
+            resI = resI.add(sumI);
+        }
+        sum = sum.add(resI);
+        if (i !== 0)
+            for (let j = 0; j < windowSize; j++)
+                sum = sum.double();
+    }
+    return sum;
+}
 function validateBasic(curve) {
@@ -159,0 +214,0 @@ (0, modular_js_1.validateField)(curve.Fp);

abstract/edwards.d.ts

@@ -64,2 +64,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
     fromPrivateKey(privateKey: Hex): ExtPointType;
+    msm(points: ExtPointType[], scalars: bigint[]): ExtPointType;
 }
@@ -66,0 +67,0 @@ /**

abstract/edwards.js

@@ -43,2 +43,3 @@ "use strict";
     const modP = Fp.create; // Function overrides
+    const Fn = (0, modular_js_1.Field)(CURVE.n, CURVE.nBitLength);
     // sqrt(u/v)
@@ -142,2 +143,6 @@ const uvRatio = CURVE.uvRatio ||
         }
+        // Multiscalar Multiplication
+        static msm(points, scalars) {
+            return (0, curve_js_1.pippenger)(Point, Fn, points, scalars);
+        }
         // "Private method", don't use it directly
@@ -144,0 +149,0 @@ _setWindowSize(windowSize) {

abstract/hash-to-curve.js

@@ -14,2 +14,4 @@ "use strict";
 function i2osp(value, length) {
+    anum(value);
+    anum(length);
     if (value < 0 || value >= 1 << (8 * length)) {
@@ -47,4 +49,4 @@ throw new Error(`bad I2OSP call: value=${value} length=${length}`);
     const ell = Math.ceil(lenInBytes / b_in_bytes);
-    if (ell > 255)
-        throw new Error('Invalid xmd length');
+    if (lenInBytes > 65535 || ell > 255)
+        throw new Error('expand_message_xmd: invalid lenInBytes');
     const DST_prime = (0, utils_js_1.concatBytes)(DST, i2osp(DST.length, 1));
@@ -51,0 +53,0 @@ const Z_pad = i2osp(0, r_in_bytes);

abstract/tower.d.ts

@@ -0,1 +1,2 @@
+/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 import * as mod from './modular.js';
@@ -2,0 +3,0 @@ import type { ProjConstructor, ProjPointType } from './weierstrass.js';

abstract/tower.js

@@ -5,2 +5,3 @@ "use strict";
 exports.tower12 = tower12;
+/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 const mod = require("./modular.js");
@@ -7,0 +8,0 @@ const utils_js_1 = require("./utils.js");

abstract/weierstrass.d.ts

@@ -80,2 +80,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
     normalizeZ(points: ProjPointType<T>[]): ProjPointType<T>[];
+    msm(points: ProjPointType<T>[], scalars: bigint[]): ProjPointType<T>;
 }
@@ -114,2 +115,9 @@ export type CurvePointsType<T> = BasicWCurve<T> & {
 };
+/**
+ * ASN.1 DER encoding utilities. ASN is very complex & fragile. Format:
+ *
+ *     [0x30 (SEQUENCE), bytelength, 0x02 (INTEGER), intLength, R, 0x02 (INTEGER), intLength, S]
+ *
+ * Docs: https://letsencrypt.org/docs/a-warm-welcome-to-asn1-and-der/, https://luca.ntop.org/Teaching/Appunti/asn1.html
+ */
 export declare const DER: {
@@ -123,6 +131,13 @@ Err: {
     };
-    _parseInt(data: Uint8Array): {
-        d: bigint;
-        l: Uint8Array;
+    _tlv: {
+        encode: (tag: number, data: string) => string;
+        decode(tag: number, data: Uint8Array): {
+            v: Uint8Array;
+            l: Uint8Array;
+        };
     };
+    _int: {
+        encode(num: bigint): string;
+        decode(data: Uint8Array): bigint;
+    };
     toSig(hex: string | Uint8Array): {
@@ -129,0 +144,0 @@ r: bigint;

abstract/weierstrass.js

@@ -47,4 +47,10 @@ "use strict";
 }
-// ASN.1 DER encoding utilities
 const { bytesToNumberBE: b2n, hexToBytes: h2b } = ut;
+/**
+ * ASN.1 DER encoding utilities. ASN is very complex & fragile. Format:
+ *
+ *     [0x30 (SEQUENCE), bytelength, 0x02 (INTEGER), intLength, R, 0x02 (INTEGER), intLength, S]
+ *
+ * Docs: https://letsencrypt.org/docs/a-warm-welcome-to-asn1-and-der/, https://luca.ntop.org/Teaching/Appunti/asn1.html
+ */
 exports.DER = {
@@ -57,50 +63,99 @@ // asn.1 DER encoding utils
     },
-    _parseInt(data) {
-        const { Err: E } = exports.DER;
-        if (data.length < 2 || data[0] !== 0x02)
-            throw new E('Invalid signature integer tag');
-        const len = data[1];
-        const res = data.subarray(2, len + 2);
-        if (!len || res.length !== len)
-            throw new E('Invalid signature integer: wrong length');
-        // https://crypto.stackexchange.com/a/57734 Leftmost bit of first byte is 'negative' flag,
-        // since we always use positive integers here. It must always be empty:
-        // - add zero byte if exists
-        // - if next byte doesn't have a flag, leading zero is not allowed (minimal encoding)
-        if (res[0] & 0b10000000)
-            throw new E('Invalid signature integer: negative');
-        if (res[0] === 0x00 && !(res[1] & 0b10000000))
-            throw new E('Invalid signature integer: unnecessary leading zero');
-        return { d: b2n(res), l: data.subarray(len + 2) }; // d is data, l is left
+    // Basic building block is TLV (Tag-Length-Value)
+    _tlv: {
+        encode: (tag, data) => {
+            const { Err: E } = exports.DER;
+            if (tag < 0 || tag > 256)
+                throw new E('tlv.encode: wrong tag');
+            if (data.length & 1)
+                throw new E('tlv.encode: unpadded data');
+            const dataLen = data.length / 2;
+            const len = ut.numberToHexUnpadded(dataLen);
+            if ((len.length / 2) & 128)
+                throw new E('tlv.encode: long form length too big');
+            // length of length with long form flag
+            const lenLen = dataLen > 127 ? ut.numberToHexUnpadded((len.length / 2) | 128) : '';
+            return `${ut.numberToHexUnpadded(tag)}${lenLen}${len}${data}`;
+        },
+        // v - value, l - left bytes (unparsed)
+        decode(tag, data) {
+            const { Err: E } = exports.DER;
+            let pos = 0;
+            if (tag < 0 || tag > 256)
+                throw new E('tlv.encode: wrong tag');
+            if (data.length < 2 || data[pos++] !== tag)
+                throw new E('tlv.decode: wrong tlv');
+            const first = data[pos++];
+            const isLong = !!(first & 128); // First bit of first length byte is flag for short/long form
+            let length = 0;
+            if (!isLong)
+                length = first;
+            else {
+                // Long form: [longFlag(1bit), lengthLength(7bit), length (BE)]
+                const lenLen = first & 127;
+                if (!lenLen)
+                    throw new E('tlv.decode(long): indefinite length not supported');
+                if (lenLen > 4)
+                    throw new E('tlv.decode(long): byte length is too big'); // this will overflow u32 in js
+                const lengthBytes = data.subarray(pos, pos + lenLen);
+                if (lengthBytes.length !== lenLen)
+                    throw new E('tlv.decode: length bytes not complete');
+                if (lengthBytes[0] === 0)
+                    throw new E('tlv.decode(long): zero leftmost byte');
+                for (const b of lengthBytes)
+                    length = (length << 8) | b;
+                pos += lenLen;
+                if (length < 128)
+                    throw new E('tlv.decode(long): not minimal encoding');
+            }
+            const v = data.subarray(pos, pos + length);
+            if (v.length !== length)
+                throw new E('tlv.decode: wrong value length');
+            return { v, l: data.subarray(pos + length) };
+        },
     },
+    // https://crypto.stackexchange.com/a/57734 Leftmost bit of first byte is 'negative' flag,
+    // since we always use positive integers here. It must always be empty:
+    // - add zero byte if exists
+    // - if next byte doesn't have a flag, leading zero is not allowed (minimal encoding)
+    _int: {
+        encode(num) {
+            const { Err: E } = exports.DER;
+            if (num < _0n)
+                throw new E('integer: negative integers are not allowed');
+            let hex = ut.numberToHexUnpadded(num);
+            // Pad with zero byte if negative flag is present
+            if (Number.parseInt(hex[0], 16) & 0b1000)
+                hex = '00' + hex;
+            if (hex.length & 1)
+                throw new E('unexpected assertion');
+            return hex;
+        },
+        decode(data) {
+            const { Err: E } = exports.DER;
+            if (data[0] & 128)
+                throw new E('Invalid signature integer: negative');
+            if (data[0] === 0x00 && !(data[1] & 128))
+                throw new E('Invalid signature integer: unnecessary leading zero');
+            return b2n(data);
+        },
+    },
     toSig(hex) {
         // parse DER signature
-        const { Err: E } = exports.DER;
+        const { Err: E, _int: int, _tlv: tlv } = exports.DER;
         const data = typeof hex === 'string' ? h2b(hex) : hex;
         ut.abytes(data);
-        let l = data.length;
-        if (l < 2 || data[0] != 0x30)
-            throw new E('Invalid signature tag');
-        if (data[1] !== l - 2)
-            throw new E('Invalid signature: incorrect length');
-        const { d: r, l: sBytes } = exports.DER._parseInt(data.subarray(2));
-        const { d: s, l: rBytesLeft } = exports.DER._parseInt(sBytes);
-        if (rBytesLeft.length)
+        const { v: seqBytes, l: seqLeftBytes } = tlv.decode(0x30, data);
+        if (seqLeftBytes.length)
             throw new E('Invalid signature: left bytes after parsing');
-        return { r, s };
+        const { v: rBytes, l: rLeftBytes } = tlv.decode(0x02, seqBytes);
+        const { v: sBytes, l: sLeftBytes } = tlv.decode(0x02, rLeftBytes);
+        if (sLeftBytes.length)
+            throw new E('Invalid signature: left bytes after parsing');
+        return { r: int.decode(rBytes), s: int.decode(sBytes) };
     },
     hexFromSig(sig) {
-        // Add leading zero if first byte has negative bit enabled. More details in '_parseInt'
-        const slice = (s) => (Number.parseInt(s[0], 16) & 0b1000 ? '00' + s : s);
-        const h = (num) => {
-            const hex = num.toString(16);
-            return hex.length & 1 ? `0${hex}` : hex;
-        };
-        const s = slice(h(sig.s));
-        const r = slice(h(sig.r));
-        const shl = s.length / 2;
-        const rhl = r.length / 2;
-        const sl = h(shl);
-        const rl = h(rhl);
-        return `30${h(rhl + shl + 4)}02${rl}${r}02${sl}${s}`;
+        const { _tlv: tlv, _int: int } = exports.DER;
+        const seq = `${tlv.encode(0x02, int.encode(sig.r))}${tlv.encode(0x02, int.encode(sig.s))}`;
+        return tlv.encode(0x30, seq);
     },
@@ -114,2 +169,3 @@ };
     const { Fp } = CURVE; // All curves has same field / group length as for now, but they can differ
+    const Fn = mod.Field(CURVE.n, CURVE.nBitLength);
     const toBytes = CURVE.toBytes ||
@@ -288,2 +344,6 @@ ((_c, point, _isCompressed) => {
         }
+        // Multiscalar Multiplication
+        static msm(points, scalars) {
+            return (0, curve_js_1.pippenger)(Point, Fn, points, scalars);
+        }
         // "Private method", don't use it directly
@@ -290,0 +350,0 @@ _setWindowSize(windowSize) {

esm/abstract/curve.d.ts

@@ -54,2 +54,14 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 };
+/**
+ * Pippenger algorithm for multi-scalar multiplication (MSM).
+ * MSM is basically (Pa + Qb + Rc + ...).
+ * 30x faster vs naive addition on L=4096, 10x faster with precomputes.
+ * For N=254bit, L=1, it does: 1024 ADD + 254 DBL. For L=5: 1536 ADD + 254 DBL.
+ * Algorithmically constant-time (for same L), even when 1 point + scalar, or when scalar = 0.
+ * @param c Curve Point constructor
+ * @param field field over CURVE.N - important that it's not over CURVE.P
+ * @param points array of L curve points
+ * @param scalars array of L scalars (aka private keys / bigints)
+ */
+export declare function pippenger<T extends Group<T>>(c: GroupConstructor<T>, field: IField<bigint>, points: T[], scalars: bigint[]): T;
 export type BasicCurve<T> = {
@@ -56,0 +68,0 @@ Fp: IField<T>;

esm/abstract/curve.js

 /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 // Abelian group utilities
 import { validateField, nLength } from './modular.js';
-import { validateObject } from './utils.js';
+import { validateObject, bitLen } from './utils.js';
 const _0n = BigInt(0);
@@ -153,2 +153,56 @@ const _1n = BigInt(1);
 }
+/**
+ * Pippenger algorithm for multi-scalar multiplication (MSM).
+ * MSM is basically (Pa + Qb + Rc + ...).
+ * 30x faster vs naive addition on L=4096, 10x faster with precomputes.
+ * For N=254bit, L=1, it does: 1024 ADD + 254 DBL. For L=5: 1536 ADD + 254 DBL.
+ * Algorithmically constant-time (for same L), even when 1 point + scalar, or when scalar = 0.
+ * @param c Curve Point constructor
+ * @param field field over CURVE.N - important that it's not over CURVE.P
+ * @param points array of L curve points
+ * @param scalars array of L scalars (aka private keys / bigints)
+ */
+export function pippenger(c, field, points, scalars) {
+    // If we split scalars by some window (let's say 8 bits), every chunk will only
+    // take 256 buckets even if there are 4096 scalars, also re-uses double.
+    // TODO:
+    // - https://eprint.iacr.org/2024/750.pdf
+    // - https://tches.iacr.org/index.php/TCHES/article/view/10287
+    // 0 is accepted in scalars
+    if (!Array.isArray(points) || !Array.isArray(scalars) || scalars.length !== points.length)
+        throw new Error('arrays of points and scalars must have equal length');
+    scalars.forEach((s, i) => {
+        if (!field.isValid(s))
+            throw new Error(`wrong scalar at index ${i}`);
+    });
+    points.forEach((p, i) => {
+        if (!(p instanceof c))
+            throw new Error(`wrong point at index ${i}`);
+    });
+    const wbits = bitLen(BigInt(points.length));
+    const windowSize = wbits > 12 ? wbits - 3 : wbits > 4 ? wbits - 2 : wbits ? 2 : 1; // in bits
+    const MASK = (1 << windowSize) - 1;
+    const buckets = new Array(MASK + 1).fill(c.ZERO); // +1 for zero array
+    const lastBits = Math.floor((field.BITS - 1) / windowSize) * windowSize;
+    let sum = c.ZERO;
+    for (let i = lastBits; i >= 0; i -= windowSize) {
+        buckets.fill(c.ZERO);
+        for (let j = 0; j < scalars.length; j++) {
+            const scalar = scalars[j];
+            const wbits = Number((scalar >> BigInt(i)) & BigInt(MASK));
+            buckets[wbits] = buckets[wbits].add(points[j]);
+        }
+        let resI = c.ZERO; // not using this will do small speed-up, but will lose ct
+        // Skip first bucket, because it is zero
+        for (let j = buckets.length - 1, sumI = c.ZERO; j > 0; j--) {
+            sumI = sumI.add(buckets[j]);
+            resI = resI.add(sumI);
+        }
+        sum = sum.add(resI);
+        if (i !== 0)
+            for (let j = 0; j < windowSize; j++)
+                sum = sum.double();
+    }
+    return sum;
+}
 export function validateBasic(curve) {
@@ -155,0 +209,0 @@ validateField(curve.Fp);

esm/abstract/edwards.d.ts

@@ -64,2 +64,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
     fromPrivateKey(privateKey: Hex): ExtPointType;
+    msm(points: ExtPointType[], scalars: bigint[]): ExtPointType;
 }
@@ -66,0 +67,0 @@ /**

esm/abstract/edwards.js

 /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 // Twisted Edwards curve. The formula is: ax² + y² = 1 + dx²y²
-import { validateBasic, wNAF } from './curve.js';
-import { mod } from './modular.js';
+import { validateBasic, wNAF, pippenger, } from './curve.js';
+import { mod, Field } from './modular.js';
 import * as ut from './utils.js';
@@ -40,2 +40,3 @@ import { ensureBytes, memoized, abool } from './utils.js';
     const modP = Fp.create; // Function overrides
+    const Fn = Field(CURVE.n, CURVE.nBitLength);
     // sqrt(u/v)
@@ -139,2 +140,6 @@ const uvRatio = CURVE.uvRatio ||
         }
+        // Multiscalar Multiplication
+        static msm(points, scalars) {
+            return pippenger(Point, Fn, points, scalars);
+        }
         // "Private method", don't use it directly
@@ -141,0 +146,0 @@ _setWindowSize(windowSize) {

esm/abstract/hash-to-curve.js

@@ -7,2 +7,4 @@ import { mod } from './modular.js';
 function i2osp(value, length) {
+    anum(value);
+    anum(length);
     if (value < 0 || value >= 1 << (8 * length)) {
@@ -40,4 +42,4 @@ throw new Error(`bad I2OSP call: value=${value} length=${length}`);
     const ell = Math.ceil(lenInBytes / b_in_bytes);
-    if (ell > 255)
-        throw new Error('Invalid xmd length');
+    if (lenInBytes > 65535 || ell > 255)
+        throw new Error('expand_message_xmd: invalid lenInBytes');
     const DST_prime = concatBytes(DST, i2osp(DST.length, 1));
@@ -44,0 +46,0 @@ const Z_pad = i2osp(0, r_in_bytes);

esm/abstract/tower.d.ts

@@ -0,1 +1,2 @@
+/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 import * as mod from './modular.js';
@@ -2,0 +3,0 @@ import type { ProjConstructor, ProjPointType } from './weierstrass.js';

esm/abstract/tower.js

@@ -0,1 +1,2 @@
+/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 import * as mod from './modular.js';
@@ -2,0 +3,0 @@ import { bitLen, bitMask, concatBytes, notImplemented } from './utils.js';

esm/abstract/weierstrass.d.ts

@@ -80,2 +80,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
     normalizeZ(points: ProjPointType<T>[]): ProjPointType<T>[];
+    msm(points: ProjPointType<T>[], scalars: bigint[]): ProjPointType<T>;
 }
@@ -114,2 +115,9 @@ export type CurvePointsType<T> = BasicWCurve<T> & {
 };
+/**
+ * ASN.1 DER encoding utilities. ASN is very complex & fragile. Format:
+ *
+ *     [0x30 (SEQUENCE), bytelength, 0x02 (INTEGER), intLength, R, 0x02 (INTEGER), intLength, S]
+ *
+ * Docs: https://letsencrypt.org/docs/a-warm-welcome-to-asn1-and-der/, https://luca.ntop.org/Teaching/Appunti/asn1.html
+ */
 export declare const DER: {
@@ -123,6 +131,13 @@ Err: {
     };
-    _parseInt(data: Uint8Array): {
-        d: bigint;
-        l: Uint8Array;
+    _tlv: {
+        encode: (tag: number, data: string) => string;
+        decode(tag: number, data: Uint8Array): {
+            v: Uint8Array;
+            l: Uint8Array;
+        };
     };
+    _int: {
+        encode(num: bigint): string;
+        decode(data: Uint8Array): bigint;
+    };
     toSig(hex: string | Uint8Array): {
@@ -129,0 +144,0 @@ r: bigint;

esm/abstract/weierstrass.js

 /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 // Short Weierstrass curve. The formula is: y² = x³ + ax + b
-import { validateBasic, wNAF } from './curve.js';
+import { validateBasic, wNAF, pippenger, } from './curve.js';
 import * as mod from './modular.js';
@@ -40,4 +40,10 @@ import * as ut from './utils.js';
 }
-// ASN.1 DER encoding utilities
 const { bytesToNumberBE: b2n, hexToBytes: h2b } = ut;
+/**
+ * ASN.1 DER encoding utilities. ASN is very complex & fragile. Format:
+ *
+ *     [0x30 (SEQUENCE), bytelength, 0x02 (INTEGER), intLength, R, 0x02 (INTEGER), intLength, S]
+ *
+ * Docs: https://letsencrypt.org/docs/a-warm-welcome-to-asn1-and-der/, https://luca.ntop.org/Teaching/Appunti/asn1.html
+ */
 export const DER = {
@@ -50,50 +56,99 @@ // asn.1 DER encoding utils
     },
-    _parseInt(data) {
-        const { Err: E } = DER;
-        if (data.length < 2 || data[0] !== 0x02)
-            throw new E('Invalid signature integer tag');
-        const len = data[1];
-        const res = data.subarray(2, len + 2);
-        if (!len || res.length !== len)
-            throw new E('Invalid signature integer: wrong length');
-        // https://crypto.stackexchange.com/a/57734 Leftmost bit of first byte is 'negative' flag,
-        // since we always use positive integers here. It must always be empty:
-        // - add zero byte if exists
-        // - if next byte doesn't have a flag, leading zero is not allowed (minimal encoding)
-        if (res[0] & 0b10000000)
-            throw new E('Invalid signature integer: negative');
-        if (res[0] === 0x00 && !(res[1] & 0b10000000))
-            throw new E('Invalid signature integer: unnecessary leading zero');
-        return { d: b2n(res), l: data.subarray(len + 2) }; // d is data, l is left
+    // Basic building block is TLV (Tag-Length-Value)
+    _tlv: {
+        encode: (tag, data) => {
+            const { Err: E } = DER;
+            if (tag < 0 || tag > 256)
+                throw new E('tlv.encode: wrong tag');
+            if (data.length & 1)
+                throw new E('tlv.encode: unpadded data');
+            const dataLen = data.length / 2;
+            const len = ut.numberToHexUnpadded(dataLen);
+            if ((len.length / 2) & 128)
+                throw new E('tlv.encode: long form length too big');
+            // length of length with long form flag
+            const lenLen = dataLen > 127 ? ut.numberToHexUnpadded((len.length / 2) | 128) : '';
+            return `${ut.numberToHexUnpadded(tag)}${lenLen}${len}${data}`;
+        },
+        // v - value, l - left bytes (unparsed)
+        decode(tag, data) {
+            const { Err: E } = DER;
+            let pos = 0;
+            if (tag < 0 || tag > 256)
+                throw new E('tlv.encode: wrong tag');
+            if (data.length < 2 || data[pos++] !== tag)
+                throw new E('tlv.decode: wrong tlv');
+            const first = data[pos++];
+            const isLong = !!(first & 128); // First bit of first length byte is flag for short/long form
+            let length = 0;
+            if (!isLong)
+                length = first;
+            else {
+                // Long form: [longFlag(1bit), lengthLength(7bit), length (BE)]
+                const lenLen = first & 127;
+                if (!lenLen)
+                    throw new E('tlv.decode(long): indefinite length not supported');
+                if (lenLen > 4)
+                    throw new E('tlv.decode(long): byte length is too big'); // this will overflow u32 in js
+                const lengthBytes = data.subarray(pos, pos + lenLen);
+                if (lengthBytes.length !== lenLen)
+                    throw new E('tlv.decode: length bytes not complete');
+                if (lengthBytes[0] === 0)
+                    throw new E('tlv.decode(long): zero leftmost byte');
+                for (const b of lengthBytes)
+                    length = (length << 8) | b;
+                pos += lenLen;
+                if (length < 128)
+                    throw new E('tlv.decode(long): not minimal encoding');
+            }
+            const v = data.subarray(pos, pos + length);
+            if (v.length !== length)
+                throw new E('tlv.decode: wrong value length');
+            return { v, l: data.subarray(pos + length) };
+        },
     },
+    // https://crypto.stackexchange.com/a/57734 Leftmost bit of first byte is 'negative' flag,
+    // since we always use positive integers here. It must always be empty:
+    // - add zero byte if exists
+    // - if next byte doesn't have a flag, leading zero is not allowed (minimal encoding)
+    _int: {
+        encode(num) {
+            const { Err: E } = DER;
+            if (num < _0n)
+                throw new E('integer: negative integers are not allowed');
+            let hex = ut.numberToHexUnpadded(num);
+            // Pad with zero byte if negative flag is present
+            if (Number.parseInt(hex[0], 16) & 0b1000)
+                hex = '00' + hex;
+            if (hex.length & 1)
+                throw new E('unexpected assertion');
+            return hex;
+        },
+        decode(data) {
+            const { Err: E } = DER;
+            if (data[0] & 128)
+                throw new E('Invalid signature integer: negative');
+            if (data[0] === 0x00 && !(data[1] & 128))
+                throw new E('Invalid signature integer: unnecessary leading zero');
+            return b2n(data);
+        },
+    },
     toSig(hex) {
         // parse DER signature
-        const { Err: E } = DER;
+        const { Err: E, _int: int, _tlv: tlv } = DER;
         const data = typeof hex === 'string' ? h2b(hex) : hex;
         ut.abytes(data);
-        let l = data.length;
-        if (l < 2 || data[0] != 0x30)
-            throw new E('Invalid signature tag');
-        if (data[1] !== l - 2)
-            throw new E('Invalid signature: incorrect length');
-        const { d: r, l: sBytes } = DER._parseInt(data.subarray(2));
-        const { d: s, l: rBytesLeft } = DER._parseInt(sBytes);
-        if (rBytesLeft.length)
+        const { v: seqBytes, l: seqLeftBytes } = tlv.decode(0x30, data);
+        if (seqLeftBytes.length)
             throw new E('Invalid signature: left bytes after parsing');
-        return { r, s };
+        const { v: rBytes, l: rLeftBytes } = tlv.decode(0x02, seqBytes);
+        const { v: sBytes, l: sLeftBytes } = tlv.decode(0x02, rLeftBytes);
+        if (sLeftBytes.length)
+            throw new E('Invalid signature: left bytes after parsing');
+        return { r: int.decode(rBytes), s: int.decode(sBytes) };
     },
     hexFromSig(sig) {
-        // Add leading zero if first byte has negative bit enabled. More details in '_parseInt'
-        const slice = (s) => (Number.parseInt(s[0], 16) & 0b1000 ? '00' + s : s);
-        const h = (num) => {
-            const hex = num.toString(16);
-            return hex.length & 1 ? `0${hex}` : hex;
-        };
-        const s = slice(h(sig.s));
-        const r = slice(h(sig.r));
-        const shl = s.length / 2;
-        const rhl = r.length / 2;
-        const sl = h(shl);
-        const rl = h(rhl);
-        return `30${h(rhl + shl + 4)}02${rl}${r}02${sl}${s}`;
+        const { _tlv: tlv, _int: int } = DER;
+        const seq = `${tlv.encode(0x02, int.encode(sig.r))}${tlv.encode(0x02, int.encode(sig.s))}`;
+        return tlv.encode(0x30, seq);
     },
@@ -107,2 +162,3 @@ };
     const { Fp } = CURVE; // All curves has same field / group length as for now, but they can differ
+    const Fn = mod.Field(CURVE.n, CURVE.nBitLength);
     const toBytes = CURVE.toBytes ||
@@ -281,2 +337,6 @@ ((_c, point, _isCompressed) => {
         }
+        // Multiscalar Multiplication
+        static msm(points, scalars) {
+            return pippenger(Point, Fn, points, scalars);
+        }
         // "Private method", don't use it directly
@@ -283,0 +343,0 @@ _setWindowSize(windowSize) {

esm/jubjub.js

@@ -43,13 +43,19 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 }
+// No secret data is leaked here at all.
+// It operates over public data:
+// const G_SPEND = jubjub.findGroupHash(new Uint8Array(), utf8ToBytes('Item_G_'));
 export function findGroupHash(m, personalization) {
     const tag = concatBytes(m, new Uint8Array([0]));
+    const hashes = [];
     for (let i = 0; i < 256; i++) {
         tag[tag.length - 1] = i;
         try {
-            return groupHash(tag, personalization);
+            hashes.push(groupHash(tag, personalization));
         }
         catch (e) { }
     }
-    throw new Error('findGroupHash tag overflow');
+    if (!hashes.length)
+        throw new Error('findGroupHash tag overflow');
+    return hashes[0];
 }
 //# sourceMappingURL=jubjub.js.map

jubjub.js

@@ -48,13 +48,19 @@ "use strict";
 }
+// No secret data is leaked here at all.
+// It operates over public data:
+// const G_SPEND = jubjub.findGroupHash(new Uint8Array(), utf8ToBytes('Item_G_'));
 function findGroupHash(m, personalization) {
     const tag = (0, utils_1.concatBytes)(m, new Uint8Array([0]));
+    const hashes = [];
     for (let i = 0; i < 256; i++) {
         tag[tag.length - 1] = i;
         try {
-            return groupHash(tag, personalization);
+            hashes.push(groupHash(tag, personalization));
         }
         catch (e) { }
     }
-    throw new Error('findGroupHash tag overflow');
+    if (!hashes.length)
+        throw new Error('findGroupHash tag overflow');
+    return hashes[0];
 }
 //# sourceMappingURL=jubjub.js.map

package.json

 {
   "name": "@noble/curves",
-  "version": "1.5.0",
+  "version": "1.6.0",
   "description": "Audited & minimal JS implementation of elliptic curve cryptography",
@@ -31,3 +31,3 @@ "files": [
   "dependencies": {
-    "@noble/hashes": "1.4.0"
+    "@noble/hashes": "1.5.0"
   },
@@ -49,2 +49,10 @@ "devDependencies": {
     },
+    "./abstract/bls": {
+      "import": "./esm/abstract/bls.js",
+      "require": "./abstract/bls.js"
+    },
+    "./abstract/curve": {
+      "import": "./esm/abstract/curve.js",
+      "require": "./abstract/curve.js"
+    },
     "./abstract/edwards": {
@@ -54,2 +62,6 @@ "import": "./esm/abstract/edwards.js",
     },
+    "./abstract/hash-to-curve": {
+      "import": "./esm/abstract/hash-to-curve.js",
+      "require": "./abstract/hash-to-curve.js"
+    },
     "./abstract/modular": {
@@ -63,18 +75,10 @@ "import": "./esm/abstract/modular.js",
     },
-    "./abstract/weierstrass": {
-      "import": "./esm/abstract/weierstrass.js",
-      "require": "./abstract/weierstrass.js"
+    "./abstract/poseidon": {
+      "import": "./esm/abstract/poseidon.js",
+      "require": "./abstract/poseidon.js"
     },
-    "./abstract/bls": {
-      "import": "./esm/abstract/bls.js",
-      "require": "./abstract/bls.js"
+    "./abstract/tower": {
+      "import": "./esm/abstract/tower.js",
+      "require": "./abstract/tower.js"
     },
-    "./abstract/hash-to-curve": {
-      "import": "./esm/abstract/hash-to-curve.js",
-      "require": "./abstract/hash-to-curve.js"
-    },
-    "./abstract/curve": {
-      "import": "./esm/abstract/curve.js",
-      "require": "./abstract/curve.js"
-    },
     "./abstract/utils": {
@@ -84,5 +88,5 @@ "import": "./esm/abstract/utils.js",
     },
-    "./abstract/poseidon": {
-      "import": "./esm/abstract/poseidon.js",
-      "require": "./abstract/poseidon.js"
+    "./abstract/weierstrass": {
+      "import": "./esm/abstract/weierstrass.js",
+      "require": "./abstract/weierstrass.js"
     },
@@ -138,2 +142,5 @@ "./_shortw_utils": {
   },
+  "engines": {
+    "node": "^14.21.3 || >=16"
+  },
   "keywords": [
@@ -140,0 +147,0 @@ "elliptic",

README.md

@@ -5,3 +5,3 @@ # noble-curves
 
-- 🔒 [**Audited**](#security) by an independent security firms
+- 🔒 [**Audited**](#security) by independent security firms
 - 🔻 Tree-shakeable: unused code is excluded from your builds
@@ -14,7 +14,5 @@ - 🏎 Fast: hand-optimized for caveats of JS engines
 - 🧜‍♂️ Poseidon ZK-friendly hash
-- 🪶 178KB (87KB gzipped) for everything including bundled hashes, 22KB (10KB gzipped) for single-curve build
+- 🪶 190KB (92KB gzipped) for everything with hashes, 22KB (10KB gzipped) for single-curve build
 
-For discussions, questions and support, visit
-[GitHub Discussions](https://github.com/paulmillr/noble-curves/discussions)
-section of the repository.
+Take a glance at [GitHub Discussions](https://github.com/paulmillr/noble-curves/discussions) for questions and support.
 
@@ -50,3 +48,3 @@ ### This library belongs to _noble_ cryptography
 import { secp256k1 } from '@noble/curves/secp256k1'; // ESM and Common.js
-// import { secp256k1 } from 'npm:@noble/curves@1.4.0/secp256k1'; // Deno
+// import { secp256k1 } from 'npm:@noble/curves@1.6.0/secp256k1'; // Deno
 ```
@@ -63,2 +61,3 @@
   - [bn254 aka alt_bn128](#bn254-aka-alt_bn128)
+  - [Multi-scalar-multiplication](#multi-scalar-multiplication)
   - [All available imports](#all-available-imports)
@@ -70,3 +69,3 @@ - [Accessing a curve's variables](#accessing-a-curves-variables)
   - [montgomery: Montgomery curve](#montgomery-montgomery-curve)
-  - [bls: Boneh-Lynn-Shacham signatures](#bls-boneh-lynn-shacham-signatures)
+  - [bls: Barreto-Lynn-Scott curves](#bls-barreto-lynn-scott-curves)
   - [hash-to-curve: Hashing strings to curve points](#hash-to-curve-hashing-strings-to-curve-points)
@@ -319,2 +318,15 @@ - [poseidon: Poseidon hash](#poseidon-poseidon-hash)
 
+#### Multi-scalar-multiplication
+
+```ts
+import { secp256k1 } from '@noble/curves/secp256k1';
+const p = secp256k1.ProjectivePoint;
+const points = [p.BASE, p.BASE.multiply(2n), p.BASE.multiply(4n), p.BASE.multiply(8n)];
+p.msm(points, [3n, 5n, 7n, 11n]).equals(p.BASE.multiply(129n)); // 129*G
+```
+
+Pippenger algorithm is used underneath.
+Multi-scalar-multiplication (MSM) is basically `(Pa + Qb + Rc + ...)`.
+It's 10-30x faster vs naive addition for large amount of points.
+
 #### All available imports
@@ -471,2 +483,3 @@
   fromPrivateKey(privateKey: PrivKey): ProjPointType<T>;
+  msm(points: ProjPointType[], scalars: bigint[]): ProjPointType<T>;
 }
@@ -624,2 +637,3 @@ ```
   fromPrivateKey(privateKey: Hex): ExtPointType;
+  msm(points: ExtPointType[], scalars: bigint[]): ExtPointType;
 }
@@ -826,2 +840,7 @@ ```
 
+- at version 1.6.0, in Sep 2024, by [cure53](https://cure53.de)
+  - PDFs: [in-repo](./audit/2024-09-cure53-audit-nbl4.pdf)
+  - [Changes since audit](https://github.com/paulmillr/noble-curves/compare/1.6.0..main)
+  - Scope: ed25519, ed448, their add-ons, bls12-381, bn254,
+    hash-to-curve, low-level primitives bls, tower, edwards, montgomery etc.
 - at version 1.2.0, in Sep 2023, by [Kudelski Security](https://kudelskisecurity.com)
@@ -828,0 +847,0 @@ - PDFs: [offline](./audit/2023-09-kudelski-audit-starknet.pdf)

src/abstract/curve.ts

 /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 // Abelian group utilities
 import { IField, validateField, nLength } from './modular.js';
-import { validateObject } from './utils.js';
+import { validateObject, bitLen } from './utils.js';
 const _0n = BigInt(0);
@@ -184,2 +184,58 @@ const _1n = BigInt(1);
 
+/**
+ * Pippenger algorithm for multi-scalar multiplication (MSM).
+ * MSM is basically (Pa + Qb + Rc + ...).
+ * 30x faster vs naive addition on L=4096, 10x faster with precomputes.
+ * For N=254bit, L=1, it does: 1024 ADD + 254 DBL. For L=5: 1536 ADD + 254 DBL.
+ * Algorithmically constant-time (for same L), even when 1 point + scalar, or when scalar = 0.
+ * @param c Curve Point constructor
+ * @param field field over CURVE.N - important that it's not over CURVE.P
+ * @param points array of L curve points
+ * @param scalars array of L scalars (aka private keys / bigints)
+ */
+export function pippenger<T extends Group<T>>(
+  c: GroupConstructor<T>,
+  field: IField<bigint>,
+  points: T[],
+  scalars: bigint[]
+): T {
+  // If we split scalars by some window (let's say 8 bits), every chunk will only
+  // take 256 buckets even if there are 4096 scalars, also re-uses double.
+  // TODO:
+  // - https://eprint.iacr.org/2024/750.pdf
+  // - https://tches.iacr.org/index.php/TCHES/article/view/10287
+  // 0 is accepted in scalars
+  if (!Array.isArray(points) || !Array.isArray(scalars) || scalars.length !== points.length)
+    throw new Error('arrays of points and scalars must have equal length');
+  scalars.forEach((s, i) => {
+    if (!field.isValid(s)) throw new Error(`wrong scalar at index ${i}`);
+  });
+  points.forEach((p, i) => {
+    if (!(p instanceof (c as any))) throw new Error(`wrong point at index ${i}`);
+  });
+  const wbits = bitLen(BigInt(points.length));
+  const windowSize = wbits > 12 ? wbits - 3 : wbits > 4 ? wbits - 2 : wbits ? 2 : 1; // in bits
+  const MASK = (1 << windowSize) - 1;
+  const buckets = new Array(MASK + 1).fill(c.ZERO); // +1 for zero array
+  const lastBits = Math.floor((field.BITS - 1) / windowSize) * windowSize;
+  let sum = c.ZERO;
+  for (let i = lastBits; i >= 0; i -= windowSize) {
+    buckets.fill(c.ZERO);
+    for (let j = 0; j < scalars.length; j++) {
+      const scalar = scalars[j];
+      const wbits = Number((scalar >> BigInt(i)) & BigInt(MASK));
+      buckets[wbits] = buckets[wbits].add(points[j]);
+    }
+    let resI = c.ZERO; // not using this will do small speed-up, but will lose ct
+    // Skip first bucket, because it is zero
+    for (let j = buckets.length - 1, sumI = c.ZERO; j > 0; j--) {
+      sumI = sumI.add(buckets[j]);
+      resI = resI.add(sumI);
+    }
+    sum = sum.add(resI);
+    if (i !== 0) for (let j = 0; j < windowSize; j++) sum = sum.double();
+  }
+  return sum as T;
+}
+
 // Generic BasicCurve interface: works even for polynomial fields (BLS): P, n, h would be ok.
@@ -186,0 +242,0 @@ // Though generator can be different (Fp2 / Fp6 for BLS).

src/abstract/edwards.ts

 /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 // Twisted Edwards curve. The formula is: ax² + y² = 1 + dx²y²
-import { AffinePoint, BasicCurve, Group, GroupConstructor, validateBasic, wNAF } from './curve.js';
-import { mod } from './modular.js';
+import {
+  AffinePoint,
+  BasicCurve,
+  Group,
+  GroupConstructor,
+  validateBasic,
+  wNAF,
+  pippenger,
+} from './curve.js';
+import { mod, Field } from './modular.js';
 import * as ut from './utils.js';
@@ -73,2 +81,3 @@ import { ensureBytes, FHash, Hex, memoized, abool } from './utils.js';
   fromPrivateKey(privateKey: Hex): ExtPointType;
+  msm(points: ExtPointType[], scalars: bigint[]): ExtPointType;
 }
@@ -123,2 +132,3 @@
   const modP = Fp.create; // Function overrides
+  const Fn = Field(CURVE.n, CURVE.nBitLength);
 
@@ -223,2 +233,6 @@ // sqrt(u/v)
     }
+    // Multiscalar Multiplication
+    static msm(points: Point[], scalars: bigint[]) {
+      return pippenger(Point, Fn, points, scalars);
+    }
 
@@ -225,0 +239,0 @@ // "Private method", don't use it directly

src/abstract/hash-to-curve.ts

@@ -30,2 +30,4 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 function i2osp(value: number, length: number): Uint8Array {
+  anum(value);
+  anum(length);
   if (value < 0 || value >= 1 << (8 * length)) {
@@ -69,3 +71,3 @@ throw new Error(`bad I2OSP call: value=${value} length=${length}`);
   const ell = Math.ceil(lenInBytes / b_in_bytes);
-  if (ell > 255) throw new Error('Invalid xmd length');
+  if (lenInBytes > 65535 || ell > 255) throw new Error('expand_message_xmd: invalid lenInBytes');
   const DST_prime = concatBytes(DST, i2osp(DST.length, 1));
@@ -72,0 +74,0 @@ const Z_pad = i2osp(0, r_in_bytes);

src/abstract/tower.ts

@@ -0,1 +1,2 @@
+/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 import * as mod from './modular.js';
@@ -2,0 +3,0 @@ import { bitLen, bitMask, concatBytes, notImplemented } from './utils.js';

src/abstract/weierstrass.ts

 /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 // Short Weierstrass curve. The formula is: y² = x³ + ax + b
-import { AffinePoint, BasicCurve, Group, GroupConstructor, validateBasic, wNAF } from './curve.js';
+import {
+  AffinePoint,
+  BasicCurve,
+  Group,
+  GroupConstructor,
+  validateBasic,
+  wNAF,
+  pippenger,
+} from './curve.js';
 import * as mod from './modular.js';
@@ -88,2 +96,3 @@ import * as ut from './utils.js';
   normalizeZ(points: ProjPointType<T>[]): ProjPointType<T>[];
+  msm(points: ProjPointType<T>[], scalars: bigint[]): ProjPointType<T>;
 }
@@ -139,4 +148,11 @@
 
-// ASN.1 DER encoding utilities
 const { bytesToNumberBE: b2n, hexToBytes: h2b } = ut;
+
+/**
+ * ASN.1 DER encoding utilities. ASN is very complex & fragile. Format:
+ *
+ *     [0x30 (SEQUENCE), bytelength, 0x02 (INTEGER), intLength, R, 0x02 (INTEGER), intLength, S]
+ *
+ * Docs: https://letsencrypt.org/docs/a-warm-welcome-to-asn1-and-der/, https://luca.ntop.org/Teaching/Appunti/asn1.html
+ */
 export const DER = {
@@ -149,44 +165,80 @@ // asn.1 DER encoding utils
   },
-  _parseInt(data: Uint8Array): { d: bigint; l: Uint8Array } {
-    const { Err: E } = DER;
-    if (data.length < 2 || data[0] !== 0x02) throw new E('Invalid signature integer tag');
-    const len = data[1];
-    const res = data.subarray(2, len + 2);
-    if (!len || res.length !== len) throw new E('Invalid signature integer: wrong length');
-    // https://crypto.stackexchange.com/a/57734 Leftmost bit of first byte is 'negative' flag,
-    // since we always use positive integers here. It must always be empty:
-    // - add zero byte if exists
-    // - if next byte doesn't have a flag, leading zero is not allowed (minimal encoding)
-    if (res[0] & 0b10000000) throw new E('Invalid signature integer: negative');
-    if (res[0] === 0x00 && !(res[1] & 0b10000000))
-      throw new E('Invalid signature integer: unnecessary leading zero');
-    return { d: b2n(res), l: data.subarray(len + 2) }; // d is data, l is left
+  // Basic building block is TLV (Tag-Length-Value)
+  _tlv: {
+    encode: (tag: number, data: string) => {
+      const { Err: E } = DER;
+      if (tag < 0 || tag > 256) throw new E('tlv.encode: wrong tag');
+      if (data.length & 1) throw new E('tlv.encode: unpadded data');
+      const dataLen = data.length / 2;
+      const len = ut.numberToHexUnpadded(dataLen);
+      if ((len.length / 2) & 0b1000_0000) throw new E('tlv.encode: long form length too big');
+      // length of length with long form flag
+      const lenLen = dataLen > 127 ? ut.numberToHexUnpadded((len.length / 2) | 0b1000_0000) : '';
+      return `${ut.numberToHexUnpadded(tag)}${lenLen}${len}${data}`;
+    },
+    // v - value, l - left bytes (unparsed)
+    decode(tag: number, data: Uint8Array): { v: Uint8Array; l: Uint8Array } {
+      const { Err: E } = DER;
+      let pos = 0;
+      if (tag < 0 || tag > 256) throw new E('tlv.encode: wrong tag');
+      if (data.length < 2 || data[pos++] !== tag) throw new E('tlv.decode: wrong tlv');
+      const first = data[pos++];
+      const isLong = !!(first & 0b1000_0000); // First bit of first length byte is flag for short/long form
+      let length = 0;
+      if (!isLong) length = first;
+      else {
+        // Long form: [longFlag(1bit), lengthLength(7bit), length (BE)]
+        const lenLen = first & 0b0111_1111;
+        if (!lenLen) throw new E('tlv.decode(long): indefinite length not supported');
+        if (lenLen > 4) throw new E('tlv.decode(long): byte length is too big'); // this will overflow u32 in js
+        const lengthBytes = data.subarray(pos, pos + lenLen);
+        if (lengthBytes.length !== lenLen) throw new E('tlv.decode: length bytes not complete');
+        if (lengthBytes[0] === 0) throw new E('tlv.decode(long): zero leftmost byte');
+        for (const b of lengthBytes) length = (length << 8) | b;
+        pos += lenLen;
+        if (length < 128) throw new E('tlv.decode(long): not minimal encoding');
+      }
+      const v = data.subarray(pos, pos + length);
+      if (v.length !== length) throw new E('tlv.decode: wrong value length');
+      return { v, l: data.subarray(pos + length) };
+    },
   },
+  // https://crypto.stackexchange.com/a/57734 Leftmost bit of first byte is 'negative' flag,
+  // since we always use positive integers here. It must always be empty:
+  // - add zero byte if exists
+  // - if next byte doesn't have a flag, leading zero is not allowed (minimal encoding)
+  _int: {
+    encode(num: bigint) {
+      const { Err: E } = DER;
+      if (num < _0n) throw new E('integer: negative integers are not allowed');
+      let hex = ut.numberToHexUnpadded(num);
+      // Pad with zero byte if negative flag is present
+      if (Number.parseInt(hex[0], 16) & 0b1000) hex = '00' + hex;
+      if (hex.length & 1) throw new E('unexpected assertion');
+      return hex;
+    },
+    decode(data: Uint8Array): bigint {
+      const { Err: E } = DER;
+      if (data[0] & 0b1000_0000) throw new E('Invalid signature integer: negative');
+      if (data[0] === 0x00 && !(data[1] & 0b1000_0000))
+        throw new E('Invalid signature integer: unnecessary leading zero');
+      return b2n(data);
+    },
+  },
   toSig(hex: string | Uint8Array): { r: bigint; s: bigint } {
     // parse DER signature
-    const { Err: E } = DER;
+    const { Err: E, _int: int, _tlv: tlv } = DER;
     const data = typeof hex === 'string' ? h2b(hex) : hex;
     ut.abytes(data);
-    let l = data.length;
-    if (l < 2 || data[0] != 0x30) throw new E('Invalid signature tag');
-    if (data[1] !== l - 2) throw new E('Invalid signature: incorrect length');
-    const { d: r, l: sBytes } = DER._parseInt(data.subarray(2));
-    const { d: s, l: rBytesLeft } = DER._parseInt(sBytes);
-    if (rBytesLeft.length) throw new E('Invalid signature: left bytes after parsing');
-    return { r, s };
+    const { v: seqBytes, l: seqLeftBytes } = tlv.decode(0x30, data);
+    if (seqLeftBytes.length) throw new E('Invalid signature: left bytes after parsing');
+    const { v: rBytes, l: rLeftBytes } = tlv.decode(0x02, seqBytes);
+    const { v: sBytes, l: sLeftBytes } = tlv.decode(0x02, rLeftBytes);
+    if (sLeftBytes.length) throw new E('Invalid signature: left bytes after parsing');
+    return { r: int.decode(rBytes), s: int.decode(sBytes) };
   },
   hexFromSig(sig: { r: bigint; s: bigint }): string {
-    // Add leading zero if first byte has negative bit enabled. More details in '_parseInt'
-    const slice = (s: string): string => (Number.parseInt(s[0], 16) & 0b1000 ? '00' + s : s);
-    const h = (num: number | bigint) => {
-      const hex = num.toString(16);
-      return hex.length & 1 ? `0${hex}` : hex;
-    };
-    const s = slice(h(sig.s));
-    const r = slice(h(sig.r));
-    const shl = s.length / 2;
-    const rhl = r.length / 2;
-    const sl = h(shl);
-    const rl = h(rhl);
-    return `30${h(rhl + shl + 4)}02${rl}${r}02${sl}${s}`;
+    const { _tlv: tlv, _int: int } = DER;
+    const seq = `${tlv.encode(0x02, int.encode(sig.r))}${tlv.encode(0x02, int.encode(sig.s))}`;
+    return tlv.encode(0x30, seq);
   },
@@ -202,2 +254,3 @@ };
   const { Fp } = CURVE; // All curves has same field / group length as for now, but they can differ
+  const Fn = mod.Field(CURVE.n, CURVE.nBitLength);
 
@@ -376,2 +429,7 @@ const toBytes =
 
+    // Multiscalar Multiplication
+    static msm(points: Point[], scalars: bigint[]) {
+      return pippenger(Point, Fn, points, scalars);
+    }
+
     // "Private method", don't use it directly
@@ -378,0 +436,0 @@ _setWindowSize(windowSize: number) {

src/jubjub.ts

@@ -49,11 +49,16 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
 
+// No secret data is leaked here at all.
+// It operates over public data:
+// const G_SPEND = jubjub.findGroupHash(new Uint8Array(), utf8ToBytes('Item_G_'));
 export function findGroupHash(m: Uint8Array, personalization: Uint8Array) {
   const tag = concatBytes(m, new Uint8Array([0]));
+  const hashes = [];
   for (let i = 0; i < 256; i++) {
     tag[tag.length - 1] = i;
     try {
-      return groupHash(tag, personalization);
+      hashes.push(groupHash(tag, personalization));
     } catch (e) {}
   }
-  throw new Error('findGroupHash tag overflow');
+  if (!hashes.length) throw new Error('findGroupHash tag overflow');
+  return hashes[0];
 }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

1602603

increased by2.04%

Lines of code

22330

increased by2.05%

Number of lines in readme file

1063

increased by1.82%

Dependency changes

• + Added@noble/hashes@1.5.0(transitive)

• - Removed@noble/hashes@1.4.0(transitive)

• Updated@noble/hashes@1.5.0