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    Source: https://en.wikipedia.org/wiki/Montgomery_curve
 22
 23                1 + y       1 + y
 24    [u, v] = [ -------  , ---------- ]
 25                1 - y      (1 - y)x
 26
 27 */
 28 pragma circom 2.0.0;
 29
 30template Edwards2Montgomery() {
 31    signal input in[2];
 32    signal output out[2];
 33
 34    out[0] <-- (1 + in[1]) / (1 - in[1]);
 35    out[1] <-- out[0] / in[0];
 36
 37
 38    out[0] * (1-in[1]) === (1 + in[1]);
 39    out[1] * in[0] === out[0];
 40}
 41
 42/*
 43
 44                u    u - 1
 45    [x, y] = [ ---, ------- ]
 46                v    u + 1
 47
 48 */
 49template Montgomery2Edwards() {
 50    signal input in[2];
 51    signal output out[2];
 52
 53    out[0] <-- in[0] / in[1];
 54    out[1] <-- (in[0] - 1) / (in[0] + 1);
 55
 56    out[0] * in[1] === in[0];
 57    out[1] * (in[0] + 1) === in[0] - 1;
 58}
 59
 60
 61/*
 62             x2 - x1
 63    lamda = ---------
 64             y2 - y1
 65
 66                                                    x3 + A + x1 + x2
 67    x3 = B * lamda^2 - A - x1 -x2    =>  lamda^2 = ------------------
 68                                                         B
 69
 70    y3 = (2*x1 + x2 + A)*lamda - B*lamda^3 - y1  =>
 71
 72
 73    =>  y3 = lamda * ( 2*x1 + x2 + A  - x3 - A - x1 - x2)  - y1 =>
 74
 75    =>  y3 = lamda * ( x1 - x3 ) - y1
 76
 77----------
 78
 79             y2 - y1
 80    lamda = ---------
 81             x2 - x1
 82
 83    x3 = B * lamda^2 - A - x1 -x2
 84
 85    y3 = lamda * ( x1 - x3 ) - y1
 86
 87 */
 88
 89template MontgomeryAdd() {
 90    signal input in1[2];
 91    signal input in2[2];
 92    signal output out[2];
 93
 94    var a = 168700;
 95    var d = 168696;
 96
 97    var A = (2 * (a + d)) / (a - d);
 98    var B = 4 / (a - d);
 99
100    signal lamda;
101
102    lamda <-- (in2[1] - in1[1]) / (in2[0] - in1[0]);
103    lamda * (in2[0] - in1[0]) === (in2[1] - in1[1]);
104
105    out[0] <== B*lamda*lamda - A - in1[0] -in2[0];
106    out[1] <== lamda * (in1[0] - out[0]) - in1[1];
107}
108
109/*
110
111    x1_2 = x1*x1
112
113             3*x1_2 + 2*A*x1 + 1
114    lamda = ---------------------
115                   2*B*y1
116
117    x3 = B * lamda^2 - A - x1 -x1
118
119    y3 = lamda * ( x1 - x3 ) - y1
120
121 */
122template MontgomeryDouble() {
123    signal input in[2];
124    signal output out[2];
125
126    var a = 168700;
127    var d = 168696;
128
129    var A = (2 * (a + d)) / (a - d);
130    var B = 4 / (a - d);
131
132    signal lamda;
133    signal x1_2;
134
135    x1_2 <== in[0] * in[0];
136
137    lamda <-- (3*x1_2 + 2*A*in[0] + 1 ) / (2*B*in[1]);
138    lamda * (2*B*in[1]) === (3*x1_2 + 2*A*in[0] + 1 );
139
140    out[0] <== B*lamda*lamda - A - 2*in[0];
141    out[1] <== lamda * (in[0] - out[0]) - in[1];
142}