websnark/src/build_curve.js
src/build_curve.jsRaw
1/*
2 Copyright 2019 0KIMS association.
3
4 This file is part of websnark (Web Assembly zkSnark Prover).
5
6 websnark is a free software: you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 websnark is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with websnark. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const buildTimesScalar = require("./build_timesscalar");
21
22module.exports = function buildCurve(module, prefix, prefixField) {
23
24
25 const n64 = module.modules[prefixField].n64;
26 const n8 = n64*8;
27
28 if (module.modules[prefix]) return prefix; // already builded
29 module.modules[prefix] = {
30 n64: n64*3
31 };
32
33 function buildIsZero() {
34 const f = module.addFunction(prefix + "_isZero");
35 f.addParam("p1", "i32");
36 f.setReturnType("i32");
37
38 const c = f.getCodeBuilder();
39
40 f.addCode(c.call(
41 prefixField + "_isZero",
42 c.i32_add(
43 c.getLocal("p1"),
44 c.i32_const(n8*2)
45 )
46 ));
47 }
48
49 function buildCopy() {
50 const f = module.addFunction(prefix + "_copy");
51 f.addParam("p1", "i32");
52 f.addParam("pr", "i32");
53
54 const c = f.getCodeBuilder();
55
56 f.addCode(c.call(
57 prefixField + "_copy",
58 c.getLocal("p1"),
59 c.getLocal("pr")
60 ));
61
62 f.addCode(c.call(
63 prefixField + "_copy",
64 c.i32_add(
65 c.getLocal("p1"),
66 c.i32_const(n8)
67 ),
68 c.i32_add(
69 c.getLocal("pr"),
70 c.i32_const(n8)
71 )
72 ));
73
74 f.addCode(c.call(
75 prefixField + "_copy",
76 c.i32_add(
77 c.getLocal("p1"),
78 c.i32_const(n8*2)
79 ),
80 c.i32_add(
81 c.getLocal("pr"),
82 c.i32_const(n8*2)
83 )
84 ));
85 }
86
87 function buildZero() {
88 const f = module.addFunction(prefix + "_zero");
89 f.addParam("pr", "i32");
90
91 const c = f.getCodeBuilder();
92
93 f.addCode(c.call(
94 prefixField + "_zero",
95 c.getLocal("pr")
96 ));
97
98 f.addCode(c.call(
99 prefixField + "_one",
100 c.i32_add(
101 c.getLocal("pr"),
102 c.i32_const(n8)
103 )
104 ));
105
106 f.addCode(c.call(
107 prefixField + "_zero",
108 c.i32_add(
109 c.getLocal("pr"),
110 c.i32_const(n8*2)
111 )
112 ));
113 }
114
115 function buildDouble() {
116 const f = module.addFunction(prefix + "_double");
117 f.addParam("p1", "i32");
118 f.addParam("pr", "i32");
119
120 const c = f.getCodeBuilder();
121
122 const x = c.getLocal("p1");
123 const y = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
124 const z = c.i32_add(c.getLocal("p1"), c.i32_const(n8*2));
125 const x3 = c.getLocal("pr");
126 const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
127 const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
128
129 const A = c.i32_const(module.alloc(n8));
130 const B = c.i32_const(module.alloc(n8));
131 const C = c.i32_const(module.alloc(n8));
132 const D = c.i32_const(module.alloc(n8));
133 const E = c.i32_const(module.alloc(n8));
134 const F = c.i32_const(module.alloc(n8));
135 const G = c.i32_const(module.alloc(n8));
136 const eightC = c.i32_const(module.alloc(n8));
137
138 f.addCode(
139 c.if(
140 c.call(prefix + "_isZero", c.getLocal("p1")),
141 [
142 ...c.call(prefix + "_copy", c.getLocal("p1"), c.getLocal("pr")),
143 ...c.ret([])
144 ]
145 ),
146
147 c.call(prefixField + "_mul", x, x, A),
148 c.call(prefixField + "_mul", y, y, B),
149 c.call(prefixField + "_mul", B, B, C),
150
151 c.call(prefixField + "_add", x, B, D),
152 c.call(prefixField + "_mul", D, D, D),
153 c.call(prefixField + "_sub", D, A, D),
154 c.call(prefixField + "_sub", D, C, D),
155 c.call(prefixField + "_add", D, D, D),
156
157 c.call(prefixField + "_add", A, A, E),
158 c.call(prefixField + "_add", E, A, E),
159 c.call(prefixField + "_mul", E, E, F),
160
161 c.call(prefixField + "_mul", y, z, G),
162
163 c.call(prefixField + "_add", D, D, x3),
164 c.call(prefixField + "_sub", F, x3, x3),
165
166 c.call(prefixField + "_add", C, C, eightC),
167 c.call(prefixField + "_add", eightC, eightC, eightC),
168 c.call(prefixField + "_add", eightC, eightC, eightC),
169
170 c.call(prefixField + "_sub", D, x3, y3),
171 c.call(prefixField + "_mul", y3, E, y3),
172 c.call(prefixField + "_sub", y3, eightC, y3),
173
174 c.call(prefixField + "_add", G, G, z3),
175 );
176 }
177
178 function buildToMontgomery() {
179 const f = module.addFunction(prefix + "_toMontgomery");
180 f.addParam("p1", "i32");
181 f.addParam("pr", "i32");
182
183 const c = f.getCodeBuilder();
184
185 f.addCode(c.call(
186 prefixField + "_toMontgomery",
187 c.getLocal("p1"),
188 c.getLocal("pr")
189 ));
190 for (let i=1; i<3; i++) {
191 f.addCode(c.call(
192 prefixField + "_toMontgomery",
193 c.i32_add(c.getLocal("p1"), c.i32_const(i*n8)),
194 c.i32_add(c.getLocal("pr"), c.i32_const(i*n8))
195 ));
196 }
197 }
198
199 function buildFromMontgomery() {
200 const f = module.addFunction(prefix + "_fromMontgomery");
201 f.addParam("p1", "i32");
202 f.addParam("pr", "i32");
203
204 const c = f.getCodeBuilder();
205
206 f.addCode(c.call(
207 prefixField + "_fromMontgomery",
208 c.getLocal("p1"),
209 c.getLocal("pr")
210 ));
211 for (let i=1; i<3; i++) {
212 f.addCode(c.call(
213 prefixField + "_fromMontgomery",
214 c.i32_add(c.getLocal("p1"), c.i32_const(i*n8)),
215 c.i32_add(c.getLocal("pr"), c.i32_const(i*n8))
216 ));
217 }
218 }
219
220
221 function buildAdd() {
222
223 const f = module.addFunction(prefix + "_add");
224 f.addParam("p1", "i32");
225 f.addParam("p2", "i32");
226 f.addParam("pr", "i32");
227 f.addLocal("z1", "i32");
228 f.addLocal("z2", "i32");
229
230 const c = f.getCodeBuilder();
231
232 const x1 = c.getLocal("p1");
233 const y1 = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
234 f.addCode(c.setLocal("z1", c.i32_add(c.getLocal("p1"), c.i32_const(n8*2))));
235 const z1 = c.getLocal("z1");
236 const x2 = c.getLocal("p2");
237 const y2 = c.i32_add(c.getLocal("p2"), c.i32_const(n8));
238 f.addCode(c.setLocal("z2", c.i32_add(c.getLocal("p2"), c.i32_const(n8*2))));
239 const z2 = c.getLocal("z2");
240 const x3 = c.getLocal("pr");
241 const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
242 const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
243
244 const Z1Z1 = c.i32_const(module.alloc(n8));
245 const Z2Z2 = c.i32_const(module.alloc(n8));
246 const U1 = c.i32_const(module.alloc(n8));
247 const U2 = c.i32_const(module.alloc(n8));
248 const Z1_cubed = c.i32_const(module.alloc(n8));
249 const Z2_cubed = c.i32_const(module.alloc(n8));
250 const S1 = c.i32_const(module.alloc(n8));
251 const S2 = c.i32_const(module.alloc(n8));
252 const H = c.i32_const(module.alloc(n8));
253 const S2_minus_S1 = c.i32_const(module.alloc(n8));
254 const I = c.i32_const(module.alloc(n8));
255 const J = c.i32_const(module.alloc(n8));
256 const r = c.i32_const(module.alloc(n8));
257 const r2 = c.i32_const(module.alloc(n8));
258 const V = c.i32_const(module.alloc(n8));
259 const V2 = c.i32_const(module.alloc(n8));
260 const S1_J2 = c.i32_const(module.alloc(n8));
261
262 f.addCode(
263 c.if(
264 c.call(prefix + "_isZero", c.getLocal("p1")),
265 [
266 ...c.call(prefix + "_copy", c.getLocal("p2"), c.getLocal("pr")),
267 ...c.ret([])
268 ]
269 ),
270
271 c.if(
272 c.call(prefix + "_isZero", c.getLocal("p2")),
273 [
274 ...c.call(prefix + "_copy", c.getLocal("p1"), c.getLocal("pr")),
275 ...c.ret([])
276 ]
277 ),
278
279 c.call(prefixField + "_mul", z1, z1, Z1Z1),
280 c.call(prefixField + "_mul", z2, z2, Z2Z2),
281 c.call(prefixField + "_mul", x1, Z2Z2, U1),
282 c.call(prefixField + "_mul", x2, Z1Z1, U2),
283 c.call(prefixField + "_mul", z1, Z1Z1, Z1_cubed),
284 c.call(prefixField + "_mul", z2, Z2Z2, Z2_cubed),
285 c.call(prefixField + "_mul", y1, Z2_cubed, S1),
286 c.call(prefixField + "_mul", y2, Z1_cubed, S2),
287
288 c.if(
289 c.call(prefixField + "_eq", U1, U2),
290 c.if(
291 c.call(prefixField + "_eq", S1, S2),
292 [
293 ...c.call(prefix + "_double", c.getLocal("p1"), c.getLocal("pr")),
294 ...c.ret([])
295 ]
296 )
297 ),
298
299 c.call(prefixField + "_sub", U2, U1, H),
300 c.call(prefixField + "_sub", S2, S1, S2_minus_S1),
301 c.call(prefixField + "_add", H, H, I),
302 c.call(prefixField + "_mul", I, I, I),
303 c.call(prefixField + "_mul", H, I, J),
304 c.call(prefixField + "_add", S2_minus_S1, S2_minus_S1, r),
305 c.call(prefixField + "_mul", U1, I, V),
306 c.call(prefixField + "_mul", r, r, r2),
307 c.call(prefixField + "_add", V, V, V2),
308
309 c.call(prefixField + "_sub", r2, J, x3),
310 c.call(prefixField + "_sub", x3, V2, x3),
311
312 c.call(prefixField + "_mul", S1, J, S1_J2),
313 c.call(prefixField + "_add", S1_J2, S1_J2, S1_J2),
314
315 c.call(prefixField + "_sub", V, x3, y3),
316 c.call(prefixField + "_mul", y3, r, y3),
317 c.call(prefixField + "_sub", y3, S1_J2, y3),
318
319 c.call(prefixField + "_add", z1, z2, z3),
320 c.call(prefixField + "_mul", z3, z3, z3),
321 c.call(prefixField + "_sub", z3, Z1Z1, z3),
322 c.call(prefixField + "_sub", z3, Z2Z2, z3),
323 c.call(prefixField + "_mul", z3, H, z3),
324 );
325
326 }
327
328 function buildNeg() {
329 const f = module.addFunction(prefix + "_neg");
330 f.addParam("p1", "i32");
331 f.addParam("pr", "i32");
332
333 const c = f.getCodeBuilder();
334
335 const x = c.getLocal("p1");
336 const y = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
337 const z = c.i32_add(c.getLocal("p1"), c.i32_const(n8*2));
338 const x3 = c.getLocal("pr");
339 const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
340 const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
341
342 f.addCode(
343 c.call(prefixField + "_copy", x, x3),
344 c.call(prefixField + "_neg", y, y3),
345 c.call(prefixField + "_copy", z, z3)
346 );
347 }
348
349 function buildSub() {
350 const f = module.addFunction(prefix + "_sub");
351 f.addParam("p1", "i32");
352 f.addParam("p2", "i32");
353 f.addParam("pr", "i32");
354
355 const c = f.getCodeBuilder();
356
357 f.addCode(
358 c.call(prefix + "_neg", c.getLocal("p2"), c.getLocal("pr")),
359 c.call(prefix + "_add", c.getLocal("p1"), c.getLocal("pr"), c.getLocal("pr")),
360 );
361 }
362
363
364 function buildAffine() {
365 const f = module.addFunction(prefix + "_affine");
366 f.addParam("p1", "i32");
367 f.addParam("pr", "i32");
368
369 const c = f.getCodeBuilder();
370
371 const x = c.getLocal("p1");
372 const y = c.i32_add(c.getLocal("p1"), c.i32_const(n8));
373 const z = c.i32_add(c.getLocal("p1"), c.i32_const(n8*2));
374 const x3 = c.getLocal("pr");
375 const y3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8));
376 const z3 = c.i32_add(c.getLocal("pr"), c.i32_const(n8*2));
377
378
379 const Z_inv = c.i32_const(module.alloc(n8));
380 const Z2_inv = c.i32_const(module.alloc(n8));
381 const Z3_inv = c.i32_const(module.alloc(n8));
382
383 f.addCode(
384 c.if(
385 c.call(prefix + "_isZero", c.getLocal("p1")),
386 c.call(prefix + "_zero", c.getLocal("pr")),
387 [
388 ...c.call(prefixField + "_inverse", z, Z_inv),
389 ...c.call(prefixField + "_mul", Z_inv, Z_inv, Z2_inv),
390 ...c.call(prefixField + "_mul", Z_inv, Z2_inv, Z3_inv),
391 ...c.call(prefixField + "_mul", x, Z2_inv, x3),
392 ...c.call(prefixField + "_mul", y, Z3_inv, y3),
393 ...c.call(prefixField + "_one", z3)
394 ]
395 )
396 );
397 }
398
399
400 buildIsZero();
401 buildZero();
402 buildCopy();
403 buildDouble();
404 buildAdd();
405 buildNeg();
406 buildSub();
407 buildFromMontgomery();
408 buildToMontgomery();
409 buildAffine();
410 buildTimesScalar(
411 module,
412 prefix + "_timesScalar",
413 n8*3,
414 prefix + "_add",
415 prefix + "_double",
416 prefix
417 );
418 module.exportFunction(prefix + "_isZero");
419 module.exportFunction(prefix + "_copy");
420 module.exportFunction(prefix + "_zero");
421 module.exportFunction(prefix + "_double");
422 module.exportFunction(prefix + "_add");
423 module.exportFunction(prefix + "_neg");
424 module.exportFunction(prefix + "_sub");
425 module.exportFunction(prefix + "_fromMontgomery");
426 module.exportFunction(prefix + "_toMontgomery");
427 module.exportFunction(prefix + "_affine");
428 module.exportFunction(prefix + "_timesScalar");
429
430 /*
431 buildG1MulScalar(module, zq);
432 module.exportFunction("g1MulScalar");
433 */
434
435 return prefix;
436};