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