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