Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
variable.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for:
5  - a variable (i.e., x_i),
6  - a linear term (i.e., a_i * x_i), and
7  - a linear combination (i.e., sum_i a_i * x_i).
8 
9  See variabe.hpp .
10 
11  *****************************************************************************
12  * @author This file is part of libsnark, developed by SCIPR Lab
13  * and contributors (see AUTHORS).
14  * @copyright MIT license (see LICENSE file)
15  *****************************************************************************/
16 
17 #ifndef VARIABLE_TCC_
18 #define VARIABLE_TCC_
19 
20 #include <algorithm>
21 #include <cassert>
22 #include <libff/algebra/fields/bigint.hpp>
23 
24 namespace libsnark
25 {
26 
27 template<typename FieldT>
28 linear_term<FieldT> variable<FieldT>::operator*(
29  const integer_coeff_t int_coeff) const
30 {
31  return linear_term<FieldT>(*this, int_coeff);
32 }
33 
34 template<typename FieldT>
35 linear_term<FieldT> variable<FieldT>::operator*(const FieldT &field_coeff) const
36 {
37  return linear_term<FieldT>(*this, field_coeff);
38 }
39 
40 template<typename FieldT>
41 linear_combination<FieldT> variable<FieldT>::operator+(
42  const linear_combination<FieldT> &other) const
43 {
44  linear_combination<FieldT> result;
45 
46  result.add_term(*this);
47  result.terms.insert(
48  result.terms.begin(), other.terms.begin(), other.terms.end());
49 
50  return result;
51 }
52 
53 template<typename FieldT>
54 linear_combination<FieldT> variable<FieldT>::operator-(
55  const linear_combination<FieldT> &other) const
56 {
57  return (*this) + (-other);
58 }
59 
60 template<typename FieldT>
61 linear_term<FieldT> variable<FieldT>::operator-() const
62 {
63  return linear_term<FieldT>(*this, -FieldT::one());
64 }
65 
66 template<typename FieldT>
67 bool variable<FieldT>::operator==(const variable<FieldT> &other) const
68 {
69  return (this->index == other.index);
70 }
71 
72 template<typename FieldT>
73 linear_term<FieldT> operator*(
74  const integer_coeff_t int_coeff, const variable<FieldT> &var)
75 {
76  return linear_term<FieldT>(var, int_coeff);
77 }
78 
79 template<typename FieldT>
80 linear_term<FieldT> operator*(
81  const FieldT &field_coeff, const variable<FieldT> &var)
82 {
83  return linear_term<FieldT>(var, field_coeff);
84 }
85 
86 template<typename FieldT>
87 linear_combination<FieldT> operator+(
88  const integer_coeff_t int_coeff, const variable<FieldT> &var)
89 {
90  return linear_combination<FieldT>(int_coeff) + var;
91 }
92 
93 template<typename FieldT>
94 linear_combination<FieldT> operator+(
95  const FieldT &field_coeff, const variable<FieldT> &var)
96 {
97  return linear_combination<FieldT>(field_coeff) + var;
98 }
99 
100 template<typename FieldT>
101 linear_combination<FieldT> operator-(
102  const integer_coeff_t int_coeff, const variable<FieldT> &var)
103 {
104  return linear_combination<FieldT>(int_coeff) - var;
105 }
106 
107 template<typename FieldT>
108 linear_combination<FieldT> operator-(
109  const FieldT &field_coeff, const variable<FieldT> &var)
110 {
111  return linear_combination<FieldT>(field_coeff) - var;
112 }
113 
114 template<typename FieldT>
115 linear_term<FieldT>::linear_term(const variable<FieldT> &var)
116  : index(var.index), coeff(FieldT::one())
117 {
118 }
119 
120 template<typename FieldT>
121 linear_term<FieldT>::linear_term(
122  const variable<FieldT> &var, const integer_coeff_t int_coeff)
123  : index(var.index), coeff(FieldT(int_coeff))
124 {
125 }
126 
127 template<typename FieldT>
128 linear_term<FieldT>::linear_term(
129  const variable<FieldT> &var, const FieldT &coeff)
130  : index(var.index), coeff(coeff)
131 {
132 }
133 
134 template<typename FieldT>
135 linear_term<FieldT> linear_term<FieldT>::operator*(
136  const integer_coeff_t int_coeff) const
137 {
138  return (this->operator*(FieldT(int_coeff)));
139 }
140 
141 template<typename FieldT>
142 linear_term<FieldT> linear_term<FieldT>::operator*(
143  const FieldT &field_coeff) const
144 {
145  return linear_term<FieldT>(this->index, field_coeff * this->coeff);
146 }
147 
148 template<typename FieldT>
149 linear_combination<FieldT> operator+(
150  const integer_coeff_t int_coeff, const linear_term<FieldT> &lt)
151 {
152  return linear_combination<FieldT>(int_coeff) + lt;
153 }
154 
155 template<typename FieldT>
156 linear_combination<FieldT> operator+(
157  const FieldT &field_coeff, const linear_term<FieldT> &lt)
158 {
159  return linear_combination<FieldT>(field_coeff) + lt;
160 }
161 
162 template<typename FieldT>
163 linear_combination<FieldT> operator-(
164  const integer_coeff_t int_coeff, const linear_term<FieldT> &lt)
165 {
166  return linear_combination<FieldT>(int_coeff) - lt;
167 }
168 
169 template<typename FieldT>
170 linear_combination<FieldT> operator-(
171  const FieldT &field_coeff, const linear_term<FieldT> &lt)
172 {
173  return linear_combination<FieldT>(field_coeff) - lt;
174 }
175 
176 template<typename FieldT>
177 linear_combination<FieldT> linear_term<FieldT>::operator+(
178  const linear_combination<FieldT> &other) const
179 {
180  return linear_combination<FieldT>(*this) + other;
181 }
182 
183 template<typename FieldT>
184 linear_combination<FieldT> linear_term<FieldT>::operator-(
185  const linear_combination<FieldT> &other) const
186 {
187  return (*this) + (-other);
188 }
189 
190 template<typename FieldT>
191 linear_term<FieldT> linear_term<FieldT>::operator-() const
192 {
193  return linear_term<FieldT>(this->index, -this->coeff);
194 }
195 
196 template<typename FieldT>
197 bool linear_term<FieldT>::operator==(const linear_term<FieldT> &other) const
198 {
199  return (this->index == other.index && this->coeff == other.coeff);
200 }
201 
202 template<typename FieldT>
203 linear_term<FieldT> operator*(
204  const integer_coeff_t int_coeff, const linear_term<FieldT> &lt)
205 {
206  return FieldT(int_coeff) * lt;
207 }
208 
209 template<typename FieldT>
210 linear_term<FieldT> operator*(
211  const FieldT &field_coeff, const linear_term<FieldT> &lt)
212 {
213  return linear_term<FieldT>(lt.index, field_coeff * lt.coeff);
214 }
215 
216 template<typename FieldT>
217 linear_combination<FieldT>::linear_combination(const integer_coeff_t int_coeff)
218 {
219  this->add_term(linear_term<FieldT>(0, int_coeff));
220 }
221 
222 template<typename FieldT>
223 linear_combination<FieldT>::linear_combination(const FieldT &field_coeff)
224 {
225  this->add_term(linear_term<FieldT>(0, field_coeff));
226 }
227 
228 template<typename FieldT>
229 linear_combination<FieldT>::linear_combination(const variable<FieldT> &var)
230 {
231  this->add_term(var);
232 }
233 
234 template<typename FieldT>
235 linear_combination<FieldT>::linear_combination(const linear_term<FieldT> &lt)
236 {
237  this->add_term(lt);
238 }
239 
240 template<typename FieldT>
241 typename std::vector<linear_term<FieldT>>::const_iterator linear_combination<
242  FieldT>::begin() const
243 {
244  return terms.begin();
245 }
246 
247 template<typename FieldT>
248 typename std::vector<linear_term<FieldT>>::const_iterator linear_combination<
249  FieldT>::end() const
250 {
251  return terms.end();
252 }
253 
254 template<typename FieldT>
255 void linear_combination<FieldT>::add_term(const variable<FieldT> &var)
256 {
257  this->terms.emplace_back(linear_term<FieldT>(var.index, FieldT::one()));
258 }
259 
260 template<typename FieldT>
261 void linear_combination<FieldT>::add_term(
262  const variable<FieldT> &var, const integer_coeff_t int_coeff)
263 {
264  this->terms.emplace_back(linear_term<FieldT>(var.index, int_coeff));
265 }
266 
267 template<typename FieldT>
268 void linear_combination<FieldT>::add_term(
269  const variable<FieldT> &var, const FieldT &coeff)
270 {
271  this->terms.emplace_back(linear_term<FieldT>(var.index, coeff));
272 }
273 
274 template<typename FieldT>
275 void linear_combination<FieldT>::add_term(const linear_term<FieldT> &other)
276 {
277  this->terms.emplace_back(other);
278 }
279 
280 template<typename FieldT>
281 linear_combination<FieldT> linear_combination<FieldT>::operator*(
282  const integer_coeff_t int_coeff) const
283 {
284  return (*this) * FieldT(int_coeff);
285 }
286 
287 template<typename FieldT>
288 FieldT linear_combination<FieldT>::evaluate(
289  const std::vector<FieldT> &assignment) const
290 {
291  FieldT acc = FieldT::zero();
292  for (auto &lt : terms) {
293  acc += (lt.index == 0 ? FieldT::one() : assignment[lt.index - 1]) *
294  lt.coeff;
295  }
296  return acc;
297 }
298 
299 template<typename FieldT>
300 linear_combination<FieldT> linear_combination<FieldT>::operator*(
301  const FieldT &field_coeff) const
302 {
303  linear_combination<FieldT> result;
304  result.terms.reserve(this->terms.size());
305  for (const linear_term<FieldT> &lt : this->terms) {
306  result.terms.emplace_back(lt * field_coeff);
307  }
308  return result;
309 }
310 
311 template<typename FieldT>
312 linear_combination<FieldT> linear_combination<FieldT>::operator+(
313  const linear_combination<FieldT> &other) const
314 {
315  linear_combination<FieldT> result;
316 
317  auto it1 = this->terms.begin();
318  auto it2 = other.terms.begin();
319 
320  /* invariant: it1 and it2 always point to unprocessed items in the
321  * corresponding linear combinations */
322  while (it1 != this->terms.end() && it2 != other.terms.end()) {
323  if (it1->index < it2->index) {
324  result.terms.emplace_back(*it1);
325  ++it1;
326  } else if (it1->index > it2->index) {
327  result.terms.emplace_back(*it2);
328  ++it2;
329  } else {
330  /* it1->index == it2->index */
331  result.terms.emplace_back(linear_term<FieldT>(
332  variable<FieldT>(it1->index), it1->coeff + it2->coeff));
333  ++it1;
334  ++it2;
335  }
336  }
337 
338  if (it1 != this->terms.end()) {
339  result.terms.insert(result.terms.end(), it1, this->terms.end());
340  } else {
341  result.terms.insert(result.terms.end(), it2, other.terms.end());
342  }
343 
344  return result;
345 }
346 
347 template<typename FieldT>
348 linear_combination<FieldT> linear_combination<FieldT>::operator-(
349  const linear_combination<FieldT> &other) const
350 {
351  return (*this) + (-other);
352 }
353 
354 template<typename FieldT>
355 linear_combination<FieldT> linear_combination<FieldT>::operator-() const
356 {
357  return (*this) * (-FieldT::one());
358 }
359 
360 template<typename FieldT>
361 bool linear_combination<FieldT>::operator==(
362  const linear_combination<FieldT> &other) const
363 {
364  return (this->terms == other.terms);
365 }
366 
367 template<typename FieldT>
368 bool linear_combination<FieldT>::is_valid(const size_t num_variables) const
369 {
370  /* check that all terms in linear combination are sorted */
371  for (size_t i = 1; i < terms.size(); ++i) {
372  if (terms[i - 1].index >= terms[i].index) {
373  return false;
374  }
375  }
376 
377  /* check that the variables are in proper range. as the variables
378  are sorted, it suffices to check the last term */
379  if ((--terms.end())->index >= num_variables) {
380  return false;
381  }
382 
383  return true;
384 }
385 
386 template<typename FieldT>
387 void linear_combination<FieldT>::print(
388  const std::map<size_t, std::string> &variable_annotations) const
389 {
390  for (auto &lt : terms) {
391  if (lt.index == 0) {
392  printf(" 1 * ");
393  lt.coeff.print();
394  } else {
395  auto it = variable_annotations.find(lt.index);
396  printf(
397  " x_%zu (%s) * ",
398  lt.index,
399  (it == variable_annotations.end() ? "no annotation"
400  : it->second.c_str()));
401  lt.coeff.print();
402  }
403  }
404 }
405 
406 template<typename FieldT>
407 void linear_combination<FieldT>::print_with_assignment(
408  const std::vector<FieldT> &full_assignment,
409  const std::map<size_t, std::string> &variable_annotations) const
410 {
411  for (auto &lt : terms) {
412  if (lt.index == 0) {
413  printf(" 1 * ");
414  lt.coeff.print();
415  } else {
416  printf(" x_%zu * ", lt.index);
417  lt.coeff.print();
418 
419  auto it = variable_annotations.find(lt.index);
420  printf(
421  " where x_%zu (%s) was assigned value ",
422  lt.index,
423  (it == variable_annotations.end() ? "no annotation"
424  : it->second.c_str()));
425  full_assignment[lt.index - 1].print();
426  printf(" i.e. negative of ");
427  (-full_assignment[lt.index - 1]).print();
428  }
429  }
430 }
431 
432 template<typename FieldT>
433 std::ostream &operator<<(
434  std::ostream &out, const linear_combination<FieldT> &lc)
435 {
436  out << lc.terms.size() << "\n";
437  for (const linear_term<FieldT> &lt : lc.terms) {
438  out << lt.index << "\n";
439  out << lt.coeff << OUTPUT_NEWLINE;
440  }
441 
442  return out;
443 }
444 
445 template<typename FieldT>
446 std::istream &operator>>(std::istream &in, linear_combination<FieldT> &lc)
447 {
448  lc.terms.clear();
449 
450  size_t s;
451  in >> s;
452 
453  libff::consume_newline(in);
454 
455  lc.terms.reserve(s);
456 
457  for (size_t i = 0; i < s; ++i) {
458  linear_term<FieldT> lt;
459  in >> lt.index;
460  libff::consume_newline(in);
461  in >> lt.coeff;
462  libff::consume_OUTPUT_NEWLINE(in);
463  lc.terms.emplace_back(lt);
464  }
465 
466  return in;
467 }
468 
469 template<typename FieldT>
470 linear_combination<FieldT> operator*(
471  const integer_coeff_t int_coeff, const linear_combination<FieldT> &lc)
472 {
473  return lc * int_coeff;
474 }
475 
476 template<typename FieldT>
477 linear_combination<FieldT> operator*(
478  const FieldT &field_coeff, const linear_combination<FieldT> &lc)
479 {
480  return lc * field_coeff;
481 }
482 
483 template<typename FieldT>
484 linear_combination<FieldT> operator+(
485  const integer_coeff_t int_coeff, const linear_combination<FieldT> &lc)
486 {
487  return linear_combination<FieldT>(int_coeff) + lc;
488 }
489 
490 template<typename FieldT>
491 linear_combination<FieldT> operator+(
492  const FieldT &field_coeff, const linear_combination<FieldT> &lc)
493 {
494  return linear_combination<FieldT>(field_coeff) + lc;
495 }
496 
497 template<typename FieldT>
498 linear_combination<FieldT> operator-(
499  const integer_coeff_t int_coeff, const linear_combination<FieldT> &lc)
500 {
501  return linear_combination<FieldT>(int_coeff) - lc;
502 }
503 
504 template<typename FieldT>
505 linear_combination<FieldT> operator-(
506  const FieldT &field_coeff, const linear_combination<FieldT> &lc)
507 {
508  return linear_combination<FieldT>(field_coeff) - lc;
509 }
510 
511 template<typename FieldT>
512 linear_combination<FieldT>::linear_combination(
513  const std::vector<linear_term<FieldT>> &all_terms)
514 {
515  if (all_terms.empty()) {
516  return;
517  }
518 
519  terms = all_terms;
520  std::sort(
521  terms.begin(),
522  terms.end(),
523  [](linear_term<FieldT> a, linear_term<FieldT> b) {
524  return a.index < b.index;
525  });
526 
527  auto result_it = terms.begin();
528  for (auto it = ++terms.begin(); it != terms.end(); ++it) {
529  if (it->index == result_it->index) {
530  result_it->coeff += it->coeff;
531  } else {
532  *(++result_it) = *it;
533  }
534  }
535  terms.resize((result_it - terms.begin()) + 1);
536 }
537 
538 } // namespace libsnark
539 
540 #endif // VARIABLE_TCC
Generated on Wed Jan 25 2023 11:05:58 for Clearmatics Libsnark by   doxygen 1.8.17