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