snarkjs/src/prover.js
src/prover.jsRaw
1/*
2 Copyright 2018 0kims association.
3
4 This file is part of snarkjs.
5
6 snarkjs is a free software: you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as published by the
8 Free Software Foundation, either version 3 of the License, or (at your option)
9 any later version.
10
11 snarkjs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 more details.
15
16 You should have received a copy of the GNU General Public License along with
17 snarkjs. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const BN128 = require("./bn128.js");
21const PolField = require("./polfield.js");
22const ZqField = require("./zqfield.js");
23
24const bn128 = new BN128();
25const PolF = new PolField(new ZqField(bn128.r));
26const G1 = bn128.G1;
27const G2 = bn128.G2;
28
29module.exports = function genProof(vk_proof, witness) {
30
31 const proof = {};
32
33
34 const d1 = PolF.F.random();
35 const d2 = PolF.F.random();
36 const d3 = PolF.F.random();
37
38 proof.pi_a = G1.zero;
39 proof.pi_ap = G1.zero;
40 proof.pi_b = G2.zero;
41 proof.pi_bp = G1.zero;
42 proof.pi_c = G1.zero;
43 proof.pi_cp = G1.zero;
44 proof.pi_kp = G1.zero;
45 proof.pi_h = G1.zero;
46
47
48 // Skip public entries and the "1" signal that are forced by the verifier
49 for (let s= vk_proof.nPublic+1; s< vk_proof.nVars; s++) {
50
51 // pi_a = pi_a + A[s] * witness[s];
52 proof.pi_a = G1.add( proof.pi_a, G1.mulScalar( vk_proof.A[s], witness[s]));
53
54 // pi_ap = pi_ap + Ap[s] * witness[s];
55 proof.pi_ap = G1.add( proof.pi_ap, G1.mulScalar( vk_proof.Ap[s], witness[s]));
56 }
57
58 for (let s= 0; s< vk_proof.nVars; s++) {
59 // pi_a = pi_a + A[s] * witness[s];
60 proof.pi_b = G2.add( proof.pi_b, G2.mulScalar( vk_proof.B[s], witness[s]));
61
62 // pi_ap = pi_ap + Ap[s] * witness[s];
63 proof.pi_bp = G1.add( proof.pi_bp, G1.mulScalar( vk_proof.Bp[s], witness[s]));
64
65 // pi_a = pi_a + A[s] * witness[s];
66 proof.pi_c = G1.add( proof.pi_c, G1.mulScalar( vk_proof.C[s], witness[s]));
67
68 // pi_ap = pi_ap + Ap[s] * witness[s];
69 proof.pi_cp = G1.add( proof.pi_cp, G1.mulScalar( vk_proof.Cp[s], witness[s]));
70
71 // pi_ap = pi_ap + Ap[s] * witness[s];
72 proof.pi_kp = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[s], witness[s]));
73 }
74
75 proof.pi_a = G1.add( proof.pi_a, G1.mulScalar( vk_proof.A[vk_proof.nVars], d1));
76 proof.pi_ap = G1.add( proof.pi_ap, G1.mulScalar( vk_proof.Ap[vk_proof.nVars], d1));
77
78 proof.pi_b = G2.add( proof.pi_b, G2.mulScalar( vk_proof.B[vk_proof.nVars], d2));
79 proof.pi_bp = G1.add( proof.pi_bp, G1.mulScalar( vk_proof.Bp[vk_proof.nVars], d2));
80
81 proof.pi_c = G1.add( proof.pi_c, G1.mulScalar( vk_proof.C[vk_proof.nVars], d3));
82 proof.pi_cp = G1.add( proof.pi_cp, G1.mulScalar( vk_proof.Cp[vk_proof.nVars], d3));
83
84 proof.pi_kp = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[vk_proof.nVars ], d1));
85 proof.pi_kp = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[vk_proof.nVars+1], d2));
86 proof.pi_kp = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[vk_proof.nVars+2], d3));
87
88/*
89 let polA = [];
90 let polB = [];
91 let polC = [];
92
93 for (let s= 0; s< vk_proof.nVars; s++) {
94 polA = PolF.add(
95 polA,
96 PolF.mul(
97 vk_proof.polsA[s],
98 [witness[s]] ));
99
100 polB = PolF.add(
101 polB,
102 PolF.mul(
103 vk_proof.polsB[s],
104 [witness[s]] ));
105
106 polC = PolF.add(
107 polC,
108 PolF.mul(
109 vk_proof.polsC[s],
110 [witness[s]] ));
111 }
112
113
114 let polFull = PolF.sub(PolF.mul( polA, polB), polC);
115
116 const h = PolF.div(polFull, vk_proof.polZ );
117*/
118
119 const h = calculateH(vk_proof, witness, d1, d2, d3);
120
121// console.log(h.length + "/" + vk_proof.hExps.length);
122
123 for (let i = 0; i < h.length; i++) {
124 proof.pi_h = G1.add( proof.pi_h, G1.mulScalar( vk_proof.hExps[i], h[i]));
125 }
126
127 proof.pi_a = G1.affine(proof.pi_a);
128 proof.pi_b = G2.affine(proof.pi_b);
129 proof.pi_c = G1.affine(proof.pi_c);
130 proof.pi_ap = G1.affine(proof.pi_ap);
131 proof.pi_bp = G1.affine(proof.pi_bp);
132 proof.pi_cp = G1.affine(proof.pi_cp);
133 proof.pi_kp = G1.affine(proof.pi_kp);
134 proof.pi_h = G1.affine(proof.pi_h);
135
136// proof.h=h;
137
138 const publicSignals = witness.slice(1, vk_proof.nPublic+1);
139
140 return {proof, publicSignals};
141};
142
143
144function calculateH(vk_proof, witness, d1, d2, d3) {
145
146 const F = PolF.F;
147 const m = vk_proof.domainSize;
148 const polA_T = new Array(m).fill(PolF.F.zero);
149 const polB_T = new Array(m).fill(PolF.F.zero);
150 const polC_T = new Array(m).fill(PolF.F.zero);
151
152 for (let s=0; s<vk_proof.nVars; s++) {
153 for (let c in vk_proof.polsA[s]) {
154 polA_T[c] = F.add(polA_T[c], F.mul(witness[s], vk_proof.polsA[s][c]));
155 }
156 for (let c in vk_proof.polsB[s]) {
157 polB_T[c] = F.add(polB_T[c], F.mul(witness[s], vk_proof.polsB[s][c]));
158 }
159 for (let c in vk_proof.polsC[s]) {
160 polC_T[c] = F.add(polC_T[c], F.mul(witness[s], vk_proof.polsC[s][c]));
161 }
162 }
163
164 const polA_S = PolF.ifft(polA_T);
165 const polB_S = PolF.ifft(polB_T);
166
167 const polAB_S = PolF.mul(polA_S, polB_S);
168
169 const polC_S = PolF.ifft(polC_T);
170
171 const polABC_S = PolF.sub(polAB_S, polC_S);
172
173 const polZ_S = new Array(m+1).fill(F.zero);
174 polZ_S[m] = F.one;
175 polZ_S[0] = F.neg(F.one);
176
177 let H_S = PolF.div(polABC_S, polZ_S);
178/*
179 const H2S = PolF.mul(H_S, polZ_S);
180
181 if (PolF.equals(H2S, polABC_S)) {
182 console.log("Is Divisible!");
183 } else {
184 console.log("ERROR: Not divisible!");
185 }
186*/
187
188 /* add coefficients of the polynomial (d2*A + d1*B - d3) + d1*d2*Z */
189
190 H_S = PolF.extend(H_S, m+1);
191
192 for (let i=0; i<m; i++) {
193 const d2A = PolF.F.mul(d2, polA_S[i]);
194 const d1B = PolF.F.mul(d1, polB_S[i]);
195 H_S[i] = PolF.F.add(H_S[i], PolF.F.add(d2A, d1B));
196 }
197
198 H_S[0] = PolF.F.sub(H_S[0], d3);
199
200 // Z = x^m -1
201 const d1d2 = PolF.F.mul(d1, d2);
202 H_S[m] = PolF.F.add(H_S[m], d1d2);
203 H_S[0] = PolF.F.sub(H_S[0], d1d2);
204
205 H_S = PolF.reduce(PolF.affine(H_S));
206
207 return H_S;
208}