Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
fp4_gadgets.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for Fp4 gadgets.
5 
6  See fp4_gadgets.hpp .
7 
8  *****************************************************************************
9  * @author This file is part of libsnark, developed by SCIPR Lab
10  * and contributors (see AUTHORS).
11  * @copyright MIT license (see LICENSE file)
12  *****************************************************************************/
13 
14 #ifndef FP4_GADGETS_TCC_
15 #define FP4_GADGETS_TCC_
16 
17 namespace libsnark
18 {
19 
20 template<typename Fp4T>
21 Fp4_variable<Fp4T>::Fp4_variable(
22  protoboard<FieldT> &pb, const std::string &annotation_prefix)
23  : gadget<FieldT>(pb, annotation_prefix)
24  , c0(pb, FMT(annotation_prefix, " c0"))
25  , c1(pb, FMT(annotation_prefix, " c1"))
26 {
27 }
28 
29 template<typename Fp4T>
30 Fp4_variable<Fp4T>::Fp4_variable(
31  protoboard<FieldT> &pb,
32  const Fp4T &el,
33  const std::string &annotation_prefix)
34  : gadget<FieldT>(pb, annotation_prefix)
35  , c0(pb, el.coeffs[0], FMT(annotation_prefix, " c0"))
36  , c1(pb, el.coeffs[1], FMT(annotation_prefix, " c1"))
37 {
38 }
39 
40 template<typename Fp4T>
41 Fp4_variable<Fp4T>::Fp4_variable(
42  protoboard<FieldT> &pb,
43  const Fp2_variable<Fp2T> &c0,
44  const Fp2_variable<Fp2T> &c1,
45  const std::string &annotation_prefix)
46  : gadget<FieldT>(pb, annotation_prefix), c0(c0), c1(c1)
47 {
48 }
49 
50 template<typename Fp4T>
51 void Fp4_variable<Fp4T>::generate_r1cs_equals_const_constraints(const Fp4T &el)
52 {
53  c0.generate_r1cs_equals_const_constraints(el.coeffs[0]);
54  c1.generate_r1cs_equals_const_constraints(el.coeffs[1]);
55 }
56 
57 template<typename Fp4T>
58 void Fp4_variable<Fp4T>::generate_r1cs_witness(const Fp4T &el)
59 {
60  c0.generate_r1cs_witness(el.coeffs[0]);
61  c1.generate_r1cs_witness(el.coeffs[1]);
62 }
63 
64 template<typename Fp4T> Fp4T Fp4_variable<Fp4T>::get_element()
65 {
66  Fp4T el;
67  el.coeffs[0] = c0.get_element();
68  el.coeffs[1] = c1.get_element();
69  return el;
70 }
71 
72 template<typename Fp4T>
73 Fp4_variable<Fp4T> Fp4_variable<Fp4T>::Frobenius_map(const size_t power) const
74 {
75  pb_linear_combination<FieldT> new_c0c0, new_c0c1, new_c1c0, new_c1c1;
76  new_c0c0.assign(this->pb, c0.c0);
77  new_c0c1.assign(this->pb, c0.c1 * Fp2T::Frobenius_coeffs_c1[power % 2]);
78  new_c1c0.assign(this->pb, c1.c0 * Fp4T::Frobenius_coeffs_c1[power % 4]);
79  new_c1c1.assign(
80  this->pb,
81  c1.c1 * Fp4T::Frobenius_coeffs_c1[power % 4] *
82  Fp2T::Frobenius_coeffs_c1[power % 2]);
83 
84  return Fp4_variable<Fp4T>(
85  this->pb,
86  Fp2_variable<Fp2T>(
87  this->pb,
88  new_c0c0,
89  new_c0c1,
90  FMT(this->annotation_prefix, " Frobenius_map_c0")),
91  Fp2_variable<Fp2T>(
92  this->pb,
93  new_c1c0,
94  new_c1c1,
95  FMT(this->annotation_prefix, " Frobenius_map_c1")),
96  FMT(this->annotation_prefix, " Frobenius_map"));
97 }
98 
99 template<typename Fp4T> void Fp4_variable<Fp4T>::evaluate() const
100 {
101  c0.evaluate();
102  c1.evaluate();
103 }
104 
105 template<typename Fp4T>
106 Fp4_tower_mul_gadget<Fp4T>::Fp4_tower_mul_gadget(
107  protoboard<FieldT> &pb,
108  const Fp4_variable<Fp4T> &A,
109  const Fp4_variable<Fp4T> &B,
110  const Fp4_variable<Fp4T> &result,
111  const std::string &annotation_prefix)
112  : gadget<FieldT>(pb, annotation_prefix), A(A), B(B), result(result)
113 {
114  /*
115  Karatsuba multiplication for Fp4 as a quadratic extension of Fp2:
116  v0 = A.c0 * B.c0
117  v1 = A.c1 * B.c1
118  result.c0 = v0 + non_residue * v1
119  result.c1 = (A.c0 + A.c1) * (B.c0 + B.c1) - v0 - v1
120  where "non_residue * elem" := (non_residue * elt.c1, elt.c0)
121 
122  Enforced with 3 Fp2_mul_gadget's that ensure that:
123  A.c1 * B.c1 = v1
124  A.c0 * B.c0 = v0
125  (A.c0+A.c1)*(B.c0+B.c1) = result.c1 + v0 + v1
126 
127  Reference:
128  "Multiplication and Squaring on Pairing-Friendly Fields"
129  Devegili, OhEigeartaigh, Scott, Dahab
130  */
131  v1.reset(new Fp2_variable<Fp2T>(pb, FMT(annotation_prefix, " v1")));
132 
133  compute_v1.reset(new Fp2_mul_gadget<Fp2T>(
134  pb, A.c1, B.c1, *v1, FMT(annotation_prefix, " compute_v1")));
135 
136  v0_c0.assign(pb, result.c0.c0 - Fp4T::non_residue * v1->c1);
137  v0_c1.assign(pb, result.c0.c1 - v1->c0);
138  v0.reset(new Fp2_variable<Fp2T>(
139  pb, v0_c0, v0_c1, FMT(annotation_prefix, " v0")));
140 
141  compute_v0.reset(new Fp2_mul_gadget<Fp2T>(
142  pb, A.c0, B.c0, *v0, FMT(annotation_prefix, " compute_v0")));
143 
144  Ac0_plus_Ac1_c0.assign(pb, A.c0.c0 + A.c1.c0);
145  Ac0_plus_Ac1_c1.assign(pb, A.c0.c1 + A.c1.c1);
146  Ac0_plus_Ac1.reset(new Fp2_variable<Fp2T>(
147  pb,
148  Ac0_plus_Ac1_c0,
149  Ac0_plus_Ac1_c1,
150  FMT(annotation_prefix, " Ac0_plus_Ac1")));
151 
152  Bc0_plus_Bc1_c0.assign(pb, B.c0.c0 + B.c1.c0);
153  Bc0_plus_Bc1_c1.assign(pb, B.c0.c1 + B.c1.c1);
154  Bc0_plus_Bc1.reset(new Fp2_variable<Fp2T>(
155  pb,
156  Bc0_plus_Bc1_c0,
157  Bc0_plus_Bc1_c1,
158  FMT(annotation_prefix, " Bc0_plus_Bc1")));
159 
160  result_c1_plus_v0_plus_v1_c0.assign(pb, result.c1.c0 + v0->c0 + v1->c0);
161  result_c1_plus_v0_plus_v1_c1.assign(pb, result.c1.c1 + v0->c1 + v1->c1);
162  result_c1_plus_v0_plus_v1.reset(new Fp2_variable<Fp2T>(
163  pb,
164  result_c1_plus_v0_plus_v1_c0,
165  result_c1_plus_v0_plus_v1_c1,
166  FMT(annotation_prefix, " result_c1_plus_v0_plus_v1")));
167 
168  compute_result_c1.reset(new Fp2_mul_gadget<Fp2T>(
169  pb,
170  *Ac0_plus_Ac1,
171  *Bc0_plus_Bc1,
172  *result_c1_plus_v0_plus_v1,
173  FMT(annotation_prefix, " compute_result_c1")));
174 }
175 
176 template<typename Fp4T>
177 void Fp4_tower_mul_gadget<Fp4T>::generate_r1cs_constraints()
178 {
179  compute_v0->generate_r1cs_constraints();
180  compute_v1->generate_r1cs_constraints();
181  compute_result_c1->generate_r1cs_constraints();
182 }
183 
184 template<typename Fp4T> void Fp4_tower_mul_gadget<Fp4T>::generate_r1cs_witness()
185 {
186  compute_v0->generate_r1cs_witness();
187  compute_v1->generate_r1cs_witness();
188 
189  Ac0_plus_Ac1_c0.evaluate(this->pb);
190  Ac0_plus_Ac1_c1.evaluate(this->pb);
191 
192  Bc0_plus_Bc1_c0.evaluate(this->pb);
193  Bc0_plus_Bc1_c1.evaluate(this->pb);
194 
195  compute_result_c1->generate_r1cs_witness();
196 
197  const Fp4T Aval = A.get_element();
198  const Fp4T Bval = B.get_element();
199  const Fp4T Rval = Aval * Bval;
200 
201  result.generate_r1cs_witness(Rval);
202 }
203 
204 template<typename Fp4T>
205 Fp4_direct_mul_gadget<Fp4T>::Fp4_direct_mul_gadget(
206  protoboard<FieldT> &pb,
207  const Fp4_variable<Fp4T> &A,
208  const Fp4_variable<Fp4T> &B,
209  const Fp4_variable<Fp4T> &result,
210  const std::string &annotation_prefix)
211  : gadget<FieldT>(pb, annotation_prefix), A(A), B(B), result(result)
212 {
213  /*
214  Tom-Cook-4x for Fp4 (beta is the quartic non-residue):
215  v0 = a0*b0,
216  v1 = (a0+a1+a2+a3)*(b0+b1+b2+b3),
217  v2 = (a0-a1+a2-a3)*(b0-b1+b2-b3),
218  v3 = (a0+2a1+4a2+8a3)*(b0+2b1+4b2+8b3),
219  v4 = (a0-2a1+4a2-8a3)*(b0-2b1+4b2-8b3),
220  v5 = (a0+3a1+9a2+27a3)*(b0+3b1+9b2+27b3),
221  v6 = a3*b3
222 
223  result.c0 = v0+beta((1/4)v0-(1/6)(v1+v2)+(1/24)(v3+v4)-5v6),
224  result.c1 =
225  -(1/3)v0+v1-(1/2)v2-(1/4)v3+(1/20)v4+(1/30)v5-12v6+beta(-(1/12)(v0-v1)+(1/24)(v2-v3)-(1/120)(v4-v5)-3v6),
226  result.c2 = -(5/4)v0+(2/3)(v1+v2)-(1/24)(v3+v4)+4v6+beta v6,
227  result.c3 = (1/12)(5v0-7v1)-(1/24)(v2-7v3+v4+v5)+15v6
228 
229  Enforced with 7 constraints. Doing so requires some care, as we first
230  compute three of the v_i explicitly, and then "inline"
231  result.c0/c1/c2/c3 in computations of the remaining four v_i.
232 
233  Concretely, we first compute v1, v2 and v6 explicitly, via 3 constraints
234  as above. v1 = (a0+a1+a2+a3)*(b0+b1+b2+b3), v2 =
235  (a0-a1+a2-a3)*(b0-b1+b2-b3), v6 = a3*b3
236 
237  Then we use the following 4 additional constraints:
238  (1-beta) v0 = c0 + beta c2 - (beta v1)/2 - (beta v2)/ 2 - (-1 +
239  beta) beta v6 (1-beta) v3 = -15 c0 - 30 c1 - 3 (4 + beta) c2 - 6 (4 +
240  beta) c3 + (24 - (3 beta)/2) v1 + (-8 + beta/2) v2 + 3 (-16 + beta) (-1 +
241  beta) v6 (1-beta) v4 = -15 c0 + 30 c1 - 3 (4 + beta) c2 + 6 (4 + beta) c3
242  + (-8 + beta/2) v1 + (24 - (3 beta)/2) v2 + 3 (-16 + beta) (-1 + beta) v6
243  (1-beta) v5 = -80 c0 - 240 c1 - 8 (9 + beta) c2 - 24 (9 + beta) c3 -
244  2 (-81 + beta) v1 + (-81 + beta) v2 + 8 (-81 + beta) (-1 + beta) v6
245 
246  The isomorphism between the representation above and towering is:
247  (a0, a1, a2, a3) <-> (a.c0.c0, a.c1.c0, a.c0.c1, a.c1.c1)
248 
249  Reference:
250  "Multiplication and Squaring on Pairing-Friendly Fields"
251  Devegili, OhEigeartaigh, Scott, Dahab
252 
253  NOTE: the expressions above were cherry-picked from the Mathematica
254  result of the following command:
255 
256  (# -> Solve[{c0 == v0+beta((1/4)v0-(1/6)(v1+v2)+(1/24)(v3+v4)-5v6),
257  c1 ==
258  -(1/3)v0+v1-(1/2)v2-(1/4)v3+(1/20)v4+(1/30)v5-12v6+beta(-(1/12)(v0-v1)+(1/24)(v2-v3)-(1/120)(v4-v5)-3v6),
259  c2 == -(5/4)v0+(2/3)(v1+v2)-(1/24)(v3+v4)+4v6+beta v6,
260  c3 == (1/12)(5v0-7v1)-(1/24)(v2-7v3+v4+v5)+15v6}, #] // FullSimplify) &
261  /@ Subsets[{v0, v1, v2, v3, v4, v5}, {4}]
262 
263  and simplified by multiplying the selected result by (1-beta)
264  */
265  v1.allocate(pb, FMT(annotation_prefix, " v1"));
266  v2.allocate(pb, FMT(annotation_prefix, " v2"));
267  v6.allocate(pb, FMT(annotation_prefix, " v6"));
268 }
269 
270 template<typename Fp4T>
271 void Fp4_direct_mul_gadget<Fp4T>::generate_r1cs_constraints()
272 {
273  const FieldT beta = Fp4T::non_residue;
274  const FieldT u = (FieldT::one() - beta).inverse();
275 
276  const pb_linear_combination<FieldT> &a0 = A.c0.c0, &a1 = A.c1.c0,
277  &a2 = A.c0.c1, &a3 = A.c1.c1,
278  &b0 = B.c0.c0, &b1 = B.c1.c0,
279  &b2 = B.c0.c1, &b3 = B.c1.c1,
280  &c0 = result.c0.c0, &c1 = result.c1.c0,
281  &c2 = result.c0.c1, &c3 = result.c1.c1;
282 
283  this->pb.add_r1cs_constraint(
284  r1cs_constraint<FieldT>(a0 + a1 + a2 + a3, b0 + b1 + b2 + b3, v1),
285  FMT(this->annotation_prefix, " v1"));
286  this->pb.add_r1cs_constraint(
287  r1cs_constraint<FieldT>(a0 - a1 + a2 - a3, b0 - b1 + b2 - b3, v2),
288  FMT(this->annotation_prefix, " v2"));
289  this->pb.add_r1cs_constraint(
290  r1cs_constraint<FieldT>(a3, b3, v6),
291  FMT(this->annotation_prefix, " v6"));
292 
293  this->pb.add_r1cs_constraint(
294  r1cs_constraint<FieldT>(
295  a0,
296  b0,
297  u * c0 + beta * u * c2 - beta * u * FieldT(2).inverse() * v1 -
298  beta * u * FieldT(2).inverse() * v2 + beta * v6),
299  FMT(this->annotation_prefix, " v0"));
300  this->pb.add_r1cs_constraint(
301  r1cs_constraint<FieldT>(
302  a0 + FieldT(2) * a1 + FieldT(4) * a2 + FieldT(8) * a3,
303  b0 + FieldT(2) * b1 + FieldT(4) * b2 + FieldT(8) * b3,
304  -FieldT(15) * u * c0 - FieldT(30) * u * c1 -
305  FieldT(3) * (FieldT(4) + beta) * u * c2 -
306  FieldT(6) * (FieldT(4) + beta) * u * c3 +
307  (FieldT(24) - FieldT(3) * beta * FieldT(2).inverse()) * u * v1 +
308  (-FieldT(8) + beta * FieldT(2).inverse()) * u * v2 -
309  FieldT(3) * (-FieldT(16) + beta) * v6),
310  FMT(this->annotation_prefix, " v3"));
311  this->pb.add_r1cs_constraint(
312  r1cs_constraint<FieldT>(
313  a0 - FieldT(2) * a1 + FieldT(4) * a2 - FieldT(8) * a3,
314  b0 - FieldT(2) * b1 + FieldT(4) * b2 - FieldT(8) * b3,
315  -FieldT(15) * u * c0 + FieldT(30) * u * c1 -
316  FieldT(3) * (FieldT(4) + beta) * u * c2 +
317  FieldT(6) * (FieldT(4) + beta) * u * c3 +
318  (FieldT(24) - FieldT(3) * beta * FieldT(2).inverse()) * u * v2 +
319  (-FieldT(8) + beta * FieldT(2).inverse()) * u * v1 -
320  FieldT(3) * (-FieldT(16) + beta) * v6),
321  FMT(this->annotation_prefix, " v4"));
322  this->pb.add_r1cs_constraint(
323  r1cs_constraint<FieldT>(
324  a0 + FieldT(3) * a1 + FieldT(9) * a2 + FieldT(27) * a3,
325  b0 + FieldT(3) * b1 + FieldT(9) * b2 + FieldT(27) * b3,
326  -FieldT(80) * u * c0 - FieldT(240) * u * c1 -
327  FieldT(8) * (FieldT(9) + beta) * u * c2 -
328  FieldT(24) * (FieldT(9) + beta) * u * c3 -
329  FieldT(2) * (-FieldT(81) + beta) * u * v1 +
330  (-FieldT(81) + beta) * u * v2 -
331  FieldT(8) * (-FieldT(81) + beta) * v6),
332  FMT(this->annotation_prefix, " v5"));
333 }
334 
335 template<typename Fp4T>
336 void Fp4_direct_mul_gadget<Fp4T>::generate_r1cs_witness()
337 {
338  const pb_linear_combination<FieldT> &a0 = A.c0.c0, &a1 = A.c1.c0,
339  &a2 = A.c0.c1, &a3 = A.c1.c1,
340  &b0 = B.c0.c0, &b1 = B.c1.c0,
341  &b2 = B.c0.c1, &b3 = B.c1.c1;
342 
343  this->pb.val(v1) =
344  ((this->pb.lc_val(a0) + this->pb.lc_val(a1) + this->pb.lc_val(a2) +
345  this->pb.lc_val(a3)) *
346  (this->pb.lc_val(b0) + this->pb.lc_val(b1) + this->pb.lc_val(b2) +
347  this->pb.lc_val(b3)));
348  this->pb.val(v2) =
349  ((this->pb.lc_val(a0) - this->pb.lc_val(a1) + this->pb.lc_val(a2) -
350  this->pb.lc_val(a3)) *
351  (this->pb.lc_val(b0) - this->pb.lc_val(b1) + this->pb.lc_val(b2) -
352  this->pb.lc_val(b3)));
353  this->pb.val(v6) = this->pb.lc_val(a3) * this->pb.lc_val(b3);
354 
355  const Fp4T Aval = A.get_element();
356  const Fp4T Bval = B.get_element();
357  const Fp4T Rval = Aval * Bval;
358 
359  result.generate_r1cs_witness(Rval);
360 }
361 
362 template<typename Fp4T>
363 Fp4_sqr_gadget<Fp4T>::Fp4_sqr_gadget(
364  protoboard<FieldT> &pb,
365  const Fp4_variable<Fp4T> &A,
366  const Fp4_variable<Fp4T> &result,
367  const std::string &annotation_prefix)
368  : gadget<FieldT>(pb, annotation_prefix), A(A), result(result)
369 {
370  /*
371  Karatsuba squaring for Fp4 as a quadratic extension of Fp2:
372  v0 = A.c0^2
373  v1 = A.c1^2
374  result.c0 = v0 + non_residue * v1
375  result.c1 = (A.c0 + A.c1)^2 - v0 - v1
376  where "non_residue * elem" := (non_residue * elt.c1, elt.c0)
377 
378  Enforced with 3 Fp2_sqr_gadget's that ensure that:
379  A.c1^2 = v1
380  A.c0^2 = v0
381  (A.c0+A.c1)^2 = result.c1 + v0 + v1
382 
383  Reference:
384  "Multiplication and Squaring on Pairing-Friendly Fields"
385  Devegili, OhEigeartaigh, Scott, Dahab
386  */
387  v1.reset(new Fp2_variable<Fp2T>(pb, FMT(annotation_prefix, " v1")));
388  compute_v1.reset(new Fp2_sqr_gadget<Fp2T>(
389  pb, A.c1, *v1, FMT(annotation_prefix, " compute_v1")));
390 
391  v0_c0.assign(pb, result.c0.c0 - Fp4T::non_residue * v1->c1);
392  v0_c1.assign(pb, result.c0.c1 - v1->c0);
393  v0.reset(new Fp2_variable<Fp2T>(
394  pb, v0_c0, v0_c1, FMT(annotation_prefix, " v0")));
395 
396  compute_v0.reset(new Fp2_sqr_gadget<Fp2T>(
397  pb, A.c0, *v0, FMT(annotation_prefix, " compute_v0")));
398 
399  Ac0_plus_Ac1_c0.assign(pb, A.c0.c0 + A.c1.c0);
400  Ac0_plus_Ac1_c1.assign(pb, A.c0.c1 + A.c1.c1);
401  Ac0_plus_Ac1.reset(new Fp2_variable<Fp2T>(
402  pb,
403  Ac0_plus_Ac1_c0,
404  Ac0_plus_Ac1_c1,
405  FMT(annotation_prefix, " Ac0_plus_Ac1")));
406 
407  result_c1_plus_v0_plus_v1_c0.assign(pb, result.c1.c0 + v0->c0 + v1->c0);
408  result_c1_plus_v0_plus_v1_c1.assign(pb, result.c1.c1 + v0->c1 + v1->c1);
409  result_c1_plus_v0_plus_v1.reset(new Fp2_variable<Fp2T>(
410  pb,
411  result_c1_plus_v0_plus_v1_c0,
412  result_c1_plus_v0_plus_v1_c1,
413  FMT(annotation_prefix, " result_c1_plus_v0_plus_v1")));
414 
415  compute_result_c1.reset(new Fp2_sqr_gadget<Fp2T>(
416  pb,
417  *Ac0_plus_Ac1,
418  *result_c1_plus_v0_plus_v1,
419  FMT(annotation_prefix, " compute_result_c1")));
420 }
421 
422 template<typename Fp4T> void Fp4_sqr_gadget<Fp4T>::generate_r1cs_constraints()
423 {
424  compute_v1->generate_r1cs_constraints();
425  compute_v0->generate_r1cs_constraints();
426  compute_result_c1->generate_r1cs_constraints();
427 }
428 
429 template<typename Fp4T> void Fp4_sqr_gadget<Fp4T>::generate_r1cs_witness()
430 {
431  compute_v1->generate_r1cs_witness();
432 
433  v0_c0.evaluate(this->pb);
434  v0_c1.evaluate(this->pb);
435  compute_v0->generate_r1cs_witness();
436 
437  Ac0_plus_Ac1_c0.evaluate(this->pb);
438  Ac0_plus_Ac1_c1.evaluate(this->pb);
439  compute_result_c1->generate_r1cs_witness();
440 
441  const Fp4T Aval = A.get_element();
442  const Fp4T Rval = Aval.squared();
443  result.generate_r1cs_witness(Rval);
444 }
445 
446 template<typename Fp4T>
447 Fp4_cyclotomic_sqr_gadget<Fp4T>::Fp4_cyclotomic_sqr_gadget(
448  protoboard<FieldT> &pb,
449  const Fp4_variable<Fp4T> &A,
450  const Fp4_variable<Fp4T> &result,
451  const std::string &annotation_prefix)
452  : gadget<FieldT>(pb, annotation_prefix), A(A), result(result)
453 {
454  /*
455  A = elt.c1 ^ 2
456  B = elt.c1 + elt.c0;
457  C = B ^ 2 - A
458  D = Fp2(A.c1 * non_residue, A.c0)
459  E = C - D
460  F = D + D + Fp2::one()
461  G = E - Fp2::one()
462 
463  return Fp4(F, G);
464 
465  Enforced with 2 Fp2_sqr_gadget's that ensure that:
466 
467  elt.c1 ^ 2 = Fp2(result.c0.c1 / 2, (result.c0.c0 - 1) / (2 * non_residue))
468  = A (elt.c1 + elt.c0) ^ 2 = A + result.c1 + Fp2(A.c1 * non_residue + 1,
469  A.c0)
470 
471  (elt.c1 + elt.c0) ^ 2 = Fp2(result.c0.c1 / 2 + result.c1.c0 +
472  (result.c0.c0 - 1) / 2 + 1, (result.c0.c0 - 1) / (2 * non_residue) +
473  result.c1.c1 + result.c0.c1 / 2)
474 
475  Corresponding test code:
476 
477  assert(B.squared() == A + G + my_Fp2(A.c1 * non_residue + my_Fp::one(),
478  A.c0)); assert(this->c1.squared().c0 == F.c1 * my_Fp(2).inverse());
479  assert(this->c1.squared().c1 == (F.c0 - my_Fp(1)) * (my_Fp(2) *
480  non_residue).inverse());
481  */
482  c0_expr_c0.assign(pb, result.c0.c1 * FieldT(2).inverse());
483  c0_expr_c1.assign(
484  pb,
485  (result.c0.c0 - FieldT(1)) * (FieldT(2) * Fp4T::non_residue).inverse());
486  c0_expr.reset(new Fp2_variable<Fp2T>(
487  pb, c0_expr_c0, c0_expr_c1, FMT(annotation_prefix, " c0_expr")));
488  compute_c0_expr.reset(new Fp2_sqr_gadget<Fp2T>(
489  pb, A.c1, *c0_expr, FMT(annotation_prefix, " compute_c0_expr")));
490 
491  A_c0_plus_A_c1_c0.assign(pb, A.c0.c0 + A.c1.c0);
492  A_c0_plus_A_c1_c1.assign(pb, A.c0.c1 + A.c1.c1);
493  A_c0_plus_A_c1.reset(new Fp2_variable<Fp2T>(
494  pb,
495  A_c0_plus_A_c1_c0,
496  A_c0_plus_A_c1_c1,
497  FMT(annotation_prefix, " A_c0_plus_A_c1")));
498 
499  c1_expr_c0.assign(
500  pb,
501  (result.c0.c1 + result.c0.c0 - FieldT(1)) * FieldT(2).inverse() +
502  result.c1.c0 + FieldT(1));
503  c1_expr_c1.assign(
504  pb,
505  (result.c0.c0 - FieldT(1)) * (FieldT(2) * Fp4T::non_residue).inverse() +
506  result.c1.c1 + result.c0.c1 * FieldT(2).inverse());
507  c1_expr.reset(new Fp2_variable<Fp2T>(
508  pb, c1_expr_c0, c1_expr_c1, FMT(annotation_prefix, " c1_expr")));
509 
510  compute_c1_expr.reset(new Fp2_sqr_gadget<Fp2T>(
511  pb,
512  *A_c0_plus_A_c1,
513  *c1_expr,
514  FMT(annotation_prefix, " compute_c1_expr")));
515 }
516 
517 template<typename Fp4T>
518 void Fp4_cyclotomic_sqr_gadget<Fp4T>::generate_r1cs_constraints()
519 {
520  compute_c0_expr->generate_r1cs_constraints();
521  compute_c1_expr->generate_r1cs_constraints();
522 }
523 
524 template<typename Fp4T>
525 void Fp4_cyclotomic_sqr_gadget<Fp4T>::generate_r1cs_witness()
526 {
527  compute_c0_expr->generate_r1cs_witness();
528 
529  A_c0_plus_A_c1_c0.evaluate(this->pb);
530  A_c0_plus_A_c1_c1.evaluate(this->pb);
531  compute_c1_expr->generate_r1cs_witness();
532 
533  const Fp4T Aval = A.get_element();
534  const Fp4T Rval = Aval.squared();
535  result.generate_r1cs_witness(Rval);
536 }
537 
538 } // namespace libsnark
539 
540 #endif // FP4_GADGETS_TCC_
Generated on Wed Jan 25 2023 11:05:57 for Clearmatics Libsnark by   doxygen 1.8.17