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