6020 lines
166 KiB
JavaScript
6020 lines
166 KiB
JavaScript
'use strict';
|
|
|
|
var crypto = require('crypto');
|
|
var wasmcurves = require('wasmcurves');
|
|
var os = require('os');
|
|
var Worker = require('web-worker');
|
|
var wasmbuilder = require('wasmbuilder');
|
|
|
|
/* global BigInt */
|
|
const hexLen = [ 0, 1, 2, 2, 3, 3, 3, 3, 4 ,4 ,4 ,4 ,4 ,4 ,4 ,4];
|
|
|
|
function fromString(s, radix) {
|
|
if ((!radix)||(radix==10)) {
|
|
return BigInt(s);
|
|
} else if (radix==16) {
|
|
if (s.slice(0,2) == "0x") {
|
|
return BigInt(s);
|
|
} else {
|
|
return BigInt("0x"+s);
|
|
}
|
|
}
|
|
}
|
|
|
|
const e = fromString;
|
|
|
|
function fromArray(a, radix) {
|
|
let acc =BigInt(0);
|
|
radix = BigInt(radix);
|
|
for (let i=0; i<a.length; i++) {
|
|
acc = acc*radix + BigInt(a[i]);
|
|
}
|
|
return acc;
|
|
}
|
|
|
|
function bitLength(a) {
|
|
const aS =a.toString(16);
|
|
return (aS.length-1)*4 +hexLen[parseInt(aS[0], 16)];
|
|
}
|
|
|
|
function isNegative(a) {
|
|
return BigInt(a) < BigInt(0);
|
|
}
|
|
|
|
function isZero(a) {
|
|
return !a;
|
|
}
|
|
|
|
function shiftLeft(a, n) {
|
|
return BigInt(a) << BigInt(n);
|
|
}
|
|
|
|
function shiftRight(a, n) {
|
|
return BigInt(a) >> BigInt(n);
|
|
}
|
|
|
|
const shl = shiftLeft;
|
|
const shr = shiftRight;
|
|
|
|
function isOdd(a) {
|
|
return (BigInt(a) & BigInt(1)) == BigInt(1);
|
|
}
|
|
|
|
|
|
function naf(n) {
|
|
let E = BigInt(n);
|
|
const res = [];
|
|
while (E) {
|
|
if (E & BigInt(1)) {
|
|
const z = 2 - Number(E % BigInt(4));
|
|
res.push( z );
|
|
E = E - BigInt(z);
|
|
} else {
|
|
res.push( 0 );
|
|
}
|
|
E = E >> BigInt(1);
|
|
}
|
|
return res;
|
|
}
|
|
|
|
|
|
function bits(n) {
|
|
let E = BigInt(n);
|
|
const res = [];
|
|
while (E) {
|
|
if (E & BigInt(1)) {
|
|
res.push(1);
|
|
} else {
|
|
res.push( 0 );
|
|
}
|
|
E = E >> BigInt(1);
|
|
}
|
|
return res;
|
|
}
|
|
|
|
function toNumber(s) {
|
|
if (s>BigInt(Number.MAX_SAFE_INTEGER )) {
|
|
throw new Error("Number too big");
|
|
}
|
|
return Number(s);
|
|
}
|
|
|
|
function toArray(s, radix) {
|
|
const res = [];
|
|
let rem = BigInt(s);
|
|
radix = BigInt(radix);
|
|
while (rem) {
|
|
res.unshift( Number(rem % radix));
|
|
rem = rem / radix;
|
|
}
|
|
return res;
|
|
}
|
|
|
|
|
|
function add(a, b) {
|
|
return BigInt(a) + BigInt(b);
|
|
}
|
|
|
|
function sub(a, b) {
|
|
return BigInt(a) - BigInt(b);
|
|
}
|
|
|
|
function neg(a) {
|
|
return -BigInt(a);
|
|
}
|
|
|
|
function mul(a, b) {
|
|
return BigInt(a) * BigInt(b);
|
|
}
|
|
|
|
function square(a) {
|
|
return BigInt(a) * BigInt(a);
|
|
}
|
|
|
|
function pow(a, b) {
|
|
return BigInt(a) ** BigInt(b);
|
|
}
|
|
|
|
function exp$1(a, b) {
|
|
return BigInt(a) ** BigInt(b);
|
|
}
|
|
|
|
function abs(a) {
|
|
return BigInt(a) >= 0 ? BigInt(a) : -BigInt(a);
|
|
}
|
|
|
|
function div(a, b) {
|
|
return BigInt(a) / BigInt(b);
|
|
}
|
|
|
|
function mod(a, b) {
|
|
return BigInt(a) % BigInt(b);
|
|
}
|
|
|
|
function eq(a, b) {
|
|
return BigInt(a) == BigInt(b);
|
|
}
|
|
|
|
function neq(a, b) {
|
|
return BigInt(a) != BigInt(b);
|
|
}
|
|
|
|
function lt(a, b) {
|
|
return BigInt(a) < BigInt(b);
|
|
}
|
|
|
|
function gt(a, b) {
|
|
return BigInt(a) > BigInt(b);
|
|
}
|
|
|
|
function leq(a, b) {
|
|
return BigInt(a) <= BigInt(b);
|
|
}
|
|
|
|
function geq(a, b) {
|
|
return BigInt(a) >= BigInt(b);
|
|
}
|
|
|
|
function band(a, b) {
|
|
return BigInt(a) & BigInt(b);
|
|
}
|
|
|
|
function bor(a, b) {
|
|
return BigInt(a) | BigInt(b);
|
|
}
|
|
|
|
function bxor(a, b) {
|
|
return BigInt(a) ^ BigInt(b);
|
|
}
|
|
|
|
function land(a, b) {
|
|
return BigInt(a) && BigInt(b);
|
|
}
|
|
|
|
function lor(a, b) {
|
|
return BigInt(a) || BigInt(b);
|
|
}
|
|
|
|
function lnot(a) {
|
|
return !BigInt(a);
|
|
}
|
|
|
|
// Returns a buffer with Little Endian Representation
|
|
function toRprLE(buff, o, e, n8) {
|
|
const s = "0000000" + e.toString(16);
|
|
const v = new Uint32Array(buff.buffer, buff.byteOffset + o, n8/4);
|
|
const l = (((s.length-7)*4 - 1) >> 5)+1; // Number of 32bit words;
|
|
for (let i=0; i<l; i++) v[i] = parseInt(s.substring(s.length-8*i-8, s.length-8*i), 16);
|
|
for (let i=l; i<v.length; i++) v[i] = 0;
|
|
for (let i=v.length*4; i<n8; i++) buff[i] = toNumber(band(shiftRight(e, i*8), 0xFF));
|
|
}
|
|
|
|
// Returns a buffer with Big Endian Representation
|
|
function toRprBE(buff, o, e, n8) {
|
|
const s = "0000000" + e.toString(16);
|
|
const v = new DataView(buff.buffer, buff.byteOffset + o, n8);
|
|
const l = (((s.length-7)*4 - 1) >> 5)+1; // Number of 32bit words;
|
|
for (let i=0; i<l; i++) v.setUint32(n8-i*4 -4, parseInt(s.substring(s.length-8*i-8, s.length-8*i), 16), false);
|
|
for (let i=0; i<n8/4-l; i++) v[i] = 0;
|
|
}
|
|
|
|
// Pases a buffer with Little Endian Representation
|
|
function fromRprLE(buff, o, n8) {
|
|
n8 = n8 || buff.byteLength;
|
|
o = o || 0;
|
|
const v = new Uint32Array(buff.buffer, buff.byteOffset + o, n8/4);
|
|
const a = new Array(n8/4);
|
|
v.forEach( (ch,i) => a[a.length-i-1] = ch.toString(16).padStart(8,"0") );
|
|
return fromString(a.join(""), 16);
|
|
}
|
|
|
|
// Pases a buffer with Big Endian Representation
|
|
function fromRprBE(buff, o, n8) {
|
|
n8 = n8 || buff.byteLength;
|
|
o = o || 0;
|
|
const v = new DataView(buff.buffer, buff.byteOffset + o, n8);
|
|
const a = new Array(n8/4);
|
|
for (let i=0; i<n8/4; i++) {
|
|
a[i] = v.getUint32(i*4, false).toString(16).padStart(8, "0");
|
|
}
|
|
return fromString(a.join(""), 16);
|
|
}
|
|
|
|
function toString(a, radix) {
|
|
return a.toString(radix);
|
|
}
|
|
|
|
function toLEBuff(a) {
|
|
const buff = new Uint8Array(Math.floor((bitLength(a) - 1) / 8) +1);
|
|
toRprLE(buff, 0, a, buff.byteLength);
|
|
return buff;
|
|
}
|
|
|
|
const zero = e(0);
|
|
const one = e(1);
|
|
|
|
var _Scalar = /*#__PURE__*/Object.freeze({
|
|
__proto__: null,
|
|
abs: abs,
|
|
add: add,
|
|
band: band,
|
|
bitLength: bitLength,
|
|
bits: bits,
|
|
bor: bor,
|
|
bxor: bxor,
|
|
div: div,
|
|
e: e,
|
|
eq: eq,
|
|
exp: exp$1,
|
|
fromArray: fromArray,
|
|
fromRprBE: fromRprBE,
|
|
fromRprLE: fromRprLE,
|
|
fromString: fromString,
|
|
geq: geq,
|
|
gt: gt,
|
|
isNegative: isNegative,
|
|
isOdd: isOdd,
|
|
isZero: isZero,
|
|
land: land,
|
|
leq: leq,
|
|
lnot: lnot,
|
|
lor: lor,
|
|
lt: lt,
|
|
mod: mod,
|
|
mul: mul,
|
|
naf: naf,
|
|
neg: neg,
|
|
neq: neq,
|
|
one: one,
|
|
pow: pow,
|
|
shiftLeft: shiftLeft,
|
|
shiftRight: shiftRight,
|
|
shl: shl,
|
|
shr: shr,
|
|
square: square,
|
|
sub: sub,
|
|
toArray: toArray,
|
|
toLEBuff: toLEBuff,
|
|
toNumber: toNumber,
|
|
toRprBE: toRprBE,
|
|
toRprLE: toRprLE,
|
|
toString: toString,
|
|
zero: zero
|
|
});
|
|
|
|
/*
|
|
Copyright 2018 0kims association.
|
|
|
|
This file is part of snarkjs.
|
|
|
|
snarkjs is a free software: you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License as published by the
|
|
Free Software Foundation, either version 3 of the License, or (at your option)
|
|
any later version.
|
|
|
|
snarkjs is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
more details.
|
|
|
|
You should have received a copy of the GNU General Public License along with
|
|
snarkjs. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
/*
|
|
This library does operations on polynomials with coefficients in a field F.
|
|
|
|
A polynomial P(x) = p0 + p1 * x + p2 * x^2 + ... + pn * x^n is represented
|
|
by the array [ p0, p1, p2, ... , pn ].
|
|
*/
|
|
|
|
class PolField {
|
|
constructor (F) {
|
|
this.F = F;
|
|
|
|
let rem = F.sqrt_t;
|
|
let s = F.sqrt_s;
|
|
|
|
const five = this.F.add(this.F.add(this.F.two, this.F.two), this.F.one);
|
|
|
|
this.w = new Array(s+1);
|
|
this.wi = new Array(s+1);
|
|
this.w[s] = this.F.pow(five, rem);
|
|
this.wi[s] = this.F.inv(this.w[s]);
|
|
|
|
let n=s-1;
|
|
while (n>=0) {
|
|
this.w[n] = this.F.square(this.w[n+1]);
|
|
this.wi[n] = this.F.square(this.wi[n+1]);
|
|
n--;
|
|
}
|
|
|
|
|
|
this.roots = [];
|
|
/* for (let i=0; i<16; i++) {
|
|
let r = this.F.one;
|
|
n = 1 << i;
|
|
const rootsi = new Array(n);
|
|
for (let j=0; j<n; j++) {
|
|
rootsi[j] = r;
|
|
r = this.F.mul(r, this.w[i]);
|
|
}
|
|
|
|
this.roots.push(rootsi);
|
|
}
|
|
*/
|
|
this._setRoots(15);
|
|
}
|
|
|
|
_setRoots(n) {
|
|
if (n > this.F.sqrt_s) n = this.s;
|
|
for (let i=n; (i>=0) && (!this.roots[i]); i--) {
|
|
let r = this.F.one;
|
|
const nroots = 1 << i;
|
|
const rootsi = new Array(nroots);
|
|
for (let j=0; j<nroots; j++) {
|
|
rootsi[j] = r;
|
|
r = this.F.mul(r, this.w[i]);
|
|
}
|
|
this.roots[i] = rootsi;
|
|
}
|
|
}
|
|
|
|
add(a, b) {
|
|
const m = Math.max(a.length, b.length);
|
|
const res = new Array(m);
|
|
for (let i=0; i<m; i++) {
|
|
res[i] = this.F.add(a[i] || this.F.zero, b[i] || this.F.zero);
|
|
}
|
|
return this.reduce(res);
|
|
}
|
|
|
|
double(a) {
|
|
return this.add(a,a);
|
|
}
|
|
|
|
sub(a, b) {
|
|
const m = Math.max(a.length, b.length);
|
|
const res = new Array(m);
|
|
for (let i=0; i<m; i++) {
|
|
res[i] = this.F.sub(a[i] || this.F.zero, b[i] || this.F.zero);
|
|
}
|
|
return this.reduce(res);
|
|
}
|
|
|
|
mulScalar(p, b) {
|
|
if (this.F.eq(b, this.F.zero)) return [];
|
|
if (this.F.eq(b, this.F.one)) return p;
|
|
const res = new Array(p.length);
|
|
for (let i=0; i<p.length; i++) {
|
|
res[i] = this.F.mul(p[i], b);
|
|
}
|
|
return res;
|
|
}
|
|
|
|
|
|
|
|
mul(a, b) {
|
|
if (a.length == 0) return [];
|
|
if (b.length == 0) return [];
|
|
if (a.length == 1) return this.mulScalar(b, a[0]);
|
|
if (b.length == 1) return this.mulScalar(a, b[0]);
|
|
|
|
if (b.length > a.length) {
|
|
[b, a] = [a, b];
|
|
}
|
|
|
|
if ((b.length <= 2) || (b.length < log2$2(a.length))) {
|
|
return this.mulNormal(a,b);
|
|
} else {
|
|
return this.mulFFT(a,b);
|
|
}
|
|
}
|
|
|
|
mulNormal(a, b) {
|
|
let res = [];
|
|
for (let i=0; i<b.length; i++) {
|
|
res = this.add(res, this.scaleX(this.mulScalar(a, b[i]), i) );
|
|
}
|
|
return res;
|
|
}
|
|
|
|
mulFFT(a,b) {
|
|
const longestN = Math.max(a.length, b.length);
|
|
const bitsResult = log2$2(longestN-1)+2;
|
|
this._setRoots(bitsResult);
|
|
|
|
const m = 1 << bitsResult;
|
|
const ea = this.extend(a,m);
|
|
const eb = this.extend(b,m);
|
|
|
|
const ta = __fft$1(this, ea, bitsResult, 0, 1);
|
|
const tb = __fft$1(this, eb, bitsResult, 0, 1);
|
|
|
|
const tres = new Array(m);
|
|
|
|
for (let i=0; i<m; i++) {
|
|
tres[i] = this.F.mul(ta[i], tb[i]);
|
|
}
|
|
|
|
const res = __fft$1(this, tres, bitsResult, 0, 1);
|
|
|
|
const twoinvm = this.F.inv( this.F.mulScalar(this.F.one, m) );
|
|
const resn = new Array(m);
|
|
for (let i=0; i<m; i++) {
|
|
resn[i] = this.F.mul(res[(m-i)%m], twoinvm);
|
|
}
|
|
|
|
return this.reduce(resn);
|
|
}
|
|
|
|
|
|
|
|
square(a) {
|
|
return this.mul(a,a);
|
|
}
|
|
|
|
scaleX(p, n) {
|
|
if (n==0) {
|
|
return p;
|
|
} else if (n>0) {
|
|
const z = new Array(n).fill(this.F.zero);
|
|
return z.concat(p);
|
|
} else {
|
|
if (-n >= p.length) return [];
|
|
return p.slice(-n);
|
|
}
|
|
}
|
|
|
|
eval2(p, x) {
|
|
let v = this.F.zero;
|
|
let ix = this.F.one;
|
|
for (let i=0; i<p.length; i++) {
|
|
v = this.F.add(v, this.F.mul(p[i], ix));
|
|
ix = this.F.mul(ix, x);
|
|
}
|
|
return v;
|
|
}
|
|
|
|
evaluate(p,x) {
|
|
const F = this.F;
|
|
if (p.length == 0) return F.zero;
|
|
const m = this._next2Power(p.length);
|
|
const ep = this.extend(p, m);
|
|
|
|
return _eval(ep, x, 0, 1, m);
|
|
|
|
function _eval(p, x, offset, step, n) {
|
|
if (n==1) return p[offset];
|
|
const newX = F.square(x);
|
|
const res= F.add(
|
|
_eval(p, newX, offset, step << 1, n >> 1),
|
|
F.mul(
|
|
x,
|
|
_eval(p, newX, offset+step , step << 1, n >> 1)));
|
|
return res;
|
|
}
|
|
}
|
|
|
|
lagrange(points) {
|
|
let roots = [this.F.one];
|
|
for (let i=0; i<points.length; i++) {
|
|
roots = this.mul(roots, [this.F.neg(points[i][0]), this.F.one]);
|
|
}
|
|
|
|
let sum = [];
|
|
for (let i=0; i<points.length; i++) {
|
|
let mpol = this.ruffini(roots, points[i][0]);
|
|
const factor =
|
|
this.F.mul(
|
|
this.F.inv(this.evaluate(mpol, points[i][0])),
|
|
points[i][1]);
|
|
mpol = this.mulScalar(mpol, factor);
|
|
sum = this.add(sum, mpol);
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
|
|
fft(p) {
|
|
if (p.length <= 1) return p;
|
|
const bits = log2$2(p.length-1)+1;
|
|
this._setRoots(bits);
|
|
|
|
const m = 1 << bits;
|
|
const ep = this.extend(p, m);
|
|
const res = __fft$1(this, ep, bits, 0, 1);
|
|
return res;
|
|
}
|
|
|
|
fft2(p) {
|
|
if (p.length <= 1) return p;
|
|
const bits = log2$2(p.length-1)+1;
|
|
this._setRoots(bits);
|
|
|
|
const m = 1 << bits;
|
|
const ep = this.extend(p, m);
|
|
__bitReverse(ep, bits);
|
|
const res = __fft2(this, ep, bits);
|
|
return res;
|
|
}
|
|
|
|
|
|
ifft(p) {
|
|
|
|
if (p.length <= 1) return p;
|
|
const bits = log2$2(p.length-1)+1;
|
|
this._setRoots(bits);
|
|
const m = 1 << bits;
|
|
const ep = this.extend(p, m);
|
|
const res = __fft$1(this, ep, bits, 0, 1);
|
|
|
|
const twoinvm = this.F.inv( this.F.mulScalar(this.F.one, m) );
|
|
const resn = new Array(m);
|
|
for (let i=0; i<m; i++) {
|
|
resn[i] = this.F.mul(res[(m-i)%m], twoinvm);
|
|
}
|
|
|
|
return resn;
|
|
|
|
}
|
|
|
|
|
|
ifft2(p) {
|
|
|
|
if (p.length <= 1) return p;
|
|
const bits = log2$2(p.length-1)+1;
|
|
this._setRoots(bits);
|
|
const m = 1 << bits;
|
|
const ep = this.extend(p, m);
|
|
__bitReverse(ep, bits);
|
|
const res = __fft2(this, ep, bits);
|
|
|
|
const twoinvm = this.F.inv( this.F.mulScalar(this.F.one, m) );
|
|
const resn = new Array(m);
|
|
for (let i=0; i<m; i++) {
|
|
resn[i] = this.F.mul(res[(m-i)%m], twoinvm);
|
|
}
|
|
|
|
return resn;
|
|
|
|
}
|
|
|
|
_fft(pall, bits, offset, step) {
|
|
|
|
const n = 1 << bits;
|
|
if (n==1) {
|
|
return [ pall[offset] ];
|
|
}
|
|
|
|
const ndiv2 = n >> 1;
|
|
const p1 = this._fft(pall, bits-1, offset, step*2);
|
|
const p2 = this._fft(pall, bits-1, offset+step, step*2);
|
|
|
|
const out = new Array(n);
|
|
|
|
let m= this.F.one;
|
|
for (let i=0; i<ndiv2; i++) {
|
|
out[i] = this.F.add(p1[i], this.F.mul(m, p2[i]));
|
|
out[i+ndiv2] = this.F.sub(p1[i], this.F.mul(m, p2[i]));
|
|
m = this.F.mul(m, this.w[bits]);
|
|
}
|
|
|
|
return out;
|
|
}
|
|
|
|
extend(p, e) {
|
|
if (e == p.length) return p;
|
|
const z = new Array(e-p.length).fill(this.F.zero);
|
|
|
|
return p.concat(z);
|
|
}
|
|
|
|
reduce(p) {
|
|
if (p.length == 0) return p;
|
|
if (! this.F.eq(p[p.length-1], this.F.zero) ) return p;
|
|
let i=p.length-1;
|
|
while( i>0 && this.F.eq(p[i], this.F.zero) ) i--;
|
|
return p.slice(0, i+1);
|
|
}
|
|
|
|
eq(a, b) {
|
|
const pa = this.reduce(a);
|
|
const pb = this.reduce(b);
|
|
|
|
if (pa.length != pb.length) return false;
|
|
for (let i=0; i<pb.length; i++) {
|
|
if (!this.F.eq(pa[i], pb[i])) return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
ruffini(p, r) {
|
|
const res = new Array(p.length-1);
|
|
res[res.length-1] = p[p.length-1];
|
|
for (let i = res.length-2; i>=0; i--) {
|
|
res[i] = this.F.add(this.F.mul(res[i+1], r), p[i+1]);
|
|
}
|
|
return res;
|
|
}
|
|
|
|
_next2Power(v) {
|
|
v--;
|
|
v |= v >> 1;
|
|
v |= v >> 2;
|
|
v |= v >> 4;
|
|
v |= v >> 8;
|
|
v |= v >> 16;
|
|
v++;
|
|
return v;
|
|
}
|
|
|
|
toString(p) {
|
|
const ap = this.normalize(p);
|
|
let S = "";
|
|
for (let i=ap.length-1; i>=0; i--) {
|
|
if (!this.F.eq(p[i], this.F.zero)) {
|
|
if (S!="") S += " + ";
|
|
S = S + p[i].toString(10);
|
|
if (i>0) {
|
|
S = S + "x";
|
|
if (i>1) {
|
|
S = S + "^" +i;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return S;
|
|
}
|
|
|
|
normalize(p) {
|
|
const res = new Array(p.length);
|
|
for (let i=0; i<p.length; i++) {
|
|
res[i] = this.F.normalize(p[i]);
|
|
}
|
|
return res;
|
|
}
|
|
|
|
|
|
_reciprocal(p, bits) {
|
|
const k = 1 << bits;
|
|
if (k==1) {
|
|
return [ this.F.inv(p[0]) ];
|
|
}
|
|
const np = this.scaleX(p, -k/2);
|
|
const q = this._reciprocal(np, bits-1);
|
|
const a = this.scaleX(this.double(q), 3*k/2-2);
|
|
const b = this.mul( this.square(q), p);
|
|
|
|
return this.scaleX(this.sub(a,b), -(k-2));
|
|
}
|
|
|
|
// divides x^m / v
|
|
_div2(m, v) {
|
|
const kbits = log2$2(v.length-1)+1;
|
|
const k = 1 << kbits;
|
|
|
|
const scaleV = k - v.length;
|
|
|
|
// rec = x^(k - 2) / v* x^scaleV =>
|
|
// rec = x^(k-2-scaleV)/ v
|
|
//
|
|
// res = x^m/v = x^(m + (2*k-2 - scaleV) - (2*k-2 - scaleV)) /v =>
|
|
// res = rec * x^(m - (2*k-2 - scaleV)) =>
|
|
// res = rec * x^(m - 2*k + 2 + scaleV)
|
|
|
|
const rec = this._reciprocal(this.scaleX(v, scaleV), kbits);
|
|
const res = this.scaleX(rec, m - 2*k + 2 + scaleV);
|
|
|
|
return res;
|
|
}
|
|
|
|
div(_u, _v) {
|
|
if (_u.length < _v.length) return [];
|
|
const kbits = log2$2(_v.length-1)+1;
|
|
const k = 1 << kbits;
|
|
|
|
const u = this.scaleX(_u, k-_v.length);
|
|
const v = this.scaleX(_v, k-_v.length);
|
|
|
|
const n = v.length-1;
|
|
let m = u.length-1;
|
|
|
|
const s = this._reciprocal(v, kbits);
|
|
let t;
|
|
if (m>2*n) {
|
|
t = this.sub(this.scaleX([this.F.one], 2*n), this.mul(s, v));
|
|
}
|
|
|
|
let q = [];
|
|
let rem = u;
|
|
let us, ut;
|
|
let finish = false;
|
|
|
|
while (!finish) {
|
|
us = this.mul(rem, s);
|
|
q = this.add(q, this.scaleX(us, -2*n));
|
|
|
|
if ( m > 2*n ) {
|
|
ut = this.mul(rem, t);
|
|
rem = this.scaleX(ut, -2*n);
|
|
m = rem.length-1;
|
|
} else {
|
|
finish = true;
|
|
}
|
|
}
|
|
|
|
return q;
|
|
}
|
|
|
|
|
|
// returns the ith nth-root of one
|
|
oneRoot(n, i) {
|
|
let nbits = log2$2(n-1)+1;
|
|
let res = this.F.one;
|
|
let r = i;
|
|
|
|
if(i>=n) {
|
|
throw new Error("Given 'i' should be lower than 'n'");
|
|
}
|
|
else if (1<<nbits !== n) {
|
|
throw new Error(`Internal errlr: ${n} should equal ${1<<nbits}`);
|
|
}
|
|
|
|
while (r>0) {
|
|
if (r & 1 == 1) {
|
|
res = this.F.mul(res, this.w[nbits]);
|
|
}
|
|
r = r >> 1;
|
|
nbits --;
|
|
}
|
|
return res;
|
|
}
|
|
|
|
computeVanishingPolinomial(bits, t) {
|
|
const m = 1 << bits;
|
|
return this.F.sub(this.F.pow(t, m), this.F.one);
|
|
}
|
|
|
|
evaluateLagrangePolynomials(bits, t) {
|
|
const m= 1 << bits;
|
|
const tm = this.F.pow(t, m);
|
|
const u= new Array(m).fill(this.F.zero);
|
|
this._setRoots(bits);
|
|
const omega = this.w[bits];
|
|
|
|
if (this.F.eq(tm, this.F.one)) {
|
|
for (let i = 0; i < m; i++) {
|
|
if (this.F.eq(this.roots[bits][0],t)) { // i.e., t equals omega^i
|
|
u[i] = this.F.one;
|
|
return u;
|
|
}
|
|
}
|
|
}
|
|
|
|
const z = this.F.sub(tm, this.F.one);
|
|
// let l = this.F.mul(z, this.F.pow(this.F.twoinv, m));
|
|
let l = this.F.mul(z, this.F.inv(this.F.e(m)));
|
|
for (let i = 0; i < m; i++) {
|
|
u[i] = this.F.mul(l, this.F.inv(this.F.sub(t,this.roots[bits][i])));
|
|
l = this.F.mul(l, omega);
|
|
}
|
|
|
|
return u;
|
|
}
|
|
|
|
log2(V) {
|
|
return log2$2(V);
|
|
}
|
|
}
|
|
|
|
function log2$2( V )
|
|
{
|
|
return( ( ( V & 0xFFFF0000 ) !== 0 ? ( V &= 0xFFFF0000, 16 ) : 0 ) | ( ( V & 0xFF00FF00 ) !== 0 ? ( V &= 0xFF00FF00, 8 ) : 0 ) | ( ( V & 0xF0F0F0F0 ) !== 0 ? ( V &= 0xF0F0F0F0, 4 ) : 0 ) | ( ( V & 0xCCCCCCCC ) !== 0 ? ( V &= 0xCCCCCCCC, 2 ) : 0 ) | ( ( V & 0xAAAAAAAA ) !== 0 ) );
|
|
}
|
|
|
|
|
|
function __fft$1(PF, pall, bits, offset, step) {
|
|
|
|
const n = 1 << bits;
|
|
if (n==1) {
|
|
return [ pall[offset] ];
|
|
} else if (n==2) {
|
|
return [
|
|
PF.F.add(pall[offset], pall[offset + step]),
|
|
PF.F.sub(pall[offset], pall[offset + step])];
|
|
}
|
|
|
|
const ndiv2 = n >> 1;
|
|
const p1 = __fft$1(PF, pall, bits-1, offset, step*2);
|
|
const p2 = __fft$1(PF, pall, bits-1, offset+step, step*2);
|
|
|
|
const out = new Array(n);
|
|
|
|
for (let i=0; i<ndiv2; i++) {
|
|
out[i] = PF.F.add(p1[i], PF.F.mul(PF.roots[bits][i], p2[i]));
|
|
out[i+ndiv2] = PF.F.sub(p1[i], PF.F.mul(PF.roots[bits][i], p2[i]));
|
|
}
|
|
|
|
return out;
|
|
}
|
|
|
|
|
|
function __fft2(PF, pall, bits) {
|
|
|
|
const n = 1 << bits;
|
|
if (n==1) {
|
|
return [ pall[0] ];
|
|
}
|
|
|
|
const ndiv2 = n >> 1;
|
|
const p1 = __fft2(PF, pall.slice(0, ndiv2), bits-1);
|
|
const p2 = __fft2(PF, pall.slice(ndiv2), bits-1);
|
|
|
|
const out = new Array(n);
|
|
|
|
for (let i=0; i<ndiv2; i++) {
|
|
out[i] = PF.F.add(p1[i], PF.F.mul(PF.roots[bits][i], p2[i]));
|
|
out[i+ndiv2] = PF.F.sub(p1[i], PF.F.mul(PF.roots[bits][i], p2[i]));
|
|
}
|
|
|
|
return out;
|
|
}
|
|
|
|
const _revTable$1 = [];
|
|
for (let i=0; i<256; i++) {
|
|
_revTable$1[i] = _revSlow$1(i, 8);
|
|
}
|
|
|
|
function _revSlow$1(idx, bits) {
|
|
let res =0;
|
|
let a = idx;
|
|
for (let i=0; i<bits; i++) {
|
|
res <<= 1;
|
|
res = res | (a &1);
|
|
a >>=1;
|
|
}
|
|
return res;
|
|
}
|
|
|
|
function rev(idx, bits) {
|
|
return (
|
|
_revTable$1[idx >>> 24] |
|
|
(_revTable$1[(idx >>> 16) & 0xFF] << 8) |
|
|
(_revTable$1[(idx >>> 8) & 0xFF] << 16) |
|
|
(_revTable$1[idx & 0xFF] << 24)
|
|
) >>> (32-bits);
|
|
}
|
|
|
|
function __bitReverse(p, bits) {
|
|
for (let k=0; k<p.length; k++) {
|
|
const r = rev(k, bits);
|
|
if (r>k) {
|
|
const tmp= p[k];
|
|
p[k] = p[r];
|
|
p[r] = tmp;
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
/*
|
|
Copyright 2018 0kims association.
|
|
|
|
This file is part of snarkjs.
|
|
|
|
snarkjs is a free software: you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License as published by the
|
|
Free Software Foundation, either version 3 of the License, or (at your option)
|
|
any later version.
|
|
|
|
snarkjs is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
more details.
|
|
|
|
You should have received a copy of the GNU General Public License along with
|
|
snarkjs. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
|
|
|
|
function mulScalar(F, base, e) {
|
|
let res;
|
|
|
|
if (isZero(e)) return F.zero;
|
|
|
|
const n = naf(e);
|
|
|
|
if (n[n.length-1] == 1) {
|
|
res = base;
|
|
} else if (n[n.length-1] == -1) {
|
|
res = F.neg(base);
|
|
} else {
|
|
throw new Error("invlaud NAF");
|
|
}
|
|
|
|
for (let i=n.length-2; i>=0; i--) {
|
|
|
|
res = F.double(res);
|
|
|
|
if (n[i] == 1) {
|
|
res = F.add(res, base);
|
|
} else if (n[i] == -1) {
|
|
res = F.sub(res, base);
|
|
}
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
|
|
/*
|
|
exports.mulScalar = (F, base, e) =>{
|
|
let res = F.zero;
|
|
let rem = bigInt(e);
|
|
let exp = base;
|
|
|
|
while (! rem.eq(bigInt.zero)) {
|
|
if (rem.and(bigInt.one).eq(bigInt.one)) {
|
|
res = F.add(res, exp);
|
|
}
|
|
exp = F.double(exp);
|
|
rem = rem.shiftRight(1);
|
|
}
|
|
|
|
return res;
|
|
};
|
|
*/
|
|
|
|
|
|
function exp(F, base, e) {
|
|
|
|
if (isZero(e)) return F.one;
|
|
|
|
const n = bits(e);
|
|
|
|
if (n.length==0) return F.one;
|
|
|
|
let res = base;
|
|
|
|
for (let i=n.length-2; i>=0; i--) {
|
|
|
|
res = F.square(res);
|
|
|
|
if (n[i]) {
|
|
res = F.mul(res, base);
|
|
}
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
// Check here: https://eprint.iacr.org/2012/685.pdf
|
|
|
|
function buildSqrt (F) {
|
|
if ((F.m % 2) == 1) {
|
|
if (eq(mod(F.p, 4), 1 )) {
|
|
if (eq(mod(F.p, 8), 1 )) {
|
|
if (eq(mod(F.p, 16), 1 )) {
|
|
// alg7_muller(F);
|
|
alg5_tonelliShanks(F);
|
|
} else if (eq(mod(F.p, 16), 9 )) {
|
|
alg4_kong(F);
|
|
} else {
|
|
throw new Error("Field withot sqrt");
|
|
}
|
|
} else if (eq(mod(F.p, 8), 5 )) {
|
|
alg3_atkin(F);
|
|
} else {
|
|
throw new Error("Field withot sqrt");
|
|
}
|
|
} else if (eq(mod(F.p, 4), 3 )) {
|
|
alg2_shanks(F);
|
|
}
|
|
} else {
|
|
const pm2mod4 = mod(pow(F.p, F.m/2), 4);
|
|
if (pm2mod4 == 1) {
|
|
alg10_adj(F);
|
|
} else if (pm2mod4 == 3) {
|
|
alg9_adj(F);
|
|
} else {
|
|
alg8_complex(F);
|
|
}
|
|
|
|
}
|
|
}
|
|
|
|
|
|
function alg5_tonelliShanks(F) {
|
|
F.sqrt_q = pow(F.p, F.m);
|
|
|
|
F.sqrt_s = 0;
|
|
F.sqrt_t = sub(F.sqrt_q, 1);
|
|
|
|
while (!isOdd(F.sqrt_t)) {
|
|
F.sqrt_s = F.sqrt_s + 1;
|
|
F.sqrt_t = div(F.sqrt_t, 2);
|
|
}
|
|
|
|
let c0 = F.one;
|
|
|
|
while (F.eq(c0, F.one)) {
|
|
const c = F.random();
|
|
F.sqrt_z = F.pow(c, F.sqrt_t);
|
|
c0 = F.pow(F.sqrt_z, 2 ** (F.sqrt_s-1) );
|
|
}
|
|
|
|
F.sqrt_tm1d2 = div(sub(F.sqrt_t, 1),2);
|
|
|
|
F.sqrt = function(a) {
|
|
const F=this;
|
|
if (F.isZero(a)) return F.zero;
|
|
let w = F.pow(a, F.sqrt_tm1d2);
|
|
const a0 = F.pow( F.mul(F.square(w), a), 2 ** (F.sqrt_s-1) );
|
|
if (F.eq(a0, F.negone)) return null;
|
|
|
|
let v = F.sqrt_s;
|
|
let x = F.mul(a, w);
|
|
let b = F.mul(x, w);
|
|
let z = F.sqrt_z;
|
|
while (!F.eq(b, F.one)) {
|
|
let b2k = F.square(b);
|
|
let k=1;
|
|
while (!F.eq(b2k, F.one)) {
|
|
b2k = F.square(b2k);
|
|
k++;
|
|
}
|
|
|
|
w = z;
|
|
for (let i=0; i<v-k-1; i++) {
|
|
w = F.square(w);
|
|
}
|
|
z = F.square(w);
|
|
b = F.mul(b, z);
|
|
x = F.mul(x, w);
|
|
v = k;
|
|
}
|
|
return F.geq(x, F.zero) ? x : F.neg(x);
|
|
};
|
|
}
|
|
|
|
function alg4_kong(F) {
|
|
F.sqrt = function() {
|
|
throw new Error("Sqrt alg 4 not implemented");
|
|
};
|
|
}
|
|
|
|
function alg3_atkin(F) {
|
|
F.sqrt = function() {
|
|
throw new Error("Sqrt alg 3 not implemented");
|
|
};
|
|
}
|
|
|
|
function alg2_shanks(F) {
|
|
|
|
F.sqrt_q = pow(F.p, F.m);
|
|
F.sqrt_e1 = div( sub(F.sqrt_q, 3) , 4);
|
|
|
|
F.sqrt = function(a) {
|
|
if (this.isZero(a)) return this.zero;
|
|
|
|
// Test that have solution
|
|
const a1 = this.pow(a, this.sqrt_e1);
|
|
|
|
const a0 = this.mul(this.square(a1), a);
|
|
|
|
if ( this.eq(a0, this.negone) ) return null;
|
|
|
|
const x = this.mul(a1, a);
|
|
|
|
return F.geq(x, F.zero) ? x : F.neg(x);
|
|
};
|
|
}
|
|
|
|
function alg10_adj(F) {
|
|
F.sqrt = function() {
|
|
throw new Error("Sqrt alg 10 not implemented");
|
|
};
|
|
}
|
|
|
|
function alg9_adj(F) {
|
|
F.sqrt_q = pow(F.p, F.m/2);
|
|
F.sqrt_e34 = div( sub(F.sqrt_q, 3) , 4);
|
|
F.sqrt_e12 = div( sub(F.sqrt_q, 1) , 2);
|
|
|
|
F.frobenius = function(n, x) {
|
|
if ((n%2) == 1) {
|
|
return F.conjugate(x);
|
|
} else {
|
|
return x;
|
|
}
|
|
};
|
|
|
|
F.sqrt = function(a) {
|
|
const F = this;
|
|
const a1 = F.pow(a, F.sqrt_e34);
|
|
const alfa = F.mul(F.square(a1), a);
|
|
const a0 = F.mul(F.frobenius(1, alfa), alfa);
|
|
if (F.eq(a0, F.negone)) return null;
|
|
const x0 = F.mul(a1, a);
|
|
let x;
|
|
if (F.eq(alfa, F.negone)) {
|
|
x = F.mul(x0, [F.F.zero, F.F.one]);
|
|
} else {
|
|
const b = F.pow(F.add(F.one, alfa), F.sqrt_e12);
|
|
x = F.mul(b, x0);
|
|
}
|
|
return F.geq(x, F.zero) ? x : F.neg(x);
|
|
};
|
|
}
|
|
|
|
|
|
function alg8_complex(F) {
|
|
F.sqrt = function() {
|
|
throw new Error("Sqrt alg 8 not implemented");
|
|
};
|
|
}
|
|
|
|
function quarterRound(st, a, b, c, d) {
|
|
|
|
st[a] = (st[a] + st[b]) >>> 0;
|
|
st[d] = (st[d] ^ st[a]) >>> 0;
|
|
st[d] = ((st[d] << 16) | ((st[d]>>>16) & 0xFFFF)) >>> 0;
|
|
|
|
st[c] = (st[c] + st[d]) >>> 0;
|
|
st[b] = (st[b] ^ st[c]) >>> 0;
|
|
st[b] = ((st[b] << 12) | ((st[b]>>>20) & 0xFFF)) >>> 0;
|
|
|
|
st[a] = (st[a] + st[b]) >>> 0;
|
|
st[d] = (st[d] ^ st[a]) >>> 0;
|
|
st[d] = ((st[d] << 8) | ((st[d]>>>24) & 0xFF)) >>> 0;
|
|
|
|
st[c] = (st[c] + st[d]) >>> 0;
|
|
st[b] = (st[b] ^ st[c]) >>> 0;
|
|
st[b] = ((st[b] << 7) | ((st[b]>>>25) & 0x7F)) >>> 0;
|
|
}
|
|
|
|
function doubleRound(st) {
|
|
quarterRound(st, 0, 4, 8,12);
|
|
quarterRound(st, 1, 5, 9,13);
|
|
quarterRound(st, 2, 6,10,14);
|
|
quarterRound(st, 3, 7,11,15);
|
|
|
|
quarterRound(st, 0, 5,10,15);
|
|
quarterRound(st, 1, 6,11,12);
|
|
quarterRound(st, 2, 7, 8,13);
|
|
quarterRound(st, 3, 4, 9,14);
|
|
}
|
|
|
|
class ChaCha {
|
|
|
|
constructor(seed) {
|
|
seed = seed || [0,0,0,0,0,0,0,0];
|
|
this.state = [
|
|
0x61707865,
|
|
0x3320646E,
|
|
0x79622D32,
|
|
0x6B206574,
|
|
seed[0],
|
|
seed[1],
|
|
seed[2],
|
|
seed[3],
|
|
seed[4],
|
|
seed[5],
|
|
seed[6],
|
|
seed[7],
|
|
0,
|
|
0,
|
|
0,
|
|
0
|
|
];
|
|
this.idx = 16;
|
|
this.buff = new Array(16);
|
|
}
|
|
|
|
nextU32() {
|
|
if (this.idx == 16) this.update();
|
|
return this.buff[this.idx++];
|
|
}
|
|
|
|
nextU64() {
|
|
return add(mul(this.nextU32(), 0x100000000), this.nextU32());
|
|
}
|
|
|
|
nextBool() {
|
|
return (this.nextU32() & 1) == 1;
|
|
}
|
|
|
|
update() {
|
|
// Copy the state
|
|
for (let i=0; i<16; i++) this.buff[i] = this.state[i];
|
|
|
|
// Apply the rounds
|
|
for (let i=0; i<10; i++) doubleRound(this.buff);
|
|
|
|
// Add to the initial
|
|
for (let i=0; i<16; i++) this.buff[i] = (this.buff[i] + this.state[i]) >>> 0;
|
|
|
|
this.idx = 0;
|
|
|
|
this.state[12] = (this.state[12] + 1) >>> 0;
|
|
if (this.state[12] != 0) return;
|
|
this.state[13] = (this.state[13] + 1) >>> 0;
|
|
if (this.state[13] != 0) return;
|
|
this.state[14] = (this.state[14] + 1) >>> 0;
|
|
if (this.state[14] != 0) return;
|
|
this.state[15] = (this.state[15] + 1) >>> 0;
|
|
}
|
|
}
|
|
|
|
function getRandomBytes(n) {
|
|
let array = new Uint8Array(n);
|
|
if (process.browser) { // Browser
|
|
if (typeof globalThis.crypto !== "undefined") { // Supported
|
|
globalThis.crypto.getRandomValues(array);
|
|
} else { // fallback
|
|
for (let i=0; i<n; i++) {
|
|
array[i] = (Math.random()*4294967296)>>>0;
|
|
}
|
|
}
|
|
}
|
|
else { // NodeJS
|
|
crypto.randomFillSync(array);
|
|
}
|
|
return array;
|
|
}
|
|
|
|
function getRandomSeed() {
|
|
const arr = getRandomBytes(32);
|
|
const arrV = new Uint32Array(arr.buffer);
|
|
const seed = [];
|
|
for (let i=0; i<8; i++) {
|
|
seed.push(arrV[i]);
|
|
}
|
|
return seed;
|
|
}
|
|
|
|
let threadRng = null;
|
|
|
|
function getThreadRng() {
|
|
if (threadRng) return threadRng;
|
|
threadRng = new ChaCha(getRandomSeed());
|
|
return threadRng;
|
|
}
|
|
|
|
/*
|
|
Copyright 2018 0kims association.
|
|
|
|
This file is part of snarkjs.
|
|
|
|
snarkjs is a free software: you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License as published by the
|
|
Free Software Foundation, either version 3 of the License, or (at your option)
|
|
any later version.
|
|
|
|
snarkjs is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
more details.
|
|
|
|
You should have received a copy of the GNU General Public License along with
|
|
snarkjs. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
/*
|
|
This library does operations on polynomials with coefficients in a field F.
|
|
|
|
A polynomial P(x) = p0 + p1 * x + p2 * x^2 + ... + pn * x^n is represented
|
|
by the array [ p0, p1, p2, ... , pn ].
|
|
*/
|
|
|
|
class FFT {
|
|
constructor (G, F, opMulGF) {
|
|
this.F = F;
|
|
this.G = G;
|
|
this.opMulGF = opMulGF;
|
|
|
|
let rem = F.sqrt_t || F.t;
|
|
let s = F.sqrt_s || F.s;
|
|
|
|
let nqr = F.one;
|
|
while (F.eq(F.pow(nqr, F.half), F.one)) nqr = F.add(nqr, F.one);
|
|
|
|
this.w = new Array(s+1);
|
|
this.wi = new Array(s+1);
|
|
this.w[s] = this.F.pow(nqr, rem);
|
|
this.wi[s] = this.F.inv(this.w[s]);
|
|
|
|
let n=s-1;
|
|
while (n>=0) {
|
|
this.w[n] = this.F.square(this.w[n+1]);
|
|
this.wi[n] = this.F.square(this.wi[n+1]);
|
|
n--;
|
|
}
|
|
|
|
|
|
this.roots = [];
|
|
/*
|
|
for (let i=0; i<16; i++) {
|
|
let r = this.F.one;
|
|
n = 1 << i;
|
|
const rootsi = new Array(n);
|
|
for (let j=0; j<n; j++) {
|
|
rootsi[j] = r;
|
|
r = this.F.mul(r, this.w[i]);
|
|
}
|
|
|
|
this.roots.push(rootsi);
|
|
}
|
|
*/
|
|
this._setRoots(Math.min(s, 15));
|
|
}
|
|
|
|
_setRoots(n) {
|
|
for (let i=n; (i>=0) && (!this.roots[i]); i--) {
|
|
let r = this.F.one;
|
|
const nroots = 1 << i;
|
|
const rootsi = new Array(nroots);
|
|
for (let j=0; j<nroots; j++) {
|
|
rootsi[j] = r;
|
|
r = this.F.mul(r, this.w[i]);
|
|
}
|
|
|
|
this.roots[i] = rootsi;
|
|
}
|
|
}
|
|
|
|
fft(p) {
|
|
if (p.length <= 1) return p;
|
|
const bits = log2$1(p.length-1)+1;
|
|
this._setRoots(bits);
|
|
|
|
const m = 1 << bits;
|
|
if (p.length != m) {
|
|
throw new Error("Size must be multiple of 2");
|
|
}
|
|
const res = __fft(this, p, bits, 0, 1);
|
|
return res;
|
|
}
|
|
|
|
ifft(p) {
|
|
|
|
if (p.length <= 1) return p;
|
|
const bits = log2$1(p.length-1)+1;
|
|
this._setRoots(bits);
|
|
const m = 1 << bits;
|
|
if (p.length != m) {
|
|
throw new Error("Size must be multiple of 2");
|
|
}
|
|
const res = __fft(this, p, bits, 0, 1);
|
|
const twoinvm = this.F.inv( this.F.mulScalar(this.F.one, m) );
|
|
const resn = new Array(m);
|
|
for (let i=0; i<m; i++) {
|
|
resn[i] = this.opMulGF(res[(m-i)%m], twoinvm);
|
|
}
|
|
|
|
return resn;
|
|
}
|
|
|
|
|
|
}
|
|
|
|
function log2$1( V )
|
|
{
|
|
return( ( ( V & 0xFFFF0000 ) !== 0 ? ( V &= 0xFFFF0000, 16 ) : 0 ) | ( ( V & 0xFF00FF00 ) !== 0 ? ( V &= 0xFF00FF00, 8 ) : 0 ) | ( ( V & 0xF0F0F0F0 ) !== 0 ? ( V &= 0xF0F0F0F0, 4 ) : 0 ) | ( ( V & 0xCCCCCCCC ) !== 0 ? ( V &= 0xCCCCCCCC, 2 ) : 0 ) | ( ( V & 0xAAAAAAAA ) !== 0 ) );
|
|
}
|
|
|
|
|
|
function __fft(PF, pall, bits, offset, step) {
|
|
|
|
const n = 1 << bits;
|
|
if (n==1) {
|
|
return [ pall[offset] ];
|
|
} else if (n==2) {
|
|
return [
|
|
PF.G.add(pall[offset], pall[offset + step]),
|
|
PF.G.sub(pall[offset], pall[offset + step])];
|
|
}
|
|
|
|
const ndiv2 = n >> 1;
|
|
const p1 = __fft(PF, pall, bits-1, offset, step*2);
|
|
const p2 = __fft(PF, pall, bits-1, offset+step, step*2);
|
|
|
|
const out = new Array(n);
|
|
|
|
for (let i=0; i<ndiv2; i++) {
|
|
out[i] = PF.G.add(p1[i], PF.opMulGF(p2[i], PF.roots[bits][i]));
|
|
out[i+ndiv2] = PF.G.sub(p1[i], PF.opMulGF(p2[i], PF.roots[bits][i]));
|
|
}
|
|
|
|
return out;
|
|
}
|
|
|
|
/* global BigInt */
|
|
|
|
class ZqField {
|
|
constructor(p) {
|
|
this.type="F1";
|
|
this.one = BigInt(1);
|
|
this.zero = BigInt(0);
|
|
this.p = BigInt(p);
|
|
this.m = 1;
|
|
this.negone = this.p-this.one;
|
|
this.two = BigInt(2);
|
|
this.half = this.p >> this.one;
|
|
this.bitLength = bitLength(this.p);
|
|
this.mask = (this.one << BigInt(this.bitLength)) - this.one;
|
|
|
|
this.n64 = Math.floor((this.bitLength - 1) / 64)+1;
|
|
this.n32 = this.n64*2;
|
|
this.n8 = this.n64*8;
|
|
this.R = this.e(this.one << BigInt(this.n64*64));
|
|
this.Ri = this.inv(this.R);
|
|
|
|
const e = this.negone >> this.one;
|
|
this.nqr = this.two;
|
|
let r = this.pow(this.nqr, e);
|
|
while (!this.eq(r, this.negone)) {
|
|
this.nqr = this.nqr + this.one;
|
|
r = this.pow(this.nqr, e);
|
|
}
|
|
|
|
|
|
this.s = 0;
|
|
this.t = this.negone;
|
|
|
|
while ((this.t & this.one) == this.zero) {
|
|
this.s = this.s + 1;
|
|
this.t = this.t >> this.one;
|
|
}
|
|
|
|
this.nqr_to_t = this.pow(this.nqr, this.t);
|
|
|
|
buildSqrt(this);
|
|
|
|
this.FFT = new FFT(this, this, this.mul.bind(this));
|
|
|
|
this.fft = this.FFT.fft.bind(this.FFT);
|
|
this.ifft = this.FFT.ifft.bind(this.FFT);
|
|
this.w = this.FFT.w;
|
|
this.wi = this.FFT.wi;
|
|
|
|
this.shift = this.square(this.nqr);
|
|
this.k = this.exp(this.nqr, 2**this.s);
|
|
}
|
|
|
|
e(a,b) {
|
|
let res;
|
|
if (!b) {
|
|
res = BigInt(a);
|
|
} else if (b==16) {
|
|
res = BigInt("0x"+a);
|
|
}
|
|
if (res < 0) {
|
|
let nres = -res;
|
|
if (nres >= this.p) nres = nres % this.p;
|
|
return this.p - nres;
|
|
} else {
|
|
return (res>= this.p) ? res%this.p : res;
|
|
}
|
|
|
|
}
|
|
|
|
add(a, b) {
|
|
const res = a + b;
|
|
return res >= this.p ? res-this.p : res;
|
|
}
|
|
|
|
sub(a, b) {
|
|
return (a >= b) ? a-b : this.p-b+a;
|
|
}
|
|
|
|
neg(a) {
|
|
return a ? this.p-a : a;
|
|
}
|
|
|
|
mul(a, b) {
|
|
return (a*b)%this.p;
|
|
}
|
|
|
|
mulScalar(base, s) {
|
|
return (base * this.e(s)) % this.p;
|
|
}
|
|
|
|
square(a) {
|
|
return (a*a) % this.p;
|
|
}
|
|
|
|
eq(a, b) {
|
|
return a==b;
|
|
}
|
|
|
|
neq(a, b) {
|
|
return a!=b;
|
|
}
|
|
|
|
lt(a, b) {
|
|
const aa = (a > this.half) ? a - this.p : a;
|
|
const bb = (b > this.half) ? b - this.p : b;
|
|
return aa < bb;
|
|
}
|
|
|
|
gt(a, b) {
|
|
const aa = (a > this.half) ? a - this.p : a;
|
|
const bb = (b > this.half) ? b - this.p : b;
|
|
return aa > bb;
|
|
}
|
|
|
|
leq(a, b) {
|
|
const aa = (a > this.half) ? a - this.p : a;
|
|
const bb = (b > this.half) ? b - this.p : b;
|
|
return aa <= bb;
|
|
}
|
|
|
|
geq(a, b) {
|
|
const aa = (a > this.half) ? a - this.p : a;
|
|
const bb = (b > this.half) ? b - this.p : b;
|
|
return aa >= bb;
|
|
}
|
|
|
|
div(a, b) {
|
|
return this.mul(a, this.inv(b));
|
|
}
|
|
|
|
idiv(a, b) {
|
|
if (!b) throw new Error("Division by zero");
|
|
return a / b;
|
|
}
|
|
|
|
inv(a) {
|
|
if (!a) throw new Error("Division by zero");
|
|
|
|
let t = this.zero;
|
|
let r = this.p;
|
|
let newt = this.one;
|
|
let newr = a % this.p;
|
|
while (newr) {
|
|
let q = r/newr;
|
|
[t, newt] = [newt, t-q*newt];
|
|
[r, newr] = [newr, r-q*newr];
|
|
}
|
|
if (t<this.zero) t += this.p;
|
|
return t;
|
|
}
|
|
|
|
mod(a, b) {
|
|
return a % b;
|
|
}
|
|
|
|
pow(b, e) {
|
|
return exp(this, b, e);
|
|
}
|
|
|
|
exp(b, e) {
|
|
return exp(this, b, e);
|
|
}
|
|
|
|
band(a, b) {
|
|
const res = ((a & b) & this.mask);
|
|
return res >= this.p ? res-this.p : res;
|
|
}
|
|
|
|
bor(a, b) {
|
|
const res = ((a | b) & this.mask);
|
|
return res >= this.p ? res-this.p : res;
|
|
}
|
|
|
|
bxor(a, b) {
|
|
const res = ((a ^ b) & this.mask);
|
|
return res >= this.p ? res-this.p : res;
|
|
}
|
|
|
|
bnot(a) {
|
|
const res = a ^ this.mask;
|
|
return res >= this.p ? res-this.p : res;
|
|
}
|
|
|
|
shl(a, b) {
|
|
if (Number(b) < this.bitLength) {
|
|
const res = (a << b) & this.mask;
|
|
return res >= this.p ? res-this.p : res;
|
|
} else {
|
|
const nb = this.p - b;
|
|
if (Number(nb) < this.bitLength) {
|
|
return a >> nb;
|
|
} else {
|
|
return this.zero;
|
|
}
|
|
}
|
|
}
|
|
|
|
shr(a, b) {
|
|
if (Number(b) < this.bitLength) {
|
|
return a >> b;
|
|
} else {
|
|
const nb = this.p - b;
|
|
if (Number(nb) < this.bitLength) {
|
|
const res = (a << nb) & this.mask;
|
|
return res >= this.p ? res-this.p : res;
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
land(a, b) {
|
|
return (a && b) ? this.one : this.zero;
|
|
}
|
|
|
|
lor(a, b) {
|
|
return (a || b) ? this.one : this.zero;
|
|
}
|
|
|
|
lnot(a) {
|
|
return (a) ? this.zero : this.one;
|
|
}
|
|
|
|
sqrt_old(n) {
|
|
|
|
if (n == this.zero) return this.zero;
|
|
|
|
// Test that have solution
|
|
const res = this.pow(n, this.negone >> this.one);
|
|
if ( res != this.one ) return null;
|
|
|
|
let m = this.s;
|
|
let c = this.nqr_to_t;
|
|
let t = this.pow(n, this.t);
|
|
let r = this.pow(n, this.add(this.t, this.one) >> this.one );
|
|
|
|
while ( t != this.one ) {
|
|
let sq = this.square(t);
|
|
let i = 1;
|
|
while (sq != this.one ) {
|
|
i++;
|
|
sq = this.square(sq);
|
|
}
|
|
|
|
// b = c ^ m-i-1
|
|
let b = c;
|
|
for (let j=0; j< m-i-1; j ++) b = this.square(b);
|
|
|
|
m = i;
|
|
c = this.square(b);
|
|
t = this.mul(t, c);
|
|
r = this.mul(r, b);
|
|
}
|
|
|
|
if (r > (this.p >> this.one)) {
|
|
r = this.neg(r);
|
|
}
|
|
|
|
return r;
|
|
}
|
|
|
|
normalize(a, b) {
|
|
a = BigInt(a,b);
|
|
if (a < 0) {
|
|
let na = -a;
|
|
if (na >= this.p) na = na % this.p;
|
|
return this.p - na;
|
|
} else {
|
|
return (a>= this.p) ? a%this.p : a;
|
|
}
|
|
}
|
|
|
|
random() {
|
|
const nBytes = (this.bitLength*2 / 8);
|
|
let res =this.zero;
|
|
for (let i=0; i<nBytes; i++) {
|
|
res = (res << BigInt(8)) + BigInt(getRandomBytes(1)[0]);
|
|
}
|
|
return res % this.p;
|
|
}
|
|
|
|
toString(a, base) {
|
|
base = base || 10;
|
|
let vs;
|
|
if ((a > this.half)&&(base == 10)) {
|
|
const v = this.p-a;
|
|
vs = "-"+v.toString(base);
|
|
} else {
|
|
vs = a.toString(base);
|
|
}
|
|
return vs;
|
|
}
|
|
|
|
isZero(a) {
|
|
return a == this.zero;
|
|
}
|
|
|
|
fromRng(rng) {
|
|
let v;
|
|
do {
|
|
v=this.zero;
|
|
for (let i=0; i<this.n64; i++) {
|
|
v += rng.nextU64() << BigInt(64 *i);
|
|
}
|
|
v &= this.mask;
|
|
} while (v >= this.p);
|
|
v = (v * this.Ri) % this.p; // Convert from montgomery
|
|
return v;
|
|
}
|
|
|
|
fft(a) {
|
|
return this.FFT.fft(a);
|
|
}
|
|
|
|
ifft(a) {
|
|
return this.FFT.ifft(a);
|
|
}
|
|
|
|
// Returns a buffer with Little Endian Representation
|
|
toRprLE(buff, o, e) {
|
|
toRprLE(buff, o, e, this.n64*8);
|
|
}
|
|
|
|
// Returns a buffer with Big Endian Representation
|
|
toRprBE(buff, o, e) {
|
|
toRprBE(buff, o, e, this.n64*8);
|
|
}
|
|
|
|
// Returns a buffer with Big Endian Montgomery Representation
|
|
toRprBEM(buff, o, e) {
|
|
return this.toRprBE(buff, o, this.mul(this.R, e));
|
|
}
|
|
|
|
toRprLEM(buff, o, e) {
|
|
return this.toRprLE(buff, o, this.mul(this.R, e));
|
|
}
|
|
|
|
|
|
// Pases a buffer with Little Endian Representation
|
|
fromRprLE(buff, o) {
|
|
return fromRprLE(buff, o, this.n8);
|
|
}
|
|
|
|
// Pases a buffer with Big Endian Representation
|
|
fromRprBE(buff, o) {
|
|
return fromRprBE(buff, o, this.n8);
|
|
}
|
|
|
|
fromRprLEM(buff, o) {
|
|
return this.mul(this.fromRprLE(buff, o), this.Ri);
|
|
}
|
|
|
|
fromRprBEM(buff, o) {
|
|
return this.mul(this.fromRprBE(buff, o), this.Ri);
|
|
}
|
|
|
|
toObject(a) {
|
|
return a;
|
|
}
|
|
}
|
|
|
|
/*
|
|
Copyright 2018 0kims association.
|
|
|
|
This file is part of snarkjs.
|
|
|
|
snarkjs is a free software: you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License as published by the
|
|
Free Software Foundation, either version 3 of the License, or (at your option)
|
|
any later version.
|
|
|
|
snarkjs is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
more details.
|
|
|
|
You should have received a copy of the GNU General Public License along with
|
|
snarkjs. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
|
|
class F2Field {
|
|
constructor(F, nonResidue) {
|
|
this.type="F2";
|
|
this.F = F;
|
|
this.zero = [this.F.zero, this.F.zero];
|
|
this.one = [this.F.one, this.F.zero];
|
|
this.negone = this.neg(this.one);
|
|
this.nonResidue = nonResidue;
|
|
this.m = F.m*2;
|
|
this.p = F.p;
|
|
this.n64 = F.n64*2;
|
|
this.n32 = this.n64*2;
|
|
this.n8 = this.n64*8;
|
|
|
|
buildSqrt(this);
|
|
}
|
|
|
|
_mulByNonResidue(a) {
|
|
return this.F.mul(this.nonResidue, a);
|
|
}
|
|
|
|
copy(a) {
|
|
return [this.F.copy(a[0]), this.F.copy(a[1])];
|
|
}
|
|
|
|
add(a, b) {
|
|
return [
|
|
this.F.add(a[0], b[0]),
|
|
this.F.add(a[1], b[1])
|
|
];
|
|
}
|
|
|
|
double(a) {
|
|
return this.add(a,a);
|
|
}
|
|
|
|
sub(a, b) {
|
|
return [
|
|
this.F.sub(a[0], b[0]),
|
|
this.F.sub(a[1], b[1])
|
|
];
|
|
}
|
|
|
|
neg(a) {
|
|
return this.sub(this.zero, a);
|
|
}
|
|
|
|
conjugate(a) {
|
|
return [
|
|
a[0],
|
|
this.F.neg(a[1])
|
|
];
|
|
}
|
|
|
|
mul(a, b) {
|
|
const aA = this.F.mul(a[0] , b[0]);
|
|
const bB = this.F.mul(a[1] , b[1]);
|
|
|
|
return [
|
|
this.F.add( aA , this._mulByNonResidue(bB)),
|
|
this.F.sub(
|
|
this.F.mul(
|
|
this.F.add(a[0], a[1]),
|
|
this.F.add(b[0], b[1])),
|
|
this.F.add(aA, bB))];
|
|
}
|
|
|
|
inv(a) {
|
|
const t0 = this.F.square(a[0]);
|
|
const t1 = this.F.square(a[1]);
|
|
const t2 = this.F.sub(t0, this._mulByNonResidue(t1));
|
|
const t3 = this.F.inv(t2);
|
|
return [
|
|
this.F.mul(a[0], t3),
|
|
this.F.neg(this.F.mul( a[1], t3)) ];
|
|
}
|
|
|
|
div(a, b) {
|
|
return this.mul(a, this.inv(b));
|
|
}
|
|
|
|
square(a) {
|
|
const ab = this.F.mul(a[0] , a[1]);
|
|
|
|
/*
|
|
[
|
|
(a + b) * (a + non_residue * b) - ab - non_residue * ab,
|
|
ab + ab
|
|
];
|
|
*/
|
|
|
|
return [
|
|
this.F.sub(
|
|
this.F.mul(
|
|
this.F.add(a[0], a[1]) ,
|
|
this.F.add(
|
|
a[0] ,
|
|
this._mulByNonResidue(a[1]))),
|
|
this.F.add(
|
|
ab,
|
|
this._mulByNonResidue(ab))),
|
|
this.F.add(ab, ab)
|
|
];
|
|
}
|
|
|
|
isZero(a) {
|
|
return this.F.isZero(a[0]) && this.F.isZero(a[1]);
|
|
}
|
|
|
|
eq(a, b) {
|
|
return this.F.eq(a[0], b[0]) && this.F.eq(a[1], b[1]);
|
|
}
|
|
|
|
mulScalar(base, e) {
|
|
return mulScalar(this, base, e);
|
|
}
|
|
|
|
pow(base, e) {
|
|
return exp(this, base, e);
|
|
}
|
|
|
|
exp(base, e) {
|
|
return exp(this, base, e);
|
|
}
|
|
|
|
toString(a) {
|
|
return `[ ${this.F.toString(a[0])} , ${this.F.toString(a[1])} ]`;
|
|
}
|
|
|
|
fromRng(rng) {
|
|
const c0 = this.F.fromRng(rng);
|
|
const c1 = this.F.fromRng(rng);
|
|
return [c0, c1];
|
|
}
|
|
|
|
gt(a, b) {
|
|
if (this.F.gt(a[0], b[0])) return true;
|
|
if (this.F.gt(b[0], a[0])) return false;
|
|
if (this.F.gt(a[1], b[1])) return true;
|
|
return false;
|
|
}
|
|
|
|
geq(a, b) {
|
|
return this.gt(a, b) || this.eq(a, b);
|
|
}
|
|
|
|
lt(a, b) {
|
|
return !this.geq(a,b);
|
|
}
|
|
|
|
leq(a, b) {
|
|
return !this.gt(a,b);
|
|
}
|
|
|
|
neq(a, b) {
|
|
return !this.eq(a,b);
|
|
}
|
|
|
|
random() {
|
|
return [this.F.random(), this.F.random()];
|
|
}
|
|
|
|
|
|
toRprLE(buff, o, e) {
|
|
this.F.toRprLE(buff, o, e[0]);
|
|
this.F.toRprLE(buff, o+this.F.n8, e[1]);
|
|
}
|
|
|
|
toRprBE(buff, o, e) {
|
|
this.F.toRprBE(buff, o, e[1]);
|
|
this.F.toRprBE(buff, o+this.F.n8, e[0]);
|
|
}
|
|
|
|
toRprLEM(buff, o, e) {
|
|
this.F.toRprLEM(buff, o, e[0]);
|
|
this.F.toRprLEM(buff, o+this.F.n8, e[1]);
|
|
}
|
|
|
|
|
|
toRprBEM(buff, o, e) {
|
|
this.F.toRprBEM(buff, o, e[1]);
|
|
this.F.toRprBEM(buff, o+this.F.n8, e[0]);
|
|
}
|
|
|
|
fromRprLE(buff, o) {
|
|
o = o || 0;
|
|
const c0 = this.F.fromRprLE(buff, o);
|
|
const c1 = this.F.fromRprLE(buff, o+this.F.n8);
|
|
return [c0, c1];
|
|
}
|
|
|
|
fromRprBE(buff, o) {
|
|
o = o || 0;
|
|
const c1 = this.F.fromRprBE(buff, o);
|
|
const c0 = this.F.fromRprBE(buff, o+this.F.n8);
|
|
return [c0, c1];
|
|
}
|
|
|
|
fromRprLEM(buff, o) {
|
|
o = o || 0;
|
|
const c0 = this.F.fromRprLEM(buff, o);
|
|
const c1 = this.F.fromRprLEM(buff, o+this.F.n8);
|
|
return [c0, c1];
|
|
}
|
|
|
|
fromRprBEM(buff, o) {
|
|
o = o || 0;
|
|
const c1 = this.F.fromRprBEM(buff, o);
|
|
const c0 = this.F.fromRprBEM(buff, o+this.F.n8);
|
|
return [c0, c1];
|
|
}
|
|
|
|
toObject(a) {
|
|
return a;
|
|
}
|
|
|
|
}
|
|
|
|
/*
|
|
Copyright 2018 0kims association.
|
|
|
|
This file is part of snarkjs.
|
|
|
|
snarkjs is a free software: you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License as published by the
|
|
Free Software Foundation, either version 3 of the License, or (at your option)
|
|
any later version.
|
|
|
|
snarkjs is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
more details.
|
|
|
|
You should have received a copy of the GNU General Public License along with
|
|
snarkjs. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
|
|
class F3Field {
|
|
constructor(F, nonResidue) {
|
|
this.type="F3";
|
|
this.F = F;
|
|
this.zero = [this.F.zero, this.F.zero, this.F.zero];
|
|
this.one = [this.F.one, this.F.zero, this.F.zero];
|
|
this.negone = this.neg(this.one);
|
|
this.nonResidue = nonResidue;
|
|
this.m = F.m*3;
|
|
this.p = F.p;
|
|
this.n64 = F.n64*3;
|
|
this.n32 = this.n64*2;
|
|
this.n8 = this.n64*8;
|
|
}
|
|
|
|
_mulByNonResidue(a) {
|
|
return this.F.mul(this.nonResidue, a);
|
|
}
|
|
|
|
copy(a) {
|
|
return [this.F.copy(a[0]), this.F.copy(a[1]), this.F.copy(a[2])];
|
|
}
|
|
|
|
add(a, b) {
|
|
return [
|
|
this.F.add(a[0], b[0]),
|
|
this.F.add(a[1], b[1]),
|
|
this.F.add(a[2], b[2])
|
|
];
|
|
}
|
|
|
|
double(a) {
|
|
return this.add(a,a);
|
|
}
|
|
|
|
sub(a, b) {
|
|
return [
|
|
this.F.sub(a[0], b[0]),
|
|
this.F.sub(a[1], b[1]),
|
|
this.F.sub(a[2], b[2])
|
|
];
|
|
}
|
|
|
|
neg(a) {
|
|
return this.sub(this.zero, a);
|
|
}
|
|
|
|
mul(a, b) {
|
|
|
|
const aA = this.F.mul(a[0] , b[0]);
|
|
const bB = this.F.mul(a[1] , b[1]);
|
|
const cC = this.F.mul(a[2] , b[2]);
|
|
|
|
return [
|
|
this.F.add(
|
|
aA,
|
|
this._mulByNonResidue(
|
|
this.F.sub(
|
|
this.F.mul(
|
|
this.F.add(a[1], a[2]),
|
|
this.F.add(b[1], b[2])),
|
|
this.F.add(bB, cC)))), // aA + non_residue*((b+c)*(B+C)-bB-cC),
|
|
|
|
this.F.add(
|
|
this.F.sub(
|
|
this.F.mul(
|
|
this.F.add(a[0], a[1]),
|
|
this.F.add(b[0], b[1])),
|
|
this.F.add(aA, bB)),
|
|
this._mulByNonResidue( cC)), // (a+b)*(A+B)-aA-bB+non_residue*cC
|
|
|
|
this.F.add(
|
|
this.F.sub(
|
|
this.F.mul(
|
|
this.F.add(a[0], a[2]),
|
|
this.F.add(b[0], b[2])),
|
|
this.F.add(aA, cC)),
|
|
bB)]; // (a+c)*(A+C)-aA+bB-cC)
|
|
}
|
|
|
|
inv(a) {
|
|
const t0 = this.F.square(a[0]); // t0 = a^2 ;
|
|
const t1 = this.F.square(a[1]); // t1 = b^2 ;
|
|
const t2 = this.F.square(a[2]); // t2 = c^2;
|
|
const t3 = this.F.mul(a[0],a[1]); // t3 = ab
|
|
const t4 = this.F.mul(a[0],a[2]); // t4 = ac
|
|
const t5 = this.F.mul(a[1],a[2]); // t5 = bc;
|
|
// c0 = t0 - non_residue * t5;
|
|
const c0 = this.F.sub(t0, this._mulByNonResidue(t5));
|
|
// c1 = non_residue * t2 - t3;
|
|
const c1 = this.F.sub(this._mulByNonResidue(t2), t3);
|
|
const c2 = this.F.sub(t1, t4); // c2 = t1-t4
|
|
|
|
// t6 = (a * c0 + non_residue * (c * c1 + b * c2)).inv();
|
|
const t6 =
|
|
this.F.inv(
|
|
this.F.add(
|
|
this.F.mul(a[0], c0),
|
|
this._mulByNonResidue(
|
|
this.F.add(
|
|
this.F.mul(a[2], c1),
|
|
this.F.mul(a[1], c2)))));
|
|
|
|
return [
|
|
this.F.mul(t6, c0), // t6*c0
|
|
this.F.mul(t6, c1), // t6*c1
|
|
this.F.mul(t6, c2)]; // t6*c2
|
|
}
|
|
|
|
div(a, b) {
|
|
return this.mul(a, this.inv(b));
|
|
}
|
|
|
|
square(a) {
|
|
const s0 = this.F.square(a[0]); // s0 = a^2
|
|
const ab = this.F.mul(a[0], a[1]); // ab = a*b
|
|
const s1 = this.F.add(ab, ab); // s1 = 2ab;
|
|
const s2 = this.F.square(
|
|
this.F.add(this.F.sub(a[0],a[1]), a[2])); // s2 = (a - b + c)^2;
|
|
const bc = this.F.mul(a[1],a[2]); // bc = b*c
|
|
const s3 = this.F.add(bc, bc); // s3 = 2*bc
|
|
const s4 = this.F.square(a[2]); // s4 = c^2
|
|
|
|
|
|
return [
|
|
this.F.add(
|
|
s0,
|
|
this._mulByNonResidue(s3)), // s0 + non_residue * s3,
|
|
this.F.add(
|
|
s1,
|
|
this._mulByNonResidue(s4)), // s1 + non_residue * s4,
|
|
this.F.sub(
|
|
this.F.add( this.F.add(s1, s2) , s3 ),
|
|
this.F.add(s0, s4))]; // s1 + s2 + s3 - s0 - s4
|
|
}
|
|
|
|
isZero(a) {
|
|
return this.F.isZero(a[0]) && this.F.isZero(a[1]) && this.F.isZero(a[2]);
|
|
}
|
|
|
|
eq(a, b) {
|
|
return this.F.eq(a[0], b[0]) && this.F.eq(a[1], b[1]) && this.F.eq(a[2], b[2]);
|
|
}
|
|
|
|
affine(a) {
|
|
return [this.F.affine(a[0]), this.F.affine(a[1]), this.F.affine(a[2])];
|
|
}
|
|
|
|
mulScalar(base, e) {
|
|
return mulScalar(this, base, e);
|
|
}
|
|
|
|
pow(base, e) {
|
|
return exp(this, base, e);
|
|
}
|
|
|
|
exp(base, e) {
|
|
return exp(this, base, e);
|
|
}
|
|
|
|
toString(a) {
|
|
return `[ ${this.F.toString(a[0])} , ${this.F.toString(a[1])}, ${this.F.toString(a[2])} ]`;
|
|
}
|
|
|
|
fromRng(rng) {
|
|
const c0 = this.F.fromRng(rng);
|
|
const c1 = this.F.fromRng(rng);
|
|
const c2 = this.F.fromRng(rng);
|
|
return [c0, c1, c2];
|
|
}
|
|
|
|
gt(a, b) {
|
|
if (this.F.gt(a[0], b[0])) return true;
|
|
if (this.F.gt(b[0], a[0])) return false;
|
|
if (this.F.gt(a[1], b[1])) return true;
|
|
if (this.F.gt(b[1], a[1])) return false;
|
|
if (this.F.gt(a[2], b[2])) return true;
|
|
return false;
|
|
}
|
|
|
|
|
|
geq(a, b) {
|
|
return this.gt(a, b) || this.eq(a, b);
|
|
}
|
|
|
|
lt(a, b) {
|
|
return !this.geq(a,b);
|
|
}
|
|
|
|
leq(a, b) {
|
|
return !this.gt(a,b);
|
|
}
|
|
|
|
neq(a, b) {
|
|
return !this.eq(a,b);
|
|
}
|
|
|
|
random() {
|
|
return [this.F.random(), this.F.random(), this.F.random()];
|
|
}
|
|
|
|
|
|
toRprLE(buff, o, e) {
|
|
this.F.toRprLE(buff, o, e[0]);
|
|
this.F.toRprLE(buff, o+this.F.n8, e[1]);
|
|
this.F.toRprLE(buff, o+this.F.n8*2, e[2]);
|
|
}
|
|
|
|
toRprBE(buff, o, e) {
|
|
this.F.toRprBE(buff, o, e[2]);
|
|
this.F.toRprBE(buff, o+this.F.n8, e[1]);
|
|
this.F.toRprBE(buff, o+this.F.n8*2, e[0]);
|
|
}
|
|
|
|
toRprLEM(buff, o, e) {
|
|
this.F.toRprLEM(buff, o, e[0]);
|
|
this.F.toRprLEM(buff, o+this.F.n8, e[1]);
|
|
this.F.toRprLEM(buff, o+this.F.n8*2, e[2]);
|
|
}
|
|
|
|
|
|
toRprBEM(buff, o, e) {
|
|
this.F.toRprBEM(buff, o, e[2]);
|
|
this.F.toRprBEM(buff, o+this.F.n8, e[1]);
|
|
this.F.toRprBEM(buff, o+this.F.n8*2, e[0]);
|
|
}
|
|
|
|
fromRprLE(buff, o) {
|
|
o = o || 0;
|
|
const c0 = this.F.fromRprLE(buff, o);
|
|
const c1 = this.F.fromRprLE(buff, o+this.n8);
|
|
const c2 = this.F.fromRprLE(buff, o+this.n8*2);
|
|
return [c0, c1, c2];
|
|
}
|
|
|
|
fromRprBE(buff, o) {
|
|
o = o || 0;
|
|
const c2 = this.F.fromRprBE(buff, o);
|
|
const c1 = this.F.fromRprBE(buff, o+this.n8);
|
|
const c0 = this.F.fromRprBE(buff, o+this.n8*2);
|
|
return [c0, c1, c2];
|
|
}
|
|
|
|
fromRprLEM(buff, o) {
|
|
o = o || 0;
|
|
const c0 = this.F.fromRprLEM(buff, o);
|
|
const c1 = this.F.fromRprLEM(buff, o+this.n8);
|
|
const c2 = this.F.fromRprLEM(buff, o+this.n8*2);
|
|
return [c0, c1, c2];
|
|
}
|
|
|
|
fromRprBEM(buff, o) {
|
|
o = o || 0;
|
|
const c2 = this.F.fromRprBEM(buff, o);
|
|
const c1 = this.F.fromRprBEM(buff, o+this.n8);
|
|
const c0 = this.F.fromRprBEM(buff, o+this.n8*2);
|
|
return [c0, c1, c2];
|
|
}
|
|
|
|
toObject(a) {
|
|
return a;
|
|
}
|
|
}
|
|
|
|
/*
|
|
Copyright 2018 0kims association.
|
|
|
|
This file is part of snarkjs.
|
|
|
|
snarkjs is a free software: you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License as published by the
|
|
Free Software Foundation, either version 3 of the License, or (at your option)
|
|
any later version.
|
|
|
|
snarkjs is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
more details.
|
|
|
|
You should have received a copy of the GNU General Public License along with
|
|
snarkjs. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
|
|
|
|
function isGreatest(F, a) {
|
|
if (Array.isArray(a)) {
|
|
for (let i=a.length-1; i>=0; i--) {
|
|
if (!F.F.isZero(a[i])) {
|
|
return isGreatest(F.F, a[i]);
|
|
}
|
|
}
|
|
return 0;
|
|
} else {
|
|
const na = F.neg(a);
|
|
return gt(a, na);
|
|
}
|
|
}
|
|
|
|
|
|
class EC {
|
|
|
|
constructor(F, g) {
|
|
this.F = F;
|
|
this.g = g;
|
|
if (this.g.length == 2) this.g[2] = this.F.one;
|
|
this.zero = [this.F.zero, this.F.one, this.F.zero];
|
|
}
|
|
|
|
add(p1, p2) {
|
|
|
|
const F = this.F;
|
|
|
|
if (this.eq(p1, this.zero)) return p2;
|
|
if (this.eq(p2, this.zero)) return p1;
|
|
|
|
const res = new Array(3);
|
|
|
|
const Z1Z1 = F.square( p1[2] );
|
|
const Z2Z2 = F.square( p2[2] );
|
|
|
|
const U1 = F.mul( p1[0] , Z2Z2 ); // U1 = X1 * Z2Z2
|
|
const U2 = F.mul( p2[0] , Z1Z1 ); // U2 = X2 * Z1Z1
|
|
|
|
const Z1_cubed = F.mul( p1[2] , Z1Z1);
|
|
const Z2_cubed = F.mul( p2[2] , Z2Z2);
|
|
|
|
const S1 = F.mul( p1[1] , Z2_cubed); // S1 = Y1 * Z2 * Z2Z2
|
|
const S2 = F.mul( p2[1] , Z1_cubed); // S2 = Y2 * Z1 * Z1Z1
|
|
|
|
if (F.eq(U1,U2) && F.eq(S1,S2)) {
|
|
return this.double(p1);
|
|
}
|
|
|
|
const H = F.sub( U2 , U1 ); // H = U2-U1
|
|
|
|
const S2_minus_S1 = F.sub( S2 , S1 );
|
|
|
|
const I = F.square( F.add(H,H) ); // I = (2 * H)^2
|
|
const J = F.mul( H , I ); // J = H * I
|
|
|
|
const r = F.add( S2_minus_S1 , S2_minus_S1 ); // r = 2 * (S2-S1)
|
|
const V = F.mul( U1 , I ); // V = U1 * I
|
|
|
|
res[0] =
|
|
F.sub(
|
|
F.sub( F.square(r) , J ),
|
|
F.add( V , V )); // X3 = r^2 - J - 2 * V
|
|
|
|
const S1_J = F.mul( S1 , J );
|
|
|
|
res[1] =
|
|
F.sub(
|
|
F.mul( r , F.sub(V,res[0])),
|
|
F.add( S1_J,S1_J )); // Y3 = r * (V-X3)-2 S1 J
|
|
|
|
res[2] =
|
|
F.mul(
|
|
H,
|
|
F.sub(
|
|
F.square( F.add(p1[2],p2[2]) ),
|
|
F.add( Z1Z1 , Z2Z2 ))); // Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2) * H
|
|
|
|
return res;
|
|
}
|
|
|
|
neg(p) {
|
|
return [p[0], this.F.neg(p[1]), p[2]];
|
|
}
|
|
|
|
sub(a, b) {
|
|
return this.add(a, this.neg(b));
|
|
}
|
|
|
|
double(p) {
|
|
const F = this.F;
|
|
|
|
const res = new Array(3);
|
|
|
|
if (this.eq(p, this.zero)) return p;
|
|
|
|
const A = F.square( p[0] ); // A = X1^2
|
|
const B = F.square( p[1] ); // B = Y1^2
|
|
const C = F.square( B ); // C = B^2
|
|
|
|
let D =
|
|
F.sub(
|
|
F.square( F.add(p[0] , B )),
|
|
F.add( A , C));
|
|
D = F.add(D,D); // D = 2 * ((X1 + B)^2 - A - C)
|
|
|
|
const E = F.add( F.add(A,A), A); // E = 3 * A
|
|
const FF =F.square( E ); // F = E^2
|
|
|
|
res[0] = F.sub( FF , F.add(D,D) ); // X3 = F - 2 D
|
|
|
|
let eightC = F.add( C , C );
|
|
eightC = F.add( eightC , eightC );
|
|
eightC = F.add( eightC , eightC );
|
|
|
|
res[1] =
|
|
F.sub(
|
|
F.mul(
|
|
E,
|
|
F.sub( D, res[0] )),
|
|
eightC); // Y3 = E * (D - X3) - 8 * C
|
|
|
|
const Y1Z1 = F.mul( p[1] , p[2] );
|
|
res[2] = F.add( Y1Z1 , Y1Z1 ); // Z3 = 2 * Y1 * Z1
|
|
|
|
return res;
|
|
}
|
|
|
|
timesScalar(base, e) {
|
|
return mulScalar(this, base, e);
|
|
}
|
|
|
|
mulScalar(base, e) {
|
|
return mulScalar(this, base, e);
|
|
}
|
|
|
|
affine(p) {
|
|
const F = this.F;
|
|
if (this.isZero(p)) {
|
|
return this.zero;
|
|
} else if (F.eq(p[2], F.one)) {
|
|
return p;
|
|
} else {
|
|
const Z_inv = F.inv(p[2]);
|
|
const Z2_inv = F.square(Z_inv);
|
|
const Z3_inv = F.mul(Z2_inv, Z_inv);
|
|
|
|
const res = new Array(3);
|
|
res[0] = F.mul(p[0],Z2_inv);
|
|
res[1] = F.mul(p[1],Z3_inv);
|
|
res[2] = F.one;
|
|
|
|
return res;
|
|
}
|
|
}
|
|
|
|
multiAffine(arr) {
|
|
const keys = Object.keys(arr);
|
|
const F = this.F;
|
|
const accMul = new Array(keys.length+1);
|
|
accMul[0] = F.one;
|
|
for (let i = 0; i< keys.length; i++) {
|
|
if (F.eq(arr[keys[i]][2], F.zero)) {
|
|
accMul[i+1] = accMul[i];
|
|
} else {
|
|
accMul[i+1] = F.mul(accMul[i], arr[keys[i]][2]);
|
|
}
|
|
}
|
|
|
|
accMul[keys.length] = F.inv(accMul[keys.length]);
|
|
|
|
for (let i = keys.length-1; i>=0; i--) {
|
|
if (F.eq(arr[keys[i]][2], F.zero)) {
|
|
accMul[i] = accMul[i+1];
|
|
arr[keys[i]] = this.zero;
|
|
} else {
|
|
const Z_inv = F.mul(accMul[i], accMul[i+1]);
|
|
accMul[i] = F.mul(arr[keys[i]][2], accMul[i+1]);
|
|
|
|
const Z2_inv = F.square(Z_inv);
|
|
const Z3_inv = F.mul(Z2_inv, Z_inv);
|
|
|
|
arr[keys[i]][0] = F.mul(arr[keys[i]][0],Z2_inv);
|
|
arr[keys[i]][1] = F.mul(arr[keys[i]][1],Z3_inv);
|
|
arr[keys[i]][2] = F.one;
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
eq(p1, p2) {
|
|
const F = this.F;
|
|
|
|
if (this.F.eq(p1[2], this.F.zero)) return this.F.eq(p2[2], this.F.zero);
|
|
if (this.F.eq(p2[2], this.F.zero)) return false;
|
|
|
|
const Z1Z1 = F.square( p1[2] );
|
|
const Z2Z2 = F.square( p2[2] );
|
|
|
|
const U1 = F.mul( p1[0] , Z2Z2 );
|
|
const U2 = F.mul( p2[0] , Z1Z1 );
|
|
|
|
const Z1_cubed = F.mul( p1[2] , Z1Z1);
|
|
const Z2_cubed = F.mul( p2[2] , Z2Z2);
|
|
|
|
const S1 = F.mul( p1[1] , Z2_cubed);
|
|
const S2 = F.mul( p2[1] , Z1_cubed);
|
|
|
|
return (F.eq(U1,U2) && F.eq(S1,S2));
|
|
}
|
|
|
|
isZero(p) {
|
|
return this.F.isZero(p[2]);
|
|
}
|
|
|
|
toString(p) {
|
|
const cp = this.affine(p);
|
|
return `[ ${this.F.toString(cp[0])} , ${this.F.toString(cp[1])} ]`;
|
|
}
|
|
|
|
fromRng(rng) {
|
|
const F = this.F;
|
|
let P = [];
|
|
let greatest;
|
|
do {
|
|
P[0] = F.fromRng(rng);
|
|
greatest = rng.nextBool();
|
|
const x3b = F.add(F.mul(F.square(P[0]), P[0]), this.b);
|
|
P[1] = F.sqrt(x3b);
|
|
} while ((P[1] == null)||(F.isZero[P]));
|
|
|
|
const s = isGreatest(F, P[1]);
|
|
if (greatest ^ s) P[1] = F.neg(P[1]);
|
|
P[2] = F.one;
|
|
|
|
if (this.cofactor) {
|
|
P = this.mulScalar(P, this.cofactor);
|
|
}
|
|
|
|
P = this.affine(P);
|
|
|
|
return P;
|
|
|
|
}
|
|
|
|
toRprLE(buff, o, p) {
|
|
p = this.affine(p);
|
|
if (this.isZero(p)) {
|
|
const BuffV = new Uint8Array(buff, o, this.F.n8*2);
|
|
BuffV.fill(0);
|
|
return;
|
|
}
|
|
this.F.toRprLE(buff, o, p[0]);
|
|
this.F.toRprLE(buff, o+this.F.n8, p[1]);
|
|
}
|
|
|
|
toRprBE(buff, o, p) {
|
|
p = this.affine(p);
|
|
if (this.isZero(p)) {
|
|
const BuffV = new Uint8Array(buff, o, this.F.n8*2);
|
|
BuffV.fill(0);
|
|
return;
|
|
}
|
|
this.F.toRprBE(buff, o, p[0]);
|
|
this.F.toRprBE(buff, o+this.F.n8, p[1]);
|
|
}
|
|
|
|
toRprLEM(buff, o, p) {
|
|
p = this.affine(p);
|
|
if (this.isZero(p)) {
|
|
const BuffV = new Uint8Array(buff, o, this.F.n8*2);
|
|
BuffV.fill(0);
|
|
return;
|
|
}
|
|
this.F.toRprLEM(buff, o, p[0]);
|
|
this.F.toRprLEM(buff, o+this.F.n8, p[1]);
|
|
}
|
|
|
|
toRprLEJM(buff, o, p) {
|
|
p = this.affine(p);
|
|
if (this.isZero(p)) {
|
|
const BuffV = new Uint8Array(buff, o, this.F.n8*2);
|
|
BuffV.fill(0);
|
|
return;
|
|
}
|
|
this.F.toRprLEM(buff, o, p[0]);
|
|
this.F.toRprLEM(buff, o+this.F.n8, p[1]);
|
|
this.F.toRprLEM(buff, o+2*this.F.n8, p[2]);
|
|
}
|
|
|
|
|
|
toRprBEM(buff, o, p) {
|
|
p = this.affine(p);
|
|
if (this.isZero(p)) {
|
|
const BuffV = new Uint8Array(buff, o, this.F.n8*2);
|
|
BuffV.fill(0);
|
|
return;
|
|
}
|
|
this.F.toRprBEM(buff, o, p[0]);
|
|
this.F.toRprBEM(buff, o+this.F.n8, p[1]);
|
|
}
|
|
|
|
fromRprLE(buff, o) {
|
|
o = o || 0;
|
|
const x = this.F.fromRprLE(buff, o);
|
|
const y = this.F.fromRprLE(buff, o+this.F.n8);
|
|
if (this.F.isZero(x) && this.F.isZero(y)) {
|
|
return this.zero;
|
|
}
|
|
return [x, y, this.F.one];
|
|
}
|
|
|
|
fromRprBE(buff, o) {
|
|
o = o || 0;
|
|
const x = this.F.fromRprBE(buff, o);
|
|
const y = this.F.fromRprBE(buff, o+this.F.n8);
|
|
if (this.F.isZero(x) && this.F.isZero(y)) {
|
|
return this.zero;
|
|
}
|
|
return [x, y, this.F.one];
|
|
}
|
|
|
|
fromRprLEM(buff, o) {
|
|
o = o || 0;
|
|
const x = this.F.fromRprLEM(buff, o);
|
|
const y = this.F.fromRprLEM(buff, o+this.F.n8);
|
|
if (this.F.isZero(x) && this.F.isZero(y)) {
|
|
return this.zero;
|
|
}
|
|
return [x, y, this.F.one];
|
|
}
|
|
|
|
fromRprLEJM(buff, o) {
|
|
o = o || 0;
|
|
const x = this.F.fromRprLEM(buff, o);
|
|
const y = this.F.fromRprLEM(buff, o+this.F.n8);
|
|
const z = this.F.fromRprLEM(buff, o+this.F.n8*2);
|
|
if (this.F.isZero(x) && this.F.isZero(y)) {
|
|
return this.zero;
|
|
}
|
|
return [x, y, z];
|
|
}
|
|
|
|
fromRprBEM(buff, o) {
|
|
o = o || 0;
|
|
const x = this.F.fromRprBEM(buff, o);
|
|
const y = this.F.fromRprBEM(buff, o+this.F.n8);
|
|
if (this.F.isZero(x) && this.F.isZero(y)) {
|
|
return this.zero;
|
|
}
|
|
return [x, y, this.F.one];
|
|
}
|
|
|
|
fromRprCompressed(buff, o) {
|
|
const F = this.F;
|
|
const v = new Uint8Array(buff.buffer, o, F.n8);
|
|
if (v[0] & 0x40) return this.zero;
|
|
const P = new Array(3);
|
|
|
|
const greatest = ((v[0] & 0x80) != 0);
|
|
v[0] = v[0] & 0x7F;
|
|
P[0] = F.fromRprBE(buff, o);
|
|
if (greatest) v[0] = v[0] | 0x80; // set back again the old value
|
|
|
|
const x3b = F.add(F.mul(F.square(P[0]), P[0]), this.b);
|
|
P[1] = F.sqrt(x3b);
|
|
|
|
if (P[1] === null) {
|
|
throw new Error("Invalid Point!");
|
|
}
|
|
|
|
const s = isGreatest(F, P[1]);
|
|
if (greatest ^ s) P[1] = F.neg(P[1]);
|
|
P[2] = F.one;
|
|
|
|
return P;
|
|
}
|
|
|
|
toRprCompressed(buff, o, p) {
|
|
p = this.affine(p);
|
|
const v = new Uint8Array(buff.buffer, o, this.F.n8);
|
|
if (this.isZero(p)) {
|
|
v.fill(0);
|
|
v[0] = 0x40;
|
|
return;
|
|
}
|
|
this.F.toRprBE(buff, o, p[0]);
|
|
|
|
if (isGreatest(this.F, p[1])) {
|
|
v[0] = v[0] | 0x80;
|
|
}
|
|
}
|
|
|
|
|
|
fromRprUncompressed(buff, o) {
|
|
if (buff[0] & 0x40) return this.zero;
|
|
|
|
return this.fromRprBE(buff, o);
|
|
}
|
|
|
|
toRprUncompressed(buff, o, p) {
|
|
this.toRprBE(buff, o, p);
|
|
|
|
if (this.isZero(p)) {
|
|
buff[o] = buff[o] | 0x40;
|
|
}
|
|
}
|
|
|
|
|
|
}
|
|
|
|
/* global BigInt */
|
|
|
|
function stringifyBigInts(o) {
|
|
if (typeof o == "bigint" || o.eq !== undefined) {
|
|
return o.toString(10);
|
|
} else if (o instanceof Uint8Array) {
|
|
return fromRprLE(o, 0);
|
|
} else if (Array.isArray(o)) {
|
|
return o.map(stringifyBigInts);
|
|
} else if (typeof o == "object") {
|
|
const res = {};
|
|
const keys = Object.keys(o);
|
|
keys.forEach((k) => {
|
|
res[k] = stringifyBigInts(o[k]);
|
|
});
|
|
return res;
|
|
} else {
|
|
return o;
|
|
}
|
|
}
|
|
|
|
function unstringifyBigInts(o) {
|
|
if (typeof o == "string" && /^[0-9]+$/.test(o)) {
|
|
return BigInt(o);
|
|
} else if (typeof o == "string" && /^0x[0-9a-fA-F]+$/.test(o)) {
|
|
return BigInt(o);
|
|
} else if (Array.isArray(o)) {
|
|
return o.map(unstringifyBigInts);
|
|
} else if (typeof o == "object") {
|
|
if (o === null) return null;
|
|
const res = {};
|
|
const keys = Object.keys(o);
|
|
keys.forEach((k) => {
|
|
res[k] = unstringifyBigInts(o[k]);
|
|
});
|
|
return res;
|
|
} else {
|
|
return o;
|
|
}
|
|
}
|
|
|
|
function beBuff2int(buff) {
|
|
let res = BigInt(0);
|
|
let i = buff.length;
|
|
let offset = 0;
|
|
const buffV = new DataView(buff.buffer, buff.byteOffset, buff.byteLength);
|
|
while (i > 0) {
|
|
if (i >= 4) {
|
|
i -= 4;
|
|
res += BigInt(buffV.getUint32(i)) << BigInt(offset * 8);
|
|
offset += 4;
|
|
} else if (i >= 2) {
|
|
i -= 2;
|
|
res += BigInt(buffV.getUint16(i)) << BigInt(offset * 8);
|
|
offset += 2;
|
|
} else {
|
|
i -= 1;
|
|
res += BigInt(buffV.getUint8(i)) << BigInt(offset * 8);
|
|
offset += 1;
|
|
}
|
|
}
|
|
return res;
|
|
}
|
|
|
|
function beInt2Buff(n, len) {
|
|
let r = n;
|
|
const buff = new Uint8Array(len);
|
|
const buffV = new DataView(buff.buffer);
|
|
let o = len;
|
|
while (o > 0) {
|
|
if (o - 4 >= 0) {
|
|
o -= 4;
|
|
buffV.setUint32(o, Number(r & BigInt(0xffffffff)));
|
|
r = r >> BigInt(32);
|
|
} else if (o - 2 >= 0) {
|
|
o -= 2;
|
|
buffV.setUint16(o, Number(r & BigInt(0xffff)));
|
|
r = r >> BigInt(16);
|
|
} else {
|
|
o -= 1;
|
|
buffV.setUint8(o, Number(r & BigInt(0xff)));
|
|
r = r >> BigInt(8);
|
|
}
|
|
}
|
|
if (r) {
|
|
throw new Error("Number does not fit in this length");
|
|
}
|
|
return buff;
|
|
}
|
|
|
|
function leBuff2int(buff) {
|
|
let res = BigInt(0);
|
|
let i = 0;
|
|
const buffV = new DataView(buff.buffer, buff.byteOffset, buff.byteLength);
|
|
while (i < buff.length) {
|
|
if (i + 4 <= buff.length) {
|
|
res += BigInt(buffV.getUint32(i, true)) << BigInt(i * 8);
|
|
i += 4;
|
|
} else if (i + 2 <= buff.length) {
|
|
res += BigInt(buffV.getUint16(i, true)) << BigInt(i * 8);
|
|
i += 2;
|
|
} else {
|
|
res += BigInt(buffV.getUint8(i, true)) << BigInt(i * 8);
|
|
i += 1;
|
|
}
|
|
}
|
|
return res;
|
|
}
|
|
|
|
function leInt2Buff(n, len) {
|
|
let r = n;
|
|
if (typeof len === "undefined") {
|
|
len = Math.floor((bitLength(n) - 1) / 8) + 1;
|
|
if (len == 0) len = 1;
|
|
}
|
|
const buff = new Uint8Array(len);
|
|
const buffV = new DataView(buff.buffer);
|
|
let o = 0;
|
|
while (o < len) {
|
|
if (o + 4 <= len) {
|
|
buffV.setUint32(o, Number(r & BigInt(0xffffffff)), true);
|
|
o += 4;
|
|
r = r >> BigInt(32);
|
|
} else if (o + 2 <= len) {
|
|
buffV.setUint16(o, Number(r & BigInt(0xffff)), true);
|
|
o += 2;
|
|
r = r >> BigInt(16);
|
|
} else {
|
|
buffV.setUint8(o, Number(r & BigInt(0xff)), true);
|
|
o += 1;
|
|
r = r >> BigInt(8);
|
|
}
|
|
}
|
|
if (r) {
|
|
throw new Error("Number does not fit in this length");
|
|
}
|
|
return buff;
|
|
}
|
|
|
|
function stringifyFElements(F, o) {
|
|
if (typeof o == "bigint" || o.eq !== undefined) {
|
|
return o.toString(10);
|
|
} else if (o instanceof Uint8Array) {
|
|
return F.toString(F.e(o));
|
|
} else if (Array.isArray(o)) {
|
|
return o.map(stringifyFElements.bind(this, F));
|
|
} else if (typeof o == "object") {
|
|
const res = {};
|
|
const keys = Object.keys(o);
|
|
keys.forEach((k) => {
|
|
res[k] = stringifyFElements(F, o[k]);
|
|
});
|
|
return res;
|
|
} else {
|
|
return o;
|
|
}
|
|
}
|
|
|
|
function unstringifyFElements(F, o) {
|
|
if (typeof o == "string" && /^[0-9]+$/.test(o)) {
|
|
return F.e(o);
|
|
} else if (typeof o == "string" && /^0x[0-9a-fA-F]+$/.test(o)) {
|
|
return F.e(o);
|
|
} else if (Array.isArray(o)) {
|
|
return o.map(unstringifyFElements.bind(this, F));
|
|
} else if (typeof o == "object") {
|
|
if (o === null) return null;
|
|
const res = {};
|
|
const keys = Object.keys(o);
|
|
keys.forEach((k) => {
|
|
res[k] = unstringifyFElements(F, o[k]);
|
|
});
|
|
return res;
|
|
} else {
|
|
return o;
|
|
}
|
|
}
|
|
|
|
const _revTable = [];
|
|
for (let i = 0; i < 256; i++) {
|
|
_revTable[i] = _revSlow(i, 8);
|
|
}
|
|
|
|
function _revSlow(idx, bits) {
|
|
let res = 0;
|
|
let a = idx;
|
|
for (let i = 0; i < bits; i++) {
|
|
res <<= 1;
|
|
res = res | (a & 1);
|
|
a >>= 1;
|
|
}
|
|
return res;
|
|
}
|
|
|
|
function bitReverse(idx, bits) {
|
|
return (
|
|
(_revTable[idx >>> 24] |
|
|
(_revTable[(idx >>> 16) & 0xff] << 8) |
|
|
(_revTable[(idx >>> 8) & 0xff] << 16) |
|
|
(_revTable[idx & 0xff] << 24)) >>>
|
|
(32 - bits)
|
|
);
|
|
}
|
|
|
|
function log2(V) {
|
|
return (
|
|
((V & 0xffff0000) !== 0 ? ((V &= 0xffff0000), 16) : 0) |
|
|
((V & 0xff00ff00) !== 0 ? ((V &= 0xff00ff00), 8) : 0) |
|
|
((V & 0xf0f0f0f0) !== 0 ? ((V &= 0xf0f0f0f0), 4) : 0) |
|
|
((V & 0xcccccccc) !== 0 ? ((V &= 0xcccccccc), 2) : 0) |
|
|
((V & 0xaaaaaaaa) !== 0)
|
|
);
|
|
}
|
|
|
|
function buffReverseBits(buff, eSize) {
|
|
const n = buff.byteLength / eSize;
|
|
const bits = log2(n);
|
|
if (n != 1 << bits) {
|
|
throw new Error("Invalid number of pointers");
|
|
}
|
|
for (let i = 0; i < n; i++) {
|
|
const r = bitReverse(i, bits);
|
|
if (i > r) {
|
|
const tmp = buff.slice(i * eSize, (i + 1) * eSize);
|
|
buff.set(buff.slice(r * eSize, (r + 1) * eSize), i * eSize);
|
|
buff.set(tmp, r * eSize);
|
|
}
|
|
}
|
|
}
|
|
|
|
function array2buffer(arr, sG) {
|
|
const buff = new Uint8Array(sG * arr.length);
|
|
|
|
for (let i = 0; i < arr.length; i++) {
|
|
buff.set(arr[i], i * sG);
|
|
}
|
|
|
|
return buff;
|
|
}
|
|
|
|
function buffer2array(buff, sG) {
|
|
const n = buff.byteLength / sG;
|
|
const arr = new Array(n);
|
|
for (let i = 0; i < n; i++) {
|
|
arr[i] = buff.slice(i * sG, i * sG + sG);
|
|
}
|
|
return arr;
|
|
}
|
|
|
|
var _utils = /*#__PURE__*/Object.freeze({
|
|
__proto__: null,
|
|
array2buffer: array2buffer,
|
|
beBuff2int: beBuff2int,
|
|
beInt2Buff: beInt2Buff,
|
|
bitReverse: bitReverse,
|
|
buffReverseBits: buffReverseBits,
|
|
buffer2array: buffer2array,
|
|
leBuff2int: leBuff2int,
|
|
leInt2Buff: leInt2Buff,
|
|
log2: log2,
|
|
stringifyBigInts: stringifyBigInts,
|
|
stringifyFElements: stringifyFElements,
|
|
unstringifyBigInts: unstringifyBigInts,
|
|
unstringifyFElements: unstringifyFElements
|
|
});
|
|
|
|
const PAGE_SIZE = 1<<30;
|
|
|
|
class BigBuffer {
|
|
|
|
constructor(size) {
|
|
this.buffers = [];
|
|
this.byteLength = size;
|
|
for (let i=0; i<size; i+= PAGE_SIZE) {
|
|
const n = Math.min(size-i, PAGE_SIZE);
|
|
this.buffers.push(new Uint8Array(n));
|
|
}
|
|
|
|
}
|
|
|
|
slice(fr, to) {
|
|
if ( to === undefined ) to = this.byteLength;
|
|
if ( fr === undefined ) fr = 0;
|
|
const len = to-fr;
|
|
|
|
const firstPage = Math.floor(fr / PAGE_SIZE);
|
|
const lastPage = Math.floor((fr+len-1) / PAGE_SIZE);
|
|
|
|
if ((firstPage == lastPage)||(len==0))
|
|
return this.buffers[firstPage].slice(fr%PAGE_SIZE, fr%PAGE_SIZE + len);
|
|
|
|
let buff;
|
|
|
|
let p = firstPage;
|
|
let o = fr % PAGE_SIZE;
|
|
// Remaining bytes to read
|
|
let r = len;
|
|
while (r>0) {
|
|
// bytes to copy from this page
|
|
const l = (o+r > PAGE_SIZE) ? (PAGE_SIZE -o) : r;
|
|
const srcView = new Uint8Array(this.buffers[p].buffer, this.buffers[p].byteOffset+o, l);
|
|
if (l == len) return srcView.slice();
|
|
if (!buff) {
|
|
if (len <= PAGE_SIZE) {
|
|
buff = new Uint8Array(len);
|
|
} else {
|
|
buff = new BigBuffer(len);
|
|
}
|
|
}
|
|
buff.set(srcView, len-r);
|
|
r = r-l;
|
|
p ++;
|
|
o = 0;
|
|
}
|
|
|
|
return buff;
|
|
}
|
|
|
|
set(buff, offset) {
|
|
if (offset === undefined) offset = 0;
|
|
|
|
const len = buff.byteLength;
|
|
|
|
if (len==0) return;
|
|
|
|
const firstPage = Math.floor(offset / PAGE_SIZE);
|
|
const lastPage = Math.floor((offset+len-1) / PAGE_SIZE);
|
|
|
|
if (firstPage == lastPage) {
|
|
if ((buff instanceof BigBuffer)&&(buff.buffers.length==1)) {
|
|
return this.buffers[firstPage].set(buff.buffers[0], offset % PAGE_SIZE);
|
|
} else {
|
|
return this.buffers[firstPage].set(buff, offset % PAGE_SIZE);
|
|
}
|
|
|
|
}
|
|
|
|
|
|
let p = firstPage;
|
|
let o = offset % PAGE_SIZE;
|
|
let r = len;
|
|
while (r>0) {
|
|
const l = (o+r > PAGE_SIZE) ? (PAGE_SIZE -o) : r;
|
|
const srcView = buff.slice( len -r, len -r+l);
|
|
const dstView = new Uint8Array(this.buffers[p].buffer, this.buffers[p].byteOffset + o, l);
|
|
dstView.set(srcView);
|
|
r = r-l;
|
|
p ++;
|
|
o = 0;
|
|
}
|
|
|
|
}
|
|
}
|
|
|
|
function buildBatchConvert(tm, fnName, sIn, sOut) {
|
|
return async function batchConvert(buffIn) {
|
|
const nPoints = Math.floor(buffIn.byteLength / sIn);
|
|
if ( nPoints * sIn !== buffIn.byteLength) {
|
|
throw new Error("Invalid buffer size");
|
|
}
|
|
const pointsPerChunk = Math.floor(nPoints/tm.concurrency);
|
|
const opPromises = [];
|
|
for (let i=0; i<tm.concurrency; i++) {
|
|
let n;
|
|
if (i< tm.concurrency-1) {
|
|
n = pointsPerChunk;
|
|
} else {
|
|
n = nPoints - i*pointsPerChunk;
|
|
}
|
|
if (n==0) continue;
|
|
|
|
const buffChunk = buffIn.slice(i*pointsPerChunk*sIn, i*pointsPerChunk*sIn + n*sIn);
|
|
const task = [
|
|
{cmd: "ALLOCSET", var: 0, buff:buffChunk},
|
|
{cmd: "ALLOC", var: 1, len:sOut * n},
|
|
{cmd: "CALL", fnName: fnName, params: [
|
|
{var: 0},
|
|
{val: n},
|
|
{var: 1}
|
|
]},
|
|
{cmd: "GET", out: 0, var: 1, len:sOut * n},
|
|
];
|
|
opPromises.push(
|
|
tm.queueAction(task)
|
|
);
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let fullBuffOut;
|
|
if (buffIn instanceof BigBuffer) {
|
|
fullBuffOut = new BigBuffer(nPoints*sOut);
|
|
} else {
|
|
fullBuffOut = new Uint8Array(nPoints*sOut);
|
|
}
|
|
|
|
let p =0;
|
|
for (let i=0; i<result.length; i++) {
|
|
fullBuffOut.set(result[i][0], p);
|
|
p+=result[i][0].byteLength;
|
|
}
|
|
|
|
return fullBuffOut;
|
|
};
|
|
}
|
|
|
|
class WasmField1 {
|
|
|
|
constructor(tm, prefix, n8, p) {
|
|
this.tm = tm;
|
|
this.prefix = prefix;
|
|
|
|
this.p = p;
|
|
this.n8 = n8;
|
|
this.type = "F1";
|
|
this.m = 1;
|
|
|
|
this.half = shiftRight(p, one);
|
|
this.bitLength = bitLength(p);
|
|
this.mask = sub(shiftLeft(one, this.bitLength), one);
|
|
|
|
this.pOp1 = tm.alloc(n8);
|
|
this.pOp2 = tm.alloc(n8);
|
|
this.pOp3 = tm.alloc(n8);
|
|
this.tm.instance.exports[prefix + "_zero"](this.pOp1);
|
|
this.zero = this.tm.getBuff(this.pOp1, this.n8);
|
|
this.tm.instance.exports[prefix + "_one"](this.pOp1);
|
|
this.one = this.tm.getBuff(this.pOp1, this.n8);
|
|
|
|
this.negone = this.neg(this.one);
|
|
this.two = this.add(this.one, this.one);
|
|
|
|
this.n64 = Math.floor(n8/8);
|
|
this.n32 = Math.floor(n8/4);
|
|
|
|
if(this.n64*8 != this.n8) {
|
|
throw new Error("n8 must be a multiple of 8");
|
|
}
|
|
|
|
this.half = shiftRight(this.p, one);
|
|
this.nqr = this.two;
|
|
let r = this.exp(this.nqr, this.half);
|
|
while (!this.eq(r, this.negone)) {
|
|
this.nqr = this.add(this.nqr, this.one);
|
|
r = this.exp(this.nqr, this.half);
|
|
}
|
|
|
|
this.shift = this.mul(this.nqr, this.nqr);
|
|
this.shiftInv = this.inv(this.shift);
|
|
|
|
this.s = 0;
|
|
let t = sub(this.p, one);
|
|
|
|
while ( !isOdd(t) ) {
|
|
this.s = this.s + 1;
|
|
t = shiftRight(t, one);
|
|
}
|
|
|
|
this.w = [];
|
|
this.w[this.s] = this.exp(this.nqr, t);
|
|
|
|
for (let i= this.s-1; i>=0; i--) {
|
|
this.w[i] = this.square(this.w[i+1]);
|
|
}
|
|
|
|
if (!this.eq(this.w[0], this.one)) {
|
|
throw new Error("Error calculating roots of unity");
|
|
}
|
|
|
|
this.batchToMontgomery = buildBatchConvert(tm, prefix + "_batchToMontgomery", this.n8, this.n8);
|
|
this.batchFromMontgomery = buildBatchConvert(tm, prefix + "_batchFromMontgomery", this.n8, this.n8);
|
|
}
|
|
|
|
|
|
op2(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
op2Bool(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2);
|
|
}
|
|
|
|
op1(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
op1Bool(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
}
|
|
|
|
add(a,b) {
|
|
return this.op2("_add", a, b);
|
|
}
|
|
|
|
|
|
eq(a,b) {
|
|
return this.op2Bool("_eq", a, b);
|
|
}
|
|
|
|
isZero(a) {
|
|
return this.op1Bool("_isZero", a);
|
|
}
|
|
|
|
sub(a,b) {
|
|
return this.op2("_sub", a, b);
|
|
}
|
|
|
|
neg(a) {
|
|
return this.op1("_neg", a);
|
|
}
|
|
|
|
inv(a) {
|
|
return this.op1("_inverse", a);
|
|
}
|
|
|
|
toMontgomery(a) {
|
|
return this.op1("_toMontgomery", a);
|
|
}
|
|
|
|
fromMontgomery(a) {
|
|
return this.op1("_fromMontgomery", a);
|
|
}
|
|
|
|
mul(a,b) {
|
|
return this.op2("_mul", a, b);
|
|
}
|
|
|
|
div(a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + "_inverse"](this.pOp2, this.pOp2);
|
|
this.tm.instance.exports[this.prefix + "_mul"](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
square(a) {
|
|
return this.op1("_square", a);
|
|
}
|
|
|
|
isSquare(a) {
|
|
return this.op1Bool("_isSquare", a);
|
|
}
|
|
|
|
sqrt(a) {
|
|
return this.op1("_sqrt", a);
|
|
}
|
|
|
|
exp(a, b) {
|
|
if (!(b instanceof Uint8Array)) {
|
|
b = toLEBuff(e(b));
|
|
}
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + "_exp"](this.pOp1, this.pOp2, b.byteLength, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
isNegative(a) {
|
|
return this.op1Bool("_isNegative", a);
|
|
}
|
|
|
|
e(a, b) {
|
|
if (a instanceof Uint8Array) return a;
|
|
let ra = e(a, b);
|
|
if (isNegative(ra)) {
|
|
ra = neg(ra);
|
|
if (gt(ra, this.p)) {
|
|
ra = mod(ra, this.p);
|
|
}
|
|
ra = sub(this.p, ra);
|
|
} else {
|
|
if (gt(ra, this.p)) {
|
|
ra = mod(ra, this.p);
|
|
}
|
|
}
|
|
const buff = leInt2Buff(ra, this.n8);
|
|
return this.toMontgomery(buff);
|
|
}
|
|
|
|
toString(a, radix) {
|
|
const an = this.fromMontgomery(a);
|
|
const s = fromRprLE(an, 0);
|
|
return toString(s, radix);
|
|
}
|
|
|
|
fromRng(rng) {
|
|
let v;
|
|
const buff = new Uint8Array(this.n8);
|
|
do {
|
|
v = zero;
|
|
for (let i=0; i<this.n64; i++) {
|
|
v = add(v, shiftLeft(rng.nextU64(), 64*i));
|
|
}
|
|
v = band(v, this.mask);
|
|
} while (geq(v, this.p));
|
|
toRprLE(buff, 0, v, this.n8);
|
|
return buff;
|
|
}
|
|
|
|
random() {
|
|
return this.fromRng(getThreadRng());
|
|
}
|
|
|
|
toObject(a) {
|
|
const an = this.fromMontgomery(a);
|
|
return fromRprLE(an, 0);
|
|
}
|
|
|
|
fromObject(a) {
|
|
const buff = new Uint8Array(this.n8);
|
|
toRprLE(buff, 0, a, this.n8);
|
|
return this.toMontgomery(buff);
|
|
}
|
|
|
|
toRprLE(buff, offset, a) {
|
|
buff.set(this.fromMontgomery(a), offset);
|
|
}
|
|
|
|
toRprBE(buff, offset, a) {
|
|
const buff2 = this.fromMontgomery(a);
|
|
for (let i=0; i<this.n8/2; i++) {
|
|
const aux = buff2[i];
|
|
buff2[i] = buff2[this.n8-1-i];
|
|
buff2[this.n8-1-i] = aux;
|
|
}
|
|
buff.set(buff2, offset);
|
|
}
|
|
|
|
fromRprLE(buff, offset) {
|
|
offset = offset || 0;
|
|
const res = buff.slice(offset, offset + this.n8);
|
|
return this.toMontgomery(res);
|
|
}
|
|
|
|
async batchInverse(buffIn) {
|
|
let returnArray = false;
|
|
const sIn = this.n8;
|
|
const sOut = this.n8;
|
|
|
|
if (Array.isArray(buffIn)) {
|
|
buffIn = array2buffer(buffIn, sIn );
|
|
returnArray = true;
|
|
} else {
|
|
buffIn = buffIn.slice(0, buffIn.byteLength);
|
|
}
|
|
|
|
const nPoints = Math.floor(buffIn.byteLength / sIn);
|
|
if ( nPoints * sIn !== buffIn.byteLength) {
|
|
throw new Error("Invalid buffer size");
|
|
}
|
|
const pointsPerChunk = Math.floor(nPoints/this.tm.concurrency);
|
|
const opPromises = [];
|
|
for (let i=0; i<this.tm.concurrency; i++) {
|
|
let n;
|
|
if (i< this.tm.concurrency-1) {
|
|
n = pointsPerChunk;
|
|
} else {
|
|
n = nPoints - i*pointsPerChunk;
|
|
}
|
|
if (n==0) continue;
|
|
|
|
const buffChunk = buffIn.slice(i*pointsPerChunk*sIn, i*pointsPerChunk*sIn + n*sIn);
|
|
const task = [
|
|
{cmd: "ALLOCSET", var: 0, buff:buffChunk},
|
|
{cmd: "ALLOC", var: 1, len:sOut * n},
|
|
{cmd: "CALL", fnName: this.prefix + "_batchInverse", params: [
|
|
{var: 0},
|
|
{val: sIn},
|
|
{val: n},
|
|
{var: 1},
|
|
{val: sOut},
|
|
]},
|
|
{cmd: "GET", out: 0, var: 1, len:sOut * n},
|
|
];
|
|
opPromises.push(
|
|
this.tm.queueAction(task)
|
|
);
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let fullBuffOut;
|
|
if (buffIn instanceof BigBuffer) {
|
|
fullBuffOut = new BigBuffer(nPoints*sOut);
|
|
} else {
|
|
fullBuffOut = new Uint8Array(nPoints*sOut);
|
|
}
|
|
|
|
let p =0;
|
|
for (let i=0; i<result.length; i++) {
|
|
fullBuffOut.set(result[i][0], p);
|
|
p+=result[i][0].byteLength;
|
|
}
|
|
|
|
if (returnArray) {
|
|
return buffer2array(fullBuffOut, sOut);
|
|
} else {
|
|
return fullBuffOut;
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
class WasmField2 {
|
|
|
|
constructor(tm, prefix, F) {
|
|
this.tm = tm;
|
|
this.prefix = prefix;
|
|
|
|
this.F = F;
|
|
this.type = "F2";
|
|
this.m = F.m * 2;
|
|
this.n8 = this.F.n8*2;
|
|
this.n32 = this.F.n32*2;
|
|
this.n64 = this.F.n64*2;
|
|
|
|
this.pOp1 = tm.alloc(F.n8*2);
|
|
this.pOp2 = tm.alloc(F.n8*2);
|
|
this.pOp3 = tm.alloc(F.n8*2);
|
|
this.tm.instance.exports[prefix + "_zero"](this.pOp1);
|
|
this.zero = tm.getBuff(this.pOp1, this.n8);
|
|
this.tm.instance.exports[prefix + "_one"](this.pOp1);
|
|
this.one = tm.getBuff(this.pOp1, this.n8);
|
|
|
|
this.negone = this.neg(this.one);
|
|
this.two = this.add(this.one, this.one);
|
|
|
|
}
|
|
|
|
op2(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
op2Bool(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2);
|
|
}
|
|
|
|
op1(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
op1Bool(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
}
|
|
|
|
add(a,b) {
|
|
return this.op2("_add", a, b);
|
|
}
|
|
|
|
eq(a,b) {
|
|
return this.op2Bool("_eq", a, b);
|
|
}
|
|
|
|
isZero(a) {
|
|
return this.op1Bool("_isZero", a);
|
|
}
|
|
|
|
sub(a,b) {
|
|
return this.op2("_sub", a, b);
|
|
}
|
|
|
|
neg(a) {
|
|
return this.op1("_neg", a);
|
|
}
|
|
|
|
inv(a) {
|
|
return this.op1("_inverse", a);
|
|
}
|
|
|
|
isNegative(a) {
|
|
return this.op1Bool("_isNegative", a);
|
|
}
|
|
|
|
toMontgomery(a) {
|
|
return this.op1("_toMontgomery", a);
|
|
}
|
|
|
|
fromMontgomery(a) {
|
|
return this.op1("_fromMontgomery", a);
|
|
}
|
|
|
|
mul(a,b) {
|
|
return this.op2("_mul", a, b);
|
|
}
|
|
|
|
mul1(a,b) {
|
|
return this.op2("_mul1", a, b);
|
|
}
|
|
|
|
div(a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + "_inverse"](this.pOp2, this.pOp2);
|
|
this.tm.instance.exports[this.prefix + "_mul"](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
square(a) {
|
|
return this.op1("_square", a);
|
|
}
|
|
|
|
isSquare(a) {
|
|
return this.op1Bool("_isSquare", a);
|
|
}
|
|
|
|
sqrt(a) {
|
|
return this.op1("_sqrt", a);
|
|
}
|
|
|
|
exp(a, b) {
|
|
if (!(b instanceof Uint8Array)) {
|
|
b = toLEBuff(e(b));
|
|
}
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + "_exp"](this.pOp1, this.pOp2, b.byteLength, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
e(a, b) {
|
|
if (a instanceof Uint8Array) return a;
|
|
if ((Array.isArray(a)) && (a.length == 2)) {
|
|
const c1 = this.F.e(a[0], b);
|
|
const c2 = this.F.e(a[1], b);
|
|
const res = new Uint8Array(this.F.n8*2);
|
|
res.set(c1);
|
|
res.set(c2, this.F.n8*2);
|
|
return res;
|
|
} else {
|
|
throw new Error("invalid F2");
|
|
}
|
|
}
|
|
|
|
toString(a, radix) {
|
|
const s1 = this.F.toString(a.slice(0, this.F.n8), radix);
|
|
const s2 = this.F.toString(a.slice(this.F.n8), radix);
|
|
return `[${s1}, ${s2}]`;
|
|
}
|
|
|
|
fromRng(rng) {
|
|
const c1 = this.F.fromRng(rng);
|
|
const c2 = this.F.fromRng(rng);
|
|
const res = new Uint8Array(this.F.n8*2);
|
|
res.set(c1);
|
|
res.set(c2, this.F.n8);
|
|
return res;
|
|
}
|
|
|
|
random() {
|
|
return this.fromRng(getThreadRng());
|
|
}
|
|
|
|
toObject(a) {
|
|
const c1 = this.F.toObject(a.slice(0, this.F.n8));
|
|
const c2 = this.F.toObject(a.slice(this.F.n8, this.F.n8*2));
|
|
return [c1, c2];
|
|
}
|
|
|
|
fromObject(a) {
|
|
const buff = new Uint8Array(this.F.n8*2);
|
|
const b1 = this.F.fromObject(a[0]);
|
|
const b2 = this.F.fromObject(a[1]);
|
|
buff.set(b1);
|
|
buff.set(b2, this.F.n8);
|
|
return buff;
|
|
}
|
|
|
|
c1(a) {
|
|
return a.slice(0, this.F.n8);
|
|
}
|
|
|
|
c2(a) {
|
|
return a.slice(this.F.n8);
|
|
}
|
|
|
|
}
|
|
|
|
class WasmField3 {
|
|
|
|
constructor(tm, prefix, F) {
|
|
this.tm = tm;
|
|
this.prefix = prefix;
|
|
|
|
this.F = F;
|
|
this.type = "F3";
|
|
this.m = F.m * 3;
|
|
this.n8 = this.F.n8*3;
|
|
this.n32 = this.F.n32*3;
|
|
this.n64 = this.F.n64*3;
|
|
|
|
this.pOp1 = tm.alloc(F.n8*3);
|
|
this.pOp2 = tm.alloc(F.n8*3);
|
|
this.pOp3 = tm.alloc(F.n8*3);
|
|
this.tm.instance.exports[prefix + "_zero"](this.pOp1);
|
|
this.zero = tm.getBuff(this.pOp1, this.n8);
|
|
this.tm.instance.exports[prefix + "_one"](this.pOp1);
|
|
this.one = tm.getBuff(this.pOp1, this.n8);
|
|
|
|
this.negone = this.neg(this.one);
|
|
this.two = this.add(this.one, this.one);
|
|
|
|
}
|
|
|
|
op2(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
op2Bool(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2);
|
|
}
|
|
|
|
op1(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
op1Bool(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
}
|
|
|
|
|
|
eq(a,b) {
|
|
return this.op2Bool("_eq", a, b);
|
|
}
|
|
|
|
isZero(a) {
|
|
return this.op1Bool("_isZero", a);
|
|
}
|
|
|
|
add(a,b) {
|
|
return this.op2("_add", a, b);
|
|
}
|
|
|
|
sub(a,b) {
|
|
return this.op2("_sub", a, b);
|
|
}
|
|
|
|
neg(a) {
|
|
return this.op1("_neg", a);
|
|
}
|
|
|
|
inv(a) {
|
|
return this.op1("_inverse", a);
|
|
}
|
|
|
|
isNegative(a) {
|
|
return this.op1Bool("_isNegative", a);
|
|
}
|
|
|
|
toMontgomery(a) {
|
|
return this.op1("_toMontgomery", a);
|
|
}
|
|
|
|
fromMontgomery(a) {
|
|
return this.op1("_fromMontgomery", a);
|
|
}
|
|
|
|
mul(a,b) {
|
|
return this.op2("_mul", a, b);
|
|
}
|
|
|
|
div(a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + "_inverse"](this.pOp2, this.pOp2);
|
|
this.tm.instance.exports[this.prefix + "_mul"](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
square(a) {
|
|
return this.op1("_square", a);
|
|
}
|
|
|
|
isSquare(a) {
|
|
return this.op1Bool("_isSquare", a);
|
|
}
|
|
|
|
sqrt(a) {
|
|
return this.op1("_sqrt", a);
|
|
}
|
|
|
|
exp(a, b) {
|
|
if (!(b instanceof Uint8Array)) {
|
|
b = toLEBuff(e(b));
|
|
}
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + "_exp"](this.pOp1, this.pOp2, b.byteLength, this.pOp3);
|
|
return this.getBuff(this.pOp3, this.n8);
|
|
}
|
|
|
|
e(a, b) {
|
|
if (a instanceof Uint8Array) return a;
|
|
if ((Array.isArray(a)) && (a.length == 3)) {
|
|
const c1 = this.F.e(a[0], b);
|
|
const c2 = this.F.e(a[1], b);
|
|
const c3 = this.F.e(a[2], b);
|
|
const res = new Uint8Array(this.F.n8*3);
|
|
res.set(c1);
|
|
res.set(c2, this.F.n8);
|
|
res.set(c3, this.F.n8*2);
|
|
return res;
|
|
} else {
|
|
throw new Error("invalid F3");
|
|
}
|
|
}
|
|
|
|
toString(a, radix) {
|
|
const s1 = this.F.toString(a.slice(0, this.F.n8), radix);
|
|
const s2 = this.F.toString(a.slice(this.F.n8, this.F.n8*2), radix);
|
|
const s3 = this.F.toString(a.slice(this.F.n8*2), radix);
|
|
return `[${s1}, ${s2}, ${s3}]`;
|
|
}
|
|
|
|
fromRng(rng) {
|
|
const c1 = this.F.fromRng(rng);
|
|
const c2 = this.F.fromRng(rng);
|
|
const c3 = this.F.fromRng(rng);
|
|
const res = new Uint8Array(this.F.n8*3);
|
|
res.set(c1);
|
|
res.set(c2, this.F.n8);
|
|
res.set(c3, this.F.n8*2);
|
|
return res;
|
|
}
|
|
|
|
random() {
|
|
return this.fromRng(getThreadRng());
|
|
}
|
|
|
|
toObject(a) {
|
|
const c1 = this.F.toObject(a.slice(0, this.F.n8));
|
|
const c2 = this.F.toObject(a.slice(this.F.n8, this.F.n8*2));
|
|
const c3 = this.F.toObject(a.slice(this.F.n8*2, this.F.n8*3));
|
|
return [c1, c2, c3];
|
|
}
|
|
|
|
fromObject(a) {
|
|
const buff = new Uint8Array(this.F.n8*3);
|
|
const b1 = this.F.fromObject(a[0]);
|
|
const b2 = this.F.fromObject(a[1]);
|
|
const b3 = this.F.fromObject(a[2]);
|
|
buff.set(b1);
|
|
buff.set(b2, this.F.n8);
|
|
buff.set(b3, this.F.n8*2);
|
|
return buff;
|
|
}
|
|
|
|
c1(a) {
|
|
return a.slice(0, this.F.n8);
|
|
}
|
|
|
|
c2(a) {
|
|
return a.slice(this.F.n8, this.F.n8*2);
|
|
}
|
|
|
|
c3(a) {
|
|
return a.slice(this.F.n8*2);
|
|
}
|
|
|
|
}
|
|
|
|
class WasmCurve {
|
|
|
|
constructor(tm, prefix, F, pGen, pGb, cofactor) {
|
|
this.tm = tm;
|
|
this.prefix = prefix;
|
|
this.F = F;
|
|
|
|
this.pOp1 = tm.alloc(F.n8*3);
|
|
this.pOp2 = tm.alloc(F.n8*3);
|
|
this.pOp3 = tm.alloc(F.n8*3);
|
|
this.tm.instance.exports[prefix + "_zero"](this.pOp1);
|
|
this.zero = this.tm.getBuff(this.pOp1, F.n8*3);
|
|
this.tm.instance.exports[prefix + "_zeroAffine"](this.pOp1);
|
|
this.zeroAffine = this.tm.getBuff(this.pOp1, F.n8*2);
|
|
this.one = this.tm.getBuff(pGen, F.n8*3);
|
|
this.g = this.one;
|
|
this.oneAffine = this.tm.getBuff(pGen, F.n8*2);
|
|
this.gAffine = this.oneAffine;
|
|
this.b = this.tm.getBuff(pGb, F.n8);
|
|
|
|
if (cofactor) {
|
|
this.cofactor = toLEBuff(cofactor);
|
|
}
|
|
|
|
this.negone = this.neg(this.one);
|
|
this.two = this.add(this.one, this.one);
|
|
|
|
this.batchLEMtoC = buildBatchConvert(tm, prefix + "_batchLEMtoC", F.n8*2, F.n8);
|
|
this.batchLEMtoU = buildBatchConvert(tm, prefix + "_batchLEMtoU", F.n8*2, F.n8*2);
|
|
this.batchCtoLEM = buildBatchConvert(tm, prefix + "_batchCtoLEM", F.n8, F.n8*2);
|
|
this.batchUtoLEM = buildBatchConvert(tm, prefix + "_batchUtoLEM", F.n8*2, F.n8*2);
|
|
this.batchToJacobian = buildBatchConvert(tm, prefix + "_batchToJacobian", F.n8*2, F.n8*3);
|
|
this.batchToAffine = buildBatchConvert(tm, prefix + "_batchToAffine", F.n8*3, F.n8*2);
|
|
}
|
|
|
|
op2(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.F.n8*3);
|
|
}
|
|
|
|
op2bool(opName, a, b) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, b);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp2, this.pOp3);
|
|
}
|
|
|
|
op1(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.F.n8*3);
|
|
}
|
|
|
|
op1Affine(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.F.n8*2);
|
|
}
|
|
|
|
op1Bool(opName, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
return !!this.tm.instance.exports[this.prefix + opName](this.pOp1, this.pOp3);
|
|
}
|
|
|
|
add(a,b) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
if (b.byteLength == this.F.n8*3) {
|
|
return this.op2("_add", a, b);
|
|
} else if (b.byteLength == this.F.n8*2) {
|
|
return this.op2("_addMixed", a, b);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
if (b.byteLength == this.F.n8*3) {
|
|
return this.op2("_addMixed", b, a);
|
|
} else if (b.byteLength == this.F.n8*2) {
|
|
return this.op2("_addAffine", a, b);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
sub(a,b) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
if (b.byteLength == this.F.n8*3) {
|
|
return this.op2("_sub", a, b);
|
|
} else if (b.byteLength == this.F.n8*2) {
|
|
return this.op2("_subMixed", a, b);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
if (b.byteLength == this.F.n8*3) {
|
|
return this.op2("_subMixed", b, a);
|
|
} else if (b.byteLength == this.F.n8*2) {
|
|
return this.op2("_subAffine", a, b);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
neg(a) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
return this.op1("_neg", a);
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
return this.op1Affine("_negAffine", a);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
double(a) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
return this.op1("_double", a);
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
return this.op1("_doubleAffine", a);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
isZero(a) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
return this.op1Bool("_isZero", a);
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
return this.op1Bool("_isZeroAffine", a);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
timesScalar(a, s) {
|
|
if (!(s instanceof Uint8Array)) {
|
|
s = toLEBuff(e(s));
|
|
}
|
|
let fnName;
|
|
if (a.byteLength == this.F.n8*3) {
|
|
fnName = this.prefix + "_timesScalar";
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
fnName = this.prefix + "_timesScalarAffine";
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, s);
|
|
this.tm.instance.exports[fnName](this.pOp1, this.pOp2, s.byteLength, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.F.n8*3);
|
|
}
|
|
|
|
timesFr(a, s) {
|
|
let fnName;
|
|
if (a.byteLength == this.F.n8*3) {
|
|
fnName = this.prefix + "_timesFr";
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
fnName = this.prefix + "_timesFrAffine";
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.setBuff(this.pOp2, s);
|
|
this.tm.instance.exports[fnName](this.pOp1, this.pOp2, this.pOp3);
|
|
return this.tm.getBuff(this.pOp3, this.F.n8*3);
|
|
}
|
|
|
|
eq(a,b) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
if (b.byteLength == this.F.n8*3) {
|
|
return this.op2bool("_eq", a, b);
|
|
} else if (b.byteLength == this.F.n8*2) {
|
|
return this.op2bool("_eqMixed", a, b);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
if (b.byteLength == this.F.n8*3) {
|
|
return this.op2bool("_eqMixed", b, a);
|
|
} else if (b.byteLength == this.F.n8*2) {
|
|
return this.op2bool("_eqAffine", a, b);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
toAffine(a) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
return this.op1Affine("_toAffine", a);
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
return a;
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
toJacobian(a) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
return a;
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
return this.op1("_toJacobian", a);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
toRprUncompressed(arr, offset, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
if (a.byteLength == this.F.n8*3) {
|
|
this.tm.instance.exports[this.prefix + "_toAffine"](this.pOp1, this.pOp1);
|
|
} else if (a.byteLength != this.F.n8*2) {
|
|
throw new Error("invalid point size");
|
|
}
|
|
this.tm.instance.exports[this.prefix + "_LEMtoU"](this.pOp1, this.pOp1);
|
|
const res = this.tm.getBuff(this.pOp1, this.F.n8*2);
|
|
arr.set(res, offset);
|
|
}
|
|
|
|
fromRprUncompressed(arr, offset) {
|
|
const buff = arr.slice(offset, offset + this.F.n8*2);
|
|
this.tm.setBuff(this.pOp1, buff);
|
|
this.tm.instance.exports[this.prefix + "_UtoLEM"](this.pOp1, this.pOp1);
|
|
return this.tm.getBuff(this.pOp1, this.F.n8*2);
|
|
}
|
|
|
|
toRprCompressed(arr, offset, a) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
if (a.byteLength == this.F.n8*3) {
|
|
this.tm.instance.exports[this.prefix + "_toAffine"](this.pOp1, this.pOp1);
|
|
} else if (a.byteLength != this.F.n8*2) {
|
|
throw new Error("invalid point size");
|
|
}
|
|
this.tm.instance.exports[this.prefix + "_LEMtoC"](this.pOp1, this.pOp1);
|
|
const res = this.tm.getBuff(this.pOp1, this.F.n8);
|
|
arr.set(res, offset);
|
|
}
|
|
|
|
fromRprCompressed(arr, offset) {
|
|
const buff = arr.slice(offset, offset + this.F.n8);
|
|
this.tm.setBuff(this.pOp1, buff);
|
|
this.tm.instance.exports[this.prefix + "_CtoLEM"](this.pOp1, this.pOp2);
|
|
return this.tm.getBuff(this.pOp2, this.F.n8*2);
|
|
}
|
|
|
|
toUncompressed(a) {
|
|
const buff = new Uint8Array(this.F.n8*2);
|
|
this.toRprUncompressed(buff, 0, a);
|
|
return buff;
|
|
}
|
|
|
|
toRprLEM(arr, offset, a) {
|
|
if (a.byteLength == this.F.n8*2) {
|
|
arr.set(a, offset);
|
|
return;
|
|
} else if (a.byteLength == this.F.n8*3) {
|
|
this.tm.setBuff(this.pOp1, a);
|
|
this.tm.instance.exports[this.prefix + "_toAffine"](this.pOp1, this.pOp1);
|
|
const res = this.tm.getBuff(this.pOp1, this.F.n8*2);
|
|
arr.set(res, offset);
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
fromRprLEM(arr, offset) {
|
|
offset = offset || 0;
|
|
return arr.slice(offset, offset+this.F.n8*2);
|
|
}
|
|
|
|
toString(a, radix) {
|
|
if (a.byteLength == this.F.n8*3) {
|
|
const x = this.F.toString(a.slice(0, this.F.n8), radix);
|
|
const y = this.F.toString(a.slice(this.F.n8, this.F.n8*2), radix);
|
|
const z = this.F.toString(a.slice(this.F.n8*2), radix);
|
|
return `[ ${x}, ${y}, ${z} ]`;
|
|
} else if (a.byteLength == this.F.n8*2) {
|
|
const x = this.F.toString(a.slice(0, this.F.n8), radix);
|
|
const y = this.F.toString(a.slice(this.F.n8), radix);
|
|
return `[ ${x}, ${y} ]`;
|
|
} else {
|
|
throw new Error("invalid point size");
|
|
}
|
|
}
|
|
|
|
isValid(a) {
|
|
if (this.isZero(a)) return true;
|
|
const F = this.F;
|
|
const aa = this.toAffine(a);
|
|
const x = aa.slice(0, this.F.n8);
|
|
const y = aa.slice(this.F.n8, this.F.n8*2);
|
|
const x3b = F.add(F.mul(F.square(x),x), this.b);
|
|
const y2 = F.square(y);
|
|
return F.eq(x3b, y2);
|
|
}
|
|
|
|
fromRng(rng) {
|
|
const F = this.F;
|
|
let P = [];
|
|
let greatest;
|
|
let x3b;
|
|
do {
|
|
P[0] = F.fromRng(rng);
|
|
greatest = rng.nextBool();
|
|
x3b = F.add(F.mul(F.square(P[0]), P[0]), this.b);
|
|
} while (!F.isSquare(x3b));
|
|
|
|
P[1] = F.sqrt(x3b);
|
|
|
|
const s = F.isNegative(P[1]);
|
|
if (greatest ^ s) P[1] = F.neg(P[1]);
|
|
|
|
let Pbuff = new Uint8Array(this.F.n8*2);
|
|
Pbuff.set(P[0]);
|
|
Pbuff.set(P[1], this.F.n8);
|
|
|
|
if (this.cofactor) {
|
|
Pbuff = this.timesScalar(Pbuff, this.cofactor);
|
|
}
|
|
|
|
return Pbuff;
|
|
}
|
|
|
|
|
|
|
|
toObject(a) {
|
|
if (this.isZero(a)) {
|
|
return [
|
|
this.F.toObject(this.F.zero),
|
|
this.F.toObject(this.F.one),
|
|
this.F.toObject(this.F.zero),
|
|
];
|
|
}
|
|
const x = this.F.toObject(a.slice(0, this.F.n8));
|
|
const y = this.F.toObject(a.slice(this.F.n8, this.F.n8*2));
|
|
let z;
|
|
if (a.byteLength == this.F.n8*3) {
|
|
z = this.F.toObject(a.slice(this.F.n8*2, this.F.n8*3));
|
|
} else {
|
|
z = this.F.toObject(this.F.one);
|
|
}
|
|
return [x, y, z];
|
|
}
|
|
|
|
fromObject(a) {
|
|
const x = this.F.fromObject(a[0]);
|
|
const y = this.F.fromObject(a[1]);
|
|
let z;
|
|
if (a.length==3) {
|
|
z = this.F.fromObject(a[2]);
|
|
} else {
|
|
z = this.F.one;
|
|
}
|
|
if (this.F.isZero(z, this.F.one)) {
|
|
return this.zeroAffine;
|
|
} else if (this.F.eq(z, this.F.one)) {
|
|
const buff = new Uint8Array(this.F.n8*2);
|
|
buff.set(x);
|
|
buff.set(y, this.F.n8);
|
|
return buff;
|
|
} else {
|
|
const buff = new Uint8Array(this.F.n8*3);
|
|
buff.set(x);
|
|
buff.set(y, this.F.n8);
|
|
buff.set(z, this.F.n8*2);
|
|
return buff;
|
|
}
|
|
}
|
|
|
|
e(a) {
|
|
if (a instanceof Uint8Array) return a;
|
|
return this.fromObject(a);
|
|
}
|
|
|
|
x(a) {
|
|
const tmp = this.toAffine(a);
|
|
return tmp.slice(0, this.F.n8);
|
|
}
|
|
|
|
y(a) {
|
|
const tmp = this.toAffine(a);
|
|
return tmp.slice(this.F.n8);
|
|
}
|
|
|
|
}
|
|
|
|
/* global WebAssembly */
|
|
|
|
function thread(self) {
|
|
const MAXMEM = 32767;
|
|
let instance;
|
|
let memory;
|
|
|
|
if (self) {
|
|
self.onmessage = function(e) {
|
|
let data;
|
|
if (e.data) {
|
|
data = e.data;
|
|
} else {
|
|
data = e;
|
|
}
|
|
|
|
if (data[0].cmd == "INIT") {
|
|
init(data[0]).then(function() {
|
|
self.postMessage(data.result);
|
|
});
|
|
} else if (data[0].cmd == "TERMINATE") {
|
|
self.close();
|
|
} else {
|
|
const res = runTask(data);
|
|
self.postMessage(res);
|
|
}
|
|
};
|
|
}
|
|
|
|
async function init(data) {
|
|
const code = new Uint8Array(data.code);
|
|
const wasmModule = await WebAssembly.compile(code);
|
|
memory = new WebAssembly.Memory({initial:data.init, maximum: MAXMEM});
|
|
|
|
instance = await WebAssembly.instantiate(wasmModule, {
|
|
env: {
|
|
"memory": memory
|
|
}
|
|
});
|
|
}
|
|
|
|
|
|
|
|
function alloc(length) {
|
|
const u32 = new Uint32Array(memory.buffer, 0, 1);
|
|
while (u32[0] & 3) u32[0]++; // Return always aligned pointers
|
|
const res = u32[0];
|
|
u32[0] += length;
|
|
if (u32[0] + length > memory.buffer.byteLength) {
|
|
const currentPages = memory.buffer.byteLength / 0x10000;
|
|
let requiredPages = Math.floor((u32[0] + length) / 0x10000)+1;
|
|
if (requiredPages>MAXMEM) requiredPages=MAXMEM;
|
|
memory.grow(requiredPages-currentPages);
|
|
}
|
|
return res;
|
|
}
|
|
|
|
function allocBuffer(buffer) {
|
|
const p = alloc(buffer.byteLength);
|
|
setBuffer(p, buffer);
|
|
return p;
|
|
}
|
|
|
|
function getBuffer(pointer, length) {
|
|
const u8 = new Uint8Array(memory.buffer);
|
|
return new Uint8Array(u8.buffer, u8.byteOffset + pointer, length);
|
|
}
|
|
|
|
function setBuffer(pointer, buffer) {
|
|
const u8 = new Uint8Array(memory.buffer);
|
|
u8.set(new Uint8Array(buffer), pointer);
|
|
}
|
|
|
|
function runTask(task) {
|
|
if (task[0].cmd == "INIT") {
|
|
return init(task[0]);
|
|
}
|
|
const ctx = {
|
|
vars: [],
|
|
out: []
|
|
};
|
|
const u32a = new Uint32Array(memory.buffer, 0, 1);
|
|
const oldAlloc = u32a[0];
|
|
for (let i=0; i<task.length; i++) {
|
|
switch (task[i].cmd) {
|
|
case "ALLOCSET":
|
|
ctx.vars[task[i].var] = allocBuffer(task[i].buff);
|
|
break;
|
|
case "ALLOC":
|
|
ctx.vars[task[i].var] = alloc(task[i].len);
|
|
break;
|
|
case "SET":
|
|
setBuffer(ctx.vars[task[i].var], task[i].buff);
|
|
break;
|
|
case "CALL": {
|
|
const params = [];
|
|
for (let j=0; j<task[i].params.length; j++) {
|
|
const p = task[i].params[j];
|
|
if (typeof p.var !== "undefined") {
|
|
params.push(ctx.vars[p.var] + (p.offset || 0));
|
|
} else if (typeof p.val != "undefined") {
|
|
params.push(p.val);
|
|
}
|
|
}
|
|
instance.exports[task[i].fnName](...params);
|
|
break;
|
|
}
|
|
case "GET":
|
|
ctx.out[task[i].out] = getBuffer(ctx.vars[task[i].var], task[i].len).slice();
|
|
break;
|
|
default:
|
|
throw new Error("Invalid cmd");
|
|
}
|
|
}
|
|
const u32b = new Uint32Array(memory.buffer, 0, 1);
|
|
u32b[0] = oldAlloc;
|
|
return ctx.out;
|
|
}
|
|
|
|
|
|
return runTask;
|
|
}
|
|
|
|
/*
|
|
Copyright 2019 0KIMS association.
|
|
|
|
This file is part of wasmsnark (Web Assembly zkSnark Prover).
|
|
|
|
wasmsnark is a free software: you can redistribute it and/or modify it
|
|
under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
wasmsnark is distributed in the hope that it will be useful, but WITHOUT
|
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
|
|
License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with wasmsnark. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
// const MEM_SIZE = 1000; // Memory size in 64K Pakes (512Mb)
|
|
const MEM_SIZE = 25; // Memory size in 64K Pakes (1600Kb)
|
|
|
|
class Deferred {
|
|
constructor() {
|
|
this.promise = new Promise((resolve, reject)=> {
|
|
this.reject = reject;
|
|
this.resolve = resolve;
|
|
});
|
|
}
|
|
}
|
|
|
|
function sleep(ms) {
|
|
return new Promise(resolve => setTimeout(resolve, ms));
|
|
}
|
|
|
|
let workerSource;
|
|
|
|
const threadStr = `(${thread.toString()})(self)`;
|
|
if(process.browser) {
|
|
if(globalThis?.Blob) {
|
|
const threadBytes= new TextEncoder().encode(threadStr);
|
|
const workerBlob = new Blob([threadBytes], { type: "application/javascript" }) ;
|
|
workerSource = URL.createObjectURL(workerBlob);
|
|
} else {
|
|
workerSource = "data:application/javascript;base64," + globalThis.btoa(threadStr);
|
|
}
|
|
} else {
|
|
workerSource = "data:application/javascript;base64," + Buffer.from(threadStr).toString("base64");
|
|
}
|
|
|
|
|
|
|
|
async function buildThreadManager(wasm, singleThread) {
|
|
const tm = new ThreadManager();
|
|
|
|
tm.memory = new WebAssembly.Memory({initial:MEM_SIZE});
|
|
tm.u8 = new Uint8Array(tm.memory.buffer);
|
|
tm.u32 = new Uint32Array(tm.memory.buffer);
|
|
|
|
const wasmModule = await WebAssembly.compile(wasm.code);
|
|
|
|
tm.instance = await WebAssembly.instantiate(wasmModule, {
|
|
env: {
|
|
"memory": tm.memory
|
|
}
|
|
});
|
|
|
|
if(process.browser && !globalThis?.Worker) {
|
|
singleThread = true;
|
|
}
|
|
|
|
tm.singleThread = singleThread;
|
|
tm.initalPFree = tm.u32[0]; // Save the Pointer to free space.
|
|
tm.pq = wasm.pq;
|
|
tm.pr = wasm.pr;
|
|
tm.pG1gen = wasm.pG1gen;
|
|
tm.pG1zero = wasm.pG1zero;
|
|
tm.pG2gen = wasm.pG2gen;
|
|
tm.pG2zero = wasm.pG2zero;
|
|
tm.pOneT = wasm.pOneT;
|
|
|
|
// tm.pTmp0 = tm.alloc(curve.G2.F.n8*3);
|
|
// tm.pTmp1 = tm.alloc(curve.G2.F.n8*3);
|
|
|
|
if (singleThread) {
|
|
tm.code = wasm.code;
|
|
tm.taskManager = thread();
|
|
await tm.taskManager([{
|
|
cmd: "INIT",
|
|
init: MEM_SIZE,
|
|
code: tm.code.slice()
|
|
}]);
|
|
tm.concurrency = 1;
|
|
} else {
|
|
tm.workers = [];
|
|
tm.pendingDeferreds = [];
|
|
tm.working = [];
|
|
|
|
let concurrency = 2;
|
|
if (process.browser) {
|
|
if (typeof navigator === "object" && navigator.hardwareConcurrency) {
|
|
concurrency = navigator.hardwareConcurrency;
|
|
}
|
|
} else {
|
|
concurrency = os.cpus().length;
|
|
}
|
|
|
|
if(concurrency == 0){
|
|
concurrency = 2;
|
|
}
|
|
|
|
// Limit to 64 threads for memory reasons.
|
|
if (concurrency>64) concurrency=64;
|
|
tm.concurrency = concurrency;
|
|
|
|
for (let i = 0; i<concurrency; i++) {
|
|
|
|
tm.workers[i] = new Worker(workerSource);
|
|
|
|
tm.workers[i].addEventListener("message", getOnMsg(i));
|
|
|
|
tm.working[i]=false;
|
|
}
|
|
|
|
const initPromises = [];
|
|
for (let i=0; i<tm.workers.length;i++) {
|
|
const copyCode = wasm.code.slice();
|
|
initPromises.push(tm.postAction(i, [{
|
|
cmd: "INIT",
|
|
init: MEM_SIZE,
|
|
code: copyCode
|
|
}], [copyCode.buffer]));
|
|
}
|
|
|
|
await Promise.all(initPromises);
|
|
|
|
}
|
|
return tm;
|
|
|
|
function getOnMsg(i) {
|
|
return function(e) {
|
|
let data;
|
|
if ((e)&&(e.data)) {
|
|
data = e.data;
|
|
} else {
|
|
data = e;
|
|
}
|
|
|
|
tm.working[i]=false;
|
|
tm.pendingDeferreds[i].resolve(data);
|
|
tm.processWorks();
|
|
};
|
|
}
|
|
|
|
}
|
|
|
|
class ThreadManager {
|
|
constructor() {
|
|
this.actionQueue = [];
|
|
this.oldPFree = 0;
|
|
}
|
|
|
|
startSyncOp() {
|
|
if (this.oldPFree != 0) throw new Error("Sync operation in progress");
|
|
this.oldPFree = this.u32[0];
|
|
}
|
|
|
|
endSyncOp() {
|
|
if (this.oldPFree == 0) throw new Error("No sync operation in progress");
|
|
this.u32[0] = this.oldPFree;
|
|
this.oldPFree = 0;
|
|
}
|
|
|
|
postAction(workerId, e, transfers, _deferred) {
|
|
if (this.working[workerId]) {
|
|
throw new Error("Posting a job t a working worker");
|
|
}
|
|
this.working[workerId] = true;
|
|
|
|
this.pendingDeferreds[workerId] = _deferred ? _deferred : new Deferred();
|
|
this.workers[workerId].postMessage(e, transfers);
|
|
|
|
return this.pendingDeferreds[workerId].promise;
|
|
}
|
|
|
|
processWorks() {
|
|
for (let i=0; (i<this.workers.length)&&(this.actionQueue.length > 0); i++) {
|
|
if (this.working[i] == false) {
|
|
const work = this.actionQueue.shift();
|
|
this.postAction(i, work.data, work.transfers, work.deferred);
|
|
}
|
|
}
|
|
}
|
|
|
|
queueAction(actionData, transfers) {
|
|
const d = new Deferred();
|
|
|
|
if (this.singleThread) {
|
|
const res = this.taskManager(actionData);
|
|
d.resolve(res);
|
|
} else {
|
|
this.actionQueue.push({
|
|
data: actionData,
|
|
transfers: transfers,
|
|
deferred: d
|
|
});
|
|
this.processWorks();
|
|
}
|
|
return d.promise;
|
|
}
|
|
|
|
resetMemory() {
|
|
this.u32[0] = this.initalPFree;
|
|
}
|
|
|
|
allocBuff(buff) {
|
|
const pointer = this.alloc(buff.byteLength);
|
|
this.setBuff(pointer, buff);
|
|
return pointer;
|
|
}
|
|
|
|
getBuff(pointer, length) {
|
|
return this.u8.slice(pointer, pointer+ length);
|
|
}
|
|
|
|
setBuff(pointer, buffer) {
|
|
this.u8.set(new Uint8Array(buffer), pointer);
|
|
}
|
|
|
|
alloc(length) {
|
|
while (this.u32[0] & 3) this.u32[0]++; // Return always aligned pointers
|
|
const res = this.u32[0];
|
|
this.u32[0] += length;
|
|
return res;
|
|
}
|
|
|
|
async terminate() {
|
|
for (let i=0; i<this.workers.length; i++) {
|
|
this.workers[i].postMessage([{cmd: "TERMINATE"}]);
|
|
}
|
|
await sleep(200);
|
|
}
|
|
|
|
}
|
|
|
|
function buildBatchApplyKey(curve, groupName) {
|
|
const G = curve[groupName];
|
|
const Fr = curve.Fr;
|
|
const tm = curve.tm;
|
|
|
|
curve[groupName].batchApplyKey = async function(buff, first, inc, inType, outType) {
|
|
inType = inType || "affine";
|
|
outType = outType || "affine";
|
|
let fnName, fnAffine;
|
|
let sGin, sGmid, sGout;
|
|
if (groupName == "G1") {
|
|
if (inType == "jacobian") {
|
|
sGin = G.F.n8*3;
|
|
fnName = "g1m_batchApplyKey";
|
|
} else {
|
|
sGin = G.F.n8*2;
|
|
fnName = "g1m_batchApplyKeyMixed";
|
|
}
|
|
sGmid = G.F.n8*3;
|
|
if (outType == "jacobian") {
|
|
sGout = G.F.n8*3;
|
|
} else {
|
|
fnAffine = "g1m_batchToAffine";
|
|
sGout = G.F.n8*2;
|
|
}
|
|
} else if (groupName == "G2") {
|
|
if (inType == "jacobian") {
|
|
sGin = G.F.n8*3;
|
|
fnName = "g2m_batchApplyKey";
|
|
} else {
|
|
sGin = G.F.n8*2;
|
|
fnName = "g2m_batchApplyKeyMixed";
|
|
}
|
|
sGmid = G.F.n8*3;
|
|
if (outType == "jacobian") {
|
|
sGout = G.F.n8*3;
|
|
} else {
|
|
fnAffine = "g2m_batchToAffine";
|
|
sGout = G.F.n8*2;
|
|
}
|
|
} else if (groupName == "Fr") {
|
|
fnName = "frm_batchApplyKey";
|
|
sGin = G.n8;
|
|
sGmid = G.n8;
|
|
sGout = G.n8;
|
|
} else {
|
|
throw new Error("Invalid group: " + groupName);
|
|
}
|
|
const nPoints = Math.floor(buff.byteLength / sGin);
|
|
const pointsPerChunk = Math.floor(nPoints/tm.concurrency);
|
|
const opPromises = [];
|
|
inc = Fr.e(inc);
|
|
let t = Fr.e(first);
|
|
for (let i=0; i<tm.concurrency; i++) {
|
|
let n;
|
|
if (i< tm.concurrency-1) {
|
|
n = pointsPerChunk;
|
|
} else {
|
|
n = nPoints - i*pointsPerChunk;
|
|
}
|
|
if (n==0) continue;
|
|
|
|
const task = [];
|
|
|
|
task.push({
|
|
cmd: "ALLOCSET",
|
|
var: 0,
|
|
buff: buff.slice(i*pointsPerChunk*sGin, i*pointsPerChunk*sGin + n*sGin)
|
|
});
|
|
task.push({cmd: "ALLOCSET", var: 1, buff: t});
|
|
task.push({cmd: "ALLOCSET", var: 2, buff: inc});
|
|
task.push({cmd: "ALLOC", var: 3, len: n*Math.max(sGmid, sGout)});
|
|
task.push({
|
|
cmd: "CALL",
|
|
fnName: fnName,
|
|
params: [
|
|
{var: 0},
|
|
{val: n},
|
|
{var: 1},
|
|
{var: 2},
|
|
{var:3}
|
|
]
|
|
});
|
|
if (fnAffine) {
|
|
task.push({
|
|
cmd: "CALL",
|
|
fnName: fnAffine,
|
|
params: [
|
|
{var: 3},
|
|
{val: n},
|
|
{var: 3},
|
|
]
|
|
});
|
|
}
|
|
task.push({cmd: "GET", out: 0, var: 3, len: n*sGout});
|
|
|
|
opPromises.push(tm.queueAction(task));
|
|
t = Fr.mul(t, Fr.exp(inc, n));
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let outBuff;
|
|
if (buff instanceof BigBuffer) {
|
|
outBuff = new BigBuffer(nPoints*sGout);
|
|
} else {
|
|
outBuff = new Uint8Array(nPoints*sGout);
|
|
}
|
|
|
|
let p=0;
|
|
for (let i=0; i<result.length; i++) {
|
|
outBuff.set(result[i][0], p);
|
|
p += result[i][0].byteLength;
|
|
}
|
|
|
|
return outBuff;
|
|
};
|
|
}
|
|
|
|
function buildPairing(curve) {
|
|
const tm = curve.tm;
|
|
curve.pairing = function pairing(a, b) {
|
|
|
|
tm.startSyncOp();
|
|
const pA = tm.allocBuff(curve.G1.toJacobian(a));
|
|
const pB = tm.allocBuff(curve.G2.toJacobian(b));
|
|
const pRes = tm.alloc(curve.Gt.n8);
|
|
tm.instance.exports[curve.name + "_pairing"](pA, pB, pRes);
|
|
|
|
const res = tm.getBuff(pRes, curve.Gt.n8);
|
|
|
|
tm.endSyncOp();
|
|
return res;
|
|
};
|
|
|
|
curve.pairingEq = async function pairingEq() {
|
|
let buffCt;
|
|
let nEqs;
|
|
if ((arguments.length % 2) == 1) {
|
|
buffCt = arguments[arguments.length-1];
|
|
nEqs = (arguments.length -1) /2;
|
|
} else {
|
|
buffCt = curve.Gt.one;
|
|
nEqs = arguments.length /2;
|
|
}
|
|
|
|
const opPromises = [];
|
|
for (let i=0; i<nEqs; i++) {
|
|
|
|
const task = [];
|
|
|
|
const g1Buff = curve.G1.toJacobian(arguments[i*2]);
|
|
task.push({cmd: "ALLOCSET", var: 0, buff: g1Buff});
|
|
task.push({cmd: "ALLOC", var: 1, len: curve.prePSize});
|
|
|
|
const g2Buff = curve.G2.toJacobian(arguments[i*2 +1]);
|
|
task.push({cmd: "ALLOCSET", var: 2, buff: g2Buff});
|
|
task.push({cmd: "ALLOC", var: 3, len: curve.preQSize});
|
|
|
|
task.push({cmd: "ALLOC", var: 4, len: curve.Gt.n8});
|
|
|
|
task.push({cmd: "CALL", fnName: curve.name + "_prepareG1", params: [
|
|
{var: 0},
|
|
{var: 1}
|
|
]});
|
|
|
|
task.push({cmd: "CALL", fnName: curve.name + "_prepareG2", params: [
|
|
{var: 2},
|
|
{var: 3}
|
|
]});
|
|
|
|
task.push({cmd: "CALL", fnName: curve.name + "_millerLoop", params: [
|
|
{var: 1},
|
|
{var: 3},
|
|
{var: 4}
|
|
]});
|
|
|
|
task.push({cmd: "GET", out: 0, var: 4, len: curve.Gt.n8});
|
|
|
|
opPromises.push(
|
|
tm.queueAction(task)
|
|
);
|
|
}
|
|
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
tm.startSyncOp();
|
|
const pRes = tm.alloc(curve.Gt.n8);
|
|
tm.instance.exports.ftm_one(pRes);
|
|
|
|
for (let i=0; i<result.length; i++) {
|
|
const pMR = tm.allocBuff(result[i][0]);
|
|
tm.instance.exports.ftm_mul(pRes, pMR, pRes);
|
|
}
|
|
tm.instance.exports[curve.name + "_finalExponentiation"](pRes, pRes);
|
|
|
|
const pCt = tm.allocBuff(buffCt);
|
|
|
|
const r = !!tm.instance.exports.ftm_eq(pRes, pCt);
|
|
|
|
tm.endSyncOp();
|
|
|
|
return r;
|
|
};
|
|
|
|
curve.prepareG1 = function(p) {
|
|
this.tm.startSyncOp();
|
|
const pP = this.tm.allocBuff(p);
|
|
const pPrepP = this.tm.alloc(this.prePSize);
|
|
this.tm.instance.exports[this.name + "_prepareG1"](pP, pPrepP);
|
|
const res = this.tm.getBuff(pPrepP, this.prePSize);
|
|
this.tm.endSyncOp();
|
|
return res;
|
|
};
|
|
|
|
curve.prepareG2 = function(q) {
|
|
this.tm.startSyncOp();
|
|
const pQ = this.tm.allocBuff(q);
|
|
const pPrepQ = this.tm.alloc(this.preQSize);
|
|
this.tm.instance.exports[this.name + "_prepareG2"](pQ, pPrepQ);
|
|
const res = this.tm.getBuff(pPrepQ, this.preQSize);
|
|
this.tm.endSyncOp();
|
|
return res;
|
|
};
|
|
|
|
curve.millerLoop = function(preP, preQ) {
|
|
this.tm.startSyncOp();
|
|
const pPreP = this.tm.allocBuff(preP);
|
|
const pPreQ = this.tm.allocBuff(preQ);
|
|
const pRes = this.tm.alloc(this.Gt.n8);
|
|
this.tm.instance.exports[this.name + "_millerLoop"](pPreP, pPreQ, pRes);
|
|
const res = this.tm.getBuff(pRes, this.Gt.n8);
|
|
this.tm.endSyncOp();
|
|
return res;
|
|
};
|
|
|
|
curve.finalExponentiation = function(a) {
|
|
this.tm.startSyncOp();
|
|
const pA = this.tm.allocBuff(a);
|
|
const pRes = this.tm.alloc(this.Gt.n8);
|
|
this.tm.instance.exports[this.name + "_finalExponentiation"](pA, pRes);
|
|
const res = this.tm.getBuff(pRes, this.Gt.n8);
|
|
this.tm.endSyncOp();
|
|
return res;
|
|
};
|
|
|
|
}
|
|
|
|
const pTSizes = [
|
|
1 , 1, 1, 1, 2, 3, 4, 5,
|
|
6 , 7, 7, 8, 9, 10, 11, 12,
|
|
13, 13, 14, 15, 16, 16, 17, 17,
|
|
17, 17, 17, 17, 17, 17, 17, 17
|
|
];
|
|
|
|
function buildMultiexp(curve, groupName) {
|
|
const G = curve[groupName];
|
|
const tm = G.tm;
|
|
async function _multiExpChunk(buffBases, buffScalars, inType, logger, logText) {
|
|
if ( ! (buffBases instanceof Uint8Array) ) {
|
|
if (logger) logger.error(`${logText} _multiExpChunk buffBases is not Uint8Array`);
|
|
throw new Error(`${logText} _multiExpChunk buffBases is not Uint8Array`);
|
|
}
|
|
if ( ! (buffScalars instanceof Uint8Array) ) {
|
|
if (logger) logger.error(`${logText} _multiExpChunk buffScalars is not Uint8Array`);
|
|
throw new Error(`${logText} _multiExpChunk buffScalars is not Uint8Array`);
|
|
}
|
|
inType = inType || "affine";
|
|
|
|
let sGIn;
|
|
let fnName;
|
|
if (groupName == "G1") {
|
|
if (inType == "affine") {
|
|
fnName = "g1m_multiexpAffine_chunk";
|
|
sGIn = G.F.n8*2;
|
|
} else {
|
|
fnName = "g1m_multiexp_chunk";
|
|
sGIn = G.F.n8*3;
|
|
}
|
|
} else if (groupName == "G2") {
|
|
if (inType == "affine") {
|
|
fnName = "g2m_multiexpAffine_chunk";
|
|
sGIn = G.F.n8*2;
|
|
} else {
|
|
fnName = "g2m_multiexp_chunk";
|
|
sGIn = G.F.n8*3;
|
|
}
|
|
} else {
|
|
throw new Error("Invalid group");
|
|
}
|
|
const nPoints = Math.floor(buffBases.byteLength / sGIn);
|
|
|
|
if (nPoints == 0) return G.zero;
|
|
const sScalar = Math.floor(buffScalars.byteLength / nPoints);
|
|
if( sScalar * nPoints != buffScalars.byteLength) {
|
|
throw new Error("Scalar size does not match");
|
|
}
|
|
|
|
const bitChunkSize = pTSizes[log2(nPoints)];
|
|
const nChunks = Math.floor((sScalar*8 - 1) / bitChunkSize) +1;
|
|
|
|
const opPromises = [];
|
|
for (let i=0; i<nChunks; i++) {
|
|
const task = [
|
|
{cmd: "ALLOCSET", var: 0, buff: buffBases},
|
|
{cmd: "ALLOCSET", var: 1, buff: buffScalars},
|
|
{cmd: "ALLOC", var: 2, len: G.F.n8*3},
|
|
{cmd: "CALL", fnName: fnName, params: [
|
|
{var: 0},
|
|
{var: 1},
|
|
{val: sScalar},
|
|
{val: nPoints},
|
|
{val: i*bitChunkSize},
|
|
{val: Math.min(sScalar*8 - i*bitChunkSize, bitChunkSize)},
|
|
{var: 2}
|
|
]},
|
|
{cmd: "GET", out: 0, var: 2, len: G.F.n8*3}
|
|
];
|
|
opPromises.push(
|
|
G.tm.queueAction(task)
|
|
);
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let res = G.zero;
|
|
for (let i=result.length-1; i>=0; i--) {
|
|
if (!G.isZero(res)) {
|
|
for (let j=0; j<bitChunkSize; j++) res = G.double(res);
|
|
}
|
|
res = G.add(res, result[i][0]);
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
async function _multiExp(buffBases, buffScalars, inType, logger, logText) {
|
|
const MAX_CHUNK_SIZE = 1 << 22;
|
|
const MIN_CHUNK_SIZE = 1 << 10;
|
|
let sGIn;
|
|
|
|
if (groupName == "G1") {
|
|
if (inType == "affine") {
|
|
sGIn = G.F.n8*2;
|
|
} else {
|
|
sGIn = G.F.n8*3;
|
|
}
|
|
} else if (groupName == "G2") {
|
|
if (inType == "affine") {
|
|
sGIn = G.F.n8*2;
|
|
} else {
|
|
sGIn = G.F.n8*3;
|
|
}
|
|
} else {
|
|
throw new Error("Invalid group");
|
|
}
|
|
|
|
const nPoints = Math.floor(buffBases.byteLength / sGIn);
|
|
if (nPoints == 0) return G.zero;
|
|
const sScalar = Math.floor(buffScalars.byteLength / nPoints);
|
|
if( sScalar * nPoints != buffScalars.byteLength) {
|
|
throw new Error("Scalar size does not match");
|
|
}
|
|
|
|
const bitChunkSize = pTSizes[log2(nPoints)];
|
|
const nChunks = Math.floor((sScalar*8 - 1) / bitChunkSize) +1;
|
|
|
|
let chunkSize;
|
|
chunkSize = Math.floor(nPoints / (tm.concurrency /nChunks));
|
|
if (chunkSize>MAX_CHUNK_SIZE) chunkSize = MAX_CHUNK_SIZE;
|
|
if (chunkSize<MIN_CHUNK_SIZE) chunkSize = MIN_CHUNK_SIZE;
|
|
|
|
const opPromises = [];
|
|
for (let i=0; i<nPoints; i += chunkSize) {
|
|
if (logger) logger.debug(`Multiexp start: ${logText}: ${i}/${nPoints}`);
|
|
const n= Math.min(nPoints - i, chunkSize);
|
|
const buffBasesChunk = buffBases.slice(i*sGIn, (i+n)*sGIn);
|
|
const buffScalarsChunk = buffScalars.slice(i*sScalar, (i+n)*sScalar);
|
|
opPromises.push(_multiExpChunk(buffBasesChunk, buffScalarsChunk, inType, logger, logText).then( (r) => {
|
|
if (logger) logger.debug(`Multiexp end: ${logText}: ${i}/${nPoints}`);
|
|
return r;
|
|
}));
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let res = G.zero;
|
|
for (let i=result.length-1; i>=0; i--) {
|
|
res = G.add(res, result[i]);
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
G.multiExp = async function multiExpAffine(buffBases, buffScalars, logger, logText) {
|
|
return await _multiExp(buffBases, buffScalars, "jacobian", logger, logText);
|
|
};
|
|
G.multiExpAffine = async function multiExpAffine(buffBases, buffScalars, logger, logText) {
|
|
return await _multiExp(buffBases, buffScalars, "affine", logger, logText);
|
|
};
|
|
}
|
|
|
|
function buildFFT(curve, groupName) {
|
|
const G = curve[groupName];
|
|
const Fr = curve.Fr;
|
|
const tm = G.tm;
|
|
async function _fft(buff, inverse, inType, outType, logger, loggerTxt) {
|
|
|
|
inType = inType || "affine";
|
|
outType = outType || "affine";
|
|
const MAX_BITS_THREAD = 14;
|
|
|
|
let sIn, sMid, sOut, fnIn2Mid, fnMid2Out, fnFFTMix, fnFFTJoin, fnFFTFinal;
|
|
if (groupName == "G1") {
|
|
if (inType == "affine") {
|
|
sIn = G.F.n8*2;
|
|
fnIn2Mid = "g1m_batchToJacobian";
|
|
} else {
|
|
sIn = G.F.n8*3;
|
|
}
|
|
sMid = G.F.n8*3;
|
|
if (inverse) {
|
|
fnFFTFinal = "g1m_fftFinal";
|
|
}
|
|
fnFFTJoin = "g1m_fftJoin";
|
|
fnFFTMix = "g1m_fftMix";
|
|
|
|
if (outType == "affine") {
|
|
sOut = G.F.n8*2;
|
|
fnMid2Out = "g1m_batchToAffine";
|
|
} else {
|
|
sOut = G.F.n8*3;
|
|
}
|
|
|
|
} else if (groupName == "G2") {
|
|
if (inType == "affine") {
|
|
sIn = G.F.n8*2;
|
|
fnIn2Mid = "g2m_batchToJacobian";
|
|
} else {
|
|
sIn = G.F.n8*3;
|
|
}
|
|
sMid = G.F.n8*3;
|
|
if (inverse) {
|
|
fnFFTFinal = "g2m_fftFinal";
|
|
}
|
|
fnFFTJoin = "g2m_fftJoin";
|
|
fnFFTMix = "g2m_fftMix";
|
|
if (outType == "affine") {
|
|
sOut = G.F.n8*2;
|
|
fnMid2Out = "g2m_batchToAffine";
|
|
} else {
|
|
sOut = G.F.n8*3;
|
|
}
|
|
} else if (groupName == "Fr") {
|
|
sIn = G.n8;
|
|
sMid = G.n8;
|
|
sOut = G.n8;
|
|
if (inverse) {
|
|
fnFFTFinal = "frm_fftFinal";
|
|
}
|
|
fnFFTMix = "frm_fftMix";
|
|
fnFFTJoin = "frm_fftJoin";
|
|
}
|
|
|
|
|
|
let returnArray = false;
|
|
if (Array.isArray(buff)) {
|
|
buff = array2buffer(buff, sIn);
|
|
returnArray = true;
|
|
} else {
|
|
buff = buff.slice(0, buff.byteLength);
|
|
}
|
|
|
|
const nPoints = buff.byteLength / sIn;
|
|
const bits = log2(nPoints);
|
|
|
|
if ((1 << bits) != nPoints) {
|
|
throw new Error("fft must be multiple of 2" );
|
|
}
|
|
|
|
if (bits == Fr.s +1) {
|
|
let buffOut;
|
|
|
|
if (inverse) {
|
|
buffOut = await _fftExtInv(buff, inType, outType, logger, loggerTxt);
|
|
} else {
|
|
buffOut = await _fftExt(buff, inType, outType, logger, loggerTxt);
|
|
}
|
|
|
|
if (returnArray) {
|
|
return buffer2array(buffOut, sOut);
|
|
} else {
|
|
return buffOut;
|
|
}
|
|
}
|
|
|
|
let inv;
|
|
if (inverse) {
|
|
inv = Fr.inv(Fr.e(nPoints));
|
|
}
|
|
|
|
let buffOut;
|
|
|
|
buffReverseBits(buff, sIn);
|
|
|
|
let chunks;
|
|
let pointsInChunk = Math.min(1 << MAX_BITS_THREAD, nPoints);
|
|
let nChunks = nPoints / pointsInChunk;
|
|
|
|
while ((nChunks < tm.concurrency)&&(pointsInChunk>=16)) {
|
|
nChunks *= 2;
|
|
pointsInChunk /= 2;
|
|
}
|
|
|
|
const l2Chunk = log2(pointsInChunk);
|
|
|
|
const promises = [];
|
|
for (let i = 0; i< nChunks; i++) {
|
|
if (logger) logger.debug(`${loggerTxt}: fft ${bits} mix start: ${i}/${nChunks}`);
|
|
const task = [];
|
|
task.push({cmd: "ALLOC", var: 0, len: sMid*pointsInChunk});
|
|
const buffChunk = buff.slice( (pointsInChunk * i)*sIn, (pointsInChunk * (i+1))*sIn);
|
|
task.push({cmd: "SET", var: 0, buff: buffChunk});
|
|
if (fnIn2Mid) {
|
|
task.push({cmd: "CALL", fnName:fnIn2Mid, params: [{var:0}, {val: pointsInChunk}, {var: 0}]});
|
|
}
|
|
for (let j=1; j<=l2Chunk;j++) {
|
|
task.push({cmd: "CALL", fnName:fnFFTMix, params: [{var:0}, {val: pointsInChunk}, {val: j}]});
|
|
}
|
|
|
|
if (l2Chunk==bits) {
|
|
if (fnFFTFinal) {
|
|
task.push({cmd: "ALLOCSET", var: 1, buff: inv});
|
|
task.push({cmd: "CALL", fnName: fnFFTFinal, params:[
|
|
{var: 0},
|
|
{val: pointsInChunk},
|
|
{var: 1},
|
|
]});
|
|
}
|
|
if (fnMid2Out) {
|
|
task.push({cmd: "CALL", fnName:fnMid2Out, params: [{var:0}, {val: pointsInChunk}, {var: 0}]});
|
|
}
|
|
task.push({cmd: "GET", out: 0, var: 0, len: pointsInChunk*sOut});
|
|
} else {
|
|
task.push({cmd: "GET", out:0, var: 0, len: sMid*pointsInChunk});
|
|
}
|
|
promises.push(tm.queueAction(task).then( (r) => {
|
|
if (logger) logger.debug(`${loggerTxt}: fft ${bits} mix end: ${i}/${nChunks}`);
|
|
return r;
|
|
}));
|
|
}
|
|
|
|
chunks = await Promise.all(promises);
|
|
for (let i = 0; i< nChunks; i++) chunks[i] = chunks[i][0];
|
|
|
|
for (let i = l2Chunk+1; i<=bits; i++) {
|
|
if (logger) logger.debug(`${loggerTxt}: fft ${bits} join: ${i}/${bits}`);
|
|
const nGroups = 1 << (bits - i);
|
|
const nChunksPerGroup = nChunks / nGroups;
|
|
const opPromises = [];
|
|
for (let j=0; j<nGroups; j++) {
|
|
for (let k=0; k <nChunksPerGroup/2; k++) {
|
|
const first = Fr.exp( Fr.w[i], k*pointsInChunk);
|
|
const inc = Fr.w[i];
|
|
const o1 = j*nChunksPerGroup + k;
|
|
const o2 = j*nChunksPerGroup + k + nChunksPerGroup/2;
|
|
|
|
const task = [];
|
|
task.push({cmd: "ALLOCSET", var: 0, buff: chunks[o1]});
|
|
task.push({cmd: "ALLOCSET", var: 1, buff: chunks[o2]});
|
|
task.push({cmd: "ALLOCSET", var: 2, buff: first});
|
|
task.push({cmd: "ALLOCSET", var: 3, buff: inc});
|
|
task.push({cmd: "CALL", fnName: fnFFTJoin, params:[
|
|
{var: 0},
|
|
{var: 1},
|
|
{val: pointsInChunk},
|
|
{var: 2},
|
|
{var: 3}
|
|
]});
|
|
if (i==bits) {
|
|
if (fnFFTFinal) {
|
|
task.push({cmd: "ALLOCSET", var: 4, buff: inv});
|
|
task.push({cmd: "CALL", fnName: fnFFTFinal, params:[
|
|
{var: 0},
|
|
{val: pointsInChunk},
|
|
{var: 4},
|
|
]});
|
|
task.push({cmd: "CALL", fnName: fnFFTFinal, params:[
|
|
{var: 1},
|
|
{val: pointsInChunk},
|
|
{var: 4},
|
|
]});
|
|
}
|
|
if (fnMid2Out) {
|
|
task.push({cmd: "CALL", fnName:fnMid2Out, params: [{var:0}, {val: pointsInChunk}, {var: 0}]});
|
|
task.push({cmd: "CALL", fnName:fnMid2Out, params: [{var:1}, {val: pointsInChunk}, {var: 1}]});
|
|
}
|
|
task.push({cmd: "GET", out: 0, var: 0, len: pointsInChunk*sOut});
|
|
task.push({cmd: "GET", out: 1, var: 1, len: pointsInChunk*sOut});
|
|
} else {
|
|
task.push({cmd: "GET", out: 0, var: 0, len: pointsInChunk*sMid});
|
|
task.push({cmd: "GET", out: 1, var: 1, len: pointsInChunk*sMid});
|
|
}
|
|
opPromises.push(tm.queueAction(task).then( (r) => {
|
|
if (logger) logger.debug(`${loggerTxt}: fft ${bits} join ${i}/${bits} ${j+1}/${nGroups} ${k}/${nChunksPerGroup/2}`);
|
|
return r;
|
|
}));
|
|
}
|
|
}
|
|
|
|
const res = await Promise.all(opPromises);
|
|
for (let j=0; j<nGroups; j++) {
|
|
for (let k=0; k <nChunksPerGroup/2; k++) {
|
|
const o1 = j*nChunksPerGroup + k;
|
|
const o2 = j*nChunksPerGroup + k + nChunksPerGroup/2;
|
|
const resChunk = res.shift();
|
|
chunks[o1] = resChunk[0];
|
|
chunks[o2] = resChunk[1];
|
|
}
|
|
}
|
|
}
|
|
|
|
if (buff instanceof BigBuffer) {
|
|
buffOut = new BigBuffer(nPoints*sOut);
|
|
} else {
|
|
buffOut = new Uint8Array(nPoints*sOut);
|
|
}
|
|
if (inverse) {
|
|
buffOut.set(chunks[0].slice((pointsInChunk-1)*sOut));
|
|
let p= sOut;
|
|
for (let i=nChunks-1; i>0; i--) {
|
|
buffOut.set(chunks[i], p);
|
|
p += pointsInChunk*sOut;
|
|
delete chunks[i]; // Liberate mem
|
|
}
|
|
buffOut.set(chunks[0].slice(0, (pointsInChunk-1)*sOut), p);
|
|
delete chunks[0];
|
|
} else {
|
|
for (let i=0; i<nChunks; i++) {
|
|
buffOut.set(chunks[i], pointsInChunk*sOut*i);
|
|
delete chunks[i];
|
|
}
|
|
}
|
|
|
|
if (returnArray) {
|
|
return buffer2array(buffOut, sOut);
|
|
} else {
|
|
return buffOut;
|
|
}
|
|
}
|
|
|
|
async function _fftExt(buff, inType, outType, logger, loggerTxt) {
|
|
let b1, b2;
|
|
b1 = buff.slice( 0 , buff.byteLength/2);
|
|
b2 = buff.slice( buff.byteLength/2, buff.byteLength);
|
|
|
|
const promises = [];
|
|
|
|
[b1, b2] = await _fftJoinExt(b1, b2, "fftJoinExt", Fr.one, Fr.shift, inType, "jacobian", logger, loggerTxt);
|
|
|
|
promises.push( _fft(b1, false, "jacobian", outType, logger, loggerTxt));
|
|
promises.push( _fft(b2, false, "jacobian", outType, logger, loggerTxt));
|
|
|
|
const res1 = await Promise.all(promises);
|
|
|
|
let buffOut;
|
|
if (res1[0].byteLength > (1<<28)) {
|
|
buffOut = new BigBuffer(res1[0].byteLength*2);
|
|
} else {
|
|
buffOut = new Uint8Array(res1[0].byteLength*2);
|
|
}
|
|
|
|
buffOut.set(res1[0]);
|
|
buffOut.set(res1[1], res1[0].byteLength);
|
|
|
|
return buffOut;
|
|
}
|
|
|
|
async function _fftExtInv(buff, inType, outType, logger, loggerTxt) {
|
|
let b1, b2;
|
|
b1 = buff.slice( 0 , buff.byteLength/2);
|
|
b2 = buff.slice( buff.byteLength/2, buff.byteLength);
|
|
|
|
const promises = [];
|
|
|
|
promises.push( _fft(b1, true, inType, "jacobian", logger, loggerTxt));
|
|
promises.push( _fft(b2, true, inType, "jacobian", logger, loggerTxt));
|
|
|
|
[b1, b2] = await Promise.all(promises);
|
|
|
|
const res1 = await _fftJoinExt(b1, b2, "fftJoinExtInv", Fr.one, Fr.shiftInv, "jacobian", outType, logger, loggerTxt);
|
|
|
|
let buffOut;
|
|
if (res1[0].byteLength > (1<<28)) {
|
|
buffOut = new BigBuffer(res1[0].byteLength*2);
|
|
} else {
|
|
buffOut = new Uint8Array(res1[0].byteLength*2);
|
|
}
|
|
|
|
buffOut.set(res1[0]);
|
|
buffOut.set(res1[1], res1[0].byteLength);
|
|
|
|
return buffOut;
|
|
}
|
|
|
|
|
|
async function _fftJoinExt(buff1, buff2, fn, first, inc, inType, outType, logger, loggerTxt) {
|
|
const MAX_CHUNK_SIZE = 1<<16;
|
|
const MIN_CHUNK_SIZE = 1<<4;
|
|
|
|
let fnName;
|
|
let fnIn2Mid, fnMid2Out;
|
|
let sOut, sIn, sMid;
|
|
|
|
if (groupName == "G1") {
|
|
if (inType == "affine") {
|
|
sIn = G.F.n8*2;
|
|
fnIn2Mid = "g1m_batchToJacobian";
|
|
} else {
|
|
sIn = G.F.n8*3;
|
|
}
|
|
sMid = G.F.n8*3;
|
|
fnName = "g1m_"+fn;
|
|
if (outType == "affine") {
|
|
fnMid2Out = "g1m_batchToAffine";
|
|
sOut = G.F.n8*2;
|
|
} else {
|
|
sOut = G.F.n8*3;
|
|
}
|
|
} else if (groupName == "G2") {
|
|
if (inType == "affine") {
|
|
sIn = G.F.n8*2;
|
|
fnIn2Mid = "g2m_batchToJacobian";
|
|
} else {
|
|
sIn = G.F.n8*3;
|
|
}
|
|
fnName = "g2m_"+fn;
|
|
sMid = G.F.n8*3;
|
|
if (outType == "affine") {
|
|
fnMid2Out = "g2m_batchToAffine";
|
|
sOut = G.F.n8*2;
|
|
} else {
|
|
sOut = G.F.n8*3;
|
|
}
|
|
} else if (groupName == "Fr") {
|
|
sIn = Fr.n8;
|
|
sOut = Fr.n8;
|
|
sMid = Fr.n8;
|
|
fnName = "frm_" + fn;
|
|
} else {
|
|
throw new Error("Invalid group");
|
|
}
|
|
|
|
if (buff1.byteLength != buff2.byteLength) {
|
|
throw new Error("Invalid buffer size");
|
|
}
|
|
const nPoints = Math.floor(buff1.byteLength / sIn);
|
|
if (nPoints != 1 << log2(nPoints)) {
|
|
throw new Error("Invalid number of points");
|
|
}
|
|
|
|
let chunkSize = Math.floor(nPoints /tm.concurrency);
|
|
if (chunkSize < MIN_CHUNK_SIZE) chunkSize = MIN_CHUNK_SIZE;
|
|
if (chunkSize > MAX_CHUNK_SIZE) chunkSize = MAX_CHUNK_SIZE;
|
|
|
|
const opPromises = [];
|
|
|
|
for (let i=0; i<nPoints; i += chunkSize) {
|
|
if (logger) logger.debug(`${loggerTxt}: fftJoinExt Start: ${i}/${nPoints}`);
|
|
const n= Math.min(nPoints - i, chunkSize);
|
|
|
|
const firstChunk = Fr.mul(first, Fr.exp( inc, i));
|
|
const task = [];
|
|
|
|
const b1 = buff1.slice(i*sIn, (i+n)*sIn);
|
|
const b2 = buff2.slice(i*sIn, (i+n)*sIn);
|
|
|
|
task.push({cmd: "ALLOC", var: 0, len: sMid*n});
|
|
task.push({cmd: "SET", var: 0, buff: b1});
|
|
task.push({cmd: "ALLOC", var: 1, len: sMid*n});
|
|
task.push({cmd: "SET", var: 1, buff: b2});
|
|
task.push({cmd: "ALLOCSET", var: 2, buff: firstChunk});
|
|
task.push({cmd: "ALLOCSET", var: 3, buff: inc});
|
|
if (fnIn2Mid) {
|
|
task.push({cmd: "CALL", fnName:fnIn2Mid, params: [{var:0}, {val: n}, {var: 0}]});
|
|
task.push({cmd: "CALL", fnName:fnIn2Mid, params: [{var:1}, {val: n}, {var: 1}]});
|
|
}
|
|
task.push({cmd: "CALL", fnName: fnName, params: [
|
|
{var: 0},
|
|
{var: 1},
|
|
{val: n},
|
|
{var: 2},
|
|
{var: 3},
|
|
{val: Fr.s},
|
|
]});
|
|
if (fnMid2Out) {
|
|
task.push({cmd: "CALL", fnName:fnMid2Out, params: [{var:0}, {val: n}, {var: 0}]});
|
|
task.push({cmd: "CALL", fnName:fnMid2Out, params: [{var:1}, {val: n}, {var: 1}]});
|
|
}
|
|
task.push({cmd: "GET", out: 0, var: 0, len: n*sOut});
|
|
task.push({cmd: "GET", out: 1, var: 1, len: n*sOut});
|
|
opPromises.push(
|
|
tm.queueAction(task).then( (r) => {
|
|
if (logger) logger.debug(`${loggerTxt}: fftJoinExt End: ${i}/${nPoints}`);
|
|
return r;
|
|
})
|
|
);
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let fullBuffOut1;
|
|
let fullBuffOut2;
|
|
if (nPoints * sOut > 1<<28) {
|
|
fullBuffOut1 = new BigBuffer(nPoints*sOut);
|
|
fullBuffOut2 = new BigBuffer(nPoints*sOut);
|
|
} else {
|
|
fullBuffOut1 = new Uint8Array(nPoints*sOut);
|
|
fullBuffOut2 = new Uint8Array(nPoints*sOut);
|
|
}
|
|
|
|
let p =0;
|
|
for (let i=0; i<result.length; i++) {
|
|
fullBuffOut1.set(result[i][0], p);
|
|
fullBuffOut2.set(result[i][1], p);
|
|
p+=result[i][0].byteLength;
|
|
}
|
|
|
|
return [fullBuffOut1, fullBuffOut2];
|
|
}
|
|
|
|
|
|
G.fft = async function(buff, inType, outType, logger, loggerTxt) {
|
|
return await _fft(buff, false, inType, outType, logger, loggerTxt);
|
|
};
|
|
|
|
G.ifft = async function(buff, inType, outType, logger, loggerTxt) {
|
|
return await _fft(buff, true, inType, outType, logger, loggerTxt);
|
|
};
|
|
|
|
G.lagrangeEvaluations = async function (buff, inType, outType, logger, loggerTxt) {
|
|
inType = inType || "affine";
|
|
outType = outType || "affine";
|
|
|
|
let sIn;
|
|
if (groupName == "G1") {
|
|
if (inType == "affine") {
|
|
sIn = G.F.n8*2;
|
|
} else {
|
|
sIn = G.F.n8*3;
|
|
}
|
|
} else if (groupName == "G2") {
|
|
if (inType == "affine") {
|
|
sIn = G.F.n8*2;
|
|
} else {
|
|
sIn = G.F.n8*3;
|
|
}
|
|
} else if (groupName == "Fr") {
|
|
sIn = Fr.n8;
|
|
} else {
|
|
throw new Error("Invalid group");
|
|
}
|
|
|
|
const nPoints = buff.byteLength /sIn;
|
|
const bits = log2(nPoints);
|
|
|
|
if ((2 ** bits)*sIn != buff.byteLength) {
|
|
if (logger) logger.error("lagrangeEvaluations iinvalid input size");
|
|
throw new Error("lagrangeEvaluations invalid Input size");
|
|
}
|
|
|
|
if (bits <= Fr.s) {
|
|
return await G.ifft(buff, inType, outType, logger, loggerTxt);
|
|
}
|
|
|
|
if (bits > Fr.s+1) {
|
|
if (logger) logger.error("lagrangeEvaluations input too big");
|
|
throw new Error("lagrangeEvaluations input too big");
|
|
}
|
|
|
|
let t0 = buff.slice(0, buff.byteLength/2);
|
|
let t1 = buff.slice(buff.byteLength/2, buff.byteLength);
|
|
|
|
|
|
const shiftToSmallM = Fr.exp(Fr.shift, nPoints/2);
|
|
const sConst = Fr.inv( Fr.sub(Fr.one, shiftToSmallM));
|
|
|
|
[t0, t1] = await _fftJoinExt(t0, t1, "prepareLagrangeEvaluation", sConst, Fr.shiftInv, inType, "jacobian", logger, loggerTxt + " prep");
|
|
|
|
const promises = [];
|
|
|
|
promises.push( _fft(t0, true, "jacobian", outType, logger, loggerTxt + " t0"));
|
|
promises.push( _fft(t1, true, "jacobian", outType, logger, loggerTxt + " t1"));
|
|
|
|
[t0, t1] = await Promise.all(promises);
|
|
|
|
let buffOut;
|
|
if (t0.byteLength > (1<<28)) {
|
|
buffOut = new BigBuffer(t0.byteLength*2);
|
|
} else {
|
|
buffOut = new Uint8Array(t0.byteLength*2);
|
|
}
|
|
|
|
buffOut.set(t0);
|
|
buffOut.set(t1, t0.byteLength);
|
|
|
|
return buffOut;
|
|
};
|
|
|
|
G.fftMix = async function fftMix(buff) {
|
|
const sG = G.F.n8*3;
|
|
let fnName, fnFFTJoin;
|
|
if (groupName == "G1") {
|
|
fnName = "g1m_fftMix";
|
|
fnFFTJoin = "g1m_fftJoin";
|
|
} else if (groupName == "G2") {
|
|
fnName = "g2m_fftMix";
|
|
fnFFTJoin = "g2m_fftJoin";
|
|
} else if (groupName == "Fr") {
|
|
fnName = "frm_fftMix";
|
|
fnFFTJoin = "frm_fftJoin";
|
|
} else {
|
|
throw new Error("Invalid group");
|
|
}
|
|
|
|
const nPoints = Math.floor(buff.byteLength / sG);
|
|
const power = log2(nPoints);
|
|
|
|
let nChunks = 1 << log2(tm.concurrency);
|
|
|
|
if (nPoints <= nChunks*2) nChunks = 1;
|
|
|
|
const pointsPerChunk = nPoints / nChunks;
|
|
|
|
const powerChunk = log2(pointsPerChunk);
|
|
|
|
const opPromises = [];
|
|
for (let i=0; i<nChunks; i++) {
|
|
const task = [];
|
|
const b = buff.slice((i* pointsPerChunk)*sG, ((i+1)* pointsPerChunk)*sG);
|
|
task.push({cmd: "ALLOCSET", var: 0, buff: b});
|
|
for (let j=1; j<=powerChunk; j++) {
|
|
task.push({cmd: "CALL", fnName: fnName, params: [
|
|
{var: 0},
|
|
{val: pointsPerChunk},
|
|
{val: j}
|
|
]});
|
|
}
|
|
task.push({cmd: "GET", out: 0, var: 0, len: pointsPerChunk*sG});
|
|
opPromises.push(
|
|
tm.queueAction(task)
|
|
);
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
const chunks = [];
|
|
for (let i=0; i<result.length; i++) chunks[i] = result[i][0];
|
|
|
|
|
|
for (let i = powerChunk+1; i<=power; i++) {
|
|
const nGroups = 1 << (power - i);
|
|
const nChunksPerGroup = nChunks / nGroups;
|
|
const opPromises = [];
|
|
for (let j=0; j<nGroups; j++) {
|
|
for (let k=0; k <nChunksPerGroup/2; k++) {
|
|
const first = Fr.exp( Fr.w[i], k*pointsPerChunk);
|
|
const inc = Fr.w[i];
|
|
const o1 = j*nChunksPerGroup + k;
|
|
const o2 = j*nChunksPerGroup + k + nChunksPerGroup/2;
|
|
|
|
const task = [];
|
|
task.push({cmd: "ALLOCSET", var: 0, buff: chunks[o1]});
|
|
task.push({cmd: "ALLOCSET", var: 1, buff: chunks[o2]});
|
|
task.push({cmd: "ALLOCSET", var: 2, buff: first});
|
|
task.push({cmd: "ALLOCSET", var: 3, buff: inc});
|
|
task.push({cmd: "CALL", fnName: fnFFTJoin, params:[
|
|
{var: 0},
|
|
{var: 1},
|
|
{val: pointsPerChunk},
|
|
{var: 2},
|
|
{var: 3}
|
|
]});
|
|
task.push({cmd: "GET", out: 0, var: 0, len: pointsPerChunk*sG});
|
|
task.push({cmd: "GET", out: 1, var: 1, len: pointsPerChunk*sG});
|
|
opPromises.push(tm.queueAction(task));
|
|
}
|
|
}
|
|
|
|
const res = await Promise.all(opPromises);
|
|
for (let j=0; j<nGroups; j++) {
|
|
for (let k=0; k <nChunksPerGroup/2; k++) {
|
|
const o1 = j*nChunksPerGroup + k;
|
|
const o2 = j*nChunksPerGroup + k + nChunksPerGroup/2;
|
|
const resChunk = res.shift();
|
|
chunks[o1] = resChunk[0];
|
|
chunks[o2] = resChunk[1];
|
|
}
|
|
}
|
|
}
|
|
|
|
let fullBuffOut;
|
|
if (buff instanceof BigBuffer) {
|
|
fullBuffOut = new BigBuffer(nPoints*sG);
|
|
} else {
|
|
fullBuffOut = new Uint8Array(nPoints*sG);
|
|
}
|
|
let p =0;
|
|
for (let i=0; i<nChunks; i++) {
|
|
fullBuffOut.set(chunks[i], p);
|
|
p+=chunks[i].byteLength;
|
|
}
|
|
|
|
return fullBuffOut;
|
|
};
|
|
|
|
G.fftJoin = async function fftJoin(buff1, buff2, first, inc) {
|
|
const sG = G.F.n8*3;
|
|
let fnName;
|
|
if (groupName == "G1") {
|
|
fnName = "g1m_fftJoin";
|
|
} else if (groupName == "G2") {
|
|
fnName = "g2m_fftJoin";
|
|
} else if (groupName == "Fr") {
|
|
fnName = "frm_fftJoin";
|
|
} else {
|
|
throw new Error("Invalid group");
|
|
}
|
|
|
|
if (buff1.byteLength != buff2.byteLength) {
|
|
throw new Error("Invalid buffer size");
|
|
}
|
|
const nPoints = Math.floor(buff1.byteLength / sG);
|
|
if (nPoints != 1 << log2(nPoints)) {
|
|
throw new Error("Invalid number of points");
|
|
}
|
|
|
|
let nChunks = 1 << log2(tm.concurrency);
|
|
if (nPoints <= nChunks*2) nChunks = 1;
|
|
|
|
const pointsPerChunk = nPoints / nChunks;
|
|
|
|
|
|
const opPromises = [];
|
|
for (let i=0; i<nChunks; i++) {
|
|
const task = [];
|
|
|
|
const firstChunk = Fr.mul(first, Fr.exp(inc, i*pointsPerChunk));
|
|
const b1 = buff1.slice((i* pointsPerChunk)*sG, ((i+1)* pointsPerChunk)*sG);
|
|
const b2 = buff2.slice((i* pointsPerChunk)*sG, ((i+1)* pointsPerChunk)*sG);
|
|
task.push({cmd: "ALLOCSET", var: 0, buff: b1});
|
|
task.push({cmd: "ALLOCSET", var: 1, buff: b2});
|
|
task.push({cmd: "ALLOCSET", var: 2, buff: firstChunk});
|
|
task.push({cmd: "ALLOCSET", var: 3, buff: inc});
|
|
task.push({cmd: "CALL", fnName: fnName, params: [
|
|
{var: 0},
|
|
{var: 1},
|
|
{val: pointsPerChunk},
|
|
{var: 2},
|
|
{var: 3}
|
|
]});
|
|
task.push({cmd: "GET", out: 0, var: 0, len: pointsPerChunk*sG});
|
|
task.push({cmd: "GET", out: 1, var: 1, len: pointsPerChunk*sG});
|
|
opPromises.push(
|
|
tm.queueAction(task)
|
|
);
|
|
|
|
}
|
|
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let fullBuffOut1;
|
|
let fullBuffOut2;
|
|
if (buff1 instanceof BigBuffer) {
|
|
fullBuffOut1 = new BigBuffer(nPoints*sG);
|
|
fullBuffOut2 = new BigBuffer(nPoints*sG);
|
|
} else {
|
|
fullBuffOut1 = new Uint8Array(nPoints*sG);
|
|
fullBuffOut2 = new Uint8Array(nPoints*sG);
|
|
}
|
|
|
|
let p =0;
|
|
for (let i=0; i<result.length; i++) {
|
|
fullBuffOut1.set(result[i][0], p);
|
|
fullBuffOut2.set(result[i][1], p);
|
|
p+=result[i][0].byteLength;
|
|
}
|
|
|
|
return [fullBuffOut1, fullBuffOut2];
|
|
};
|
|
|
|
|
|
|
|
G.fftFinal = async function fftFinal(buff, factor) {
|
|
const sG = G.F.n8*3;
|
|
const sGout = G.F.n8*2;
|
|
let fnName, fnToAffine;
|
|
if (groupName == "G1") {
|
|
fnName = "g1m_fftFinal";
|
|
fnToAffine = "g1m_batchToAffine";
|
|
} else if (groupName == "G2") {
|
|
fnName = "g2m_fftFinal";
|
|
fnToAffine = "g2m_batchToAffine";
|
|
} else {
|
|
throw new Error("Invalid group");
|
|
}
|
|
|
|
const nPoints = Math.floor(buff.byteLength / sG);
|
|
if (nPoints != 1 << log2(nPoints)) {
|
|
throw new Error("Invalid number of points");
|
|
}
|
|
|
|
const pointsPerChunk = Math.floor(nPoints / tm.concurrency);
|
|
|
|
const opPromises = [];
|
|
for (let i=0; i<tm.concurrency; i++) {
|
|
let n;
|
|
if (i< tm.concurrency-1) {
|
|
n = pointsPerChunk;
|
|
} else {
|
|
n = nPoints - i*pointsPerChunk;
|
|
}
|
|
if (n==0) continue;
|
|
const task = [];
|
|
const b = buff.slice((i* pointsPerChunk)*sG, (i*pointsPerChunk+n)*sG);
|
|
task.push({cmd: "ALLOCSET", var: 0, buff: b});
|
|
task.push({cmd: "ALLOCSET", var: 1, buff: factor});
|
|
task.push({cmd: "CALL", fnName: fnName, params: [
|
|
{var: 0},
|
|
{val: n},
|
|
{var: 1},
|
|
]});
|
|
task.push({cmd: "CALL", fnName: fnToAffine, params: [
|
|
{var: 0},
|
|
{val: n},
|
|
{var: 0},
|
|
]});
|
|
task.push({cmd: "GET", out: 0, var: 0, len: n*sGout});
|
|
opPromises.push(
|
|
tm.queueAction(task)
|
|
);
|
|
|
|
}
|
|
|
|
const result = await Promise.all(opPromises);
|
|
|
|
let fullBuffOut;
|
|
if (buff instanceof BigBuffer) {
|
|
fullBuffOut = new BigBuffer(nPoints*sGout);
|
|
} else {
|
|
fullBuffOut = new Uint8Array(nPoints*sGout);
|
|
}
|
|
|
|
let p =0;
|
|
for (let i=result.length-1; i>=0; i--) {
|
|
fullBuffOut.set(result[i][0], p);
|
|
p+=result[i][0].byteLength;
|
|
}
|
|
|
|
return fullBuffOut;
|
|
};
|
|
}
|
|
|
|
async function buildEngine(params) {
|
|
|
|
const tm = await buildThreadManager(params.wasm, params.singleThread);
|
|
|
|
|
|
const curve = {};
|
|
|
|
curve.q = e(params.wasm.q.toString());
|
|
curve.r = e(params.wasm.r.toString());
|
|
curve.name = params.name;
|
|
curve.tm = tm;
|
|
curve.prePSize = params.wasm.prePSize;
|
|
curve.preQSize = params.wasm.preQSize;
|
|
curve.Fr = new WasmField1(tm, "frm", params.n8r, params.r);
|
|
curve.F1 = new WasmField1(tm, "f1m", params.n8q, params.q);
|
|
curve.F2 = new WasmField2(tm, "f2m", curve.F1);
|
|
curve.G1 = new WasmCurve(tm, "g1m", curve.F1, params.wasm.pG1gen, params.wasm.pG1b, params.cofactorG1);
|
|
curve.G2 = new WasmCurve(tm, "g2m", curve.F2, params.wasm.pG2gen, params.wasm.pG2b, params.cofactorG2);
|
|
curve.F6 = new WasmField3(tm, "f6m", curve.F2);
|
|
curve.F12 = new WasmField2(tm, "ftm", curve.F6);
|
|
|
|
curve.Gt = curve.F12;
|
|
|
|
buildBatchApplyKey(curve, "G1");
|
|
buildBatchApplyKey(curve, "G2");
|
|
buildBatchApplyKey(curve, "Fr");
|
|
|
|
buildMultiexp(curve, "G1");
|
|
buildMultiexp(curve, "G2");
|
|
|
|
buildFFT(curve, "G1");
|
|
buildFFT(curve, "G2");
|
|
buildFFT(curve, "Fr");
|
|
|
|
buildPairing(curve);
|
|
|
|
curve.array2buffer = function(arr, sG) {
|
|
const buff = new Uint8Array(sG*arr.length);
|
|
|
|
for (let i=0; i<arr.length; i++) {
|
|
buff.set(arr[i], i*sG);
|
|
}
|
|
|
|
return buff;
|
|
};
|
|
|
|
curve.buffer2array = function(buff , sG) {
|
|
const n= buff.byteLength / sG;
|
|
const arr = new Array(n);
|
|
for (let i=0; i<n; i++) {
|
|
arr[i] = buff.slice(i*sG, i*sG+sG);
|
|
}
|
|
return arr;
|
|
};
|
|
|
|
return curve;
|
|
}
|
|
|
|
globalThis.curve_bn128 = null;
|
|
|
|
async function buildBn128(singleThread, plugins) {
|
|
if ((!singleThread) && (globalThis.curve_bn128)) return globalThis.curve_bn128;
|
|
|
|
const moduleBuilder = new wasmbuilder.ModuleBuilder();
|
|
moduleBuilder.setMemory(25);
|
|
wasmcurves.buildBn128(moduleBuilder);
|
|
|
|
if (plugins) plugins(moduleBuilder);
|
|
|
|
const bn128wasm = {};
|
|
|
|
bn128wasm.code = moduleBuilder.build();
|
|
bn128wasm.pq = moduleBuilder.modules.f1m.pq;
|
|
bn128wasm.pr = moduleBuilder.modules.frm.pq;
|
|
bn128wasm.pG1gen = moduleBuilder.modules.bn128.pG1gen;
|
|
bn128wasm.pG1zero = moduleBuilder.modules.bn128.pG1zero;
|
|
bn128wasm.pG1b = moduleBuilder.modules.bn128.pG1b;
|
|
bn128wasm.pG2gen = moduleBuilder.modules.bn128.pG2gen;
|
|
bn128wasm.pG2zero = moduleBuilder.modules.bn128.pG2zero;
|
|
bn128wasm.pG2b = moduleBuilder.modules.bn128.pG2b;
|
|
bn128wasm.pOneT = moduleBuilder.modules.bn128.pOneT;
|
|
bn128wasm.prePSize = moduleBuilder.modules.bn128.prePSize;
|
|
bn128wasm.preQSize = moduleBuilder.modules.bn128.preQSize;
|
|
bn128wasm.n8q = 32;
|
|
bn128wasm.n8r = 32;
|
|
bn128wasm.q = moduleBuilder.modules.bn128.q;
|
|
bn128wasm.r = moduleBuilder.modules.bn128.r;
|
|
|
|
const params = {
|
|
name: "bn128",
|
|
wasm: bn128wasm,
|
|
q: e("21888242871839275222246405745257275088696311157297823662689037894645226208583"),
|
|
r: e("21888242871839275222246405745257275088548364400416034343698204186575808495617"),
|
|
n8q: 32,
|
|
n8r: 32,
|
|
cofactorG2: e("30644e72e131a029b85045b68181585e06ceecda572a2489345f2299c0f9fa8d", 16),
|
|
singleThread: singleThread ? true : false
|
|
};
|
|
|
|
const curve = await buildEngine(params);
|
|
curve.terminate = async function () {
|
|
if (!params.singleThread) {
|
|
globalThis.curve_bn128 = null;
|
|
await this.tm.terminate();
|
|
}
|
|
};
|
|
|
|
if (!singleThread) {
|
|
globalThis.curve_bn128 = curve;
|
|
}
|
|
|
|
return curve;
|
|
}
|
|
|
|
globalThis.curve_bls12381 = null;
|
|
|
|
async function buildBls12381(singleThread, plugins) {
|
|
if ((!singleThread) && (globalThis.curve_bls12381)) return globalThis.curve_bls12381;
|
|
|
|
const moduleBuilder = new wasmbuilder.ModuleBuilder();
|
|
moduleBuilder.setMemory(25);
|
|
wasmcurves.buildBls12381(moduleBuilder);
|
|
|
|
if (plugins) plugins(moduleBuilder);
|
|
|
|
const bls12381wasm = {};
|
|
|
|
bls12381wasm.code = moduleBuilder.build();
|
|
bls12381wasm.pq = moduleBuilder.modules.f1m.pq;
|
|
bls12381wasm.pr = moduleBuilder.modules.frm.pq;
|
|
bls12381wasm.pG1gen = moduleBuilder.modules.bls12381.pG1gen;
|
|
bls12381wasm.pG1zero = moduleBuilder.modules.bls12381.pG1zero;
|
|
bls12381wasm.pG1b = moduleBuilder.modules.bls12381.pG1b;
|
|
bls12381wasm.pG2gen = moduleBuilder.modules.bls12381.pG2gen;
|
|
bls12381wasm.pG2zero = moduleBuilder.modules.bls12381.pG2zero;
|
|
bls12381wasm.pG2b = moduleBuilder.modules.bls12381.pG2b;
|
|
bls12381wasm.pOneT = moduleBuilder.modules.bls12381.pOneT;
|
|
bls12381wasm.prePSize = moduleBuilder.modules.bls12381.prePSize;
|
|
bls12381wasm.preQSize = moduleBuilder.modules.bls12381.preQSize;
|
|
bls12381wasm.n8q = 48;
|
|
bls12381wasm.n8r = 32;
|
|
bls12381wasm.q = moduleBuilder.modules.bls12381.q;
|
|
bls12381wasm.r = moduleBuilder.modules.bls12381.r;
|
|
|
|
|
|
const params = {
|
|
name: "bls12381",
|
|
wasm: bls12381wasm,
|
|
q: e("1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab", 16),
|
|
r: e("73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001", 16),
|
|
n8q: 48,
|
|
n8r: 32,
|
|
cofactorG1: e("0x396c8c005555e1568c00aaab0000aaab", 16),
|
|
cofactorG2: e("0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5", 16),
|
|
singleThread: singleThread ? true : false
|
|
};
|
|
|
|
const curve = await buildEngine(params);
|
|
curve.terminate = async function () {
|
|
if (!params.singleThread) {
|
|
globalThis.curve_bls12381 = null;
|
|
await this.tm.terminate();
|
|
}
|
|
};
|
|
|
|
if (!singleThread) {
|
|
globalThis.curve_bls12381 = curve;
|
|
}
|
|
|
|
return curve;
|
|
}
|
|
|
|
const bls12381r = e("73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001", 16);
|
|
const bn128r = e("21888242871839275222246405745257275088548364400416034343698204186575808495617");
|
|
|
|
const bls12381q = e("1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab", 16);
|
|
const bn128q = e("21888242871839275222246405745257275088696311157297823662689037894645226208583");
|
|
|
|
async function getCurveFromR(r, singleThread, plugins) {
|
|
let curve;
|
|
if (eq(r, bn128r)) {
|
|
curve = await buildBn128(singleThread, plugins);
|
|
} else if (eq(r, bls12381r)) {
|
|
curve = await buildBls12381(singleThread, plugins);
|
|
} else {
|
|
throw new Error(`Curve not supported: ${toString(r)}`);
|
|
}
|
|
return curve;
|
|
}
|
|
|
|
async function getCurveFromQ(q, singleThread, plugins) {
|
|
let curve;
|
|
if (eq(q, bn128q)) {
|
|
curve = await buildBn128(singleThread, plugins);
|
|
} else if (eq(q, bls12381q)) {
|
|
curve = await buildBls12381(singleThread, plugins);
|
|
} else {
|
|
throw new Error(`Curve not supported: ${toString(q, 16)}`);
|
|
}
|
|
return curve;
|
|
}
|
|
|
|
async function getCurveFromName(name, singleThread, plugins) {
|
|
let curve;
|
|
const normName = normalizeName(name);
|
|
if (["BN128", "BN254", "ALTBN128"].indexOf(normName) >= 0) {
|
|
curve = await buildBn128(singleThread, plugins);
|
|
} else if (["BLS12381"].indexOf(normName) >= 0) {
|
|
curve = await buildBls12381(singleThread, plugins);
|
|
} else {
|
|
throw new Error(`Curve not supported: ${name}`);
|
|
}
|
|
return curve;
|
|
|
|
function normalizeName(n) {
|
|
return n.toUpperCase().match(/[A-Za-z0-9]+/g).join("");
|
|
}
|
|
|
|
}
|
|
|
|
const Scalar=_Scalar;
|
|
const utils = _utils;
|
|
|
|
exports.BigBuffer = BigBuffer;
|
|
exports.ChaCha = ChaCha;
|
|
exports.EC = EC;
|
|
exports.F1Field = ZqField;
|
|
exports.F2Field = F2Field;
|
|
exports.F3Field = F3Field;
|
|
exports.PolField = PolField;
|
|
exports.Scalar = Scalar;
|
|
exports.ZqField = ZqField;
|
|
exports.buildBls12381 = buildBls12381;
|
|
exports.buildBn128 = buildBn128;
|
|
exports.getCurveFromName = getCurveFromName;
|
|
exports.getCurveFromQ = getCurveFromQ;
|
|
exports.getCurveFromR = getCurveFromR;
|
|
exports.utils = utils;
|