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