circomlib/circuits/escalarmulfix.circom
circuits/escalarmulfix.circomRaw
1/*
2 Copyright 2018 0KIMS association.
3
4 This file is part of circom (Zero Knowledge Circuit Compiler).
5
6 circom 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 circom 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 circom. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20include "mux3.circom";
21include "montgomery.circom";
22include "babyjub.circom";
23
24/*
25 Window of 3 elements, it calculates
26 out = base + base*in[0] + 2*base*in[1] + 4*base*in[2]
27 out4 = 4*base
28
29 The result should be compensated.
30 */
31
32/*
33
34 The scalar is s = a0 + a1*2^3 + a2*2^6 + ...... + a81*2^243
35 First We calculate Q = B + 2^3*B + 2^6*B + ......... + 2^246*B
36
37 Then we calculate S1 = 2*2^246*B + (1 + a0)*B + (2^3 + a1)*B + .....+ (2^243 + a81)*B
38
39 And Finaly we compute the result: RES = SQ - Q
40
41 As you can see the input of the adders cannot be equal nor zero, except for the last
42 substraction that it's done in montgomery.
43
44 A good way to see it is that the accumulator input of the adder >= 2^247*B and the other input
45 is the output of the windows that it's going to be <= 2^246*B
46 */
47template WindowMulFix() {
48 signal input in[3];
49 signal input base[2];
50 signal output out[2];
51 signal output out8[2]; // Returns 8*Base (To be linked)
52
53 component mux = MultiMux3(2);
54
55 mux.s[0] <== in[0];
56 mux.s[1] <== in[1];
57 mux.s[2] <== in[2];
58
59 component dbl2 = MontgomeryDouble();
60 component adr3 = MontgomeryAdd();
61 component adr4 = MontgomeryAdd();
62 component adr5 = MontgomeryAdd();
63 component adr6 = MontgomeryAdd();
64 component adr7 = MontgomeryAdd();
65 component adr8 = MontgomeryAdd();
66
67// in[0] -> 1*BASE
68
69 mux.c[0][0] <== base[0];
70 mux.c[1][0] <== base[1];
71
72// in[1] -> 2*BASE
73 dbl2.in[0] <== base[0];
74 dbl2.in[1] <== base[1];
75 mux.c[0][1] <== dbl2.out[0];
76 mux.c[1][1] <== dbl2.out[1];
77
78// in[2] -> 3*BASE
79 adr3.in1[0] <== base[0];
80 adr3.in1[1] <== base[1];
81 adr3.in2[0] <== dbl2.out[0];
82 adr3.in2[1] <== dbl2.out[1];
83 mux.c[0][2] <== adr3.out[0];
84 mux.c[1][2] <== adr3.out[1];
85
86// in[3] -> 4*BASE
87 adr4.in1[0] <== base[0];
88 adr4.in1[1] <== base[1];
89 adr4.in2[0] <== adr3.out[0];
90 adr4.in2[1] <== adr3.out[1];
91 mux.c[0][3] <== adr4.out[0];
92 mux.c[1][3] <== adr4.out[1];
93
94// in[4] -> 5*BASE
95 adr5.in1[0] <== base[0];
96 adr5.in1[1] <== base[1];
97 adr5.in2[0] <== adr4.out[0];
98 adr5.in2[1] <== adr4.out[1];
99 mux.c[0][4] <== adr5.out[0];
100 mux.c[1][4] <== adr5.out[1];
101
102// in[5] -> 6*BASE
103 adr6.in1[0] <== base[0];
104 adr6.in1[1] <== base[1];
105 adr6.in2[0] <== adr5.out[0];
106 adr6.in2[1] <== adr5.out[1];
107 mux.c[0][5] <== adr6.out[0];
108 mux.c[1][5] <== adr6.out[1];
109
110// in[6] -> 7*BASE
111 adr7.in1[0] <== base[0];
112 adr7.in1[1] <== base[1];
113 adr7.in2[0] <== adr6.out[0];
114 adr7.in2[1] <== adr6.out[1];
115 mux.c[0][6] <== adr7.out[0];
116 mux.c[1][6] <== adr7.out[1];
117
118// in[7] -> 8*BASE
119 adr8.in1[0] <== base[0];
120 adr8.in1[1] <== base[1];
121 adr8.in2[0] <== adr7.out[0];
122 adr8.in2[1] <== adr7.out[1];
123 mux.c[0][7] <== adr8.out[0];
124 mux.c[1][7] <== adr8.out[1];
125
126 out8[0] <== adr8.out[0];
127 out8[1] <== adr8.out[1];
128
129 out[0] <== mux.out[0];
130 out[1] <== mux.out[1];
131}
132
133
134/*
135 This component does a multiplication of a escalar times a fix base
136 Signals:
137 e: The scalar in bits
138 base: the base point in edwards format
139 out: The result
140 dbl: Point in Edwards to be linked to the next segment.
141 */
142
143template SegmentMulFix(nWindows) {
144 signal input e[nWindows*3];
145 signal input base[2];
146 signal output out[2];
147 signal output dbl[2];
148
149 var i;
150 var j;
151
152 // Convert the base to montgomery
153
154 component e2m = Edwards2Montgomery();
155 e2m.in[0] <== base[0];
156 e2m.in[1] <== base[1];
157
158 component windows[nWindows];
159 component adders[nWindows];
160 component cadders[nWindows];
161
162 // In the last step we add an extra doubler so that numbers do not match.
163 component dblLast = MontgomeryDouble();
164
165 for (i=0; i<nWindows; i++) {
166 windows[i] = WindowMulFix();
167 cadders[i] = MontgomeryAdd();
168 if (i==0) {
169 windows[i].base[0] <== e2m.out[0];
170 windows[i].base[1] <== e2m.out[1];
171 cadders[i].in1[0] <== e2m.out[0];
172 cadders[i].in1[1] <== e2m.out[1];
173 } else {
174 windows[i].base[0] <== windows[i-1].out8[0];
175 windows[i].base[1] <== windows[i-1].out8[1];
176 cadders[i].in1[0] <== cadders[i-1].out[0];
177 cadders[i].in1[1] <== cadders[i-1].out[1];
178 }
179 for (j=0; j<3; j++) {
180 windows[i].in[j] <== e[3*i+j];
181 }
182 if (i<nWindows-1) {
183 cadders[i].in2[0] <== windows[i].out8[0];
184 cadders[i].in2[1] <== windows[i].out8[1];
185 } else {
186 dblLast.in[0] <== windows[i].out8[0];
187 dblLast.in[1] <== windows[i].out8[1];
188 cadders[i].in2[0] <== dblLast.out[0];
189 cadders[i].in2[1] <== dblLast.out[1];
190 }
191 }
192
193 for (i=0; i<nWindows; i++) {
194 adders[i] = MontgomeryAdd();
195 if (i==0) {
196 adders[i].in1[0] <== dblLast.out[0];
197 adders[i].in1[1] <== dblLast.out[1];
198 } else {
199 adders[i].in1[0] <== adders[i-1].out[0];
200 adders[i].in1[1] <== adders[i-1].out[1];
201 }
202 adders[i].in2[0] <== windows[i].out[0];
203 adders[i].in2[1] <== windows[i].out[1];
204 }
205
206 component m2e = Montgomery2Edwards();
207 component cm2e = Montgomery2Edwards();
208
209 m2e.in[0] <== adders[nWindows-1].out[0];
210 m2e.in[1] <== adders[nWindows-1].out[1];
211 cm2e.in[0] <== cadders[nWindows-1].out[0];
212 cm2e.in[1] <== cadders[nWindows-1].out[1];
213
214 component cAdd = BabyAdd();
215 cAdd.x1 <== m2e.out[0];
216 cAdd.y1 <== m2e.out[1];
217 cAdd.x2 <== -cm2e.out[0];
218 cAdd.y2 <== cm2e.out[1];
219
220 cAdd.xout ==> out[0];
221 cAdd.yout ==> out[1];
222
223 windows[nWindows-1].out8[0] ==> dbl[0];
224 windows[nWindows-1].out8[1] ==> dbl[1];
225}
226
227
228/*
229This component multiplies a escalar times a fixed point BASE (twisted edwards format)
230 Signals
231 e: The escalar in binary format
232 out: The output point in twisted edwards
233 */
234template EscalarMulFix(n, BASE) {
235 signal input e[n]; // Input in binary format
236 signal output out[2]; // Point (Twisted format)
237
238 var nsegments = (n-1)\246 +1; // 249 probably would work. But I'm not sure and for security I keep 246
239 var nlastsegment = n - (nsegments-1)*249;
240
241 component segments[nsegments];
242
243 component m2e[nsegments-1];
244 component adders[nsegments-1];
245
246 var s;
247 var i;
248 var nseg;
249 var nWindows;
250
251 for (s=0; s<nsegments; s++) {
252
253 nseg = (s < nsegments-1) ? 249 : nlastsegment;
254 nWindows = ((nseg - 1)\3)+1;
255
256 segments[s] = SegmentMulFix(nWindows);
257
258 for (i=0; i<nseg; i++) {
259 segments[s].e[i] <== e[s*249+i];
260 }
261
262 for (i = nseg; i<nWindows*3; i++) {
263 segments[s].e[i] <== 0;
264 }
265
266 if (s==0) {
267 segments[s].base[0] <== BASE[0];
268 segments[s].base[1] <== BASE[1];
269 } else {
270 m2e[s-1] = Montgomery2Edwards();
271 adders[s-1] = BabyAdd();
272
273 segments[s-1].dbl[0] ==> m2e[s-1].in[0];
274 segments[s-1].dbl[1] ==> m2e[s-1].in[1];
275
276 m2e[s-1].out[0] ==> segments[s].base[0];
277 m2e[s-1].out[1] ==> segments[s].base[1];
278
279 if (s==1) {
280 segments[s-1].out[0] ==> adders[s-1].x1;
281 segments[s-1].out[1] ==> adders[s-1].y1;
282 } else {
283 adders[s-2].xout ==> adders[s-1].x1;
284 adders[s-2].yout ==> adders[s-1].y1;
285 }
286 segments[s].out[0] ==> adders[s-1].x2;
287 segments[s].out[1] ==> adders[s-1].y2;
288 }
289 }
290
291 if (nsegments == 1) {
292 segments[0].out[0] ==> out[0];
293 segments[0].out[1] ==> out[1];
294 } else {
295 adders[nsegments-2].xout ==> out[0];
296 adders[nsegments-2].yout ==> out[1];
297 }
298}