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];
144    component cadders[nWindows];
145    for (i=0; i<nWindows; i++) {
146        windows[i] = WindowMulFix();
147        cadders[i] = MontgomeryAdd();
148        if (i==0) {
149            windows[i].base[0] <== e2m.out[0];
150            windows[i].base[1] <== e2m.out[1];
151            cadders[i].in1[0] <== e2m.out[0];
152            cadders[i].in1[1] <== e2m.out[1];
153        } else {
154            windows[i].base[0] <== windows[i-1].out8[0];
155            windows[i].base[1] <== windows[i-1].out8[1];
156            cadders[i].in1[0] <== cadders[i-1].out[0];
157            cadders[i].in1[1] <== cadders[i-1].out[1];
158        }
159        cadders[i].in2[0] <== windows[i].out8[0];
160        cadders[i].in2[1] <== windows[i].out8[1];
161        for (j=0; j<3; j++) {
162            windows[i].in[j] <== e[3*i+j];
163        }
164    }
165
166    for (i=0; i<nWindows; i++) {
167        adders[i] = MontgomeryAdd();
168        if (i==0) {
169            adders[i].in1[0] <== windows[nWindows-1].out8[0];
170            adders[i].in1[1] <== windows[nWindows-1].out8[1];
171        } else {
172            adders[i].in1[0] <== adders[i-1].out[0];
173            adders[i].in1[1] <== adders[i-1].out[1];
174        }
175        adders[i].in2[0] <== windows[i].out[0];
176        adders[i].in2[1] <== windows[i].out[1];
177    }
178
179    component m2e = Montgomery2Edwards();
180    component cm2e = Montgomery2Edwards();
181
182    m2e.in[0] <== adders[nWindows-1].out[0];
183    m2e.in[1] <== adders[nWindows-1].out[1];
184    cm2e.in[0] <== cadders[nWindows-1].out[0];
185    cm2e.in[1] <== cadders[nWindows-1].out[1];
186
187    component cAdd = BabyAdd();
188    cAdd.x1 <== m2e.out[0];
189    cAdd.y1 <== m2e.out[1];
190    cAdd.x2 <== -cm2e.out[0];
191    cAdd.y2 <== cm2e.out[1];
192
193    cAdd.xout ==> out[0];
194    cAdd.yout ==> out[1];
195
196    windows[nWindows-1].out8[0] ==> dbl[0];
197    windows[nWindows-1].out8[1] ==> dbl[1];
198}
199
200
201/*
202This component multiplies a escalar times a fixed point BASE (twisted edwards format)
203    Signals
204        e: The escalar in binary format
205        out: The output point in twisted edwards
206 */
207template EscalarMulFix(n, BASE) {
208    signal input e[n];              // Input in binary format
209    signal output out[2];           // Point (Twisted format)
210
211    var nsegments = (n-1)\246 +1;       // 249 probably would work. But I'm not sure and for security I keep 246
212    var nlastsegment = n - (nsegments-1)*249;
213
214    component segments[nsegments];
215
216    component m2e[nsegments-1];
217    component adders[nsegments-1];
218
219    var s;
220    var i;
221    var nseg;
222    var nWindows
223
224    for (s=0; s<nsegments; s++) {
225
226        nseg = (s < nsegments-1) ? 249 : nlastsegment;
227        nWindows = ((nseg - 1)\3)+1;
228
229        segments[s] = SegmentMulFix(nWindows);
230
231        for (i=0; i<nseg; i++) {
232            segments[s].e[i] <== e[s*249+i];
233        }
234
235        for (i = nseg; i<nWindows*3; i++) {
236            segments[s].e[i] <== 0;
237        }
238
239        if (s==0) {
240            segments[s].base[0] <== BASE[0];
241            segments[s].base[1] <== BASE[1];
242        } else {
243            m2e[s-1] = Montgomery2Edwards();
244            adders[s-1] = BabyAdd();
245
246            segments[s-1].dbl[0] ==> m2e[s-1].in[0];
247            segments[s-1].dbl[1] ==> m2e[s-1].in[1];
248
249            m2e[s-1].out[0] ==> segments[s].base[0];
250            m2e[s-1].out[1] ==> segments[s].base[1];
251
252            if (s==1) {
253                segments[s-1].out[0] ==> adders[s-1].x1;
254                segments[s-1].out[1] ==> adders[s-1].y1;
255            } else {
256                adders[s-2].xout ==> adders[s-1].x1;
257                adders[s-2].yout ==> adders[s-1].y1;
258            }
259            segments[s].out[0] ==> adders[s-1].x2;
260            segments[s].out[1] ==> adders[s-1].y2;
261        }
262    }
263
264    if (nsegments == 1) {
265        segments[0].out[0] ==> out[0];
266        segments[0].out[1] ==> out[1];
267    } else {
268        adders[nsegments-2].xout ==> out[0];
269        adders[nsegments-2].yout ==> out[1];
270    }
271}