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 */
 63pragma circom 2.0.0;
 64
 65include "mux4.circom";
 66include "escalarmulw4table.circom";
 67include "babyjub.circom";
 68
 69template EscalarMulWindow(base, k) {
 70
 71    signal input in[2];
 72    signal input sel[4];
 73    signal output out[2];
 74
 75    var table[16][2];
 76    component mux;
 77    component adder;
 78
 79    var i;
 80
 81    table = EscalarMulW4Table(base, k);
 82    mux = MultiMux4(2);
 83    adder = BabyAdd();
 84
 85    for (i=0; i<4; i++) {
 86        sel[i] ==> mux.s[i];
 87    }
 88
 89    for (i=0; i<16; i++) {
 90        mux.c[0][i] <== table[i][0];
 91        mux.c[1][i] <== table[i][1];
 92    }
 93
 94    in[0] ==> adder.x1;
 95    in[1] ==> adder.y1;
 96
 97    mux.out[0] ==> adder.x2;
 98    mux.out[1] ==> adder.y2;
 99
100    adder.xout ==> out[0];
101    adder.yout ==> out[1];
102}
103
104/*
105
106
107                ┏━━━━━━━━━┓      ┏━━━━━━━━━┓                            ┏━━━━━━━━━━━━━━━━━━━┓
108                ┃         ┃      ┃         ┃                            ┃                   ┃
109      inp  ════▶┃Window(0)┃═════▶┃Window(1)┃════════  . . . . ═════════▶┃ Window(nBlocks-1) ┃═════▶ out
110                ┃         ┃      ┃         ┃                            ┃                   ┃
111                ┗━━━━━━━━━┛      ┗━━━━━━━━━┛                            ┗━━━━━━━━━━━━━━━━━━━┛
112                  ▲ ▲ ▲ ▲          ▲ ▲ ▲ ▲                                    ▲ ▲ ▲ ▲
113    in[0]─────────┘ │ │ │          │ │ │ │                                    │ │ │ │
114    in[1]───────────┘ │ │          │ │ │ │                                    │ │ │ │
115    in[2]─────────────┘ │          │ │ │ │                                    │ │ 0 0
116    in[3]───────────────┘          │ │ │ │                                    │ │
117    in[4]──────────────────────────┘ │ │ │                                    │ │
118    in[5]────────────────────────────┘ │ │                                    │ │
119    in[6]──────────────────────────────┘ │                                    │ │
120    in[7]────────────────────────────────┘                                    │ │
121        .                                                                     │ │
122        .                                                                     │ │
123  in[n-2]─────────────────────────────────────────────────────────────────────┘ │
124  in[n-1]───────────────────────────────────────────────────────────────────────┘
125
126 */
127
128template EscalarMul(n, base) {
129    signal input in[n];
130    signal input inp[2];   // Point input to be added
131    signal output out[2];
132
133    var nBlocks = ((n-1)>>2)+1;
134    var i;
135    var j;
136
137    component windows[nBlocks];
138
139    // Construct the windows
140    for (i=0; i<nBlocks; i++) {
141      windows[i] = EscalarMulWindow(base, i);
142    }
143
144    // Connect the selectors
145    for (i=0; i<nBlocks; i++) {
146        for (j=0; j<4; j++) {
147            if (i*4+j >= n) {
148                windows[i].sel[j] <== 0;
149            } else {
150                windows[i].sel[j] <== in[i*4+j];
151            }
152        }
153    }
154
155    // Start with generator
156    windows[0].in[0] <== inp[0];
157    windows[0].in[1] <== inp[1];
158
159    for(i=0; i<nBlocks-1; i++) {
160        windows[i].out[0] ==> windows[i+1].in[0];
161        windows[i].out[1] ==> windows[i+1].in[1];
162    }
163
164    windows[nBlocks-1].out[0] ==> out[0];
165    windows[nBlocks-1].out[1] ==> out[1];
166}