Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
fp2_gadgets.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for Fp2 gadgets.
5 
6  See fp2_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 FP2_GADGETS_TCC_
15 #define FP2_GADGETS_TCC_
16 
17 namespace libsnark
18 {
19 
20 template<typename Fp2T>
21 Fp2_variable<Fp2T>::Fp2_variable(
22  protoboard<FieldT> &pb, const std::string &annotation_prefix)
23  : gadget<FieldT>(pb, annotation_prefix)
24 {
25  pb_variable<FieldT> c0_var, c1_var;
26  c0_var.allocate(pb, FMT(annotation_prefix, " c0"));
27  c1_var.allocate(pb, FMT(annotation_prefix, " c1"));
28 
29  c0 = pb_linear_combination<FieldT>(c0_var);
30  c1 = pb_linear_combination<FieldT>(c1_var);
31 
32  all_vars.emplace_back(c0);
33  all_vars.emplace_back(c1);
34 }
35 
36 template<typename Fp2T>
37 Fp2_variable<Fp2T>::Fp2_variable(
38  protoboard<FieldT> &pb,
39  const Fp2T &el,
40  const std::string &annotation_prefix)
41  : gadget<FieldT>(pb, annotation_prefix)
42 {
43  c0.assign(pb, el.coeffs[0]);
44  c1.assign(pb, el.coeffs[1]);
45 
46  c0.evaluate(pb);
47  c1.evaluate(pb);
48 
49  all_vars.emplace_back(c0);
50  all_vars.emplace_back(c1);
51 }
52 
53 template<typename Fp2T>
54 Fp2_variable<Fp2T>::Fp2_variable(
55  protoboard<FieldT> &pb,
56  const Fp2T &el,
57  const pb_linear_combination<FieldT> &coeff,
58  const std::string &annotation_prefix)
59  : gadget<FieldT>(pb, annotation_prefix)
60 {
61  c0.assign(pb, el.coeffs[0] * coeff);
62  c1.assign(pb, el.coeffs[1] * coeff);
63 
64  all_vars.emplace_back(c0);
65  all_vars.emplace_back(c1);
66 }
67 
68 template<typename Fp2T>
69 Fp2_variable<Fp2T>::Fp2_variable(
70  protoboard<FieldT> &pb,
71  const pb_linear_combination<FieldT> &c0,
72  const pb_linear_combination<FieldT> &c1,
73  const std::string &annotation_prefix)
74  : gadget<FieldT>(pb, annotation_prefix), c0(c0), c1(c1)
75 {
76  all_vars.emplace_back(c0);
77  all_vars.emplace_back(c1);
78 }
79 
80 template<typename Fp2T>
81 void Fp2_variable<Fp2T>::generate_r1cs_equals_const_constraints(const Fp2T &el)
82 {
83  this->pb.add_r1cs_constraint(
84  r1cs_constraint<FieldT>(1, el.coeffs[0], c0),
85  FMT(this->annotation_prefix, " c0"));
86  this->pb.add_r1cs_constraint(
87  r1cs_constraint<FieldT>(1, el.coeffs[1], c1),
88  FMT(this->annotation_prefix, " c1"));
89 }
90 
91 template<typename Fp2T>
92 void Fp2_variable<Fp2T>::generate_r1cs_witness(const Fp2T &el)
93 {
94  this->pb.lc_val(c0) = el.coeffs[0];
95  this->pb.lc_val(c1) = el.coeffs[1];
96 }
97 
98 template<typename Fp2T> Fp2T Fp2_variable<Fp2T>::get_element() const
99 {
100  Fp2T el;
101  el.coeffs[0] = this->pb.lc_val(c0);
102  el.coeffs[1] = this->pb.lc_val(c1);
103  return el;
104 }
105 
106 template<typename Fp2T>
107 Fp2_variable<Fp2T> Fp2_variable<Fp2T>::operator*(const FieldT &coeff) const
108 {
109  pb_linear_combination<FieldT> new_c0, new_c1;
110  new_c0.assign(this->pb, this->c0 * coeff);
111  new_c1.assign(this->pb, this->c1 * coeff);
112  return Fp2_variable<Fp2T>(
113  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " operator*"));
114 }
115 
116 template<typename Fp2T>
117 Fp2_variable<Fp2T> Fp2_variable<Fp2T>::operator*(const Fp2T &fp2_const) const
118 {
119  pb_linear_combination<FieldT> new_c0, new_c1;
120  new_c0.assign(
121  this->pb,
122  this->c0 * fp2_const.coeffs[0] +
123  (Fp2T::non_residue) * this->c1 * fp2_const.coeffs[1]);
124  new_c1.assign(
125  this->pb,
126  this->c1 * fp2_const.coeffs[0] + this->c0 * fp2_const.coeffs[1]);
127  return Fp2_variable<Fp2T>(
128  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " operator*"));
129 }
130 
131 template<typename Fp2T>
132 Fp2_variable<Fp2T> Fp2_variable<Fp2T>::operator+(
133  const Fp2_variable<Fp2T> &other) const
134 {
135  pb_linear_combination<FieldT> new_c0, new_c1;
136  new_c0.assign(this->pb, this->c0 + other.c0);
137  new_c1.assign(this->pb, this->c1 + other.c1);
138  return Fp2_variable<Fp2T>(
139  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " operator+"));
140 }
141 
142 template<typename Fp2T>
143 Fp2_variable<Fp2T> Fp2_variable<Fp2T>::operator+(const Fp2T &fp2_const) const
144 {
145  pb_linear_combination<FieldT> new_c0, new_c1;
146  new_c0.assign(this->pb, this->c0 + fp2_const.coeffs[0]);
147  new_c1.assign(this->pb, this->c1 + fp2_const.coeffs[1]);
148  return Fp2_variable<Fp2T>(
149  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " operator+"));
150 }
151 
152 template<typename Fp2T>
153 Fp2_variable<Fp2T> Fp2_variable<Fp2T>::operator-(
154  const Fp2_variable<Fp2T> &other) const
155 {
156  pb_linear_combination<FieldT> new_c0, new_c1;
157  new_c0.assign(this->pb, this->c0 - other.c0);
158  new_c1.assign(this->pb, this->c1 - other.c1);
159  return Fp2_variable<Fp2T>(
160  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " operator-"));
161 }
162 
163 template<typename Fp2T> Fp2_variable<Fp2T> Fp2_variable<Fp2T>::operator-() const
164 {
165  pb_linear_combination<FieldT> new_c0, new_c1;
166  new_c0.assign(this->pb, -this->c0);
167  new_c1.assign(this->pb, -this->c1);
168  return Fp2_variable<Fp2T>(
169  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " operator-"));
170 }
171 
172 template<typename Fp2T> Fp2_variable<Fp2T> Fp2_variable<Fp2T>::mul_by_X() const
173 {
174  pb_linear_combination<FieldT> new_c0, new_c1;
175  new_c0.assign(this->pb, this->c1 * Fp2T::non_residue);
176  new_c1.assign(this->pb, this->c0);
177  return Fp2_variable<Fp2T>(
178  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " mul_by_X"));
179 }
180 
181 template<typename Fp2T>
182 Fp2_variable<Fp2T> Fp2_variable<Fp2T>::frobenius_map(size_t power) const
183 {
184  pb_linear_combination<FieldT> new_c0, new_c1;
185  new_c0.assign(this->pb, this->c0);
186  new_c1.assign(this->pb, this->c1 * Fp2T::Frobenius_coeffs_c1[power % 2]);
187  return Fp2_variable<Fp2T>(
188  this->pb, new_c0, new_c1, FMT(this->annotation_prefix, " frobenius"));
189 }
190 
191 template<typename Fp2T> void Fp2_variable<Fp2T>::evaluate() const
192 {
193  c0.evaluate(this->pb);
194  c1.evaluate(this->pb);
195 }
196 
197 template<typename Fp2T> bool Fp2_variable<Fp2T>::is_constant() const
198 {
199  return (c0.is_constant() && c1.is_constant());
200 }
201 
202 template<typename Fp2T> size_t Fp2_variable<Fp2T>::size_in_bits()
203 {
204  return 2 * FieldT::size_in_bits();
205 }
206 
207 template<typename Fp2T> size_t Fp2_variable<Fp2T>::num_variables() { return 2; }
208 
209 template<typename Fp2T>
210 Fp2_mul_gadget<Fp2T>::Fp2_mul_gadget(
211  protoboard<FieldT> &pb,
212  const Fp2_variable<Fp2T> &A,
213  const Fp2_variable<Fp2T> &B,
214  const Fp2_variable<Fp2T> &result,
215  const std::string &annotation_prefix)
216  : gadget<FieldT>(pb, annotation_prefix), A(A), B(B), result(result)
217 {
218  v1.allocate(pb, FMT(annotation_prefix, " v1"));
219 }
220 
221 template<typename Fp2T> void Fp2_mul_gadget<Fp2T>::generate_r1cs_constraints()
222 {
223  /*
224  Karatsuba multiplication for Fp2:
225  v0 = A.c0 * B.c0
226  v1 = A.c1 * B.c1
227  result.c0 = v0 + non_residue * v1
228  result.c1 = (A.c0 + A.c1) * (B.c0 + B.c1) - v0 - v1
229 
230  Enforced with 3 constraints:
231  A.c1 * B.c1 = v1
232  A.c0 * B.c0 = result.c0 - non_residue * v1
233  (A.c0+A.c1)*(B.c0+B.c1) = result.c1 + result.c0 + (1 - non_residue)
234  * v1
235 
236  Reference:
237  "Multiplication and Squaring on Pairing-Friendly Fields"
238  Devegili, OhEigeartaigh, Scott, Dahab
239  */
240  this->pb.add_r1cs_constraint(
241  r1cs_constraint<FieldT>(A.c1, B.c1, v1),
242  FMT(this->annotation_prefix, " v1"));
243  this->pb.add_r1cs_constraint(
244  r1cs_constraint<FieldT>(
245  A.c0, B.c0, result.c0 + v1 * (-Fp2T::non_residue)),
246  FMT(this->annotation_prefix, " result.c0"));
247  this->pb.add_r1cs_constraint(
248  r1cs_constraint<FieldT>(
249  A.c0 + A.c1,
250  B.c0 + B.c1,
251  result.c1 + result.c0 + v1 * (FieldT::one() - Fp2T::non_residue)),
252  FMT(this->annotation_prefix, " result.c1"));
253 }
254 
255 template<typename Fp2T> void Fp2_mul_gadget<Fp2T>::generate_r1cs_witness()
256 {
257  const FieldT aA = this->pb.lc_val(A.c0) * this->pb.lc_val(B.c0);
258  this->pb.val(v1) = this->pb.lc_val(A.c1) * this->pb.lc_val(B.c1);
259  this->pb.lc_val(result.c0) = aA + Fp2T::non_residue * this->pb.val(v1);
260  this->pb.lc_val(result.c1) =
261  (this->pb.lc_val(A.c0) + this->pb.lc_val(A.c1)) *
262  (this->pb.lc_val(B.c0) + this->pb.lc_val(B.c1)) -
263  aA - this->pb.lc_val(v1);
264 }
265 
266 template<typename Fp2T>
267 Fp2_mul_by_lc_gadget<Fp2T>::Fp2_mul_by_lc_gadget(
268  protoboard<FieldT> &pb,
269  const Fp2_variable<Fp2T> &A,
270  const pb_linear_combination<FieldT> &lc,
271  const Fp2_variable<Fp2T> &result,
272  const std::string &annotation_prefix)
273  : gadget<FieldT>(pb, annotation_prefix), A(A), lc(lc), result(result)
274 {
275 }
276 
277 template<typename Fp2T>
278 void Fp2_mul_by_lc_gadget<Fp2T>::generate_r1cs_constraints()
279 {
280  this->pb.add_r1cs_constraint(
281  r1cs_constraint<FieldT>(A.c0, lc, result.c0),
282  FMT(this->annotation_prefix, " result.c0"));
283  this->pb.add_r1cs_constraint(
284  r1cs_constraint<FieldT>(A.c1, lc, result.c1),
285  FMT(this->annotation_prefix, " result.c1"));
286 }
287 
288 template<typename Fp2T> void Fp2_mul_by_lc_gadget<Fp2T>::generate_r1cs_witness()
289 {
290  this->pb.lc_val(result.c0) = this->pb.lc_val(A.c0) * this->pb.lc_val(lc);
291  this->pb.lc_val(result.c1) = this->pb.lc_val(A.c1) * this->pb.lc_val(lc);
292 }
293 
294 template<typename Fp2T>
295 Fp2_sqr_gadget<Fp2T>::Fp2_sqr_gadget(
296  protoboard<FieldT> &pb,
297  const Fp2_variable<Fp2T> &A,
298  const Fp2_variable<Fp2T> &result,
299  const std::string &annotation_prefix)
300  : gadget<FieldT>(pb, annotation_prefix), A(A), result(result)
301 {
302 }
303 
304 template<typename Fp2T> void Fp2_sqr_gadget<Fp2T>::generate_r1cs_constraints()
305 {
306  /*
307  Complex multiplication for Fp2:
308  v0 = A.c0 * A.c1
309  result.c0 = (A.c0 + A.c1) * (A.c0 + non_residue * A.c1) - (1 +
310  non_residue) * v0 result.c1 = 2 * v0
311 
312  Enforced with 2 constraints:
313  (2*A.c0) * A.c1 = result.c1
314  (A.c0 + A.c1) * (A.c0 + non_residue * A.c1) = result.c0 + result.c1
315  * (1 + non_residue)/2
316 
317  Reference:
318  "Multiplication and Squaring on Pairing-Friendly Fields"
319  Devegili, OhEigeartaigh, Scott, Dahab
320  */
321  this->pb.add_r1cs_constraint(
322  r1cs_constraint<FieldT>(2 * A.c0, A.c1, result.c1),
323  FMT(this->annotation_prefix, " result.c1"));
324  this->pb.add_r1cs_constraint(
325  r1cs_constraint<FieldT>(
326  A.c0 + A.c1,
327  A.c0 + Fp2T::non_residue * A.c1,
328  result.c0 + result.c1 * (FieldT::one() + Fp2T::non_residue) *
329  FieldT(2).inverse()),
330  FMT(this->annotation_prefix, " result.c0"));
331 }
332 
333 template<typename Fp2T> void Fp2_sqr_gadget<Fp2T>::generate_r1cs_witness()
334 {
335  const FieldT a = this->pb.lc_val(A.c0);
336  const FieldT b = this->pb.lc_val(A.c1);
337  this->pb.lc_val(result.c1) = FieldT(2) * a * b;
338  this->pb.lc_val(result.c0) = (a + b) * (a + Fp2T::non_residue * b) - a * b -
339  Fp2T::non_residue * a * b;
340 }
341 
342 } // namespace libsnark
343 
344 #endif // FP2_GADGETS_TCC_
Generated on Wed Jan 25 2023 11:05:57 for Clearmatics Libsnark by   doxygen 1.8.17