snarkjs/src/f3field.js
src/f3field.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 F3Field {
22 constructor(F, nonResidue) {
23 this.F = F;
24 this.zero = [this.F.zero, this.F.zero, this.F.zero];
25 this.one = [this.F.one, this.F.zero, this.F.zero];
26 this.nonResidue = nonResidue;
27 }
28
29 _mulByNonResidue(a) {
30 return this.F.mul(this.nonResidue, a);
31 }
32
33 copy(a) {
34 return [this.F.copy(a[0]), this.F.copy(a[1]), this.F.copy(a[2])];
35 }
36
37 add(a, b) {
38 return [
39 this.F.add(a[0], b[0]),
40 this.F.add(a[1], b[1]),
41 this.F.add(a[2], b[2])
42 ];
43 }
44
45 double(a) {
46 return this.add(a,a);
47 }
48
49 sub(a, b) {
50 return [
51 this.F.sub(a[0], b[0]),
52 this.F.sub(a[1], b[1]),
53 this.F.sub(a[2], b[2])
54 ];
55 }
56
57 neg(a) {
58 return this.sub(this.zero, a);
59 }
60
61 mul(a, b) {
62
63 const aA = this.F.mul(a[0] , b[0]);
64 const bB = this.F.mul(a[1] , b[1]);
65 const cC = this.F.mul(a[2] , b[2]);
66
67 return [
68 this.F.add(
69 aA,
70 this._mulByNonResidue(
71 this.F.sub(
72 this.F.mul(
73 this.F.add(a[1], a[2]),
74 this.F.add(b[1], b[2])),
75 this.F.add(bB, cC)))), // aA + non_residue*((b+c)*(B+C)-bB-cC),
76
77 this.F.add(
78 this.F.sub(
79 this.F.mul(
80 this.F.add(a[0], a[1]),
81 this.F.add(b[0], b[1])),
82 this.F.add(aA, bB)),
83 this._mulByNonResidue( cC)), // (a+b)*(A+B)-aA-bB+non_residue*cC
84
85 this.F.add(
86 this.F.sub(
87 this.F.mul(
88 this.F.add(a[0], a[2]),
89 this.F.add(b[0], b[2])),
90 this.F.add(aA, cC)),
91 bB)]; // (a+c)*(A+C)-aA+bB-cC)
92 }
93
94 inverse(a) {
95 const t0 = this.F.square(a[0]); // t0 = a^2 ;
96 const t1 = this.F.square(a[1]); // t1 = b^2 ;
97 const t2 = this.F.square(a[2]); // t2 = c^2;
98 const t3 = this.F.mul(a[0],a[1]); // t3 = ab
99 const t4 = this.F.mul(a[0],a[2]); // t4 = ac
100 const t5 = this.F.mul(a[1],a[2]); // t5 = bc;
101 // c0 = t0 - non_residue * t5;
102 const c0 = this.F.sub(t0, this._mulByNonResidue(t5));
103 // c1 = non_residue * t2 - t3;
104 const c1 = this.F.sub(this._mulByNonResidue(t2), t3);
105 const c2 = this.F.sub(t1, t4); // c2 = t1-t4
106
107 // t6 = (a * c0 + non_residue * (c * c1 + b * c2)).inverse();
108 const t6 =
109 this.F.inverse(
110 this.F.add(
111 this.F.mul(a[0], c0),
112 this._mulByNonResidue(
113 this.F.add(
114 this.F.mul(a[2], c1),
115 this.F.mul(a[1], c2)))));
116
117 return [
118 this.F.mul(t6, c0), // t6*c0
119 this.F.mul(t6, c1), // t6*c1
120 this.F.mul(t6, c2)]; // t6*c2
121 }
122
123 div(a, b) {
124 return this.mul(a, this.inverse(b));
125 }
126
127 square(a) {
128 const s0 = this.F.square(a[0]); // s0 = a^2
129 const ab = this.F.mul(a[0], a[1]); // ab = a*b
130 const s1 = this.F.add(ab, ab); // s1 = 2ab;
131 const s2 = this.F.square(
132 this.F.add(this.F.sub(a[0],a[1]), a[2])); // s2 = (a - b + c)^2;
133 const bc = this.F.mul(a[1],a[2]); // bc = b*c
134 const s3 = this.F.add(bc, bc); // s3 = 2*bc
135 const s4 = this.F.square(a[2]); // s4 = c^2
136
137
138 return [
139 this.F.add(
140 s0,
141 this._mulByNonResidue(s3)), // s0 + non_residue * s3,
142 this.F.add(
143 s1,
144 this._mulByNonResidue(s4)), // s1 + non_residue * s4,
145 this.F.sub(
146 this.F.add( this.F.add(s1, s2) , s3 ),
147 this.F.add(s0, s4))]; // s1 + s2 + s3 - s0 - s4
148 }
149
150 isZero(a) {
151 return this.F.isZero(a[0]) && this.F.isZero(a[1]) && this.F.isZero(a[2]);
152 }
153
154 equals(a, b) {
155 return this.F.equals(a[0], b[0]) && this.F.equals(a[1], b[1]) && this.F.equals(a[2], b[2]);
156 }
157
158 affine(a) {
159 return [this.F.affine(a[0]), this.F.affine(a[1]), this.F.affine(a[2])];
160 }
161
162 mulScalar(base, e) {
163 return fUtils.mulScalar(this, base, e);
164 }
165
166 exp(base, e) {
167 return fUtils.exp(this, base, e);
168 }
169
170 toString(a) {
171 const cp = this.affine(a);
172 return `[ ${this.F.toString(cp[0])} , ${this.F.toString(cp[1])}, ${this.F.toString(cp[2])} ]`;
173 }
174}
175
176module.exports = F3Field;