Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
fp6_2over3_gadgets.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for Fp6 gadgets.
5 
6  See fp6_2over3_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 FP6_GADGETS_TCC_
15 #define FP6_GADGETS_TCC_
16 
17 namespace libsnark
18 {
19 
20 template<typename Fp6T>
21 Fp6_2over3_variable<Fp6T>::Fp6_2over3_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 Fp6T>
30 Fp6_2over3_variable<Fp6T>::Fp6_2over3_variable(
31  protoboard<FieldT> &pb,
32  const Fp6T &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 Fp6T>
41 Fp6_2over3_variable<Fp6T>::Fp6_2over3_variable(
42  protoboard<FieldT> &pb,
43  const Fp3_variable<Fp3T> &c0,
44  const Fp3_variable<Fp3T> &c1,
45  const std::string &annotation_prefix)
46  : gadget<FieldT>(pb, annotation_prefix), c0(c0), c1(c1)
47 {
48 }
49 
50 template<typename Fp6T>
51 void Fp6_2over3_variable<Fp6T>::generate_r1cs_equals_const_constraints(
52  const Fp6T &el)
53 {
54  c0.generate_r1cs_equals_const_constraints(el.coeffs[0]);
55  c1.generate_r1cs_equals_const_constraints(el.coeffs[1]);
56 }
57 
58 template<typename Fp6T>
59 void Fp6_2over3_variable<Fp6T>::generate_r1cs_witness(const Fp6T &el)
60 {
61  c0.generate_r1cs_witness(el.coeffs[0]);
62  c1.generate_r1cs_witness(el.coeffs[1]);
63 }
64 
65 template<typename Fp6T> Fp6T Fp6_2over3_variable<Fp6T>::get_element()
66 {
67  Fp6T el;
68  el.coeffs[0] = c0.get_element();
69  el.coeffs[1] = c1.get_element();
70  return el;
71 }
72 
73 template<typename Fp6T>
74 Fp6_2over3_variable<Fp6T> Fp6_2over3_variable<Fp6T>::Frobenius_map(
75  const size_t power) const
76 {
77  pb_linear_combination<FieldT> new_c0c0, new_c0c1, new_c0c2, new_c1c0,
78  new_c1c1, new_c1c2;
79  new_c0c0.assign(this->pb, c0.c0);
80  new_c0c1.assign(this->pb, c0.c1 * Fp3T::Frobenius_coeffs_c1[power % 3]);
81  new_c0c2.assign(this->pb, c0.c2 * Fp3T::Frobenius_coeffs_c2[power % 3]);
82  new_c1c0.assign(this->pb, c1.c0 * Fp6T::Frobenius_coeffs_c1[power % 6]);
83  new_c1c1.assign(
84  this->pb,
85  c1.c1 * (Fp6T::Frobenius_coeffs_c1[power % 6] *
86  Fp3T::Frobenius_coeffs_c1[power % 3]));
87  new_c1c2.assign(
88  this->pb,
89  c1.c2 * (Fp6T::Frobenius_coeffs_c1[power % 6] *
90  Fp3T::Frobenius_coeffs_c2[power % 3]));
91 
92  return Fp6_2over3_variable<Fp6T>(
93  this->pb,
94  Fp3_variable<Fp3T>(
95  this->pb,
96  new_c0c0,
97  new_c0c1,
98  new_c0c2,
99  FMT(this->annotation_prefix, " Frobenius_map_c0")),
100  Fp3_variable<Fp3T>(
101  this->pb,
102  new_c1c0,
103  new_c1c1,
104  new_c1c2,
105  FMT(this->annotation_prefix, " Frobenius_map_c1")),
106  FMT(this->annotation_prefix, " Frobenius_map"));
107 }
108 
109 template<typename Fp6T> void Fp6_2over3_variable<Fp6T>::evaluate() const
110 {
111  c0.evaluate();
112  c1.evaluate();
113 }
114 
115 template<typename Fp6T>
116 Fp6_2over3_mul_gadget<Fp6T>::Fp6_2over3_mul_gadget(
117  protoboard<FieldT> &pb,
118  const Fp6_2over3_variable<Fp6T> &A,
119  const Fp6_2over3_variable<Fp6T> &B,
120  const Fp6_2over3_variable<Fp6T> &result,
121  const std::string &annotation_prefix)
122  : gadget<FieldT>(pb, annotation_prefix), A(A), B(B), result(result)
123 {
124  /*
125  Karatsuba multiplication for Fp6 as a quadratic extension of Fp3:
126  v0 = A.c0 * B.c0
127  v1 = A.c1 * B.c1
128  result.c0 = v0 + non_residue * v1
129  result.c1 = (A.c0 + A.c1) * (B.c0 + B.c1) - v0 - v1
130  where "non_residue * elem" := (non_residue * elem.c2, elem.c0, elem.c1)
131 
132  Enforced with 3 Fp3_mul_gadget's that ensure that:
133  A.c1 * B.c1 = v1
134  A.c0 * B.c0 = v0
135  (A.c0+A.c1)*(B.c0+B.c1) = result.c1 + v0 + v1
136 
137  Reference:
138  "Multiplication and Squaring on Pairing-Friendly Fields"
139  Devegili, OhEigeartaigh, Scott, Dahab
140  */
141  v1.reset(new Fp3_variable<Fp3T>(pb, FMT(annotation_prefix, " v1")));
142 
143  compute_v1.reset(new Fp3_mul_gadget<Fp3T>(
144  pb, A.c1, B.c1, *v1, FMT(annotation_prefix, " compute_v1")));
145 
146  v0_c0.assign(pb, result.c0.c0 - Fp6T::non_residue * v1->c2);
147  v0_c1.assign(pb, result.c0.c1 - v1->c0);
148  v0_c2.assign(pb, result.c0.c2 - v1->c1);
149  v0.reset(new Fp3_variable<Fp3T>(
150  pb, v0_c0, v0_c1, v0_c2, FMT(annotation_prefix, " v0")));
151 
152  compute_v0.reset(new Fp3_mul_gadget<Fp3T>(
153  pb, A.c0, B.c0, *v0, FMT(annotation_prefix, " compute_v0")));
154 
155  Ac0_plus_Ac1_c0.assign(pb, A.c0.c0 + A.c1.c0);
156  Ac0_plus_Ac1_c1.assign(pb, A.c0.c1 + A.c1.c1);
157  Ac0_plus_Ac1_c2.assign(pb, A.c0.c2 + A.c1.c2);
158  Ac0_plus_Ac1.reset(new Fp3_variable<Fp3T>(
159  pb,
160  Ac0_plus_Ac1_c0,
161  Ac0_plus_Ac1_c1,
162  Ac0_plus_Ac1_c2,
163  FMT(annotation_prefix, " Ac0_plus_Ac1")));
164 
165  Bc0_plus_Bc1_c0.assign(pb, B.c0.c0 + B.c1.c0);
166  Bc0_plus_Bc1_c1.assign(pb, B.c0.c1 + B.c1.c1);
167  Bc0_plus_Bc1_c2.assign(pb, B.c0.c2 + B.c1.c2);
168  Bc0_plus_Bc1.reset(new Fp3_variable<Fp3T>(
169  pb,
170  Bc0_plus_Bc1_c0,
171  Bc0_plus_Bc1_c1,
172  Bc0_plus_Bc1_c2,
173  FMT(annotation_prefix, " Bc0_plus_Bc1")));
174 
175  result_c1_plus_v0_plus_v1_c0.assign(pb, result.c1.c0 + v0->c0 + v1->c0);
176  result_c1_plus_v0_plus_v1_c1.assign(pb, result.c1.c1 + v0->c1 + v1->c1);
177  result_c1_plus_v0_plus_v1_c2.assign(pb, result.c1.c2 + v0->c2 + v1->c2);
178  result_c1_plus_v0_plus_v1.reset(new Fp3_variable<Fp3T>(
179  pb,
180  result_c1_plus_v0_plus_v1_c0,
181  result_c1_plus_v0_plus_v1_c1,
182  result_c1_plus_v0_plus_v1_c2,
183  FMT(annotation_prefix, " result_c1_plus_v0_plus_v1")));
184 
185  compute_result_c1.reset(new Fp3_mul_gadget<Fp3T>(
186  pb,
187  *Ac0_plus_Ac1,
188  *Bc0_plus_Bc1,
189  *result_c1_plus_v0_plus_v1,
190  FMT(annotation_prefix, " compute_result_c1")));
191 }
192 
193 template<typename Fp6T>
194 void Fp6_2over3_mul_gadget<Fp6T>::generate_r1cs_constraints()
195 {
196  compute_v0->generate_r1cs_constraints();
197  compute_v1->generate_r1cs_constraints();
198  compute_result_c1->generate_r1cs_constraints();
199 }
200 
201 template<typename Fp6T>
202 void Fp6_2over3_mul_gadget<Fp6T>::generate_r1cs_witness()
203 {
204  compute_v0->generate_r1cs_witness();
205  compute_v1->generate_r1cs_witness();
206 
207  Ac0_plus_Ac1_c0.evaluate(this->pb);
208  Ac0_plus_Ac1_c1.evaluate(this->pb);
209  Ac0_plus_Ac1_c2.evaluate(this->pb);
210 
211  Bc0_plus_Bc1_c0.evaluate(this->pb);
212  Bc0_plus_Bc1_c1.evaluate(this->pb);
213  Bc0_plus_Bc1_c2.evaluate(this->pb);
214 
215  compute_result_c1->generate_r1cs_witness();
216 
217  const Fp6T Aval = A.get_element();
218  const Fp6T Bval = B.get_element();
219  const Fp6T Rval = Aval * Bval;
220 
221  result.generate_r1cs_witness(Rval);
222 
223  result_c1_plus_v0_plus_v1_c0.evaluate(this->pb);
224  result_c1_plus_v0_plus_v1_c1.evaluate(this->pb);
225  result_c1_plus_v0_plus_v1_c2.evaluate(this->pb);
226 
227  compute_result_c1->generate_r1cs_witness();
228 }
229 
230 template<typename Fp6T>
231 Fp6_2over3_mul_by_2345_gadget<Fp6T>::Fp6_2over3_mul_by_2345_gadget(
232  protoboard<FieldT> &pb,
233  const Fp6_2over3_variable<Fp6T> &A,
234  const Fp6_2over3_variable<Fp6T> &B,
235  const Fp6_2over3_variable<Fp6T> &result,
236  const std::string &annotation_prefix)
237  : gadget<FieldT>(pb, annotation_prefix), A(A), B(B), result(result)
238 {
239  /*
240  Karatsuba multiplication for Fp6 as a quadratic extension of Fp3:
241  v0 = A.c0 * B.c0
242  v1 = A.c1 * B.c1
243  result.c0 = v0 + non_residue * v1
244  result.c1 = (A.c0 + A.c1) * (B.c0 + B.c1) - v0 - v1
245  where "non_residue * elem" := (non_residue * elem.c2, elem.c0, elem.c1)
246 
247  We know that B.c0.c0 = B.c0.c1 = 0
248 
249  Enforced with 2 Fp3_mul_gadget's that ensure that:
250  A.c1 * B.c1 = v1
251  (A.c0+A.c1)*(B.c0+B.c1) = result.c1 + v0 + v1
252 
253  And one multiplication (three direct constraints) that enforces A.c0 *
254  B.c0 = v0, where B.c0.c0 = B.c0.c1 = 0.
255 
256  Note that (u + v * X + t * X^2) * (0 + 0 * X + z * X^2) =
257  (v * z * non_residue + t * z * non_residue * X + u * z * X^2)
258 
259  Reference:
260  "Multiplication and Squaring on Pairing-Friendly Fields"
261  Devegili, OhEigeartaigh, Scott, Dahab
262  */
263  v1.reset(new Fp3_variable<Fp3T>(pb, FMT(annotation_prefix, " v1")));
264  compute_v1.reset(new Fp3_mul_gadget<Fp3T>(
265  pb, A.c1, B.c1, *v1, FMT(annotation_prefix, " compute_v1")));
266 
267  /* we inline result.c0 in v0 as follows: v0 = (result.c0.c0 -
268  * Fp6T::non_residue * v1->c2, result.c0.c1 - v1->c0, result.c0.c2 - v1->c1)
269  */
270  v0.reset(new Fp3_variable<Fp3T>(pb, FMT(annotation_prefix, " v0")));
271 
272  Ac0_plus_Ac1_c0.assign(pb, A.c0.c0 + A.c1.c0);
273  Ac0_plus_Ac1_c1.assign(pb, A.c0.c1 + A.c1.c1);
274  Ac0_plus_Ac1_c2.assign(pb, A.c0.c2 + A.c1.c2);
275  Ac0_plus_Ac1.reset(new Fp3_variable<Fp3T>(
276  pb,
277  Ac0_plus_Ac1_c0,
278  Ac0_plus_Ac1_c1,
279  Ac0_plus_Ac1_c2,
280  FMT(annotation_prefix, " Ac0_plus_Ac1")));
281 
282  Bc0_plus_Bc1_c0.assign(pb, B.c0.c0 + B.c1.c0);
283  Bc0_plus_Bc1_c1.assign(pb, B.c0.c1 + B.c1.c1);
284  Bc0_plus_Bc1_c2.assign(pb, B.c0.c2 + B.c1.c2);
285  Bc0_plus_Bc1.reset(new Fp3_variable<Fp3T>(
286  pb,
287  Bc0_plus_Bc1_c0,
288  Bc0_plus_Bc1_c1,
289  Bc0_plus_Bc1_c2,
290  FMT(annotation_prefix, " Bc0_plus_Bc1")));
291 
292  result_c1_plus_v0_plus_v1_c0.assign(pb, result.c1.c0 + v0->c0 + v1->c0);
293  result_c1_plus_v0_plus_v1_c1.assign(pb, result.c1.c1 + v0->c1 + v1->c1);
294  result_c1_plus_v0_plus_v1_c2.assign(pb, result.c1.c2 + v0->c2 + v1->c2);
295  result_c1_plus_v0_plus_v1.reset(new Fp3_variable<Fp3T>(
296  pb,
297  result_c1_plus_v0_plus_v1_c0,
298  result_c1_plus_v0_plus_v1_c1,
299  result_c1_plus_v0_plus_v1_c2,
300  FMT(annotation_prefix, " result_c1_plus_v0_plus_v1")));
301 
302  compute_result_c1.reset(new Fp3_mul_gadget<Fp3T>(
303  pb,
304  *Ac0_plus_Ac1,
305  *Bc0_plus_Bc1,
306  *result_c1_plus_v0_plus_v1,
307  FMT(annotation_prefix, " compute_result_c1")));
308 }
309 
310 template<typename Fp6T>
311 void Fp6_2over3_mul_by_2345_gadget<Fp6T>::generate_r1cs_constraints()
312 {
313  compute_v1->generate_r1cs_constraints();
314  this->pb.add_r1cs_constraint(
315  r1cs_constraint<FieldT>(
316  A.c0.c1,
317  Fp3T::non_residue * B.c0.c2,
318  result.c0.c0 - Fp6T::non_residue * v1->c2),
319  FMT(this->annotation_prefix, " v0.c0"));
320  this->pb.add_r1cs_constraint(
321  r1cs_constraint<FieldT>(
322  A.c0.c2, Fp3T::non_residue * B.c0.c2, result.c0.c1 - v1->c0),
323  FMT(this->annotation_prefix, " v0.c1"));
324  this->pb.add_r1cs_constraint(
325  r1cs_constraint<FieldT>(A.c0.c0, B.c0.c2, result.c0.c2 - v1->c1),
326  FMT(this->annotation_prefix, " v0.c2"));
327  compute_result_c1->generate_r1cs_constraints();
328 }
329 
330 template<typename Fp6T>
331 void Fp6_2over3_mul_by_2345_gadget<Fp6T>::generate_r1cs_witness()
332 {
333  compute_v1->generate_r1cs_witness();
334 
335  const Fp3T A_c0_val = A.c0.get_element();
336  const Fp3T B_c0_val = B.c0.get_element();
337  assert(B_c0_val.coeffs[0].is_zero());
338  assert(B_c0_val.coeffs[1].is_zero());
339 
340  const Fp3T v0_val = A_c0_val * B_c0_val;
341  v0->generate_r1cs_witness(v0_val);
342 
343  Ac0_plus_Ac1_c0.evaluate(this->pb);
344  Ac0_plus_Ac1_c1.evaluate(this->pb);
345  Ac0_plus_Ac1_c2.evaluate(this->pb);
346 
347  Bc0_plus_Bc1_c0.evaluate(this->pb);
348  Bc0_plus_Bc1_c1.evaluate(this->pb);
349  Bc0_plus_Bc1_c2.evaluate(this->pb);
350 
351  compute_result_c1->generate_r1cs_witness();
352 
353  const Fp6T Aval = A.get_element();
354  const Fp6T Bval = B.get_element();
355  const Fp6T Rval = Aval * Bval;
356 
357  result.generate_r1cs_witness(Rval);
358 
359  result_c1_plus_v0_plus_v1_c0.evaluate(this->pb);
360  result_c1_plus_v0_plus_v1_c1.evaluate(this->pb);
361  result_c1_plus_v0_plus_v1_c2.evaluate(this->pb);
362 
363  compute_result_c1->generate_r1cs_witness();
364 }
365 
366 template<typename Fp6T>
367 Fp6_2over3_sqr_gadget<Fp6T>::Fp6_2over3_sqr_gadget(
368  protoboard<FieldT> &pb,
369  const Fp6_2over3_variable<Fp6T> &A,
370  const Fp6_2over3_variable<Fp6T> &result,
371  const std::string &annotation_prefix)
372  : gadget<FieldT>(pb, annotation_prefix), A(A), result(result)
373 {
374  // We can't do better than 3 Fp3_mul_gadget's for squaring, so we just use
375  // multiplication.
376  mul.reset(new Fp6_2over3_mul_gadget<Fp6T>(
377  pb, A, A, result, FMT(annotation_prefix, " mul")));
378 }
379 
380 template<typename Fp6T>
381 void Fp6_2over3_sqr_gadget<Fp6T>::generate_r1cs_constraints()
382 {
383  mul->generate_r1cs_constraints();
384 }
385 
386 template<typename Fp6T>
387 void Fp6_2over3_sqr_gadget<Fp6T>::generate_r1cs_witness()
388 {
389  mul->generate_r1cs_witness();
390 }
391 
392 template<typename Fp6T>
393 Fp6_2over3_cyclotomic_sqr_gadget<Fp6T>::Fp6_2over3_cyclotomic_sqr_gadget(
394  protoboard<FieldT> &pb,
395  const Fp6_2over3_variable<Fp6T> &A,
396  const Fp6_2over3_variable<Fp6T> &result,
397  const std::string &annotation_prefix)
398  : gadget<FieldT>(pb, annotation_prefix), A(A), result(result)
399 {
400  /*
401  my_Fp2 a = my_Fp2(c0.c0, c1.c1);
402  my_Fp2 b = my_Fp2(c1.c0, c0.c2);
403  my_Fp2 c = my_Fp2(c0.c1, c1.c2);
404 
405  my_Fp2 asq = a.squared();
406  my_Fp2 bsq = b.squared();
407  my_Fp2 csq = c.squared();
408 
409  result.c0.c0 = 3 * asq_a - 2 * a_a;
410  result.c1.c1 = 3 * asq_b + 2 * a_b;
411 
412  result.c0.c1 = 3 * bsq_a - 2 * c_a;
413  result.c1.c2 = 3 * bsq_b + 2 * c_b;
414 
415  result.c0.c2 = 3 * csq_a - 2 * b_b;
416  result.c1.c0 = 3 * my_Fp3::non_residue * csq_b + 2 * b_a;
417 
418  return Fp6_2over3_model<n, mbodulus>(my_Fp3(A_a, C_a, B_b),
419  my_Fp3(B_a, A_b, C_b))
420  */
421  a.reset(new Fp2_variable<Fp2T>(
422  pb, A.c0.c0, A.c1.c1, FMT(annotation_prefix, " a")));
423  b.reset(new Fp2_variable<Fp2T>(
424  pb, A.c1.c0, A.c0.c2, FMT(annotation_prefix, " b")));
425  c.reset(new Fp2_variable<Fp2T>(
426  pb, A.c0.c1, A.c1.c2, FMT(annotation_prefix, " c")));
427 
428  asq_c0.assign(pb, (result.c0.c0 + 2 * a->c0) * FieldT(3).inverse());
429  asq_c1.assign(pb, (result.c1.c1 - 2 * a->c1) * FieldT(3).inverse());
430 
431  bsq_c0.assign(pb, (result.c0.c1 + 2 * c->c0) * FieldT(3).inverse());
432  bsq_c1.assign(pb, (result.c1.c2 - 2 * c->c1) * FieldT(3).inverse());
433 
434  csq_c0.assign(pb, (result.c0.c2 + 2 * b->c1) * FieldT(3).inverse());
435  csq_c1.assign(
436  pb,
437  (result.c1.c0 - 2 * b->c0) * (FieldT(3) * Fp2T::non_residue).inverse());
438 
439  asq.reset(new Fp2_variable<Fp2T>(
440  pb, asq_c0, asq_c1, FMT(annotation_prefix, " asq")));
441  bsq.reset(new Fp2_variable<Fp2T>(
442  pb, bsq_c0, bsq_c1, FMT(annotation_prefix, " bsq")));
443  csq.reset(new Fp2_variable<Fp2T>(
444  pb, csq_c0, csq_c1, FMT(annotation_prefix, " csq")));
445 
446  compute_asq.reset(new Fp2_sqr_gadget<Fp2T>(
447  pb, *a, *asq, FMT(annotation_prefix, " compute_asq")));
448  compute_bsq.reset(new Fp2_sqr_gadget<Fp2T>(
449  pb, *b, *bsq, FMT(annotation_prefix, " compute_bsq")));
450  compute_csq.reset(new Fp2_sqr_gadget<Fp2T>(
451  pb, *c, *csq, FMT(annotation_prefix, " compute_csq")));
452 }
453 
454 template<typename Fp6T>
455 void Fp6_2over3_cyclotomic_sqr_gadget<Fp6T>::generate_r1cs_constraints()
456 {
457  compute_asq->generate_r1cs_constraints();
458  compute_bsq->generate_r1cs_constraints();
459  compute_csq->generate_r1cs_constraints();
460 }
461 
462 template<typename Fp6T>
463 void Fp6_2over3_cyclotomic_sqr_gadget<Fp6T>::generate_r1cs_witness()
464 {
465  const Fp6T Aval = A.get_element();
466  const Fp6T Rval = Aval.cyclotomic_squared();
467 
468  result.generate_r1cs_witness(Rval);
469 
470  asq->evaluate();
471  bsq->evaluate();
472  csq->evaluate();
473 
474  compute_asq->generate_r1cs_witness();
475  compute_bsq->generate_r1cs_witness();
476  compute_csq->generate_r1cs_witness();
477 }
478 
479 } // namespace libsnark
480 
481 #endif // FP6_GADGETS_TCC_
Generated on Wed Jan 25 2023 11:05:57 for Clearmatics Libsnark by   doxygen 1.8.17