1
  2/*
  3    Source: https://en.wikipedia.org/wiki/Montgomery_curve
  4
  5                1 + y       1 + y
  6    [u, v] = [ -------  , ---------- ]
  7                1 - y      (1 - y)x
  8
  9 */
 10
 11template Edwards2Montgomery() {
 12    signal input in[2];
 13    signal output out[2];
 14
 15    out[0] <-- (1 + in[1]) / (1 - in[1]);
 16    out[1] <-- out[0] / in[0];
 17
 18
 19    out[0] * (1-in[1]) === (1 + in[1]);
 20    out[1] * in[0] === out[0];
 21}
 22
 23/*
 24
 25                u    u - 1
 26    [x, y] = [ ---, ------- ]
 27                v    u + 1
 28
 29 */
 30template Montgomery2Edwards() {
 31    signal input in[2];
 32    signal output out[2];
 33
 34    out[0] <-- in[0] / in[1];
 35    out[1] <-- (in[0] - 1) / (in[0] + 1);
 36
 37    out[0] * in[1] === in[0];
 38    out[1] * (in[0] + 1) === in[0] - 1;
 39}
 40
 41
 42/*
 43             x2 - x1
 44    lamda = ---------
 45             y2 - y1
 46
 47                                                    x3 + A + x1 + x2
 48    x3 = B * lamda^2 - A - x1 -x2    =>  lamda^2 = ------------------
 49                                                         B
 50
 51    y3 = (2*x1 + x2 + A)*lamda - B*lamda^3 - y1  =>
 52
 53
 54    =>  y3 = lamda * ( 2*x1 + x2 + A  - x3 - A - x1 - x2)  - y1 =>
 55
 56    =>  y3 = lamda * ( x1 - x3 ) - y1
 57
 58----------
 59
 60             y2 - y1
 61    lamda = ---------
 62             x2 - x1
 63
 64    x3 = B * lamda^2 - A - x1 -x2
 65
 66    y3 = lamda * ( x1 - x3 ) - y1
 67
 68 */
 69
 70template MontgomeryAdd() {
 71    signal input in1[2];
 72    signal input in2[2];
 73    signal output out[2];
 74
 75    var a = 168700;
 76    var d = 168696;
 77
 78    var A = (2 * (a + d)) / (a - d);
 79    var B = 4 / (a - d);
 80
 81    signal lamda;
 82
 83    lamda <-- (in2[1] - in1[1]) / (in2[0] - in1[0]);
 84    lamda * (in2[0] - in1[0]) === (in2[1] - in1[1]);
 85
 86    out[0] <== B*lamda*lamda - A - in1[0] -in2[0];
 87    out[1] <== lamda * (in1[0] - out[0]) - in1[1];
 88}
 89
 90/*
 91
 92    x1_2 = x1*x1
 93
 94             3*x1_2 + 2*A*x1 + 1
 95    lamda = ---------------------
 96                   2*B*y1
 97
 98    x3 = B * lamda^2 - A - x1 -x1
 99
100    y3 = lamda * ( x1 - x3 ) - y1
101
102 */
103template MontgomeryDouble() {
104    signal input in[2];
105    signal output out[2];
106
107    var a = 168700;
108    var d = 168696;
109
110    var A = (2 * (a + d)) / (a - d);
111    var B = 4 / (a - d);
112
113    signal lamda;
114    signal x1_2;
115
116    x1_2 <== in[0] * in[0];
117
118    lamda <-- (3*x1_2 + 2*A*in[0] + 1 ) / (2*B*in[1]);
119    lamda * (2*B*in[1]) === (3*x1_2 + 2*A*in[0] + 1 );
120
121    out[0] <== B*lamda*lamda - A - 2*in[0];
122    out[1] <== lamda * (in[0] - out[0]) - in[1];
123}