circomlib/circuits/escalarmul.circom
circuits/escalarmul.circomRaw
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
20/*
21
22 ┏━━━━━━━━━━━┓
23 ┃ ┃
24 ┃ ┃
25 (inx, iny) ══════════════════════════════════════════▶┃ EC Point ┃
26 ┃ ╠═▶ (outx, outy)
27 ╔══▶┃ Adder ┃
28 ║ ┃ ┃
29 ║ ┃ ┃
30 ║ ┃ ┃
31 ┏━━━━━━━━━━━┓ ┏━━━━━━━━━━━━┓ ║ ┗━━━━━━━━━━━┛
32 ┃ ┃ ┃ ┃ ║
33 ┃ ┃ ┃ ┃ ║
34 ┃ ╠═══(p0x,p0y)═══▶┃ ┃ ║
35 ┃ ╠═══(p1x,p1y)═══▶┃ ┃ ║
36 ┃ ╠═══(p2x,p2y)═══▶┃ ┃ ║
37 ┃ ╠═══(p3x,p3y)═══▶┃ ┃ ║
38 ┃ ╠═══(p4x,p4y)═══▶┃ ┃ ║
39 ┃ ╠═══(p5x,p5y)═══▶┃ ┃ ║
40 ┃ ╠═══(p6x,p6y)═══▶┃ ┃ ║
41 ┃ Constant ╠═══(p7x,p7y)═══▶┃ ┃ ║
42 ┃ Points ┃ ┃ Mux4 ╠══╝
43 ┃ ╠═══(p8x,p8y)═══▶┃ ┃
44 ┃ ╠═══(p9x,p9y)═══▶┃ ┃
45 ┃ ╠══(p10x,p10y)══▶┃ ┃
46 ┃ ╠══(p11x,p11y)══▶┃ ┃
47 ┃ ╠══(p12x,p12y)══▶┃ ┃
48 ┃ ╠══(p13x,p13y)══▶┃ ┃
49 ┃ ╠══(p14x,p14y)══▶┃ ┃
50 ┃ ╠══(p15x,p15y)══▶┃ ┃
51 ┃ ┃ ┃ ┃
52 ┃ ┃ ┃ ┃
53 ┗━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛
54 ▲ ▲ ▲ ▲
55 │ │ │ │
56 s0 ─────────────────────────────────┘ │ │ │
57 s1 ────────────────────────────────────┘ │ │
58 s2 ───────────────────────────────────────┘ │
59 s3 ──────────────────────────────────────────┘
60
61
62 */
63
64include "mux4.circom";
65include "escalarmulw4table.circom";
66include "babyjub.circom";
67
68template EscalarMulWindow(base, k) {
69
70 signal input in[2];
71 signal input sel[4];
72 signal output out[2];
73
74 var table;
75 component mux;
76 component adder;
77
78 var i;
79
80 table = EscalarMulW4Table(base, k);
81 mux = MultiMux4(2);
82 adder = BabyAdd();
83
84 for (i=0; i<4; i++) {
85 sel[i] ==> mux.s[i];
86 }
87
88 for (i=0; i<16; i++) {
89 mux.c[0][i] <== table[i][0];
90 mux.c[1][i] <== table[i][1];
91 }
92
93 in[0] ==> adder.x1;
94 in[1] ==> adder.y1;
95
96 mux.out[0] ==> adder.x2;
97 mux.out[1] ==> adder.y2;
98
99 adder.xout ==> out[0];
100 adder.yout ==> out[1];
101}
102
103/*
104
105
106 ┏━━━━━━━━━┓ ┏━━━━━━━━━┓ ┏━━━━━━━━━━━━━━━━━━━┓
107 ┃ ┃ ┃ ┃ ┃ ┃
108 inp ════▶┃Window(0)┃═════▶┃Window(1)┃════════ . . . . ═════════▶┃ Window(nBlocks-1) ┃═════▶ out
109 ┃ ┃ ┃ ┃ ┃ ┃
110 ┗━━━━━━━━━┛ ┗━━━━━━━━━┛ ┗━━━━━━━━━━━━━━━━━━━┛
111 ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
112 in[0]─────────┘ │ │ │ │ │ │ │ │ │ │ │
113 in[1]───────────┘ │ │ │ │ │ │ │ │ │ │
114 in[2]─────────────┘ │ │ │ │ │ │ │ 0 0
115 in[3]───────────────┘ │ │ │ │ │ │
116 in[4]──────────────────────────┘ │ │ │ │ │
117 in[5]────────────────────────────┘ │ │ │ │
118 in[6]──────────────────────────────┘ │ │ │
119 in[7]────────────────────────────────┘ │ │
120 . │ │
121 . │ │
122 in[n-2]─────────────────────────────────────────────────────────────────────┘ │
123 in[n-1]───────────────────────────────────────────────────────────────────────┘
124
125 */
126
127template EscalarMul(n, base) {
128 signal input in[n];
129 signal input inp[2]; // Point input to be added
130 signal output out[2];
131
132 var nBlocks = ((n-1)>>2)+1;
133 var i;
134 var j;
135
136 component windows[nBlocks];
137
138 // Construct the windows
139 for (i=0; i<nBlocks; i++) {
140 windows[i] = EscalarMulWindow(base, i);
141 }
142
143 // Connect the selectors
144 for (i=0; i<nBlocks; i++) {
145 for (j=0; j<4; j++) {
146 if (i*4+j >= n) {
147 windows[i].sel[j] <== 0;
148 } else {
149 windows[i].sel[j] <== in[i*4+j];
150 }
151 }
152 }
153
154 // Start with generator
155 windows[0].in[0] <== inp[0];
156 windows[0].in[1] <== inp[1];
157
158 for(i=0; i<nBlocks-1; i++) {
159 windows[i].out[0] ==> windows[i+1].in[0];
160 windows[i].out[1] ==> windows[i+1].in[1];
161 }
162
163 windows[nBlocks-1].out[0] ==> out[0];
164 windows[nBlocks-1].out[1] ==> out[1];
165}