snarkjs/src/setup.js
src/setup.jsRaw
1/*
2 Copyright 2018 0kims association
3
4 This file is part of zksnark javascript library.
5
6 zksnark javascript library is free software: you can redistribute it and/or modify
7 it 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 zksnark javascript library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with zksnark javascript library. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const bigInt = require("./bigint.js");
21
22const BN128 = require("./bn128.js");
23const PolField = require("./polfield.js");
24const ZqField = require("./zqfield.js");
25const RatField = require("./ratfield.js");
26
27const bn128 = new BN128();
28const G1 = bn128.G1;
29const G2 = bn128.G2;
30const PolF = new PolField(new ZqField(bn128.r));
31const RatPolF = new PolField(new RatField(new ZqField(bn128.r)));
32const F = new ZqField(bn128.r);
33
34module.exports = function setup(circuit) {
35 const setup = {
36 vk_proof : {
37 nVars: circuit.nVars,
38 nPublic: circuit.nPubInputs + circuit.nOutputs
39 },
40 vk_verifier: {
41 nPublic: circuit.nPubInputs + circuit.nOutputs
42 },
43 toxic: {}
44 };
45
46 calculatePolynomials(setup, circuit);
47 setup.toxic.t = F.random();
48 calculateEncriptedValuesAtT(setup, circuit);
49 calculateHexps(setup, circuit);
50
51 return setup;
52};
53
54function calculatePolynomials(setup, circuit) {
55 // Calculate the points that must cross each polynomial
56
57/*
58 setup.toxic.aExtra = [];
59 setup.toxic.bExtra = [];
60 setup.toxic.cExtra = [];
61 const aPoints = [];
62 const bPoints = [];
63 const cPoints = [];
64 for (let s = 0; s<circuit.nVars; s++) {
65 aPoints[s] = [];
66 bPoints[s] = [];
67 cPoints[s] = [];
68 for (let c=0; c<circuit.nConstraints; c++) {
69 aPoints[s].push([[bigInt(c), F.one], [circuit.a(c, s), F.one]]);
70 bPoints[s].push([[bigInt(c), F.one], [circuit.b(c, s), F.one]]);
71 cPoints[s].push([[bigInt(c), F.one], [circuit.c(c, s), F.one]]);
72 }
73 // Add an extra point to avoid constant polinolials.
74 setup.toxic.aExtra[s] = F.random();
75 setup.toxic.bExtra[s] = F.random();
76 setup.toxic.cExtra[s] = F.random();
77 aPoints[s].push([[bigInt(circuit.nConstraints), F.one], [setup.toxic.aExtra[s], F.one]]);
78 bPoints[s].push([[bigInt(circuit.nConstraints), F.one], [setup.toxic.bExtra[s], F.one]]);
79 cPoints[s].push([[bigInt(circuit.nConstraints), F.one], [setup.toxic.cExtra[s], F.one]]);
80 }
81
82 // Calculate the polynomials using Lagrange
83 setup.vk_proof.polsA = [];
84 setup.vk_proof.polsB = [];
85 setup.vk_proof.polsC = [];
86 for (let s=0; s<circuit.nVars; s++) {
87// console.log(`Caclcualte Pol ${s}/${circuit.nVars}`);
88 const pA = RatPolF.lagrange( aPoints[s] );
89 const pB = RatPolF.lagrange( bPoints[s] );
90 const pC = RatPolF.lagrange( cPoints[s] );
91
92 setup.vk_proof.polsA.push( unrat(pA) );
93 setup.vk_proof.polsB.push( unrat(pB) );
94 setup.vk_proof.polsC.push( unrat(pC) );
95
96 }
97*/
98
99 setup.toxic.aExtra = [];
100 setup.toxic.bExtra = [];
101 setup.toxic.cExtra = [];
102
103 let allZerosPol = [bigInt(1)];
104
105 for (let c=0; c<=circuit.nConstraints; c++) {
106 allZerosPol = PolF.mul(allZerosPol, [F.neg(bigInt(c)), F.one]);
107 }
108
109 setup.vk_proof.polsA = [];
110 setup.vk_proof.polsB = [];
111 setup.vk_proof.polsC = [];
112 for (let s = 0; s<circuit.nVars; s++) {
113 setup.vk_proof.polsA.push([]);
114 setup.vk_proof.polsB.push([]);
115 setup.vk_proof.polsC.push([]);
116 }
117
118 for (let c=0; c<circuit.nConstraints; c++) {
119 const mpol = PolF.ruffini(allZerosPol, bigInt(c));
120 const normalizer = PolF.F.inverse(PolF.eval(mpol, bigInt(c)));
121 for (let s = 0; s<circuit.nVars; s++) {
122 const factorA = PolF.F.mul(normalizer, circuit.a(c, s));
123 const spolA = PolF.mulScalar(mpol, factorA);
124 setup.vk_proof.polsA[s] = PolF.add(setup.vk_proof.polsA[s], spolA);
125
126 const factorB = PolF.F.mul(normalizer, circuit.b(c, s));
127 const spolB = PolF.mulScalar(mpol, factorB);
128 setup.vk_proof.polsB[s] = PolF.add(setup.vk_proof.polsB[s], spolB);
129
130 const factorC = PolF.F.mul(normalizer, circuit.c(c, s));
131 const spolC = PolF.mulScalar(mpol, factorC);
132 setup.vk_proof.polsC[s] = PolF.add(setup.vk_proof.polsC[s], spolC);
133 }
134 }
135 const mpol = PolF.ruffini(allZerosPol, bigInt(circuit.nConstraints));
136 const normalizer = PolF.F.inverse(PolF.eval(mpol, bigInt(circuit.nConstraints)));
137 for (let s = 0; s<circuit.nVars; s++) {
138 setup.toxic.aExtra[s] = F.random();
139 const factorA = PolF.F.mul(normalizer, setup.toxic.aExtra[s]);
140 const spolA = PolF.mulScalar(mpol, factorA);
141 setup.vk_proof.polsA[s] = PolF.add(setup.vk_proof.polsA[s], spolA);
142
143 setup.toxic.bExtra[s] = F.random();
144 const factorB = PolF.F.mul(normalizer, setup.toxic.bExtra[s]);
145 const spolB = PolF.mulScalar(mpol, factorB);
146 setup.vk_proof.polsB[s] = PolF.add(setup.vk_proof.polsB[s], spolB);
147
148 setup.toxic.cExtra[s] = F.random();
149 const factorC = PolF.F.mul(normalizer, setup.toxic.cExtra[s]);
150 const spolC = PolF.mulScalar(mpol, factorC);
151 setup.vk_proof.polsC[s] = PolF.add(setup.vk_proof.polsC[s], spolC);
152 }
153
154
155
156 // Calculate Z polynomial
157 // Z = 1
158 setup.vk_proof.polZ = [bigInt(1)];
159 for (let c=0; c<circuit.nConstraints; c++) {
160 // Z = Z * (x - p_c)
161 setup.vk_proof.polZ = PolF.mul(
162 setup.vk_proof.polZ,
163 [F.neg(bigInt(c)), bigInt(1)] );
164 }
165}
166
167function calculateEncriptedValuesAtT(setup, circuit) {
168 setup.vk_proof.A = [];
169 setup.vk_proof.B = [];
170 setup.vk_proof.C = [];
171 setup.vk_proof.Ap = [];
172 setup.vk_proof.Bp = [];
173 setup.vk_proof.Cp = [];
174 setup.vk_proof.Kp = [];
175 setup.vk_verifier.A = [];
176
177 setup.toxic.ka = F.random();
178 setup.toxic.kb = F.random();
179 setup.toxic.kc = F.random();
180 setup.toxic.kbeta = F.random();
181 setup.toxic.kgamma = F.random();
182
183 const gb = F.mul(setup.toxic.kbeta, setup.toxic.kgamma);
184
185 setup.vk_verifier.vk_a = G2.affine(G2.mulScalar( G2.g, setup.toxic.ka));
186 setup.vk_verifier.vk_b = G1.affine(G1.mulScalar( G1.g, setup.toxic.kb));
187 setup.vk_verifier.vk_c = G2.affine(G2.mulScalar( G2.g, setup.toxic.kc));
188 setup.vk_verifier.vk_gb_1 = G1.affine(G1.mulScalar( G1.g, gb));
189 setup.vk_verifier.vk_gb_2 = G2.affine(G2.mulScalar( G2.g, gb));
190 setup.vk_verifier.vk_g = G2.affine(G2.mulScalar( G2.g, setup.toxic.kgamma));
191
192 for (let s=0; s<circuit.nVars; s++) {
193
194 // A[i] = G1 * polA(t)
195 const at = F.affine(PolF.eval(setup.vk_proof.polsA[s], setup.toxic.t));
196 const A = G1.affine(G1.mulScalar(G1.g, at));
197
198 setup.vk_proof.A.push(A);
199
200 if (s <= setup.vk_proof.nPublic) {
201 setup.vk_verifier.A.push(A);
202 }
203
204
205 // B1[i] = G1 * polB(t)
206 const bt = F.affine(PolF.eval(setup.vk_proof.polsB[s], setup.toxic.t));
207 const B1 = G1.affine(G1.mulScalar(G1.g, bt));
208
209 // B2[i] = G2 * polB(t)
210 const B2 = G2.affine(G2.mulScalar(G2.g, bt));
211
212 setup.vk_proof.B.push(B2);
213
214 // C[i] = G1 * polC(t)
215 const ct = F.affine(PolF.eval(setup.vk_proof.polsC[s], setup.toxic.t));
216 const C = G1.affine(G1.mulScalar( G1.g, ct));
217 setup.vk_proof.C.push (C);
218
219 // K = G1 * (A+B+C)
220
221 const kt = F.affine(F.add(F.add(at, bt), ct));
222 const K = G1.affine(G1.mulScalar( G1.g, kt));
223
224
225
226 const Ktest = G1.affine(G1.add(G1.add(A, B1), C));
227
228 if (!G1.equals(K, Ktest)) {
229 console.log ("=====FAIL======");
230 }
231
232
233
234 setup.vk_proof.Ap.push(G1.affine(G1.mulScalar(A, setup.toxic.ka)));
235 setup.vk_proof.Bp.push(G1.affine(G1.mulScalar(B1, setup.toxic.kb)));
236 setup.vk_proof.Cp.push(G1.affine(G1.mulScalar(C, setup.toxic.kc)));
237 setup.vk_proof.Kp.push(G1.affine(G1.mulScalar(K, setup.toxic.kbeta)));
238 }
239
240 setup.vk_verifier.vk_z = G2.affine(G2.mulScalar(
241 G2.g,
242 PolF.eval(setup.vk_proof.polZ, setup.toxic.t)));
243}
244
245function calculateHexps(setup, circuit) {
246 let maxA = 0;
247 let maxB = 0;
248 let maxC = 0;
249 for (let s=0; s<circuit.nVars; s++) {
250 maxA = Math.max(maxA, setup.vk_proof.polsA[s].length);
251 maxB = Math.max(maxB, setup.vk_proof.polsB[s].length);
252 maxC = Math.max(maxC, setup.vk_proof.polsC[s].length);
253 }
254
255 let maxFull = Math.max(maxA + maxB - 1, maxC);
256
257 const maxH = maxFull - setup.vk_proof.polZ.length + 1;
258
259 setup.vk_proof.hExps = new Array(maxH);
260 setup.vk_proof.hExps[0] = G1.g;
261 let eT = setup.toxic.t;
262 for (let i=1; i<maxH; i++) {
263 setup.vk_proof.hExps[i] = G1.affine(G1.mulScalar(G1.g, eT));
264 eT = F.mul(eT, setup.toxic.t);
265 }
266}
267/*
268function unrat(p) {
269 const res = new Array(p.length);
270 for (let i=0; i<p.length; i++) {
271 res[i] = RatPolF.F.toF(p[i]);
272 }
273 return res;
274}
275*/