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