Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
bls12_377_final_exponentiation.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3  * @author This file is part of libsnark, developed by Clearmatics Ltd
4  * (originally developed by SCIPR Lab) and contributors
5  * (see AUTHORS).
6  * @copyright MIT license (see LICENSE file)
7  *****************************************************************************/
8 
9 #ifndef LIBSNARK_GADGETLIB1_GADGETS_PAIRING_BW6_761_BLS12_377_BLS12_377_FINAL_EXPONENTIATION_TCC_
10 #define LIBSNARK_GADGETLIB1_GADGETS_PAIRING_BW6_761_BLS12_377_BLS12_377_FINAL_EXPONENTIATION_TCC_
11 
12 #include "libsnark/gadgetlib1/gadgets/basic_gadgets.hpp"
13 #include "libsnark/gadgetlib1/gadgets/pairing/bw6_761_bls12_377/bls12_377_final_exponentiation.hpp"
14 
15 namespace libsnark
16 {
17 
18 // bls12_377_final_exp_first_part_gadget methods
19 
20 template<typename ppT>
21 bls12_377_final_exp_first_part_gadget<ppT>::
22  bls12_377_final_exp_first_part_gadget(
23  protoboard<FieldT> &pb,
24  const Fp12_2over3over2_variable<FqkT> &in,
25  const Fp12_2over3over2_variable<FqkT> &result,
26  const std::string &annotation_prefix)
27  : gadget<FieldT>(pb, annotation_prefix)
28  , _result(result)
29  , _compute_B(
30  pb,
31  in,
32  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " B")),
33  FMT(annotation_prefix, " _B"))
34  , _compute_C(
35  pb,
36  in.frobenius_map(6), // _A
37  _compute_B.result(),
38  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " C")),
39  FMT(annotation_prefix, " _C"))
40  , _compute_D_times_C(
41  pb,
42  _compute_C.result().frobenius_map(2), // _D
43  _compute_C.result(),
44  _result,
45  FMT(annotation_prefix, " _D_times_C"))
46 {
47 }
48 
49 template<typename ppT>
50 const Fp12_2over3over2_variable<libff::Fqk<other_curve<ppT>>>
51  &bls12_377_final_exp_first_part_gadget<ppT>::result() const
52 {
53  return _result;
54 }
55 
56 template<typename ppT>
57 void bls12_377_final_exp_first_part_gadget<ppT>::generate_r1cs_constraints()
58 {
59  _compute_B.generate_r1cs_constraints();
60  _compute_C.generate_r1cs_constraints();
61  _compute_D_times_C.generate_r1cs_constraints();
62 }
63 
64 template<typename ppT>
65 void bls12_377_final_exp_first_part_gadget<ppT>::generate_r1cs_witness()
66 {
67  _compute_B.generate_r1cs_witness();
68  _compute_C._A.evaluate();
69  _compute_C.generate_r1cs_witness();
70  _compute_D_times_C._A.evaluate();
71  _compute_D_times_C.generate_r1cs_witness();
72 }
73 
74 // bls12_377_exp_by_z_gadget methods
75 
76 template<typename ppT>
77 bls12_377_exp_by_z_gadget<ppT>::bls12_377_exp_by_z_gadget(
78  protoboard<FieldT> &pb,
79  const Fp12_2over3over2_variable<FqkT> &in,
80  const Fp12_2over3over2_variable<FqkT> &result,
81  const std::string &annotation_prefix)
82  : gadget<FieldT>(pb, annotation_prefix), _result(result)
83 {
84  // There is some complexity in ensuring that the result uses _result as an
85  // output variable. If bls12_377_final_exponent_is_z_neg, we perform all
86  // square and multiplies into intermediate variables and then unitary
87  // inverse into _result. Otherwise, care must be taken during the final
88  // iteration so that _result holds the output from the final multiply.
89 
90  if (libff::bls12_377_final_exponent_is_z_neg) {
91  initialize_z_neg(pb, in, annotation_prefix);
92  } else {
93  initialize_z_pos(pb, in, annotation_prefix);
94  }
95 }
96 
97 template<typename ppT>
98 void bls12_377_exp_by_z_gadget<ppT>::initialize_z_neg(
99  protoboard<FieldT> &pb,
100  const Fp12_2over3over2_variable<FqkT> &in,
101  const std::string &annotation_prefix)
102 {
103  const Fp12_2over3over2_variable<FqkT> *res = &in;
104 
105  // Iterate through all bits, then perform a unitary_inverse into result
106 
107  const size_t num_bits = libff::bls12_377_final_exponent_z.num_bits();
108  for (size_t bit_idx = num_bits - 1; bit_idx > 0; --bit_idx) {
109  // result <- result.cyclotomic_squared()
110  _squares.push_back(
111  std::shared_ptr<cyclotomic_square>(new cyclotomic_square(
112  pb,
113  *res,
114  Fp12_2over3over2_variable<FqkT>(
115  pb, FMT(annotation_prefix, " res^2")),
116  FMT(annotation_prefix, " _squares[%zu]", _squares.size()))));
117  res = &(_squares.back()->result());
118 
119  if (libff::bls12_377_final_exponent_z.test_bit(bit_idx - 1)) {
120  // result <- result * elt
121  _multiplies.push_back(std::shared_ptr<multiply>(new multiply(
122  pb,
123  *res,
124  in,
125  Fp12_2over3over2_variable<FqkT>(
126  pb, FMT(annotation_prefix, " res*in")),
127  FMT(annotation_prefix,
128  " _multiplies[%zu]",
129  _multiplies.size()))));
130  res = &(_multiplies.back()->result());
131  }
132  }
133 
134  _inverse = std::shared_ptr<unitary_inverse>(new unitary_inverse(
135  pb, *res, _result, FMT(annotation_prefix, " res.inv")));
136 }
137 
138 template<typename ppT>
139 void bls12_377_exp_by_z_gadget<ppT>::initialize_z_pos(
140  protoboard<FieldT> &pb,
141  const Fp12_2over3over2_variable<FqkT> &in,
142  const std::string &annotation_prefix)
143 {
144  const Fp12_2over3over2_variable<FqkT> *res = &in;
145 
146  // Iterate through all bits, leaving the last one as a special case.
147  const size_t num_bits = libff::bls12_377_final_exponent_z.num_bits();
148  for (size_t bit_idx = num_bits - 1; bit_idx > 1; --bit_idx) {
149  // result <- result.cyclotomic_squared()
150  _squares.push_back(
151  std::shared_ptr<cyclotomic_square>(new cyclotomic_square(
152  pb,
153  *res,
154  Fp12_2over3over2_variable<FqkT>(
155  pb, FMT(annotation_prefix, " res^2")),
156  FMT(annotation_prefix, " _squares[%zu]", _squares.size()))));
157  res = &(_squares.back()->result());
158 
159  if (libff::bls12_377_final_exponent_z.test_bit(bit_idx - 1)) {
160  // result <- result * elt
161  _multiplies.push_back(std::shared_ptr<multiply>(new multiply(
162  pb,
163  *res,
164  in,
165  Fp12_2over3over2_variable<FqkT>(
166  pb, FMT(annotation_prefix, " res*in")),
167  FMT(annotation_prefix,
168  " _multiplies[%zu]",
169  _multiplies.size()))));
170  res = &(_multiplies.back()->result());
171  }
172  }
173 
174  // Write the output of the final iteration to result.
175  assert(libff::bls12_377_final_exponent_z.test_bit(0));
176  _squares.push_back(std::shared_ptr<cyclotomic_square>(new cyclotomic_square(
177  pb,
178  *res,
179  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, "res^2")),
180  FMT(annotation_prefix, " _squares[%zu]", _squares.size()))));
181  res = &(_squares.back()->result());
182 
183  _multiplies.push_back(std::shared_ptr<multiply>(new multiply(
184  pb,
185  *res,
186  in,
187  _result,
188  FMT(annotation_prefix, " _multiplies[%zu]", _multiplies.size()))));
189 }
190 
191 template<typename ppT>
192 const Fp12_2over3over2_variable<libff::Fqk<other_curve<ppT>>>
193  &bls12_377_exp_by_z_gadget<ppT>::result() const
194 {
195  return _result;
196 }
197 
198 template<typename ppT>
199 void bls12_377_exp_by_z_gadget<ppT>::generate_r1cs_constraints()
200 {
201  size_t sqr_idx = 0;
202  size_t mul_idx = 0;
203  const size_t num_bits = libff::bls12_377_final_exponent_z.num_bits();
204  for (size_t bit_idx = num_bits - 1; bit_idx > 0; --bit_idx) {
205  _squares[sqr_idx++]->generate_r1cs_constraints();
206  if (libff::bls12_377_final_exponent_z.test_bit(bit_idx - 1)) {
207  _multiplies[mul_idx++]->generate_r1cs_constraints();
208  }
209  }
210 
211  if (_inverse) {
212  _inverse->generate_r1cs_constraints();
213  }
214 }
215 
216 template<typename ppT>
217 void bls12_377_exp_by_z_gadget<ppT>::generate_r1cs_witness()
218 {
219  size_t sqr_idx = 0;
220  size_t mul_idx = 0;
221  const size_t num_bits = libff::bls12_377_final_exponent_z.num_bits();
222  for (size_t bit_idx = num_bits - 1; bit_idx > 0; --bit_idx) {
223  _squares[sqr_idx++]->generate_r1cs_witness();
224  if (libff::bls12_377_final_exponent_z.test_bit(bit_idx - 1)) {
225  _multiplies[mul_idx++]->generate_r1cs_witness();
226  }
227  }
228 
229  if (_inverse) {
230  _inverse->generate_r1cs_witness();
231  }
232 }
233 
234 // bls12_377_final_exp_last_part_gadget methods
235 
236 template<typename ppT>
237 bls12_377_final_exp_last_part_gadget<ppT>::bls12_377_final_exp_last_part_gadget(
238  protoboard<FieldT> &pb,
239  const Fp12_2over3over2_variable<FqkT> &in,
240  const Fp12_2over3over2_variable<FqkT> &result,
241  const std::string &annotation_prefix)
242  : gadget<FieldT>(pb, annotation_prefix)
243  , _result(result)
244  // A = [-2]
245  , _compute_in_squared(
246  pb,
247  in,
248  Fp12_2over3over2_variable<FqkT>(
249  pb, FMT(annotation_prefix, " in_squared")),
250  FMT(annotation_prefix, " _compute_in_squared"))
251  // B = [z]
252  , _compute_B(
253  pb,
254  in,
255  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " B")),
256  FMT(annotation_prefix, " _compute_B"))
257  // C = [2z]
258  , _compute_C(
259  pb,
260  _compute_B.result(),
261  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " C")),
262  FMT(annotation_prefix, " _compute_C"))
263  // D = [z-2]
264  , _compute_D(
265  pb,
266  _compute_in_squared.result().unitary_inverse(), // _A
267  _compute_B.result(),
268  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " D")),
269  FMT(annotation_prefix, " _compute_D"))
270  // E = [z^2-2z]
271  , _compute_E(
272  pb,
273  _compute_D.result(),
274  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " E")),
275  FMT(annotation_prefix, " _compute_E"))
276  // F = [z^3-2z^2]
277  , _compute_F(
278  pb,
279  _compute_E.result(),
280  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " F")),
281  FMT(annotation_prefix, " _compute_F"))
282  // G = [z^4-2z^3]
283  , _compute_G(
284  pb,
285  _compute_F.result(),
286  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " G")),
287  FMT(annotation_prefix, " _compute_G"))
288  // H = [z^4-2z^3+2z]
289  , _compute_H(
290  pb,
291  _compute_G.result(),
292  _compute_C.result(),
293  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " H")),
294  FMT(annotation_prefix, " _comptue_H"))
295  // I = [z^5-2z^4+2z^2]
296  , _compute_I(
297  pb,
298  _compute_H.result(),
299  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " I")),
300  FMT(annotation_prefix, " _compute_I"))
301  // J = [-z+2]
302  // K = [z^5-2z^4+2z^2-z+2]
303  , _compute_K(
304  pb,
305  _compute_I.result(),
306  _compute_D.result().unitary_inverse(), // _J
307  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " K")),
308  FMT(annotation_prefix, " _compute_K"))
309  // L = [z^5-2z^4+2z^2-z+3] = [\lambda_0]
310  , _compute_L(
311  pb,
312  _compute_K.result(),
313  in,
314  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " L")),
315  FMT(annotation_prefix, " _compute_L"))
316  // M = [-1]
317  // N = [z^2-2z+1] = [\lambda_3]
318  , _compute_N(
319  pb,
320  _compute_E.result(),
321  in,
322  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " N")),
323  FMT(annotation_prefix, " _compute_N"))
324  // O = [(z^2-2z+1) * (q^3)]
325  // P = [z^4-2z^3+2z-1] = [\lambda_1]
326  , _compute_P(
327  pb,
328  _compute_H.result(),
329  in.unitary_inverse(), // _M
330  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " P")),
331  FMT(annotation_prefix, " _compute_P"))
332  // Q = [(z^4-2z^3+2z-1) * q]
333  // R = [z^3-2z^2+z] = [\lambda_2]
334  , _compute_R(
335  pb,
336  _compute_F.result(),
337  _compute_B.result(),
338  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " R")),
339  FMT(annotation_prefix, " _compute_R"))
340  // S = [(z^3-2z^2+z) * (q^2)]
341  // T = [(z^2-2z+1) * (q^3) + (z^3-2z^2+z) * (q^2)]
342  , _compute_T(
343  pb,
344  _compute_N.result().frobenius_map(3), // _O
345  _compute_R.result().frobenius_map(2), // _S
346  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " T")),
347  FMT(annotation_prefix, " _compute_T"))
348  // U = [(z^2-2z+1) * (q^3) + (z^3-2z^2+z) * (q^2) + (z^4-2z^3+2z-1) * q]
349  , _compute_U(
350  pb,
351  _compute_T.result(),
352  _compute_P.result().frobenius_map(1), // _Q
353  Fp12_2over3over2_variable<FqkT>(pb, FMT(annotation_prefix, " U")),
354  FMT(annotation_prefix, " _compute_U"))
355  // result = [(z^2-2z+1) * (q^3) + (z^3-2z^2+z) * (q^2) + (z^4-2z^3+2z-1) * q
356  // + z^5-2z^4+2z^2-z+3]
357  // = [(p^4 - p^2 + 1)/r].
358  , _compute_U_times_L(
359  pb,
360  _compute_U.result(),
361  _compute_L.result(),
362  _result,
363  FMT(annotation_prefix, " _compute_U_times_L"))
364 {
365 }
366 
367 template<typename ppT>
368 const Fp12_2over3over2_variable<libff::Fqk<other_curve<ppT>>>
369  &bls12_377_final_exp_last_part_gadget<ppT>::result() const
370 {
371  return _result;
372 }
373 
374 template<typename ppT>
375 void bls12_377_final_exp_last_part_gadget<ppT>::generate_r1cs_constraints()
376 {
377  _compute_in_squared.generate_r1cs_constraints();
378  _compute_B.generate_r1cs_constraints();
379  _compute_C.generate_r1cs_constraints();
380  _compute_D.generate_r1cs_constraints();
381  _compute_E.generate_r1cs_constraints();
382  _compute_F.generate_r1cs_constraints();
383  _compute_G.generate_r1cs_constraints();
384  _compute_H.generate_r1cs_constraints();
385  _compute_I.generate_r1cs_constraints();
386  _compute_K.generate_r1cs_constraints();
387  _compute_L.generate_r1cs_constraints();
388  _compute_N.generate_r1cs_constraints();
389  _compute_P.generate_r1cs_constraints();
390  _compute_R.generate_r1cs_constraints();
391  _compute_T.generate_r1cs_constraints();
392  _compute_U.generate_r1cs_constraints();
393  _compute_U_times_L.generate_r1cs_constraints();
394 }
395 
396 template<typename ppT>
397 void bls12_377_final_exp_last_part_gadget<ppT>::generate_r1cs_witness()
398 {
399  _compute_in_squared.generate_r1cs_witness();
400  _compute_B.generate_r1cs_witness();
401  _compute_C.generate_r1cs_witness();
402  _compute_D._A.evaluate();
403  _compute_D.generate_r1cs_witness();
404  _compute_E.generate_r1cs_witness();
405  _compute_F.generate_r1cs_witness();
406  _compute_G.generate_r1cs_witness();
407  _compute_H.generate_r1cs_witness();
408  _compute_I.generate_r1cs_witness();
409  _compute_K._B.evaluate();
410  _compute_K.generate_r1cs_witness();
411  _compute_L.generate_r1cs_witness();
412  _compute_N._A.evaluate();
413  _compute_N.generate_r1cs_witness();
414  _compute_P._B.evaluate();
415  _compute_P.generate_r1cs_witness();
416  _compute_R.generate_r1cs_witness();
417  _compute_T._A.evaluate();
418  _compute_T._B.evaluate();
419  _compute_T.generate_r1cs_witness();
420  _compute_U._B.evaluate();
421  _compute_U.generate_r1cs_witness();
422  _compute_U_times_L.generate_r1cs_witness();
423 }
424 
425 // bls12_377_final_exp_gadget methods
426 
427 template<typename ppT>
428 bls12_377_final_exp_gadget<ppT>::bls12_377_final_exp_gadget(
429  protoboard<libff::Fr<ppT>> &pb,
430  const Fp12_2over3over2_variable<FqkT> &el,
431  const pb_variable<FieldT> &result_is_one,
432  const std::string &annotation_prefix)
433  : gadget<FieldT>(pb, annotation_prefix)
434  , _compute_first_part(
435  pb,
436  el,
437  Fqk_variable<ppT>(pb, FMT(annotation_prefix, " first_part")),
438  FMT(annotation_prefix, " _compute_first_part"))
439  , _compute_last_part(
440  pb,
441  _compute_first_part.result(),
442  Fqk_variable<ppT>(pb, FMT(annotation_prefix, "last_part")),
443  FMT(annotation_prefix, " _compute_last_part"))
444  , _result_is_one(result_is_one)
445 {
446 }
447 
448 template<typename ppT>
449 void bls12_377_final_exp_gadget<ppT>::generate_r1cs_constraints()
450 {
451  _compute_first_part.generate_r1cs_constraints();
452  _compute_last_part.generate_r1cs_constraints();
453 
454  // Constrain result_is_one to be 0 or 1.
455  generate_boolean_r1cs_constraint<FieldT>(
456  this->pb,
457  _result_is_one,
458  FMT(this->annotation_prefix, " result_is_one_boolean"));
459 
460  // Use the value of result_is_one to enable / disable the constraints on
461  // the 12 components of the result of the final exponentiation in Fq12.
462  Fqk_variable<ppT> result = _compute_last_part.result();
463  this->pb.add_r1cs_constraint(
464  r1cs_constraint<FieldT>(_result_is_one, 1 - result._c0._c0.c0, 0),
465  " c0.c0.c0==1");
466  this->pb.add_r1cs_constraint(
467  r1cs_constraint<FieldT>(_result_is_one, result._c0._c0.c1, 0),
468  " c0.c0.c1==0");
469  this->pb.add_r1cs_constraint(
470  r1cs_constraint<FieldT>(_result_is_one, result._c0._c1.c0, 0),
471  " c0.c1.c0==0");
472  this->pb.add_r1cs_constraint(
473  r1cs_constraint<FieldT>(_result_is_one, result._c0._c1.c1, 0),
474  " c0.c1.c1==0");
475  this->pb.add_r1cs_constraint(
476  r1cs_constraint<FieldT>(_result_is_one, result._c0._c2.c0, 0),
477  " c0.c2.c0==0");
478  this->pb.add_r1cs_constraint(
479  r1cs_constraint<FieldT>(_result_is_one, result._c0._c2.c1, 0),
480  " c0.c2.c1==0");
481  this->pb.add_r1cs_constraint(
482  r1cs_constraint<FieldT>(_result_is_one, result._c1._c0.c0, 0),
483  " c1.c0.c0==0");
484  this->pb.add_r1cs_constraint(
485  r1cs_constraint<FieldT>(_result_is_one, result._c1._c0.c1, 0),
486  " c1.c0.c1==0");
487  this->pb.add_r1cs_constraint(
488  r1cs_constraint<FieldT>(_result_is_one, result._c1._c1.c0, 0),
489  " c1.c1.c0==0");
490  this->pb.add_r1cs_constraint(
491  r1cs_constraint<FieldT>(_result_is_one, result._c1._c1.c1, 0),
492  " c1.c1.c1==0");
493  this->pb.add_r1cs_constraint(
494  r1cs_constraint<FieldT>(_result_is_one, result._c1._c2.c0, 0),
495  " c1.c2.c0==0");
496  this->pb.add_r1cs_constraint(
497  r1cs_constraint<FieldT>(_result_is_one, result._c1._c2.c1, 0),
498  " c1.c2.c1==0");
499 }
500 
501 template<typename ppT>
502 void bls12_377_final_exp_gadget<ppT>::generate_r1cs_witness()
503 {
504  _compute_first_part.generate_r1cs_witness();
505  _compute_last_part.generate_r1cs_witness();
506 
507  const FqkT result_val = _compute_last_part.result().get_element();
508  this->pb.val(_result_is_one) =
509  (result_val == FqkT::one()) ? FieldT::one() : FieldT::zero();
510 }
511 
512 } // namespace libsnark
513 
514 #endif // LIBSNARK_GADGETLIB1_GADGETS_PAIRING_BW6_761_BLS12_377_BLS12_377_FINAL_EXPONENTIATION_TCC_
Generated on Wed Jan 25 2023 11:05:58 for Clearmatics Libsnark by   doxygen 1.8.17