websnark/src/bn128.js
src/bn128.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/* globals WebAssembly */
20const bigInt = require("big-integer");
21const ModuleBuilder = require("wasmbuilder");
22const buildF1m = require("./build_f1m.js");
23const buildF2m = require("./build_f2m.js");
24const buildF1 = require("./build_f1.js");
25const buildCurve = require("./build_curve.js");
26const buildTest = require("./build_testg1");
27const buildFFT = require("./build_fft");
28const buildMultiexp = require("./build_multiexp");
29const buildPol = require("./build_pol");
30const utils = require("./utils");
31
32async function build() {
33 const bn128 = new Bn128();
34
35 bn128.q = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208583");
36 bn128.r = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
37 bn128.n64 = Math.floor((bn128.q.minus(1).bitLength() - 1)/64) +1;
38 bn128.n32 = bn128.n64*2;
39 bn128.n8 = bn128.n64*8;
40
41 bn128.memory = new WebAssembly.Memory({initial:10000});
42 bn128.i32 = new Uint32Array(bn128.memory.buffer);
43
44 const moduleBuilder = new ModuleBuilder();
45 moduleBuilder.setMemory(10000);
46 buildF1m(moduleBuilder, bn128.q, "f1m");
47 buildF1(moduleBuilder, bn128.r, "fr", "frm");
48 buildCurve(moduleBuilder, "g1", "f1m");
49 buildMultiexp(moduleBuilder, "g1", "g1", "f1m", "fr");
50 buildFFT(moduleBuilder, "fft", "frm");
51 buildPol(moduleBuilder, "pol", "frm");
52
53 const pNonResidueF2 = moduleBuilder.alloc(
54 utils.bigInt2BytesLE(
55 bigInt("15537367993719455909907449462855742678907882278146377936676643359958227611562"), // -1 in montgomery
56 bn128.n8
57 )
58 );
59
60 buildF2m(moduleBuilder, pNonResidueF2, "f2m", "f1m");
61 buildCurve(moduleBuilder, "g2", "f2m");
62 buildMultiexp(moduleBuilder, "g2", "g2", "f2m", "fr");
63
64 buildTest(moduleBuilder);
65
66 const code = moduleBuilder.build();
67
68 const wasmModule = await WebAssembly.compile(code);
69
70 bn128.instance = await WebAssembly.instantiate(wasmModule, {
71 env: {
72 "memory": bn128.memory
73 }
74 });
75
76 bn128.pq = moduleBuilder.modules.f1m.pq;
77 bn128.pr = moduleBuilder.modules.frm.pq;
78
79 bn128.pg1 = bn128.g1_allocPoint([bigInt(1), bigInt(2), bigInt(1)]);
80
81 Object.assign(bn128, bn128.instance.exports);
82
83 return bn128;
84}
85
86class Bn128 {
87
88 constructor() {
89
90 }
91
92 alloc(length) {
93 while (this.i32[0] & 3) this.i32[0]++; // Return always aligned pointers
94 const res = this.i32[0];
95 this.i32[0] += length;
96 return res;
97 }
98
99 putInt(pos, _a) {
100 const a = bigInt(_a);
101 if (pos & 0x7) throw new Error("Pointer must be aligned");
102 if (a.bitLength > this.n64*64) {
103 return this.putInt(a.mod(this.q));
104 }
105 for (let i=0; i<this.n32; i++) {
106 this.i32[(pos>>2)+i] = a.shiftRight(i*32).and(0xFFFFFFFF).toJSNumber();
107 }
108 }
109
110 getInt(pos) {
111 if (pos & 0x7) throw new Error("Pointer must be aligned");
112 let acc = bigInt(this.i32[(pos>>2)+this.n32-1]);
113 for (let i=this.n32-2; i>=0; i--) {
114 acc = acc.shiftLeft(32);
115 acc = acc.add(this.i32[(pos>>2)+i]);
116 }
117 return acc;
118 }
119
120 allocInt(_a) {
121 const p = this.alloc(this.n8);
122 if (_a) this.putInt(p, _a);
123 return p;
124 }
125
126 putIntF2(pos, a) {
127 this.putInt(pos, a[0]);
128 this.putInt(pos+this.n8, a[1]);
129 }
130
131 getIntF2(pos) {
132 const p = Array(2);
133 p[0] = this.getInt(pos);
134 p[1] = this.getInt(pos+this.n8);
135 return p;
136 }
137
138 allocIntF2(a) {
139 const pP = this.alloc(this.n8*2);
140 if (a) {
141 this.putIntF2(pP, a);
142 }
143 return pP;
144 }
145
146 g1_putPoint(pos, p) {
147 this.putInt(pos, p[0]);
148 this.putInt(pos+this.n8, p[1]);
149 if (p.length == 3) {
150 this.putInt(pos+this.n8*2, p[2]);
151 } else {
152 this.putInt(pos+this.n8*2, 1);
153 }
154 }
155
156 g1_getPoint(pos) {
157 const p = Array(3);
158 p[0] = this.getInt(pos);
159 p[1] = this.getInt(pos+this.n8);
160 p[2] = this.getInt(pos+this.n8*2);
161 return p;
162 }
163
164 g1_allocPoint(p) {
165 const pP = this.alloc(this.n8*3);
166 if (p) {
167 this.g1_putPoint(pP, p);
168 }
169 return pP;
170 }
171
172
173 g2_putPoint(pos, p) {
174 this.putIntF2(pos, p[0]);
175 this.putIntF2(pos+this.n8*2, p[1]);
176 if (p.length == 3) {
177 this.putIntF2(pos+this.n8*4, p[2]);
178 } else {
179 this.putIntF2(pos+this.n8*4, 1);
180 }
181 }
182
183 g2_getPoint(pos) {
184 const p = Array(3);
185 p[0] = this.getIntF2(pos);
186 p[1] = this.getIntF2(pos+this.n8*2);
187 p[2] = this.getIntF2(pos+this.n8*4);
188 return p;
189 }
190
191 g2_allocPoint(p) {
192 const pP = this.alloc(this.n8*6);
193 if (p) {
194 this.g2_putPoint(pP, p);
195 }
196 return pP;
197 }
198
199 putBin(b) {
200 const p = this.alloc(b.byteLength);
201 const s32 = new Uint32Array(b);
202 this.i32.set(s32, p/4);
203 return p;
204 }
205
206 test_AddG1(n) {
207 const start = new Date().getTime();
208
209 const pg = this.g1_allocPoint([bigInt(1), bigInt(2), bigInt(1)]);
210 this.g1_toMontgomery(pg,pg);
211 const p2 = this.g1_allocPoint();
212 this.instance.exports.testAddG1(n, pg, p2);
213 this.g1_fromMontgomery(p2,p2);
214
215 const end = new Date().getTime();
216 const time = end - start;
217
218 return time;
219 }
220
221 test_fft(n) {
222
223 const N=n;
224
225 const p = this.i32[0];
226 for (let i=0; i<N; i++) {
227 this.putInt(p+i*32, i);
228 }
229
230 const start = new Date().getTime();
231 this.fft_ifft(p, N);
232 const end = new Date().getTime();
233 const time = end - start;
234
235 return time;
236 }
237
238}
239
240module.exports = build;