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