Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
mnt_precomputation.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for pairing precomputation gadgets.
5 
6  See weierstrass_precomputation.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 LIBSNARK_GADGETLIB1_GADGETS_PAIRING_MNT_MNT_PRECOMPUTATION_TCC_
15 #define LIBSNARK_GADGETLIB1_GADGETS_PAIRING_MNT_MNT_PRECOMPUTATION_TCC_
16 
17 #include "libsnark/gadgetlib1/gadgets/pairing/mnt/mnt_pairing_params.hpp"
18 
19 #include <type_traits>
20 
21 namespace libsnark
22 {
23 
24 template<typename ppT> mnt_G1_precomputation<ppT>::mnt_G1_precomputation()
25 {
26  // will be filled in precompute_G1_gadget, so do nothing here
27 }
28 
29 template<typename ppT>
30 mnt_G1_precomputation<ppT>::mnt_G1_precomputation(
31  protoboard<FieldT> &pb,
32  const libff::G1<other_curve<ppT>> &P_val,
33  const std::string &annotation_prefix)
34 {
35  libff::G1<other_curve<ppT>> P_val_copy = P_val;
36  P_val_copy.to_affine_coordinates();
37  P.reset(new G1_variable<ppT>(pb, P_val_copy, FMT(annotation_prefix, " P")));
38  PY_twist_squared.reset(new Fqe_variable<ppT>(
39  pb,
40  P_val_copy.Y * libff::G2<other_curve<ppT>>::twist.squared(),
41  " PY_twist_squared"));
42 }
43 
44 template<typename ppT>
45 void mnt_precompute_G1_gadget<ppT>::generate_r1cs_constraints()
46 {
47  /* the same for neither ppT = mnt4 nor ppT = mnt6 */
48 }
49 
50 template<typename ppT>
51 void mnt_precompute_G1_gadget<ppT>::generate_r1cs_witness()
52 {
53  // the same for both ppT = mnt4 and ppT = mnt6
54  precomp.PY_twist_squared->evaluate();
55 }
56 
57 template<typename ppT> mnt_G2_precomputation<ppT>::mnt_G2_precomputation() {}
58 
59 template<typename ppT>
60 mnt_G2_precomputation<ppT>::mnt_G2_precomputation(
61  protoboard<FieldT> &pb,
62  const libff::G2<other_curve<ppT>> &Q_val,
63  const std::string &annotation_prefix)
64 {
65  Q.reset(new G2_variable<ppT>(pb, Q_val, FMT(annotation_prefix, " Q")));
66  const libff::affine_ate_G2_precomp<other_curve<ppT>> native_precomp =
67  other_curve<ppT>::affine_ate_precompute_G2(Q_val);
68 
69  // the last precomp remains for convenient programming
70  coeffs.resize(native_precomp.coeffs.size() + 1);
71  for (size_t i = 0; i < native_precomp.coeffs.size(); ++i) {
72  coeffs[i].reset(new mnt_precompute_G2_gadget_coeffs<ppT>());
73  coeffs[i]->RX.reset(new Fqe_variable<ppT>(
74  pb,
75  native_precomp.coeffs[i].old_RX,
76  FMT(annotation_prefix, " RX")));
77  coeffs[i]->RY.reset(new Fqe_variable<ppT>(
78  pb,
79  native_precomp.coeffs[i].old_RY,
80  FMT(annotation_prefix, " RY")));
81  coeffs[i]->gamma.reset(new Fqe_variable<ppT>(
82  pb,
83  native_precomp.coeffs[i].gamma,
84  FMT(annotation_prefix, " gamma")));
85  coeffs[i]->gamma_X.reset(new Fqe_variable<ppT>(
86  pb,
87  native_precomp.coeffs[i].gamma_X,
88  FMT(annotation_prefix, " gamma_X")));
89  }
90 }
91 
92 template<typename ppT>
93 mnt_precompute_G2_gadget_coeffs<ppT>::mnt_precompute_G2_gadget_coeffs()
94 {
95  // we will be filled in precomputed case of precompute_G2_gadget, so do
96  // nothing here
97 }
98 
99 template<typename ppT>
100 mnt_precompute_G2_gadget_coeffs<ppT>::mnt_precompute_G2_gadget_coeffs(
101  protoboard<FieldT> &pb, const std::string &annotation_prefix)
102 {
103  RX.reset(new Fqe_variable<ppT>(pb, FMT(annotation_prefix, " RX")));
104  RY.reset(new Fqe_variable<ppT>(pb, FMT(annotation_prefix, " RY")));
105  gamma.reset(new Fqe_variable<ppT>(pb, FMT(annotation_prefix, " gamma")));
106  gamma_X.reset(
107  new Fqe_variable<ppT>(pb, FMT(annotation_prefix, " gamma_X")));
108 }
109 
110 template<typename ppT>
111 mnt_precompute_G2_gadget_coeffs<ppT>::mnt_precompute_G2_gadget_coeffs(
112  protoboard<FieldT> &pb,
113  const G2_variable<ppT> &Q,
114  const std::string &annotation_prefix)
115 {
116  RX.reset(new Fqe_variable<ppT>(*(Q.X)));
117  RY.reset(new Fqe_variable<ppT>(*(Q.Y)));
118  gamma.reset(new Fqe_variable<ppT>(pb, FMT(annotation_prefix, " gamma")));
119  gamma_X.reset(
120  new Fqe_variable<ppT>(pb, FMT(annotation_prefix, " gamma_X")));
121 }
122 
123 /*
124  QX and QY -- X and Y coordinates of Q
125 
126  initialization:
127  coeffs[0].RX = QX
128  coeffs[0].RY = QY
129 
130  G2_precompute_doubling_step relates coeffs[i] and coeffs[i+1] as follows
131 
132  coeffs[i]
133  gamma = (3 * RX^2 + twist_coeff_a) * (2*RY).inverse()
134  gamma_X = gamma * RX
135 
136  coeffs[i+1]
137  RX = prev_gamma^2 - (2*prev_RX)
138  RY = prev_gamma * (prev_RX - RX) - prev_RY
139  */
140 
141 template<typename ppT>
142 mnt_precompute_G2_gadget_doubling_step<ppT>::
143  mnt_precompute_G2_gadget_doubling_step(
144  protoboard<FieldT> &pb,
145  const mnt_precompute_G2_gadget_coeffs<ppT> &cur,
146  const mnt_precompute_G2_gadget_coeffs<ppT> &next,
147  const std::string &annotation_prefix)
148  : gadget<FieldT>(pb, annotation_prefix), cur(cur), next(next)
149 {
150  RXsquared.reset(
151  new Fqe_variable<ppT>(pb, FMT(annotation_prefix, " RXsquared")));
152  compute_RXsquared.reset(new Fqe_sqr_gadget<ppT>(
153  pb,
154  *(cur.RX),
155  *RXsquared,
156  FMT(annotation_prefix, " compute_RXsquared")));
157  three_RXsquared_plus_a.reset(new Fqe_variable<ppT>(
158  (*RXsquared) * FieldT(3) + libff::G2<other_curve<ppT>>::coeff_a));
159  two_RY.reset(new Fqe_variable<ppT>(*(cur.RY) * FieldT(2)));
160 
161  compute_gamma.reset(new Fqe_mul_gadget<ppT>(
162  pb,
163  *(cur.gamma),
164  *two_RY,
165  *three_RXsquared_plus_a,
166  FMT(annotation_prefix, " compute_gamma")));
167  compute_gamma_X.reset(new Fqe_mul_gadget<ppT>(
168  pb,
169  *(cur.gamma),
170  *(cur.RX),
171  *(cur.gamma_X),
172  FMT(annotation_prefix, " compute_gamma_X")));
173 
174  next_RX_plus_two_RX.reset(
175  new Fqe_variable<ppT>(*(next.RX) + *(cur.RX) * FieldT(2)));
176  compute_next_RX.reset(new Fqe_sqr_gadget<ppT>(
177  pb,
178  *(cur.gamma),
179  *next_RX_plus_two_RX,
180  FMT(annotation_prefix, " compute_next_RX")));
181 
182  RX_minus_next_RX.reset(
183  new Fqe_variable<ppT>(*(cur.RX) + *(next.RX) * (-FieldT::one())));
184  RY_plus_next_RY.reset(new Fqe_variable<ppT>(*(cur.RY) + *(next.RY)));
185  compute_next_RY.reset(new Fqe_mul_gadget<ppT>(
186  pb,
187  *(cur.gamma),
188  *RX_minus_next_RX,
189  *RY_plus_next_RY,
190  FMT(annotation_prefix, " compute_next_RY")));
191 }
192 
193 template<typename ppT>
194 void mnt_precompute_G2_gadget_doubling_step<ppT>::generate_r1cs_constraints()
195 {
196  compute_RXsquared->generate_r1cs_constraints();
197  compute_gamma->generate_r1cs_constraints();
198  compute_gamma_X->generate_r1cs_constraints();
199  compute_next_RX->generate_r1cs_constraints();
200  compute_next_RY->generate_r1cs_constraints();
201 }
202 
203 template<typename ppT>
204 void mnt_precompute_G2_gadget_doubling_step<ppT>::generate_r1cs_witness()
205 {
206  compute_RXsquared->generate_r1cs_witness();
207  two_RY->evaluate();
208  three_RXsquared_plus_a->evaluate();
209 
210  const FqeT three_RXsquared_plus_a_val =
211  three_RXsquared_plus_a->get_element();
212  const FqeT two_RY_val = two_RY->get_element();
213  const FqeT gamma_val = three_RXsquared_plus_a_val * two_RY_val.inverse();
214  cur.gamma->generate_r1cs_witness(gamma_val);
215 
216  compute_gamma->generate_r1cs_witness();
217  compute_gamma_X->generate_r1cs_witness();
218 
219  const FqeT RX_val = cur.RX->get_element();
220  const FqeT RY_val = cur.RY->get_element();
221  const FqeT next_RX_val = gamma_val.squared() - RX_val - RX_val;
222  const FqeT next_RY_val = gamma_val * (RX_val - next_RX_val) - RY_val;
223 
224  next.RX->generate_r1cs_witness(next_RX_val);
225  next.RY->generate_r1cs_witness(next_RY_val);
226 
227  RX_minus_next_RX->evaluate();
228  RY_plus_next_RY->evaluate();
229 
230  compute_next_RX->generate_r1cs_witness();
231  compute_next_RY->generate_r1cs_witness();
232 }
233 
234 /*
235  G2_precompute_addition_step relates coeffs[i] and coeffs[i+1] as follows
236 
237  coeffs[i]
238  gamma = (RY - QY) * (RX - QX).inverse()
239  gamma_X = gamma * QX
240 
241  coeffs[i+1]
242  RX = prev_gamma^2 - (prev_RX + QX)
243  RY = prev_gamma * (prev_RX - RX) - prev_RY
244 
245  (where prev_ in [i+1] refer to things from [i])
246 
247  If invert_Q is set to true: use -QY in place of QY everywhere above.
248  */
249 template<typename ppT>
250 mnt_precompute_G2_gadget_addition_step<ppT>::
251  mnt_precompute_G2_gadget_addition_step(
252  protoboard<FieldT> &pb,
253  const bool invert_Q,
254  const mnt_precompute_G2_gadget_coeffs<ppT> &cur,
255  const mnt_precompute_G2_gadget_coeffs<ppT> &next,
256  const G2_variable<ppT> &Q,
257  const std::string &annotation_prefix)
258  : gadget<FieldT>(pb, annotation_prefix)
259  , invert_Q(invert_Q)
260  , cur(cur)
261  , next(next)
262  , Q(Q)
263 {
264  RY_minus_QY.reset(new Fqe_variable<ppT>(
265  *(cur.RY) + *(Q.Y) * (!invert_Q ? -FieldT::one() : FieldT::one())));
266 
267  RX_minus_QX.reset(
268  new Fqe_variable<ppT>(*(cur.RX) + *(Q.X) * (-FieldT::one())));
269  compute_gamma.reset(new Fqe_mul_gadget<ppT>(
270  pb,
271  *(cur.gamma),
272  *RX_minus_QX,
273  *RY_minus_QY,
274  FMT(annotation_prefix, " compute_gamma")));
275  compute_gamma_X.reset(new Fqe_mul_gadget<ppT>(
276  pb,
277  *(cur.gamma),
278  *(Q.X),
279  *(cur.gamma_X),
280  FMT(annotation_prefix, " compute_gamma_X")));
281 
282  next_RX_plus_RX_plus_QX.reset(
283  new Fqe_variable<ppT>(*(next.RX) + *(cur.RX) + *(Q.X)));
284  compute_next_RX.reset(new Fqe_sqr_gadget<ppT>(
285  pb,
286  *(cur.gamma),
287  *next_RX_plus_RX_plus_QX,
288  FMT(annotation_prefix, " compute_next_RX")));
289 
290  RX_minus_next_RX.reset(
291  new Fqe_variable<ppT>(*(cur.RX) + *(next.RX) * (-FieldT::one())));
292  RY_plus_next_RY.reset(new Fqe_variable<ppT>(*(cur.RY) + *(next.RY)));
293  compute_next_RY.reset(new Fqe_mul_gadget<ppT>(
294  pb,
295  *(cur.gamma),
296  *RX_minus_next_RX,
297  *RY_plus_next_RY,
298  FMT(annotation_prefix, " compute_next_RY")));
299 }
300 
301 template<typename ppT>
302 void mnt_precompute_G2_gadget_addition_step<ppT>::generate_r1cs_constraints()
303 {
304  compute_gamma->generate_r1cs_constraints();
305  compute_gamma_X->generate_r1cs_constraints();
306  compute_next_RX->generate_r1cs_constraints();
307  compute_next_RY->generate_r1cs_constraints();
308 }
309 
310 template<typename ppT>
311 void mnt_precompute_G2_gadget_addition_step<ppT>::generate_r1cs_witness()
312 {
313  RY_minus_QY->evaluate();
314  RX_minus_QX->evaluate();
315 
316  const FqeT RY_minus_QY_val = RY_minus_QY->get_element();
317  const FqeT RX_minus_QX_val = RX_minus_QX->get_element();
318  const FqeT gamma_val = RY_minus_QY_val * RX_minus_QX_val.inverse();
319  cur.gamma->generate_r1cs_witness(gamma_val);
320 
321  compute_gamma->generate_r1cs_witness();
322  compute_gamma_X->generate_r1cs_witness();
323 
324  const FqeT RX_val = cur.RX->get_element();
325  const FqeT RY_val = cur.RY->get_element();
326  const FqeT QX_val = Q.X->get_element();
327  const FqeT next_RX_val = gamma_val.squared() - RX_val - QX_val;
328  const FqeT next_RY_val = gamma_val * (RX_val - next_RX_val) - RY_val;
329 
330  next.RX->generate_r1cs_witness(next_RX_val);
331  next.RY->generate_r1cs_witness(next_RY_val);
332 
333  next_RX_plus_RX_plus_QX->evaluate();
334  RX_minus_next_RX->evaluate();
335  RY_plus_next_RY->evaluate();
336 
337  compute_next_RX->generate_r1cs_witness();
338  compute_next_RY->generate_r1cs_witness();
339 }
340 
341 template<typename ppT>
342 mnt_precompute_G2_gadget<ppT>::mnt_precompute_G2_gadget(
343  protoboard<FieldT> &pb,
344  const G2_variable<ppT> &Q,
345  mnt_G2_precomputation<ppT> &precomp, // will allocate this inside
346  const std::string &annotation_prefix)
347  : gadget<FieldT>(pb, annotation_prefix), precomp(precomp)
348 {
349  precomp.Q.reset(new G2_variable<ppT>(Q));
350 
351  const auto &loop_count = mnt_pairing_params<ppT>::pairing_loop_count;
352  // the last RX/RY are unused in Miller loop, but will need to get
353  // allocated somehow
354  size_t coeff_count = 1;
355  this->add_count = 0;
356  this->dbl_count = 0;
357 
358  bool found_nonzero = false;
359  std::vector<long> NAF = find_wnaf(1, loop_count);
360  for (long i = NAF.size() - 1; i >= 0; --i) {
361  if (!found_nonzero) {
362  // this skips the MSB itself
363  found_nonzero |= (NAF[i] != 0);
364  continue;
365  }
366 
367  ++dbl_count;
368  ++coeff_count;
369 
370  if (NAF[i] != 0) {
371  ++add_count;
372  ++coeff_count;
373  }
374  }
375 
376  precomp.coeffs.resize(coeff_count);
377  addition_steps.resize(add_count);
378  doubling_steps.resize(dbl_count);
379 
380  precomp.coeffs[0].reset(new mnt_precompute_G2_gadget_coeffs<ppT>(
381  pb, Q, FMT(annotation_prefix, " coeffs_0")));
382  for (size_t i = 1; i < coeff_count; ++i) {
383  precomp.coeffs[i].reset(new mnt_precompute_G2_gadget_coeffs<ppT>(
384  pb, FMT(annotation_prefix, " coeffs_%zu", i)));
385  }
386 
387  size_t add_id = 0;
388  size_t dbl_id = 0;
389  size_t coeff_id = 0;
390 
391  found_nonzero = false;
392  for (long i = NAF.size() - 1; i >= 0; --i) {
393  if (!found_nonzero) {
394  // this skips the MSB itself
395  found_nonzero |= (NAF[i] != 0);
396  continue;
397  }
398 
399  doubling_steps[dbl_id].reset(
400  new mnt_precompute_G2_gadget_doubling_step<ppT>(
401  pb,
402  *(precomp.coeffs[coeff_id]),
403  *(precomp.coeffs[coeff_id + 1]),
404  FMT(annotation_prefix, " doubling_steps_%zu", dbl_id)));
405  ++dbl_id;
406  ++coeff_id;
407 
408  if (NAF[i] != 0) {
409  addition_steps[add_id].reset(
410  new mnt_precompute_G2_gadget_addition_step<ppT>(
411  pb,
412  NAF[i] < 0,
413  *(precomp.coeffs[coeff_id]),
414  *(precomp.coeffs[coeff_id + 1]),
415  Q,
416  FMT(annotation_prefix, " addition_steps_%zu", add_id)));
417  ++add_id;
418  ++coeff_id;
419  }
420  }
421 }
422 
423 template<typename ppT>
424 void mnt_precompute_G2_gadget<ppT>::generate_r1cs_constraints()
425 {
426  for (size_t i = 0; i < dbl_count; ++i) {
427  doubling_steps[i]->generate_r1cs_constraints();
428  }
429 
430  for (size_t i = 0; i < add_count; ++i) {
431  addition_steps[i]->generate_r1cs_constraints();
432  }
433 }
434 
435 template<typename ppT>
436 void mnt_precompute_G2_gadget<ppT>::generate_r1cs_witness()
437 {
438  precomp.coeffs[0]->RX->generate_r1cs_witness(precomp.Q->X->get_element());
439  precomp.coeffs[0]->RY->generate_r1cs_witness(precomp.Q->Y->get_element());
440 
441  const auto &loop_count = mnt_pairing_params<ppT>::pairing_loop_count;
442 
443  size_t add_id = 0;
444  size_t dbl_id = 0;
445 
446  bool found_nonzero = false;
447  std::vector<long> NAF = find_wnaf(1, loop_count);
448  for (long i = NAF.size() - 1; i >= 0; --i) {
449  if (!found_nonzero) {
450  // this skips the MSB itself
451  found_nonzero |= (NAF[i] != 0);
452  continue;
453  }
454 
455  doubling_steps[dbl_id]->generate_r1cs_witness();
456  ++dbl_id;
457 
458  if (NAF[i] != 0) {
459  addition_steps[add_id]->generate_r1cs_witness();
460  ++add_id;
461  }
462  }
463 }
464 
465 } // namespace libsnark
466 
467 #endif // LIBSNARK_GADGETLIB1_GADGETS_PAIRING_MNT_MNT_PRECOMPUTATION_TCC_
Generated on Wed Jan 25 2023 11:05:58 for Clearmatics Libsnark by   doxygen 1.8.17