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 */
31template WindowMulFix() {
32 signal input in[3];
33 signal input base[2];
34 signal output out[2];
35 signal output out8[2]; // Returns 8*Base (To be linked)
36
37 component mux = MultiMux3(2);
38
39 mux.s[0] <== in[0];
40 mux.s[1] <== in[1];
41 mux.s[2] <== in[2];
42
43 component dbl2 = MontgomeryDouble();
44 component adr3 = MontgomeryAdd();
45 component adr4 = MontgomeryAdd();
46 component adr5 = MontgomeryAdd();
47 component adr6 = MontgomeryAdd();
48 component adr7 = MontgomeryAdd();
49 component adr8 = MontgomeryAdd();
50
51// in[0] -> 1*BASE
52
53 mux.c[0][0] <== base[0];
54 mux.c[1][0] <== base[1];
55
56// in[1] -> 2*BASE
57 dbl2.in[0] <== base[0];
58 dbl2.in[1] <== base[1];
59 mux.c[0][1] <== dbl2.out[0];
60 mux.c[1][1] <== dbl2.out[1];
61
62// in[2] -> 3*BASE
63 adr3.in1[0] <== base[0];
64 adr3.in1[1] <== base[1];
65 adr3.in2[0] <== dbl2.out[0];
66 adr3.in2[1] <== dbl2.out[1];
67 mux.c[0][2] <== adr3.out[0];
68 mux.c[1][2] <== adr3.out[1];
69
70// in[3] -> 4*BASE
71 adr4.in1[0] <== base[0];
72 adr4.in1[1] <== base[1];
73 adr4.in2[0] <== adr3.out[0];
74 adr4.in2[1] <== adr3.out[1];
75 mux.c[0][3] <== adr4.out[0];
76 mux.c[1][3] <== adr4.out[1];
77
78// in[4] -> 5*BASE
79 adr5.in1[0] <== base[0];
80 adr5.in1[1] <== base[1];
81 adr5.in2[0] <== adr4.out[0];
82 adr5.in2[1] <== adr4.out[1];
83 mux.c[0][4] <== adr5.out[0];
84 mux.c[1][4] <== adr5.out[1];
85
86// in[5] -> 6*BASE
87 adr6.in1[0] <== base[0];
88 adr6.in1[1] <== base[1];
89 adr6.in2[0] <== adr5.out[0];
90 adr6.in2[1] <== adr5.out[1];
91 mux.c[0][5] <== adr6.out[0];
92 mux.c[1][5] <== adr6.out[1];
93
94// in[6] -> 7*BASE
95 adr7.in1[0] <== base[0];
96 adr7.in1[1] <== base[1];
97 adr7.in2[0] <== adr6.out[0];
98 adr7.in2[1] <== adr6.out[1];
99 mux.c[0][6] <== adr7.out[0];
100 mux.c[1][6] <== adr7.out[1];
101
102// in[7] -> 8*BASE
103 adr8.in1[0] <== base[0];
104 adr8.in1[1] <== base[1];
105 adr8.in2[0] <== adr7.out[0];
106 adr8.in2[1] <== adr7.out[1];
107 mux.c[0][7] <== adr8.out[0];
108 mux.c[1][7] <== adr8.out[1];
109
110 out8[0] <== adr8.out[0];
111 out8[1] <== adr8.out[1];
112
113 out[0] <== mux.out[0];
114 out[1] <== mux.out[1];
115}
116
117
118/*
119 This component does a multiplication of a escalar times a fix base
120 Signals:
121 e: The scalar in bits
122 base: the base point in edwards format
123 out: The result
124 dbl: Point in Edwards to be linked to the next segment.
125 */
126
127template SegmentMulFix(nWindows) {
128 signal input e[nWindows*3];
129 signal input base[2];
130 signal output out[2];
131 signal output dbl[2];
132
133 var i;
134 var j;
135
136 // Convert the base to montgomery
137
138 component e2m = Edwards2Montgomery();
139 e2m.in[0] <== base[0];
140 e2m.in[1] <== base[1];
141
142 component windows[nWindows];
143 component adders[nWindows-1];
144 component cadders[nWindows-1];
145 for (i=0; i<nWindows; i++) {
146 windows[i] = WindowMulFix();
147 if (i==0) {
148 windows[i].base[0] <== e2m.out[0];
149 windows[i].base[1] <== e2m.out[1];
150 } else {
151 windows[i].base[0] <== windows[i-1].out8[0];
152 windows[i].base[1] <== windows[i-1].out8[1];
153
154 adders[i-1] = MontgomeryAdd();
155 cadders[i-1] = MontgomeryAdd();
156 if (i==1) {
157 adders[i-1].in1[0] <== windows[0].out[0];
158 adders[i-1].in1[1] <== windows[0].out[1];
159 cadders[i-1].in1[0] <== e2m.out[0];
160 cadders[i-1].in1[1] <== e2m.out[1];
161 } else {
162 adders[i-1].in1[0] <== adders[i-2].out[0];
163 adders[i-1].in1[1] <== adders[i-2].out[1];
164 cadders[i-1].in1[0] <== cadders[i-2].out[0];
165 cadders[i-1].in1[1] <== cadders[i-2].out[1];
166 }
167 adders[i-1].in2[0] <== windows[i].out[0];
168 adders[i-1].in2[1] <== windows[i].out[1];
169 cadders[i-1].in2[0] <== windows[i-1].out8[0];
170 cadders[i-1].in2[1] <== windows[i-1].out8[1];
171 }
172 for (j=0; j<3; j++) {
173 windows[i].in[j] <== e[3*i+j];
174 }
175 }
176
177 component m2e = Montgomery2Edwards();
178 component cm2e = Montgomery2Edwards();
179
180 if (nWindows > 1) {
181 m2e.in[0] <== adders[nWindows-2].out[0];
182 m2e.in[1] <== adders[nWindows-2].out[1];
183 cm2e.in[0] <== cadders[nWindows-2].out[0];
184 cm2e.in[1] <== cadders[nWindows-2].out[1];
185 } else {
186 m2e.in[0] <== windows[0].out[0];
187 m2e.in[1] <== windows[0].out[1];
188 cm2e.in[0] <== e2m.out[0];
189 cm2e.in[1] <== e2m.out[1];
190 }
191
192 component cAdd = BabyAdd();
193 cAdd.x1 <== m2e.out[0];
194 cAdd.y1 <== m2e.out[1];
195 cAdd.x2 <== -cm2e.out[0];
196 cAdd.y2 <== cm2e.out[1];
197
198
199 cAdd.xout ==> out[0];
200 cAdd.yout ==> out[1];
201
202 windows[nWindows-1].out8[0] ==> dbl[0];
203 windows[nWindows-1].out8[1] ==> dbl[1];
204}
205
206
207/*
208This component multiplies a escalar times a fixed point BASE (twisted edwards format)
209 Signals
210 e: The escalar in binary format
211 out: The output point in twisted edwards
212 */
213template EscalarMulFix(n, BASE) {
214 signal input e[n]; // Input in binary format
215 signal output out[2]; // Point (Twisted format)
216
217 var nsegments = (n-1)\249 +1;
218 var nlastsegment = n - (nsegments-1)*249;
219
220 component segments[nsegments];
221
222 component m2e[nsegments-1];
223 component adders[nsegments-1];
224
225 var s;
226 var i;
227 var nseg;
228 var nWindows
229
230 for (s=0; s<nsegments; s++) {
231
232 nseg = (s < nsegments-1) ? 249 : nlastsegment;
233 nWindows = ((nseg - 1)\3)+1;
234
235 segments[s] = SegmentMulFix(nWindows);
236
237 for (i=0; i<nseg; i++) {
238 segments[s].e[i] <== e[s*249+i];
239 }
240
241 for (i = nseg; i<nWindows*3; i++) {
242 segments[s].e[i] <== 0;
243 }
244
245 if (s==0) {
246 segments[s].base[0] <== BASE[0];
247 segments[s].base[1] <== BASE[1];
248 } else {
249 m2e[s-1] = Montgomery2Edwards();
250 adders[s-1] = BabyAdd();
251
252 segments[s-1].dbl[0] ==> m2e[s-1].in[0];
253 segments[s-1].dbl[1] ==> m2e[s-1].in[1];
254
255 m2e[s-1].out[0] ==> segments[s].base[0];
256 m2e[s-1].out[1] ==> segments[s].base[1];
257
258 if (s==1) {
259 segments[s-1].out[0] ==> adders[s-1].x1;
260 segments[s-1].out[1] ==> adders[s-1].y1;
261 } else {
262 adders[s-2].xout ==> adders[s-1].x1;
263 adders[s-2].yout ==> adders[s-1].y1;
264 }
265 segments[s].out[0] ==> adders[s-1].x2;
266 segments[s].out[1] ==> adders[s-1].y2;
267 }
268 }
269
270 if (nsegments == 1) {
271 segments[0].out[0] ==> out[0];
272 segments[0].out[1] ==> out[1];
273 } else {
274 adders[nsegments-2].xout ==> out[0];
275 adders[nsegments-2].yout ==> out[1];
276 }
277}