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 "mux3.circom";
 23include "babyjub.circom";
 24
 25template Window4() {
 26    signal input in[4];
 27    signal input base[2];
 28    signal output out[2];
 29    signal output out8[2];   // Returns 8*Base (To be linked)
 30
 31    component mux = MultiMux3(2);
 32
 33    mux.s[0] <== in[0];
 34    mux.s[1] <== in[1];
 35    mux.s[2] <== in[2];
 36
 37    component dbl2 = MontgomeryDouble();
 38    component adr3 = MontgomeryAdd();
 39    component adr4 = MontgomeryAdd();
 40    component adr5 = MontgomeryAdd();
 41    component adr6 = MontgomeryAdd();
 42    component adr7 = MontgomeryAdd();
 43    component adr8 = MontgomeryAdd();
 44
 45// in[0]  -> 1*BASE
 46
 47    mux.c[0][0] <== base[0];
 48    mux.c[1][0] <== base[1];
 49
 50// in[1] -> 2*BASE
 51    dbl2.in[0] <== base[0];
 52    dbl2.in[1] <== base[1];
 53    mux.c[0][1] <== dbl2.out[0];
 54    mux.c[1][1] <== dbl2.out[1];
 55
 56// in[2] -> 3*BASE
 57    adr3.in1[0] <== base[0];
 58    adr3.in1[1] <== base[1];
 59    adr3.in2[0] <== dbl2.out[0];
 60    adr3.in2[1] <== dbl2.out[1];
 61    mux.c[0][2] <== adr3.out[0];
 62    mux.c[1][2] <== adr3.out[1];
 63
 64// in[3] -> 4*BASE
 65    adr4.in1[0] <== base[0];
 66    adr4.in1[1] <== base[1];
 67    adr4.in2[0] <== adr3.out[0];
 68    adr4.in2[1] <== adr3.out[1];
 69    mux.c[0][3] <== adr4.out[0];
 70    mux.c[1][3] <== adr4.out[1];
 71
 72// in[4] -> 5*BASE
 73    adr5.in1[0] <== base[0];
 74    adr5.in1[1] <== base[1];
 75    adr5.in2[0] <== adr4.out[0];
 76    adr5.in2[1] <== adr4.out[1];
 77    mux.c[0][4] <== adr5.out[0];
 78    mux.c[1][4] <== adr5.out[1];
 79
 80// in[5] -> 6*BASE
 81    adr6.in1[0] <== base[0];
 82    adr6.in1[1] <== base[1];
 83    adr6.in2[0] <== adr5.out[0];
 84    adr6.in2[1] <== adr5.out[1];
 85    mux.c[0][5] <== adr6.out[0];
 86    mux.c[1][5] <== adr6.out[1];
 87
 88// in[6] -> 7*BASE
 89    adr7.in1[0] <== base[0];
 90    adr7.in1[1] <== base[1];
 91    adr7.in2[0] <== adr6.out[0];
 92    adr7.in2[1] <== adr6.out[1];
 93    mux.c[0][6] <== adr7.out[0];
 94    mux.c[1][6] <== adr7.out[1];
 95
 96// in[7] -> 8*BASE
 97    adr8.in1[0] <== base[0];
 98    adr8.in1[1] <== base[1];
 99    adr8.in2[0] <== adr7.out[0];
100    adr8.in2[1] <== adr7.out[1];
101    mux.c[0][7] <== adr8.out[0];
102    mux.c[1][7] <== adr8.out[1];
103
104    out8[0] <== adr8.out[0];
105    out8[1] <== adr8.out[1];
106
107    out[0] <== mux.out[0];
108    out[1] <== - mux.out[1]*2*in[3] + mux.out[1];  // Negate y if in[3] is one
109}
110
111
112template Segment(nWindows) {
113    signal input in[nWindows*4];
114    signal input base[2];
115    signal output out[2];
116
117    var i;
118    var j;
119
120    // Convert the base to montgomery
121
122    component e2m = Edwards2Montgomery();
123    e2m.in[0] <== base[0];
124    e2m.in[1] <== base[1];
125
126    component windows[nWindows];
127    component doublers1[nWindows-1];
128    component doublers2[nWindows-1];
129    component adders[nWindows-1];
130    for (i=0; i<nWindows; i++) {
131        windows[i] = Window4();
132        for (j=0; j<4; j++) {
133            windows[i].in[j] <== in[4*i+j];
134        }
135        if (i==0) {
136            windows[i].base[0] <== e2m.out[0];
137            windows[i].base[1] <== e2m.out[1];
138        } else {
139            doublers1[i-1] = MontgomeryDouble();
140            doublers2[i-1] = MontgomeryDouble();
141            doublers1[i-1].in[0] <== windows[i-1].out8[0];
142            doublers1[i-1].in[1] <== windows[i-1].out8[1];
143            doublers2[i-1].in[0] <== doublers1[i-1].out[0];
144            doublers2[i-1].in[1] <== doublers1[i-1].out[1];
145
146            windows[i].base[0] <== doublers2[i-1].out[0];
147            windows[i].base[1] <== doublers2[i-1].out[1];
148
149            adders[i-1] = MontgomeryAdd();
150            if (i==1) {
151                adders[i-1].in1[0] <== windows[0].out[0];
152                adders[i-1].in1[1] <== windows[0].out[1];
153            } else {
154                adders[i-1].in1[0] <== adders[i-2].out[0];
155                adders[i-1].in1[1] <== adders[i-2].out[1];
156            }
157            adders[i-1].in2[0] <== windows[i].out[0];
158            adders[i-1].in2[1] <== windows[i].out[1];
159        }
160    }
161
162    component m2e = Montgomery2Edwards();
163
164    if (nWindows > 1) {
165        m2e.in[0] <== adders[nWindows-2].out[0];
166        m2e.in[1] <== adders[nWindows-2].out[1];
167    } else {
168        m2e.in[0] <== windows[0].out[0];
169        m2e.in[1] <== windows[0].out[1];
170    }
171
172    out[0] <== m2e.out[0];
173    out[1] <== m2e.out[1];
174}
175
176template Pedersen(n) {
177    signal input in[n];
178    signal output out[2];
179
180    var BASE[10][2] = [
181        [10457101036533406547632367118273992217979173478358440826365724437999023779287,19824078218392094440610104313265183977899662750282163392862422243483260492317],
182        [2671756056509184035029146175565761955751135805354291559563293617232983272177,2663205510731142763556352975002641716101654201788071096152948830924149045094],
183        [5802099305472655231388284418920769829666717045250560929368476121199858275951,5980429700218124965372158798884772646841287887664001482443826541541529227896],
184        [7107336197374528537877327281242680114152313102022415488494307685842428166594,2857869773864086953506483169737724679646433914307247183624878062391496185654],
185        [20265828622013100949498132415626198973119240347465898028410217039057588424236,1160461593266035632937973507065134938065359936056410650153315956301179689506],
186        [1487999857809287756929114517587739322941449154962237464737694709326309567994,14017256862867289575056460215526364897734808720610101650676790868051368668003],
187        [14618644331049802168996997831720384953259095788558646464435263343433563860015,13115243279999696210147231297848654998887864576952244320558158620692603342236],
188        [6814338563135591367010655964669793483652536871717891893032616415581401894627,13660303521961041205824633772157003587453809761793065294055279768121314853695],
189        [3571615583211663069428808372184817973703476260057504149923239576077102575715,11981351099832644138306422070127357074117642951423551606012551622164230222506],
190        [18597552580465440374022635246985743886550544261632147935254624835147509493269,6753322320275422086923032033899357299485124665258735666995435957890214041481]
191
192    ];
193
194    var nSegments = ((n-1)\200)+1;
195
196    component segments[nSegments];
197
198    var i;
199    var j;
200    var nBits;
201    var nWindows;
202    for (i=0; i<nSegments; i++) {
203        nBits = (i == (nSegments-1)) ? n - (nSegments-1)*200 : 200;
204        nWindows = ((nBits - 1)\4)+1;
205        segments[i] = Segment(nWindows);
206        segments[i].base[0] <== BASE[i][0];
207        segments[i].base[1] <== BASE[i][1];
208        for (j = 0; j<nBits; j++) {
209            segments[i].in[j] <== in[i*200+j];
210        }
211        // Fill padding bits
212        for (j = nBits; j < nWindows*4; j++) {
213            segments[i].in[j] <== 0;
214        }
215    }
216
217    component adders[nSegments-1];
218
219    for (i=0; i<nSegments-1; i++) {
220        adders[i] = BabyAdd();
221        if (i==0) {
222            adders[i].x1 <== segments[0].out[0];
223            adders[i].y1 <== segments[0].out[1];
224            adders[i].x2 <== segments[1].out[0];
225            adders[i].y2 <== segments[1].out[1];
226        } else {
227            adders[i].x1 <== adders[i-1].xout;
228            adders[i].y1 <== adders[i-1].yout;
229            adders[i].x2 <== segments[i+1].out[0];
230            adders[i].y2 <== segments[i+1].out[1];
231        }
232    }
233
234/*
235    coponent packPoint = PackPoint();
236
237    if (nSegments>1) {
238        packPoint.in[0] <== adders[nSegments-2].xout;
239        packPoint.in[1] <== adders[nSegments-2].yout;
240    } else {
241        packPoint.in[0] <== segments[0].out[0];
242        packPoint.in[1] <== segments[0].out[1];
243    }
244
245    out[0] <== packPoint.out[0];
246    out[1] <== packPoint.out[1];
247*/
248
249    if (nSegments>1) {
250        out[0] <== adders[nSegments-2].xout;
251        out[1] <== adders[nSegments-2].yout;
252    } else {
253        out[0] <== segments[0].out[0];
254        out[1] <== segments[0].out[1];
255    }
256}
257