1
  2include "montgomery.circom";
  3include "babyjub.circom";
  4
  5template Multiplexor2() {
  6    signal input sel;
  7    signal input in[2][2];
  8    signal output out[2];
  9
 10    out[0] <== (in[1][0] - in[0][0])*sel + in[0][0];
 11    out[1] <== (in[1][1] - in[0][1])*sel + in[0][1];
 12}
 13
 14template BitElement() {
 15    signal input sel;
 16    signal input dblIn[2];
 17    signal input addIn[2];
 18    signal output dblOut[2];
 19    signal output addOut[2];
 20
 21    component doubler = MontgomeryDouble();
 22    component adder = MontgomeryAdd();
 23    component selector = Multiplexor2();
 24
 25
 26    sel ==> selector.sel;
 27
 28    dblIn[0] ==> doubler.in[0];
 29    dblIn[1] ==> doubler.in[1];
 30    doubler.out[0] ==> adder.in1[0];
 31    doubler.out[1] ==> adder.in1[1];
 32    addIn[0] ==> adder.in2[0];
 33    addIn[1] ==> adder.in2[1];
 34    addIn[0] ==> selector.in[0][0];
 35    addIn[1] ==> selector.in[0][1];
 36    adder.out[0] ==> selector.in[1][0];
 37    adder.out[1] ==> selector.in[1][1];
 38
 39    doubler.out[0] ==> dblOut[0];
 40    doubler.out[1] ==> dblOut[1];
 41    selector.out[0] ==> addOut[0];
 42    selector.out[1] ==> addOut[1];
 43}
 44
 45// p is montgomery point
 46// n must be <= 248
 47// returns out in twisted edwards
 48// Double is in montgomery to be linked;
 49
 50template Segment(n) {
 51    signal input e[n];
 52    signal input p[2];
 53    signal output out[2];
 54    signal output dbl[2];
 55
 56    component bits[n-1];
 57
 58    component e2m = Edwards2Montgomery();
 59
 60    p[0] ==> e2m.in[0];
 61    p[1] ==> e2m.in[1];
 62
 63    var i;
 64
 65    bits[0] = BitElement();
 66    e2m.out[0] ==> bits[0].dblIn[0]
 67    e2m.out[1] ==> bits[0].dblIn[1]
 68    e2m.out[0] ==> bits[0].addIn[0]
 69    e2m.out[1] ==> bits[0].addIn[1]
 70    e[1] ==> bits[0].sel;
 71
 72    for (i=1; i<n-1; i++) {
 73        bits[i] = BitElement();
 74
 75        bits[i-1].dblOut[0] ==> bits[i].dblIn[0]
 76        bits[i-1].dblOut[1] ==> bits[i].dblIn[1]
 77        bits[i-1].addOut[0] ==> bits[i].addIn[0]
 78        bits[i-1].addOut[1] ==> bits[i].addIn[1]
 79        e[i+1] ==> bits[i].sel;
 80    }
 81
 82    bits[n-2].dblOut[0] ==> dbl[0];
 83    bits[n-2].dblOut[1] ==> dbl[1];
 84
 85    component m2e = Montgomery2Edwards();
 86
 87    bits[n-2].addOut[0] ==> m2e.in[0];
 88    bits[n-2].addOut[1] ==> m2e.in[1];
 89
 90    component eadder = BabyAdd();
 91
 92    m2e.out[0] ==> eadder.x1;
 93    m2e.out[1] ==> eadder.y1;
 94    -p[0] ==> eadder.x2;
 95    p[1] ==> eadder.y2;
 96
 97    component lastSel = Multiplexor2();
 98
 99    e[0] ==> lastSel.sel;
100    eadder.xout ==> lastSel.in[0][0];
101    eadder.yout ==> lastSel.in[0][1];
102    m2e.out[0] ==> lastSel.in[1][0];
103    m2e.out[1] ==> lastSel.in[1][1];
104
105    lastSel.out[0] ==> out[0];
106    lastSel.out[1] ==> out[1];
107}
108
109// This function assumes that p is in the subgroup and it is different to 0
110
111template EscalarMulAny(n) {
112    signal input e[n];              // Input in binary format
113    signal input p[2];              // Point (Twisted format)
114    signal output out[2];           // Point (Twisted format)
115
116    var nsegments = (n-1)\148 +1;
117    var nlastsegment = n - (nsegments-1)*148;
118
119    component segments[nsegments];
120    component doublers[nsegments-1];
121    component m2e[nsegments-1];
122    component adders[nsegments-1];
123
124    var s;
125    var i;
126    var nseg;
127
128    for (s=0; s<nsegments; s++) {
129
130        nseg = (s < nsegments-1) ? 148 : nlastsegment;
131
132        segments[s] = Segment(nseg);
133
134        for (i=0; i<nseg; i++) {
135            e[s*148+i] ==> segments[s].e[i];
136        }
137
138        if (s==0) {
139            p[0] ==> segments[s].p[0];
140            p[1] ==> segments[s].p[1];
141        } else {
142            doublers[s-1] = MontgomeryDouble();
143            m2e[s-1] = Montgomery2Edwards();
144            adders[s-1] = BabyAdd();
145
146            segments[s-1].dbl[0] ==> doublers[s-1].in[0];
147            segments[s-1].dbl[1] ==> doublers[s-1].in[1];
148
149            doublers[s-1].out[0] ==> m2e[s-1].in[0];
150            doublers[s-1].out[1] ==> m2e[s-1].in[1];
151
152            m2e[s-1].out[0] ==> segments[s].p[0];
153            m2e[s-1].out[1] ==> segments[s].p[1];
154
155            if (s==1) {
156                segments[s-1].out[0] ==> adders[s-1].x1;
157                segments[s-1].out[1] ==> adders[s-1].y1;
158            } else {
159                adders[s-2].xout ==> adders[s-1].x1;
160                adders[s-2].yout ==> adders[s-1].y1;
161            }
162            segments[s].out[0] ==> adders[s-1].x2;
163            segments[s].out[1] ==> adders[s-1].y2;
164        }
165    }
166
167    if (nsegments == 1) {
168        segments[0].out[0] ==> out[0];
169        segments[0].out[1] ==> out[1];
170    } else {
171        adders[nsegments-2].xout ==> out[0];
172        adders[nsegments-2].yout ==> out[1];
173    }
174}