Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
weierstrass_g1_gadget.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for G1 gadgets.
5 
6  See weierstrass_g1_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 WEIERSTRASS_G1_GADGET_TCC_
15 #define WEIERSTRASS_G1_GADGET_TCC_
16 
17 namespace libsnark
18 {
19 
20 template<typename ppT>
21 G1_variable<ppT>::G1_variable(
22  protoboard<FieldT> &pb, const std::string &annotation_prefix)
23  : gadget<FieldT>(pb, annotation_prefix)
24 {
25  pb_variable<FieldT> X_var, Y_var;
26 
27  X_var.allocate(pb, FMT(annotation_prefix, " X"));
28  Y_var.allocate(pb, FMT(annotation_prefix, " Y"));
29 
30  X = pb_linear_combination<FieldT>(X_var);
31  Y = pb_linear_combination<FieldT>(Y_var);
32 
33  all_vars.emplace_back(X);
34  all_vars.emplace_back(Y);
35 }
36 
37 template<typename ppT>
38 G1_variable<ppT>::G1_variable(
39  protoboard<FieldT> &pb,
40  const libff::G1<other_curve<ppT>> &P,
41  const std::string &annotation_prefix)
42  : gadget<FieldT>(pb, annotation_prefix)
43 {
44  libff::G1<other_curve<ppT>> Pcopy = P;
45  Pcopy.to_affine_coordinates();
46 
47  X.assign(pb, Pcopy.X);
48  Y.assign(pb, Pcopy.Y);
49  X.evaluate(pb);
50  Y.evaluate(pb);
51  all_vars.emplace_back(X);
52  all_vars.emplace_back(Y);
53 }
54 
55 template<typename ppT>
56 G1_variable<ppT>::G1_variable(
57  protoboard<FieldT> &pb,
58  const pb_linear_combination<FieldT> &X,
59  const pb_linear_combination<FieldT> &Y,
60  const std::string &annotation_prefix)
61  : gadget<FieldT>(pb, annotation_prefix), X(X), Y(Y)
62 {
63  all_vars.emplace_back(X);
64  all_vars.emplace_back(Y);
65 }
66 
67 template<typename ppT> G1_variable<ppT> G1_variable<ppT>::operator-() const
68 {
69  pb_linear_combination<FieldT> minus_Y;
70  minus_Y.assign(this->pb, -Y);
71  return G1_variable<ppT>(
72  this->pb, X, minus_Y, FMT(this->annotation_prefix, " negative"));
73 }
74 
75 template<typename ppT>
76 void G1_variable<ppT>::generate_r1cs_witness(
77  const libff::G1<other_curve<ppT>> &el)
78 {
79  libff::G1<other_curve<ppT>> el_normalized = el;
80  el_normalized.to_affine_coordinates();
81 
82  this->pb.lc_val(X) = el_normalized.X;
83  this->pb.lc_val(Y) = el_normalized.Y;
84 }
85 
86 template<typename ppT>
87 libff::G1<other_curve<ppT>> G1_variable<ppT>::get_element() const
88 {
89  using nppT = other_curve<ppT>;
90  return libff::G1<nppT>(
91  this->pb.lc_val(this->X),
92  this->pb.lc_val(this->Y),
93  libff::Fq<nppT>::one());
94 }
95 
96 template<typename ppT> size_t G1_variable<ppT>::size_in_bits()
97 {
98  return 2 * FieldT::size_in_bits();
99 }
100 
101 template<typename ppT> size_t G1_variable<ppT>::num_variables() { return 2; }
102 
103 template<typename ppT>
104 G1_variable_selector_gadget<ppT>::G1_variable_selector_gadget(
105  protoboard<Field> &pb,
106  const pb_linear_combination<Field> &selector,
107  const G1_variable<ppT> &zero_case,
108  const G1_variable<ppT> &one_case,
109  const G1_variable<ppT> &result,
110  const std::string &annotation_prefix)
111  : gadget<Field>(pb, annotation_prefix)
112  , selector(selector)
113  , zero_case(zero_case)
114  , one_case(one_case)
115  , result(result)
116 {
117 }
118 
119 template<typename ppT>
120 void G1_variable_selector_gadget<ppT>::generate_r1cs_constraints()
121 {
122  // For selector \in {0, 1}, and zero_case and one_case \in G_1, we
123  // require result \in G_1 to satisfy:
124  //
125  // result = one_case if selector = 1, and
126  // result = zero_case if selector = 0.
127  // or:
128  // result.X = selector * one_case.X + (1 - selector) * zero_case.X
129  // result.Y = selector * one_case.X + (1 - selector) * zero_case.Y
130  //
131  // This can be re-arranged in terms of a single constraint as
132  // follows:
133  //
134  // result.X = selector * one_case.X + (1 - selector) * zero_case.X
135  // = selector * (one_case.X - zero_case.X) + zero_case.X
136  // <=> result.X - zero_case.X = selector * (one_case.X - zero_case.X)
137  //
138  // (and similarly for result.Y)
139 
140  // selector * (one_case.X - zero_case.X) = result.X - zero_case.X
141  this->pb.add_r1cs_constraint(
142  r1cs_constraint<Field>(
143  selector, one_case.X - zero_case.X, result.X - zero_case.X),
144  FMT(this->annotation_prefix, " select X"));
145  // selector * (one_case.Y - zero_case.Y) = result.Y - zero_case.Y
146  this->pb.add_r1cs_constraint(
147  r1cs_constraint<Field>(
148  selector, one_case.Y - zero_case.Y, result.Y - zero_case.Y),
149  FMT(this->annotation_prefix, " select Y"));
150 }
151 
152 template<typename ppT>
153 void G1_variable_selector_gadget<ppT>::generate_r1cs_witness()
154 {
155  protoboard<Field> &pb = this->pb;
156  selector.evaluate(pb);
157 
158  zero_case.X.evaluate(pb);
159  zero_case.Y.evaluate(pb);
160  one_case.X.evaluate(pb);
161  one_case.Y.evaluate(pb);
162 
163  if (pb.lc_val(selector) == Field::one()) {
164  result.generate_r1cs_witness(one_case.get_element());
165  } else {
166  result.generate_r1cs_witness(zero_case.get_element());
167  }
168 }
169 
170 template<typename ppT>
171 G1_checker_gadget<ppT>::G1_checker_gadget(
172  protoboard<FieldT> &pb,
173  const G1_variable<ppT> &P,
174  const std::string &annotation_prefix)
175  : gadget<FieldT>(pb, annotation_prefix), P(P)
176 {
177  P_X_squared.allocate(pb, FMT(annotation_prefix, " P_X_squared"));
178  P_Y_squared.allocate(pb, FMT(annotation_prefix, " P_Y_squared"));
179 }
180 
181 template<typename ppT> void G1_checker_gadget<ppT>::generate_r1cs_constraints()
182 {
183  this->pb.add_r1cs_constraint(
184  r1cs_constraint<FieldT>({P.X}, {P.X}, {P_X_squared}),
185  FMT(this->annotation_prefix, " P_X_squared"));
186  this->pb.add_r1cs_constraint(
187  r1cs_constraint<FieldT>({P.Y}, {P.Y}, {P_Y_squared}),
188  FMT(this->annotation_prefix, " P_Y_squared"));
189  this->pb.add_r1cs_constraint(
190  r1cs_constraint<FieldT>(
191  {P.X},
192  {P_X_squared, ONE * libff::G1<other_curve<ppT>>::coeff_a},
193  {P_Y_squared, ONE * (-libff::G1<other_curve<ppT>>::coeff_b)}),
194  FMT(this->annotation_prefix, " curve_equation"));
195 }
196 
197 template<typename ppT> void G1_checker_gadget<ppT>::generate_r1cs_witness()
198 {
199  this->pb.val(P_X_squared) = this->pb.lc_val(P.X).squared();
200  this->pb.val(P_Y_squared) = this->pb.lc_val(P.Y).squared();
201 }
202 
203 template<typename ppT>
204 G1_add_gadget<ppT>::G1_add_gadget(
205  protoboard<FieldT> &pb,
206  const G1_variable<ppT> &A,
207  const G1_variable<ppT> &B,
208  const G1_variable<ppT> &result,
209  const std::string &annotation_prefix)
210  : gadget<FieldT>(pb, annotation_prefix), A(A), B(B), result(result)
211 {
212  /*
213  lambda = (B.y - A.y)/(B.x - A.x)
214  C.x = lambda^2 - A.x - B.x
215  C.y = lambda(A.x - C.x) - A.y
216 
217  Special cases:
218 
219  doubling: if B.y = A.y and B.x = A.x then lambda is unbound and
220  C = (lambda^2, lambda^3)
221 
222  addition of negative point: if B.y = -A.y and B.x = A.x then no
223  lambda can satisfy the first equation unless B.y - A.y = 0. But
224  then this reduces to doubling.
225 
226  So we need to check that A.x - B.x != 0, which can be done by
227  enforcing I * (B.x - A.x) = 1
228  */
229  lambda.allocate(pb, FMT(annotation_prefix, " lambda"));
230  inv.allocate(pb, FMT(annotation_prefix, " inv"));
231 }
232 
233 template<typename ppT> void G1_add_gadget<ppT>::generate_r1cs_constraints()
234 {
235  this->pb.add_r1cs_constraint(
236  r1cs_constraint<FieldT>({lambda}, {B.X, A.X * (-1)}, {B.Y, A.Y * (-1)}),
237  FMT(this->annotation_prefix, " calc_lambda"));
238 
239  this->pb.add_r1cs_constraint(
240  r1cs_constraint<FieldT>({lambda}, {lambda}, {result.X, A.X, B.X}),
241  FMT(this->annotation_prefix, " calc_X"));
242 
243  this->pb.add_r1cs_constraint(
244  r1cs_constraint<FieldT>(
245  {lambda}, {A.X, result.X * (-1)}, {result.Y, A.Y}),
246  FMT(this->annotation_prefix, " calc_Y"));
247 
248  this->pb.add_r1cs_constraint(
249  r1cs_constraint<FieldT>({inv}, {B.X, A.X * (-1)}, {ONE}),
250  FMT(this->annotation_prefix, " no_special_cases"));
251 }
252 
253 template<typename ppT> void G1_add_gadget<ppT>::generate_r1cs_witness()
254 {
255  const libff::Fr<ppT> Ax = this->pb.lc_val(A.X);
256  const libff::Fr<ppT> Bx = this->pb.lc_val(B.X);
257  const libff::Fr<ppT> Ay = this->pb.lc_val(A.Y);
258  const libff::Fr<ppT> By = this->pb.lc_val(B.Y);
259 
260  // Guard against the inverse operation failing.
261  if (Ax == Bx) {
262  throw std::runtime_error(
263  "A.X == B.X is not supported by G1_add_gadget");
264  }
265 
266  this->pb.val(inv) = (Bx - Ax).inverse();
267  this->pb.val(lambda) = (By - Ay) * this->pb.val(inv);
268  this->pb.lc_val(result.X) = this->pb.val(lambda).squared() - Ax - Bx;
269  this->pb.lc_val(result.Y) =
270  this->pb.val(lambda) * (Ax - this->pb.lc_val(result.X)) - Ay;
271 }
272 
273 template<typename ppT>
274 G1_dbl_gadget<ppT>::G1_dbl_gadget(
275  protoboard<FieldT> &pb,
276  const G1_variable<ppT> &A,
277  const G1_variable<ppT> &result,
278  const std::string &annotation_prefix)
279  : gadget<FieldT>(pb, annotation_prefix), A(A), result(result)
280 {
281  Xsquared.allocate(pb, FMT(annotation_prefix, " X_squared"));
282  lambda.allocate(pb, FMT(annotation_prefix, " lambda"));
283 }
284 
285 template<typename ppT> void G1_dbl_gadget<ppT>::generate_r1cs_constraints()
286 {
287  this->pb.add_r1cs_constraint(
288  r1cs_constraint<FieldT>({A.X}, {A.X}, {Xsquared}),
289  FMT(this->annotation_prefix, " calc_Xsquared"));
290 
291  this->pb.add_r1cs_constraint(
292  r1cs_constraint<FieldT>(
293  {lambda * 2},
294  {A.Y},
295  {Xsquared * 3, ONE * libff::G1<other_curve<ppT>>::coeff_a}),
296  FMT(this->annotation_prefix, " calc_lambda"));
297 
298  this->pb.add_r1cs_constraint(
299  r1cs_constraint<FieldT>({lambda}, {lambda}, {result.X, A.X * 2}),
300  FMT(this->annotation_prefix, " calc_X"));
301 
302  this->pb.add_r1cs_constraint(
303  r1cs_constraint<FieldT>(
304  {lambda}, {A.X, result.X * (-1)}, {result.Y, A.Y}),
305  FMT(this->annotation_prefix, " calc_Y"));
306 }
307 
308 template<typename ppT> void G1_dbl_gadget<ppT>::generate_r1cs_witness()
309 {
310  this->pb.val(Xsquared) = this->pb.lc_val(A.X).squared();
311  this->pb.val(lambda) = (FieldT(3) * this->pb.val(Xsquared) +
312  libff::G1<other_curve<ppT>>::coeff_a) *
313  (FieldT(2) * this->pb.lc_val(A.Y)).inverse();
314  this->pb.lc_val(result.X) =
315  this->pb.val(lambda).squared() - FieldT(2) * this->pb.lc_val(A.X);
316  this->pb.lc_val(result.Y) =
317  this->pb.val(lambda) *
318  (this->pb.lc_val(A.X) - this->pb.lc_val(result.X)) -
319  this->pb.lc_val(A.Y);
320 }
321 
322 template<typename ppT>
323 G1_multiscalar_mul_gadget<ppT>::G1_multiscalar_mul_gadget(
324  protoboard<FieldT> &pb,
325  const G1_variable<ppT> &base,
326  const pb_variable_array<FieldT> &scalars,
327  const size_t elt_size,
328  const std::vector<G1_variable<ppT>> &points,
329  const G1_variable<ppT> &result,
330  const std::string &annotation_prefix)
331  : gadget<FieldT>(pb, annotation_prefix)
332  , base(base)
333  , scalars(scalars)
334  , points(points)
335  , result(result)
336  , elt_size(elt_size)
337  , num_points(points.size())
338  , scalar_size(scalars.size())
339 {
340  assert(num_points >= 1);
341  assert(num_points * elt_size == scalar_size);
342 
343  for (size_t i = 0; i < num_points; ++i) {
344  points_and_powers.emplace_back(points[i]);
345  for (size_t j = 0; j < elt_size - 1; ++j) {
346  points_and_powers.emplace_back(G1_variable<ppT>(
347  pb,
348  FMT(annotation_prefix,
349  " points_%zu_times_2_to_%zu",
350  i,
351  j + 1)));
352  doublers.emplace_back(G1_dbl_gadget<ppT>(
353  pb,
354  points_and_powers[i * elt_size + j],
355  points_and_powers[i * elt_size + j + 1],
356  FMT(annotation_prefix, " double_%zu_to_2_to_%zu", i, j + 1)));
357  }
358  }
359 
360  chosen_results.emplace_back(base);
361  for (size_t i = 0; i < scalar_size; ++i) {
362  computed_results.emplace_back(G1_variable<ppT>(
363  pb, FMT(annotation_prefix, " computed_results_%zu")));
364  if (i < scalar_size - 1) {
365  chosen_results.emplace_back(G1_variable<ppT>(
366  pb, FMT(annotation_prefix, " chosen_results_%zu")));
367  } else {
368  chosen_results.emplace_back(result);
369  }
370 
371  adders.emplace_back(G1_add_gadget<ppT>(
372  pb,
373  chosen_results[i],
374  points_and_powers[i],
375  computed_results[i],
376  FMT(annotation_prefix, " adders_%zu")));
377  }
378 }
379 
380 template<typename ppT>
381 void G1_multiscalar_mul_gadget<ppT>::generate_r1cs_constraints()
382 {
383  const size_t num_constraints_before = this->pb.num_constraints();
384 
385  for (size_t i = 0; i < scalar_size - num_points; ++i) {
386  doublers[i].generate_r1cs_constraints();
387  }
388 
389  for (size_t i = 0; i < scalar_size; ++i) {
390  adders[i].generate_r1cs_constraints();
391 
392  /*
393  chosen_results[i+1].X = scalars[i] * computed_results[i].X +
394  (1-scalars[i]) * chosen_results[i].X chosen_results[i+1].X -
395  chosen_results[i].X = scalars[i] * (computed_results[i].X -
396  chosen_results[i].X)
397  */
398  this->pb.add_r1cs_constraint(
399  r1cs_constraint<FieldT>(
400  scalars[i],
401  computed_results[i].X - chosen_results[i].X,
402  chosen_results[i + 1].X - chosen_results[i].X),
403  FMT(this->annotation_prefix, " chosen_results_%zu_X", i + 1));
404  this->pb.add_r1cs_constraint(
405  r1cs_constraint<FieldT>(
406  scalars[i],
407  computed_results[i].Y - chosen_results[i].Y,
408  chosen_results[i + 1].Y - chosen_results[i].Y),
409  FMT(this->annotation_prefix, " chosen_results_%zu_Y", i + 1));
410  }
411 
412  const size_t num_constraints_after = this->pb.num_constraints();
413  assert(
414  num_constraints_after - num_constraints_before ==
415  4 * (scalar_size - num_points) + (4 + 2) * scalar_size);
416  libff::UNUSED(num_constraints_before);
417  libff::UNUSED(num_constraints_after);
418 }
419 
420 template<typename ppT>
421 void G1_multiscalar_mul_gadget<ppT>::generate_r1cs_witness()
422 {
423  for (size_t i = 0; i < scalar_size - num_points; ++i) {
424  doublers[i].generate_r1cs_witness();
425  }
426 
427  for (size_t i = 0; i < scalar_size; ++i) {
428  adders[i].generate_r1cs_witness();
429  this->pb.lc_val(chosen_results[i + 1].X) =
430  (this->pb.val(scalars[i]) == libff::Fr<ppT>::zero()
431  ? this->pb.lc_val(chosen_results[i].X)
432  : this->pb.lc_val(computed_results[i].X));
433  this->pb.lc_val(chosen_results[i + 1].Y) =
434  (this->pb.val(scalars[i]) == libff::Fr<ppT>::zero()
435  ? this->pb.lc_val(chosen_results[i].Y)
436  : this->pb.lc_val(computed_results[i].Y));
437  }
438 }
439 
440 } // namespace libsnark
441 
442 #endif // WEIERSTRASS_G1_GADGET_TCC_
Generated on Wed Jan 25 2023 11:05:57 for Clearmatics Libsnark by   doxygen 1.8.17