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