snarkjs/src/gcurve.js
src/gcurve.jsRaw
1/*
2 Copyright 2018 0kims association.
3
4 This file is part of zksnark JavaScript library.
5
6 zksnark JavaScript library is a free software: you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as published by the
8 Free Software Foundation, either version 3 of the License, or (at your option)
9 any later version.
10
11 zksnark JavaScript library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 more details.
15
16 You should have received a copy of the GNU General Public License along with
17 zksnark JavaScript library. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const fUtils = require("./futils.js");
21
22class GCurve {
23
24 constructor(F, g) {
25 this.F = F;
26 this.g = [F.copy(g[0]), F.copy(g[1])];
27 if (this.g.length == 2) this.g[2] = this.F.one;
28 this.zero = [this.F.zero, this.F.one, this.F.zero];
29 }
30
31 isZero(p) {
32 return this.F.isZero(p[2]);
33 }
34
35 add(p1, p2) {
36
37 if (this.isZero(p1)) return p2;
38 if (this.isZero(p2)) return p1;
39
40 const res = new Array(3);
41
42 const Z1Z1 = this.F.square( p1[2] );
43 const Z2Z2 = this.F.square( p2[2] );
44
45 const U1 = this.F.mul( p1[0] , Z2Z2 ); // U1 = X1 * Z2Z2
46 const U2 = this.F.mul( p2[0] , Z1Z1 ); // U2 = X2 * Z1Z1
47
48 const Z1_cubed = this.F.mul( p1[2] , Z1Z1);
49 const Z2_cubed = this.F.mul( p2[2] , Z2Z2);
50
51 const S1 = this.F.mul( p1[1] , Z2_cubed); // S1 = Y1 * Z2 * Z2Z2
52 const S2 = this.F.mul( p2[1] , Z1_cubed); // S2 = Y2 * Z1 * Z1Z1
53
54 if (this.F.equals(U1,U2) && this.F.equals(S1,S2)) {
55 return this.double(p1);
56 }
57
58 const H = this.F.sub( U2 , U1 ); // H = U2-U1
59
60 const S2_minus_S1 = this.F.sub( S2 , S1 );
61
62 const I = this.F.square( this.F.add(H,H) ); // I = (2 * H)^2
63 const J = this.F.mul( H , I ); // J = H * I
64
65 const r = this.F.add( S2_minus_S1 , S2_minus_S1 ); // r = 2 * (S2-S1)
66 const V = this.F.mul( U1 , I ); // V = U1 * I
67
68 res[0] =
69 this.F.sub(
70 this.F.sub( this.F.square(r) , J ),
71 this.F.add( V , V )); // X3 = r^2 - J - 2 * V
72
73 const S1_J = this.F.mul( S1 , J );
74
75 res[1] =
76 this.F.sub(
77 this.F.mul( r , this.F.sub(V,res[0])),
78 this.F.add( S1_J,S1_J )); // Y3 = r * (V-X3)-2 S1 J
79
80 res[2] =
81 this.F.mul(
82 H,
83 this.F.sub(
84 this.F.square( this.F.add(p1[2],p2[2]) ),
85 this.F.add( Z1Z1 , Z2Z2 ))); // Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2) * H
86
87 return res;
88 }
89
90 neg(p) {
91 return [p[0], this.F.neg(p[1]), p[2]];
92 }
93
94 sub(a, b) {
95 return this.add(a, this.neg(b));
96 }
97
98 double(p) {
99 const res = new Array(3);
100
101 if (this.isZero(p)) return p;
102
103 const A = this.F.square( p[0] ); // A = X1^2
104 const B = this.F.square( p[1] ); // B = Y1^2
105 const C = this.F.square( B ); // C = B^2
106
107 let D =
108 this.F.sub(
109 this.F.square( this.F.add(p[0] , B )),
110 this.F.add( A , C));
111 D = this.F.add(D,D); // D = 2 * ((X1 + B)^2 - A - C)
112
113 const E = this.F.add( this.F.add(A,A), A); // E = 3 * A
114 const F = this.F.square( E ); // F = E^2
115
116 res[0] = this.F.sub( F , this.F.add(D,D) ); // X3 = F - 2 D
117
118 let eightC = this.F.add( C , C );
119 eightC = this.F.add( eightC , eightC );
120 eightC = this.F.add( eightC , eightC );
121
122 res[1] =
123 this.F.sub(
124 this.F.mul(
125 E,
126 this.F.sub( D, res[0] )),
127 eightC); // Y3 = E * (D - X3) - 8 * C
128
129 const Y1Z1 = this.F.mul( p[1] , p[2] );
130 res[2] = this.F.add( Y1Z1 , Y1Z1 ); // Z3 = 2 * Y1 * Z1
131
132 return res;
133 }
134
135 mulScalar(base, e) {
136 return fUtils.mulScalar(this, base, e);
137 }
138
139 affine(p) {
140 if (this.isZero(p)) {
141 return this.zero;
142 } else {
143 const Z_inv = this.F.inverse(p[2]);
144 const Z2_inv = this.F.square(Z_inv);
145 const Z3_inv = this.F.mul(Z2_inv, Z_inv);
146
147 const res = new Array(3);
148 res[0] = this.F.affine( this.F.mul(p[0],Z2_inv));
149 res[1] = this.F.affine( this.F.mul(p[1],Z3_inv));
150 res[2] = this.F.one;
151
152 return res;
153 }
154 }
155
156 equals(p1, p2) {
157 if (this.isZero(p1)) return this.isZero(p2);
158 if (this.isZero(p2)) return this.isZero(p1);
159
160 const Z1Z1 = this.F.square( p1[2] );
161 const Z2Z2 = this.F.square( p2[2] );
162
163 const U1 = this.F.mul( p1[0] , Z2Z2 );
164 const U2 = this.F.mul( p2[0] , Z1Z1 );
165
166 const Z1_cubed = this.F.mul( p1[2] , Z1Z1);
167 const Z2_cubed = this.F.mul( p2[2] , Z2Z2);
168
169 const S1 = this.F.mul( p1[1] , Z2_cubed);
170 const S2 = this.F.mul( p2[1] , Z1_cubed);
171
172 return (this.F.equals(U1,U2) && this.F.equals(S1,S2));
173 }
174
175 toString(p) {
176 const cp = this.affine(p);
177 return `[ ${this.F.toString(cp[0])} , ${this.F.toString(cp[1])} ]`;
178 }
179
180}
181
182module.exports = GCurve;
183