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