437 lines
14 KiB
JavaScript
437 lines
14 KiB
JavaScript
/*
|
|
Copyright 2019 0KIMS association.
|
|
|
|
This file is part of websnark (Web Assembly zkSnark Prover).
|
|
|
|
websnark 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.
|
|
|
|
websnark 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 websnark. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
const buildTimesScalar = require("./build_timesscalar");
|
|
|
|
module.exports = function buildCurve(module, prefix, prefixField) {
|
|
|
|
|
|
const n64 = module.modules[prefixField].n64;
|
|
const n8 = n64*8;
|
|
|
|
if (module.modules[prefix]) return prefix; // already builded
|
|
module.modules[prefix] = {
|
|
n64: n64*3
|
|
};
|
|
|
|
function buildIsZero() {
|
|
const f = module.addFunction(prefix + "_isZero");
|
|
f.addParam("p1", "i32");
|
|
f.setReturnType("i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_isZero",
|
|
c.i32_add(
|
|
c.getLocal("p1"),
|
|
c.i32_const(n8*2)
|
|
)
|
|
));
|
|
}
|
|
|
|
function buildCopy() {
|
|
const f = module.addFunction(prefix + "_copy");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_copy",
|
|
c.getLocal("p1"),
|
|
c.getLocal("pr")
|
|
));
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_copy",
|
|
c.i32_add(
|
|
c.getLocal("p1"),
|
|
c.i32_const(n8)
|
|
),
|
|
c.i32_add(
|
|
c.getLocal("pr"),
|
|
c.i32_const(n8)
|
|
)
|
|
));
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_copy",
|
|
c.i32_add(
|
|
c.getLocal("p1"),
|
|
c.i32_const(n8*2)
|
|
),
|
|
c.i32_add(
|
|
c.getLocal("pr"),
|
|
c.i32_const(n8*2)
|
|
)
|
|
));
|
|
}
|
|
|
|
function buildZero() {
|
|
const f = module.addFunction(prefix + "_zero");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_zero",
|
|
c.getLocal("pr")
|
|
));
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_one",
|
|
c.i32_add(
|
|
c.getLocal("pr"),
|
|
c.i32_const(n8)
|
|
)
|
|
));
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_zero",
|
|
c.i32_add(
|
|
c.getLocal("pr"),
|
|
c.i32_const(n8*2)
|
|
)
|
|
));
|
|
}
|
|
|
|
function buildDouble() {
|
|
const f = module.addFunction(prefix + "_double");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
const x = c.getLocal("p1");
|
|
const y = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
|
|
const z = c.i32_add(c.getLocal("p1"), c.i32_const(n8*2));
|
|
const x3 = c.getLocal("pr");
|
|
const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
|
|
const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
|
|
|
|
const A = c.i32_const(module.alloc(n8));
|
|
const B = c.i32_const(module.alloc(n8));
|
|
const C = c.i32_const(module.alloc(n8));
|
|
const D = c.i32_const(module.alloc(n8));
|
|
const E = c.i32_const(module.alloc(n8));
|
|
const F = c.i32_const(module.alloc(n8));
|
|
const G = c.i32_const(module.alloc(n8));
|
|
const eightC = c.i32_const(module.alloc(n8));
|
|
|
|
f.addCode(
|
|
c.if(
|
|
c.call(prefix + "_isZero", c.getLocal("p1")),
|
|
[
|
|
...c.call(prefix + "_copy", c.getLocal("p1"), c.getLocal("pr")),
|
|
...c.ret([])
|
|
]
|
|
),
|
|
|
|
c.call(prefixField + "_mul", x, x, A),
|
|
c.call(prefixField + "_mul", y, y, B),
|
|
c.call(prefixField + "_mul", B, B, C),
|
|
|
|
c.call(prefixField + "_add", x, B, D),
|
|
c.call(prefixField + "_mul", D, D, D),
|
|
c.call(prefixField + "_sub", D, A, D),
|
|
c.call(prefixField + "_sub", D, C, D),
|
|
c.call(prefixField + "_add", D, D, D),
|
|
|
|
c.call(prefixField + "_add", A, A, E),
|
|
c.call(prefixField + "_add", E, A, E),
|
|
c.call(prefixField + "_mul", E, E, F),
|
|
|
|
c.call(prefixField + "_mul", y, z, G),
|
|
|
|
c.call(prefixField + "_add", D, D, x3),
|
|
c.call(prefixField + "_sub", F, x3, x3),
|
|
|
|
c.call(prefixField + "_add", C, C, eightC),
|
|
c.call(prefixField + "_add", eightC, eightC, eightC),
|
|
c.call(prefixField + "_add", eightC, eightC, eightC),
|
|
|
|
c.call(prefixField + "_sub", D, x3, y3),
|
|
c.call(prefixField + "_mul", y3, E, y3),
|
|
c.call(prefixField + "_sub", y3, eightC, y3),
|
|
|
|
c.call(prefixField + "_add", G, G, z3),
|
|
);
|
|
}
|
|
|
|
function buildToMontgomery() {
|
|
const f = module.addFunction(prefix + "_toMontgomery");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_toMontgomery",
|
|
c.getLocal("p1"),
|
|
c.getLocal("pr")
|
|
));
|
|
for (let i=1; i<3; i++) {
|
|
f.addCode(c.call(
|
|
prefixField + "_toMontgomery",
|
|
c.i32_add(c.getLocal("p1"), c.i32_const(i*n8)),
|
|
c.i32_add(c.getLocal("pr"), c.i32_const(i*n8))
|
|
));
|
|
}
|
|
}
|
|
|
|
function buildFromMontgomery() {
|
|
const f = module.addFunction(prefix + "_fromMontgomery");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
f.addCode(c.call(
|
|
prefixField + "_fromMontgomery",
|
|
c.getLocal("p1"),
|
|
c.getLocal("pr")
|
|
));
|
|
for (let i=1; i<3; i++) {
|
|
f.addCode(c.call(
|
|
prefixField + "_fromMontgomery",
|
|
c.i32_add(c.getLocal("p1"), c.i32_const(i*n8)),
|
|
c.i32_add(c.getLocal("pr"), c.i32_const(i*n8))
|
|
));
|
|
}
|
|
}
|
|
|
|
|
|
function buildAdd() {
|
|
|
|
const f = module.addFunction(prefix + "_add");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("p2", "i32");
|
|
f.addParam("pr", "i32");
|
|
f.addLocal("z1", "i32");
|
|
f.addLocal("z2", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
const x1 = c.getLocal("p1");
|
|
const y1 = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
|
|
f.addCode(c.setLocal("z1", c.i32_add(c.getLocal("p1"), c.i32_const(n8*2))));
|
|
const z1 = c.getLocal("z1");
|
|
const x2 = c.getLocal("p2");
|
|
const y2 = c.i32_add(c.getLocal("p2"), c.i32_const(n8));
|
|
f.addCode(c.setLocal("z2", c.i32_add(c.getLocal("p2"), c.i32_const(n8*2))));
|
|
const z2 = c.getLocal("z2");
|
|
const x3 = c.getLocal("pr");
|
|
const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
|
|
const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
|
|
|
|
const Z1Z1 = c.i32_const(module.alloc(n8));
|
|
const Z2Z2 = c.i32_const(module.alloc(n8));
|
|
const U1 = c.i32_const(module.alloc(n8));
|
|
const U2 = c.i32_const(module.alloc(n8));
|
|
const Z1_cubed = c.i32_const(module.alloc(n8));
|
|
const Z2_cubed = c.i32_const(module.alloc(n8));
|
|
const S1 = c.i32_const(module.alloc(n8));
|
|
const S2 = c.i32_const(module.alloc(n8));
|
|
const H = c.i32_const(module.alloc(n8));
|
|
const S2_minus_S1 = c.i32_const(module.alloc(n8));
|
|
const I = c.i32_const(module.alloc(n8));
|
|
const J = c.i32_const(module.alloc(n8));
|
|
const r = c.i32_const(module.alloc(n8));
|
|
const r2 = c.i32_const(module.alloc(n8));
|
|
const V = c.i32_const(module.alloc(n8));
|
|
const V2 = c.i32_const(module.alloc(n8));
|
|
const S1_J2 = c.i32_const(module.alloc(n8));
|
|
|
|
f.addCode(
|
|
c.if(
|
|
c.call(prefix + "_isZero", c.getLocal("p1")),
|
|
[
|
|
...c.call(prefix + "_copy", c.getLocal("p2"), c.getLocal("pr")),
|
|
...c.ret([])
|
|
]
|
|
),
|
|
|
|
c.if(
|
|
c.call(prefix + "_isZero", c.getLocal("p2")),
|
|
[
|
|
...c.call(prefix + "_copy", c.getLocal("p1"), c.getLocal("pr")),
|
|
...c.ret([])
|
|
]
|
|
),
|
|
|
|
c.call(prefixField + "_mul", z1, z1, Z1Z1),
|
|
c.call(prefixField + "_mul", z2, z2, Z2Z2),
|
|
c.call(prefixField + "_mul", x1, Z2Z2, U1),
|
|
c.call(prefixField + "_mul", x2, Z1Z1, U2),
|
|
c.call(prefixField + "_mul", z1, Z1Z1, Z1_cubed),
|
|
c.call(prefixField + "_mul", z2, Z2Z2, Z2_cubed),
|
|
c.call(prefixField + "_mul", y1, Z2_cubed, S1),
|
|
c.call(prefixField + "_mul", y2, Z1_cubed, S2),
|
|
|
|
c.if(
|
|
c.call(prefixField + "_eq", U1, U2),
|
|
c.if(
|
|
c.call(prefixField + "_eq", S1, S2),
|
|
[
|
|
...c.call(prefix + "_double", c.getLocal("p1"), c.getLocal("pr")),
|
|
...c.ret([])
|
|
]
|
|
)
|
|
),
|
|
|
|
c.call(prefixField + "_sub", U2, U1, H),
|
|
c.call(prefixField + "_sub", S2, S1, S2_minus_S1),
|
|
c.call(prefixField + "_add", H, H, I),
|
|
c.call(prefixField + "_mul", I, I, I),
|
|
c.call(prefixField + "_mul", H, I, J),
|
|
c.call(prefixField + "_add", S2_minus_S1, S2_minus_S1, r),
|
|
c.call(prefixField + "_mul", U1, I, V),
|
|
c.call(prefixField + "_mul", r, r, r2),
|
|
c.call(prefixField + "_add", V, V, V2),
|
|
|
|
c.call(prefixField + "_sub", r2, J, x3),
|
|
c.call(prefixField + "_sub", x3, V2, x3),
|
|
|
|
c.call(prefixField + "_mul", S1, J, S1_J2),
|
|
c.call(prefixField + "_add", S1_J2, S1_J2, S1_J2),
|
|
|
|
c.call(prefixField + "_sub", V, x3, y3),
|
|
c.call(prefixField + "_mul", y3, r, y3),
|
|
c.call(prefixField + "_sub", y3, S1_J2, y3),
|
|
|
|
c.call(prefixField + "_add", z1, z2, z3),
|
|
c.call(prefixField + "_mul", z3, z3, z3),
|
|
c.call(prefixField + "_sub", z3, Z1Z1, z3),
|
|
c.call(prefixField + "_sub", z3, Z2Z2, z3),
|
|
c.call(prefixField + "_mul", z3, H, z3),
|
|
);
|
|
|
|
}
|
|
|
|
function buildNeg() {
|
|
const f = module.addFunction(prefix + "_neg");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
const x = c.getLocal("p1");
|
|
const y = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
|
|
const z = c.i32_add(c.getLocal("p1"), c.i32_const(n8*2));
|
|
const x3 = c.getLocal("pr");
|
|
const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
|
|
const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
|
|
|
|
f.addCode(
|
|
c.call(prefixField + "_copy", x, x3),
|
|
c.call(prefixField + "_neg", y, y3),
|
|
c.call(prefixField + "_copy", z, z3)
|
|
);
|
|
}
|
|
|
|
function buildSub() {
|
|
const f = module.addFunction(prefix + "_sub");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("p2", "i32");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
f.addCode(
|
|
c.call(prefix + "_neg", c.getLocal("p2"), c.getLocal("pr")),
|
|
c.call(prefix + "_add", c.getLocal("p1"), c.getLocal("pr"), c.getLocal("pr")),
|
|
);
|
|
}
|
|
|
|
|
|
function buildAffine() {
|
|
const f = module.addFunction(prefix + "_affine");
|
|
f.addParam("p1", "i32");
|
|
f.addParam("pr", "i32");
|
|
|
|
const c = f.getCodeBuilder();
|
|
|
|
const x = c.getLocal("p1");
|
|
const y = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
|
|
const z = c.i32_add(c.getLocal("p1"), c.i32_const(n8*2));
|
|
const x3 = c.getLocal("pr");
|
|
const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
|
|
const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
|
|
|
|
|
|
const Z_inv = c.i32_const(module.alloc(n8));
|
|
const Z2_inv = c.i32_const(module.alloc(n8));
|
|
const Z3_inv = c.i32_const(module.alloc(n8));
|
|
|
|
f.addCode(
|
|
c.if(
|
|
c.call(prefix + "_isZero", c.getLocal("p1")),
|
|
c.call(prefix + "_zero", c.getLocal("pr")),
|
|
[
|
|
...c.call(prefixField + "_inverse", z, Z_inv),
|
|
...c.call(prefixField + "_mul", Z_inv, Z_inv, Z2_inv),
|
|
...c.call(prefixField + "_mul", Z_inv, Z2_inv, Z3_inv),
|
|
...c.call(prefixField + "_mul", x, Z2_inv, x3),
|
|
...c.call(prefixField + "_mul", y, Z3_inv, y3),
|
|
...c.call(prefixField + "_one", z3)
|
|
]
|
|
)
|
|
);
|
|
}
|
|
|
|
|
|
buildIsZero();
|
|
buildZero();
|
|
buildCopy();
|
|
buildDouble();
|
|
buildAdd();
|
|
buildNeg();
|
|
buildSub();
|
|
buildFromMontgomery();
|
|
buildToMontgomery();
|
|
buildAffine();
|
|
buildTimesScalar(
|
|
module,
|
|
prefix + "_timesScalar",
|
|
n8*3,
|
|
prefix + "_add",
|
|
prefix + "_double",
|
|
prefix
|
|
);
|
|
module.exportFunction(prefix + "_isZero");
|
|
module.exportFunction(prefix + "_copy");
|
|
module.exportFunction(prefix + "_zero");
|
|
module.exportFunction(prefix + "_double");
|
|
module.exportFunction(prefix + "_add");
|
|
module.exportFunction(prefix + "_neg");
|
|
module.exportFunction(prefix + "_sub");
|
|
module.exportFunction(prefix + "_fromMontgomery");
|
|
module.exportFunction(prefix + "_toMontgomery");
|
|
module.exportFunction(prefix + "_affine");
|
|
module.exportFunction(prefix + "_timesScalar");
|
|
|
|
/*
|
|
buildG1MulScalar(module, zq);
|
|
module.exportFunction("g1MulScalar");
|
|
*/
|
|
|
|
return prefix;
|
|
};
|