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