Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
r1cs_ppzkadsnark.tcc
Go to the documentation of this file.
1 /** @file
2 *****************************************************************************
3 
4 Implementation of interfaces for a ppzkADSNARK for R1CS.
5 
6 See r1cs_ppzkadsnark.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 R1CS_PPZKADSNARK_TCC_
15 #define R1CS_PPZKADSNARK_TCC_
16 
17 #include <algorithm>
18 #include <cassert>
19 #include <functional>
20 #include <iostream>
21 #include <libff/algebra/scalar_multiplication/multiexp.hpp>
22 #include <libff/common/profiling.hpp>
23 #include <libff/common/utils.hpp>
24 #include <sstream>
25 
26 #ifdef MULTICORE
27 #include <omp.h>
28 #endif
29 
30 #include <libsnark/knowledge_commitment/kc_multiexp.hpp>
31 #include <libsnark/reductions/r1cs_to_qap/r1cs_to_qap.hpp>
32 
33 namespace libsnark
34 {
35 
36 template<typename ppT>
37 bool r1cs_ppzkadsnark_pub_auth_prms<ppT>::operator==(
38  const r1cs_ppzkadsnark_pub_auth_prms<ppT> &other) const
39 {
40  return (this->I1 == other.I1);
41 }
42 
43 template<typename ppT>
44 std::ostream &operator<<(
45  std::ostream &out, const r1cs_ppzkadsnark_pub_auth_prms<ppT> &pap)
46 {
47  out << pap.I1;
48 
49  return out;
50 }
51 
52 template<typename ppT>
53 std::istream &operator>>(
54  std::istream &in, r1cs_ppzkadsnark_pub_auth_prms<ppT> &pap)
55 {
56  in >> pap.I1;
57 
58  return in;
59 }
60 
61 template<typename ppT>
62 bool r1cs_ppzkadsnark_sec_auth_key<ppT>::operator==(
63  const r1cs_ppzkadsnark_sec_auth_key<ppT> &other) const
64 {
65  return (this->i == other.i) && (this->skp == other.skp) &&
66  (this->S == other.S);
67 }
68 
69 template<typename ppT>
70 std::ostream &operator<<(
71  std::ostream &out, const r1cs_ppzkadsnark_sec_auth_key<ppT> &key)
72 {
73  out << key.i;
74  out << key.skp;
75  out << key.S;
76 
77  return out;
78 }
79 
80 template<typename ppT>
81 std::istream &operator>>(
82  std::istream &in, r1cs_ppzkadsnark_sec_auth_key<ppT> &key)
83 {
84  in >> key.i;
85  in >> key.skp;
86  in >> key.S;
87 
88  return in;
89 }
90 
91 template<typename ppT>
92 bool r1cs_ppzkadsnark_pub_auth_key<ppT>::operator==(
93  const r1cs_ppzkadsnark_pub_auth_key<ppT> &other) const
94 {
95  return (this->minusI2 == other.minusI2) && (this->vkp == other.vkp);
96 }
97 
98 template<typename ppT>
99 std::ostream &operator<<(
100  std::ostream &out, const r1cs_ppzkadsnark_pub_auth_key<ppT> &key)
101 {
102  out << key.minusI2;
103  out << key.vkp;
104 
105  return out;
106 }
107 
108 template<typename ppT>
109 std::istream &operator>>(
110  std::istream &in, r1cs_ppzkadsnark_pub_auth_key<ppT> &key)
111 {
112  in >> key.minusI2;
113  in >> key.vkp;
114 
115  return in;
116 }
117 
118 template<typename ppT>
119 bool r1cs_ppzkadsnark_auth_data<ppT>::operator==(
120  const r1cs_ppzkadsnark_auth_data<ppT> &other) const
121 {
122  return (this->mu == other.mu) && (this->Lambda == other.Lambda) &&
123  (this->sigma == other.sigma);
124 }
125 
126 template<typename ppT>
127 std::ostream &operator<<(
128  std::ostream &out, const r1cs_ppzkadsnark_auth_data<ppT> &data)
129 {
130  out << data.mu;
131  out << data.Lambda;
132  out << data.sigma;
133 
134  return out;
135 }
136 
137 template<typename ppT>
138 std::istream &operator>>(
139  std::istream &in, r1cs_ppzkadsnark_auth_data<ppT> &data)
140 {
141  in >> data.mu;
142  in >> data.Lambda;
143  data.sigma;
144 
145  return in;
146 }
147 
148 template<typename ppT>
149 bool r1cs_ppzkadsnark_proving_key<ppT>::operator==(
150  const r1cs_ppzkadsnark_proving_key<ppT> &other) const
151 {
152  return (
153  this->A_query == other.A_query && this->B_query == other.B_query &&
154  this->C_query == other.C_query && this->H_query == other.H_query &&
155  this->K_query == other.K_query && this->rA_i_Z_g1 == other.rA_i_Z_g1 &&
156  this->constraint_system == other.constraint_system);
157 }
158 
159 template<typename ppT>
160 std::ostream &operator<<(
161  std::ostream &out, const r1cs_ppzkadsnark_proving_key<ppT> &pk)
162 {
163  out << pk.A_query;
164  out << pk.B_query;
165  out << pk.C_query;
166  out << pk.H_query;
167  out << pk.K_query;
168  out << pk.rA_i_Z_g1;
169  out << pk.constraint_system;
170 
171  return out;
172 }
173 
174 template<typename ppT>
175 std::istream &operator>>(
176  std::istream &in, r1cs_ppzkadsnark_proving_key<ppT> &pk)
177 {
178  in >> pk.A_query;
179  in >> pk.B_query;
180  in >> pk.C_query;
181  in >> pk.H_query;
182  in >> pk.K_query;
183  in >> pk.rA_i_Z_g1;
184  in >> pk.constraint_system;
185 
186  return in;
187 }
188 
189 template<typename ppT>
190 bool r1cs_ppzkadsnark_verification_key<ppT>::operator==(
191  const r1cs_ppzkadsnark_verification_key<ppT> &other) const
192 {
193  return (
194  this->alphaA_g2 == other.alphaA_g2 &&
195  this->alphaB_g1 == other.alphaB_g1 &&
196  this->alphaC_g2 == other.alphaC_g2 &&
197  this->gamma_g2 == other.gamma_g2 &&
198  this->gamma_beta_g1 == other.gamma_beta_g1 &&
199  this->gamma_beta_g2 == other.gamma_beta_g2 &&
200  this->rC_Z_g2 == other.rC_Z_g2 && this->A0 == other.A0 &&
201  this->Ain == other.Ain);
202 }
203 
204 template<typename ppT>
205 std::ostream &operator<<(
206  std::ostream &out, const r1cs_ppzkadsnark_verification_key<ppT> &vk)
207 {
208  out << vk.alphaA_g2 << OUTPUT_NEWLINE;
209  out << vk.alphaB_g1 << OUTPUT_NEWLINE;
210  out << vk.alphaC_g2 << OUTPUT_NEWLINE;
211  out << vk.gamma_g2 << OUTPUT_NEWLINE;
212  out << vk.gamma_beta_g1 << OUTPUT_NEWLINE;
213  out << vk.gamma_beta_g2 << OUTPUT_NEWLINE;
214  out << vk.rC_Z_g2 << OUTPUT_NEWLINE;
215  out << vk.A0 << OUTPUT_NEWLINE;
216  out << vk.Ain << OUTPUT_NEWLINE;
217 
218  return out;
219 }
220 
221 template<typename ppT>
222 std::istream &operator>>(
223  std::istream &in, r1cs_ppzkadsnark_verification_key<ppT> &vk)
224 {
225  in >> vk.alphaA_g2;
226  libff::consume_OUTPUT_NEWLINE(in);
227  in >> vk.alphaB_g1;
228  libff::consume_OUTPUT_NEWLINE(in);
229  in >> vk.alphaC_g2;
230  libff::consume_OUTPUT_NEWLINE(in);
231  in >> vk.gamma_g2;
232  libff::consume_OUTPUT_NEWLINE(in);
233  in >> vk.gamma_beta_g1;
234  libff::consume_OUTPUT_NEWLINE(in);
235  in >> vk.gamma_beta_g2;
236  libff::consume_OUTPUT_NEWLINE(in);
237  in >> vk.rC_Z_g2;
238  libff::consume_OUTPUT_NEWLINE(in);
239  in >> vk.A0;
240  libff::consume_OUTPUT_NEWLINE(in);
241  in >> vk.Ain;
242  libff::consume_OUTPUT_NEWLINE(in);
243 
244  return in;
245 }
246 
247 template<typename ppT>
248 bool r1cs_ppzkadsnark_processed_verification_key<ppT>::operator==(
249  const r1cs_ppzkadsnark_processed_verification_key<ppT> &other) const
250 {
251  bool result =
252  (this->pp_G2_one_precomp == other.pp_G2_one_precomp &&
253  this->vk_alphaA_g2_precomp == other.vk_alphaA_g2_precomp &&
254  this->vk_alphaB_g1_precomp == other.vk_alphaB_g1_precomp &&
255  this->vk_alphaC_g2_precomp == other.vk_alphaC_g2_precomp &&
256  this->vk_rC_Z_g2_precomp == other.vk_rC_Z_g2_precomp &&
257  this->vk_gamma_g2_precomp == other.vk_gamma_g2_precomp &&
258  this->vk_gamma_beta_g1_precomp == other.vk_gamma_beta_g1_precomp &&
259  this->vk_gamma_beta_g2_precomp == other.vk_gamma_beta_g2_precomp &&
260  this->vk_rC_i_g2_precomp == other.vk_rC_i_g2_precomp &&
261  this->A0 == other.A0 && this->Ain == other.Ain &&
262  this->proof_g_vki_precomp.size() == other.proof_g_vki_precomp.size());
263  if (result) {
264  for (size_t i = 0; i < this->proof_g_vki_precomp.size(); i++)
265  result &=
266  this->proof_g_vki_precomp[i] == other.proof_g_vki_precomp[i];
267  }
268  return result;
269 }
270 
271 template<typename ppT>
272 std::ostream &operator<<(
273  std::ostream &out,
274  const r1cs_ppzkadsnark_processed_verification_key<ppT> &pvk)
275 {
276  out << pvk.pp_G2_one_precomp << OUTPUT_NEWLINE;
277  out << pvk.vk_alphaA_g2_precomp << OUTPUT_NEWLINE;
278  out << pvk.vk_alphaB_g1_precomp << OUTPUT_NEWLINE;
279  out << pvk.vk_alphaC_g2_precomp << OUTPUT_NEWLINE;
280  out << pvk.vk_rC_Z_g2_precomp << OUTPUT_NEWLINE;
281  out << pvk.vk_gamma_g2_precomp << OUTPUT_NEWLINE;
282  out << pvk.vk_gamma_beta_g1_precomp << OUTPUT_NEWLINE;
283  out << pvk.vk_gamma_beta_g2_precomp << OUTPUT_NEWLINE;
284  out << pvk.vk_rC_i_g2_precomp << OUTPUT_NEWLINE;
285  out << pvk.A0 << OUTPUT_NEWLINE;
286  out << pvk.Ain << OUTPUT_NEWLINE;
287  out << pvk.proof_g_vki_precomp << OUTPUT_NEWLINE;
288 
289  return out;
290 }
291 
292 template<typename ppT>
293 std::istream &operator>>(
294  std::istream &in, r1cs_ppzkadsnark_processed_verification_key<ppT> &pvk)
295 {
296  in >> pvk.pp_G2_one_precomp;
297  libff::consume_OUTPUT_NEWLINE(in);
298  in >> pvk.vk_alphaA_g2_precomp;
299  libff::consume_OUTPUT_NEWLINE(in);
300  in >> pvk.vk_alphaB_g1_precomp;
301  libff::consume_OUTPUT_NEWLINE(in);
302  in >> pvk.vk_alphaC_g2_precomp;
303  libff::consume_OUTPUT_NEWLINE(in);
304  in >> pvk.vk_rC_Z_g2_precomp;
305  libff::consume_OUTPUT_NEWLINE(in);
306  in >> pvk.vk_gamma_g2_precomp;
307  libff::consume_OUTPUT_NEWLINE(in);
308  in >> pvk.vk_gamma_beta_g1_precomp;
309  libff::consume_OUTPUT_NEWLINE(in);
310  in >> pvk.vk_gamma_beta_g2_precomp;
311  libff::consume_OUTPUT_NEWLINE(in);
312  in >> pvk.vk_rC_i_g2_precomp;
313  libff::consume_OUTPUT_NEWLINE(in);
314  in >> pvk.A0;
315  libff::consume_OUTPUT_NEWLINE(in);
316  in >> pvk.Ain;
317  libff::consume_OUTPUT_NEWLINE(in);
318  in >> pvk.proof_g_vki_precomp;
319  libff::consume_OUTPUT_NEWLINE(in);
320 
321  return in;
322 }
323 
324 template<typename ppT>
325 bool r1cs_ppzkadsnark_proof<ppT>::operator==(
326  const r1cs_ppzkadsnark_proof<ppT> &other) const
327 {
328  return (
329  this->g_A == other.g_A && this->g_B == other.g_B &&
330  this->g_C == other.g_C && this->g_H == other.g_H &&
331  this->g_K == other.g_K && this->g_Aau == other.g_Aau &&
332  this->muA == other.muA);
333 }
334 
335 template<typename ppT>
336 std::ostream &operator<<(
337  std::ostream &out, const r1cs_ppzkadsnark_proof<ppT> &proof)
338 {
339  out << proof.g_A << OUTPUT_NEWLINE;
340  out << proof.g_B << OUTPUT_NEWLINE;
341  out << proof.g_C << OUTPUT_NEWLINE;
342  out << proof.g_H << OUTPUT_NEWLINE;
343  out << proof.g_K << OUTPUT_NEWLINE;
344  out << proof.g_Aau << OUTPUT_NEWLINE;
345  out << proof.muA << OUTPUT_NEWLINE;
346 
347  return out;
348 }
349 
350 template<typename ppT>
351 std::istream &operator>>(std::istream &in, r1cs_ppzkadsnark_proof<ppT> &proof)
352 {
353  in >> proof.g_A;
354  libff::consume_OUTPUT_NEWLINE(in);
355  in >> proof.g_B;
356  libff::consume_OUTPUT_NEWLINE(in);
357  in >> proof.g_C;
358  libff::consume_OUTPUT_NEWLINE(in);
359  in >> proof.g_H;
360  libff::consume_OUTPUT_NEWLINE(in);
361  in >> proof.g_K;
362  libff::consume_OUTPUT_NEWLINE(in);
363  in >> proof.g_Aau;
364  libff::consume_OUTPUT_NEWLINE(in);
365  in >> proof.muA;
366  libff::consume_OUTPUT_NEWLINE(in);
367 
368  return in;
369 }
370 
371 template<typename ppT>
372 r1cs_ppzkadsnark_verification_key<ppT> r1cs_ppzkadsnark_verification_key<
373  ppT>::dummy_verification_key(const size_t input_size)
374 {
375  r1cs_ppzkadsnark_verification_key<ppT> result;
376  result.alphaA_g2 = libff::Fr<snark_pp<ppT>>::random_element() *
377  libff::G2<snark_pp<ppT>>::one();
378  result.alphaB_g1 = libff::Fr<snark_pp<ppT>>::random_element() *
379  libff::G1<snark_pp<ppT>>::one();
380  result.alphaC_g2 = libff::Fr<snark_pp<ppT>>::random_element() *
381  libff::G2<snark_pp<ppT>>::one();
382  result.gamma_g2 = libff::Fr<snark_pp<ppT>>::random_element() *
383  libff::G2<snark_pp<ppT>>::one();
384  result.gamma_beta_g1 = libff::Fr<snark_pp<ppT>>::random_element() *
385  libff::G1<snark_pp<ppT>>::one();
386  result.gamma_beta_g2 = libff::Fr<snark_pp<ppT>>::random_element() *
387  libff::G2<snark_pp<ppT>>::one();
388  result.rC_Z_g2 = libff::Fr<snark_pp<ppT>>::random_element() *
389  libff::G2<snark_pp<ppT>>::one();
390 
391  result.A0 = libff::Fr<snark_pp<ppT>>::random_element() *
392  libff::G1<snark_pp<ppT>>::one();
393  for (size_t i = 0; i < input_size; ++i) {
394  result.Ain.emplace_back(
395  libff::Fr<snark_pp<ppT>>::random_element() *
396  libff::G1<snark_pp<ppT>>::one());
397  }
398 
399  return result;
400 }
401 
402 template<typename ppT>
403 r1cs_ppzkadsnark_auth_keys<ppT> r1cs_ppzkadsnark_auth_generator(void)
404 {
405  kpT<ppT> sigkp = sigGen<ppT>();
406  r1cs_ppzkadsnark_prfKeyT<ppT> prfseed = prfGen<ppT>();
407  libff::Fr<snark_pp<ppT>> i = libff::Fr<snark_pp<ppT>>::random_element();
408  libff::G1<snark_pp<ppT>> I1 = i * libff::G1<snark_pp<ppT>>::one();
409  libff::G2<snark_pp<ppT>> minusI2 =
410  libff::G2<snark_pp<ppT>>::zero() - i * libff::G2<snark_pp<ppT>>::one();
411  return r1cs_ppzkadsnark_auth_keys<ppT>(
412  r1cs_ppzkadsnark_pub_auth_prms<ppT>(std::move(I1)),
413  r1cs_ppzkadsnark_pub_auth_key<ppT>(
414  std::move(minusI2), std::move(sigkp.vk)),
415  r1cs_ppzkadsnark_sec_auth_key<ppT>(
416  std::move(i), std::move(sigkp.sk), std::move(prfseed)));
417 }
418 
419 template<typename ppT>
420 std::vector<r1cs_ppzkadsnark_auth_data<ppT>> r1cs_ppzkadsnark_auth_sign(
421  const std::vector<libff::Fr<snark_pp<ppT>>> &ins,
422  const r1cs_ppzkadsnark_sec_auth_key<ppT> &sk,
423  const std::vector<labelT> labels)
424 {
425  libff::enter_block("Call to r1cs_ppzkadsnark_auth_sign");
426  assert(labels.size() == ins.size());
427  std::vector<r1cs_ppzkadsnark_auth_data<ppT>> res;
428  res.reserve(ins.size());
429  for (size_t i = 0; i < ins.size(); i++) {
430  libff::Fr<snark_pp<ppT>> lambda = prfCompute<ppT>(sk.S, labels[i]);
431  libff::G2<snark_pp<ppT>> Lambda =
432  lambda * libff::G2<snark_pp<ppT>>::one();
433  r1cs_ppzkadsnark_sigT<ppT> sig =
434  sigSign<ppT>(sk.skp, labels[i], Lambda);
435  r1cs_ppzkadsnark_auth_data<ppT> val(
436  std::move(lambda + sk.i * ins[i]),
437  std::move(Lambda),
438  std::move(sig));
439  res.emplace_back(val);
440  }
441  libff::leave_block("Call to r1cs_ppzkadsnark_auth_sign");
442  return std::move(res);
443 }
444 
445 // symmetric
446 template<typename ppT>
447 bool r1cs_ppzkadsnark_auth_verify(
448  const std::vector<libff::Fr<snark_pp<ppT>>> &data,
449  const std::vector<r1cs_ppzkadsnark_auth_data<ppT>> &auth_data,
450  const r1cs_ppzkadsnark_sec_auth_key<ppT> &sak,
451  const std::vector<labelT> &labels)
452 {
453  libff::enter_block("Call to r1cs_ppzkadsnark_auth_verify");
454  assert(
455  (data.size() == labels.size()) && (auth_data.size() == labels.size()));
456  bool res = true;
457  for (size_t i = 0; i < data.size(); i++) {
458  libff::Fr<snark_pp<ppT>> lambda = prfCompute<ppT>(sak.S, labels[i]);
459  libff::Fr<snark_pp<ppT>> mup = lambda + sak.i * data[i];
460  res = res && (auth_data[i].mu == mup);
461  }
462  libff::leave_block("Call to r1cs_ppzkadsnark_auth_verify");
463  return res;
464 }
465 
466 // public
467 template<typename ppT>
468 bool r1cs_ppzkadsnark_auth_verify(
469  const std::vector<libff::Fr<snark_pp<ppT>>> &data,
470  const std::vector<r1cs_ppzkadsnark_auth_data<ppT>> &auth_data,
471  const r1cs_ppzkadsnark_pub_auth_key<ppT> &pak,
472  const std::vector<labelT> &labels)
473 {
474  libff::enter_block("Call to r1cs_ppzkadsnark_auth_verify");
475  assert((data.size() == labels.size()) && (data.size() == auth_data.size()));
476  bool res = true;
477  for (size_t i = 0; i < auth_data.size(); i++) {
478  libff::G2<snark_pp<ppT>> Mup =
479  auth_data[i].Lambda - data[i] * pak.minusI2;
480  res = res && (auth_data[i].mu * libff::G2<snark_pp<ppT>>::one() == Mup);
481  res = res &&
482  sigVerif<ppT>(
483  pak.vkp, labels[i], auth_data[i].Lambda, auth_data[i].sigma);
484  }
485  libff::leave_block("Call to r1cs_ppzkadsnark_auth_verify");
486  return res;
487 }
488 
489 template<typename ppT, libff::multi_exp_base_form BaseForm>
490 r1cs_ppzkadsnark_keypair<ppT> r1cs_ppzkadsnark_generator(
491  const r1cs_ppzkadsnark_constraint_system<ppT> &cs,
492  const r1cs_ppzkadsnark_pub_auth_prms<ppT> &prms)
493 {
494  libff::enter_block("Call to r1cs_ppzkadsnark_generator");
495 
496  /* make the B_query "lighter" if possible */
497  r1cs_ppzkadsnark_constraint_system<ppT> cs_copy(cs);
498  cs_copy.swap_AB_if_beneficial();
499 
500  /* draw random element at which the QAP is evaluated */
501  const libff::Fr<snark_pp<ppT>> t =
502  libff::Fr<snark_pp<ppT>>::random_element();
503 
504  qap_instance_evaluation<libff::Fr<snark_pp<ppT>>> qap_inst =
505  r1cs_to_qap_instance_map_with_evaluation(cs_copy, t);
506 
507  libff::print_indent();
508  printf("* QAP number of variables: %zu\n", qap_inst.num_variables());
509  libff::print_indent();
510  printf("* QAP pre degree: %zu\n", cs_copy.constraints.size());
511  libff::print_indent();
512  printf("* QAP degree: %zu\n", qap_inst.degree());
513  libff::print_indent();
514  printf("* QAP number of input variables: %zu\n", qap_inst.num_inputs());
515 
516  libff::enter_block("Compute query densities");
517  size_t non_zero_At = 0, non_zero_Bt = 0, non_zero_Ct = 0, non_zero_Ht = 0;
518  for (size_t i = 0; i < qap_inst.num_variables() + 1; ++i) {
519  if (!qap_inst.At[i].is_zero()) {
520  ++non_zero_At;
521  }
522  if (!qap_inst.Bt[i].is_zero()) {
523  ++non_zero_Bt;
524  }
525  if (!qap_inst.Ct[i].is_zero()) {
526  ++non_zero_Ct;
527  }
528  }
529  for (size_t i = 0; i < qap_inst.degree() + 1; ++i) {
530  if (!qap_inst.Ht[i].is_zero()) {
531  ++non_zero_Ht;
532  }
533  }
534  libff::leave_block("Compute query densities");
535 
536  libff::Fr_vector<snark_pp<ppT>> At =
537  std::move(qap_inst.At); // qap_inst.At is now in unspecified state, but
538  // we do not use it later
539  libff::Fr_vector<snark_pp<ppT>> Bt =
540  std::move(qap_inst.Bt); // qap_inst.Bt is now in unspecified state, but
541  // we do not use it later
542  libff::Fr_vector<snark_pp<ppT>> Ct =
543  std::move(qap_inst.Ct); // qap_inst.Ct is now in unspecified state, but
544  // we do not use it later
545  libff::Fr_vector<snark_pp<ppT>> Ht =
546  std::move(qap_inst.Ht); // qap_inst.Ht is now in unspecified state, but
547  // we do not use it later
548 
549  /* append Zt to At,Bt,Ct with */
550  At.emplace_back(qap_inst.Zt);
551  Bt.emplace_back(qap_inst.Zt);
552  Ct.emplace_back(qap_inst.Zt);
553 
554  const libff::Fr<snark_pp<ppT>>
555  alphaA = libff::Fr<snark_pp<ppT>>::random_element(),
556  alphaB = libff::Fr<snark_pp<ppT>>::random_element(),
557  alphaC = libff::Fr<snark_pp<ppT>>::random_element(),
558  rA = libff::Fr<snark_pp<ppT>>::random_element(),
559  rB = libff::Fr<snark_pp<ppT>>::random_element(),
560  beta = libff::Fr<snark_pp<ppT>>::random_element(),
561  gamma = libff::Fr<snark_pp<ppT>>::random_element();
562  const libff::Fr<snark_pp<ppT>> rC = rA * rB;
563 
564  // construct the same-coefficient-check query (must happen before zeroing
565  // out the prefix of At)
566  libff::Fr_vector<snark_pp<ppT>> Kt;
567  Kt.reserve(qap_inst.num_variables() + 4);
568  for (size_t i = 0; i < qap_inst.num_variables() + 1; ++i) {
569  Kt.emplace_back(beta * (rA * At[i] + rB * Bt[i] + rC * Ct[i]));
570  }
571  Kt.emplace_back(beta * rA * qap_inst.Zt);
572  Kt.emplace_back(beta * rB * qap_inst.Zt);
573  Kt.emplace_back(beta * rC * qap_inst.Zt);
574 
575  const size_t g1_exp_count =
576  2 * (non_zero_At - qap_inst.num_inputs() + non_zero_Ct) + non_zero_Bt +
577  non_zero_Ht + Kt.size();
578  const size_t g2_exp_count = non_zero_Bt;
579 
580  size_t g1_window =
581  libff::get_exp_window_size<libff::G1<snark_pp<ppT>>>(g1_exp_count);
582  size_t g2_window =
583  libff::get_exp_window_size<libff::G2<snark_pp<ppT>>>(g2_exp_count);
584  libff::print_indent();
585  printf("* G1 window: %zu\n", g1_window);
586  libff::print_indent();
587  printf("* G2 window: %zu\n", g2_window);
588 
589 #ifdef MULTICORE
590  const size_t chunks =
591  omp_get_max_threads(); // to override, set OMP_NUM_THREADS env var or
592  // call omp_set_num_threads()
593 #else
594  const size_t chunks = 1;
595 #endif
596 
597  libff::enter_block("Generating G1 multiexp table");
598  libff::window_table<libff::G1<snark_pp<ppT>>> g1_table = get_window_table(
599  libff::Fr<snark_pp<ppT>>::size_in_bits(),
600  g1_window,
601  libff::G1<snark_pp<ppT>>::one());
602  libff::leave_block("Generating G1 multiexp table");
603 
604  libff::enter_block("Generating G2 multiexp table");
605  libff::window_table<libff::G2<snark_pp<ppT>>> g2_table = get_window_table(
606  libff::Fr<snark_pp<ppT>>::size_in_bits(),
607  g2_window,
608  libff::G2<snark_pp<ppT>>::one());
609  libff::leave_block("Generating G2 multiexp table");
610 
611  libff::enter_block("Generate R1CS proving key");
612 
613  libff::enter_block("Generate knowledge commitments");
614  libff::enter_block("Compute the A-query", false);
615  knowledge_commitment_vector<
616  libff::G1<snark_pp<ppT>>,
617  libff::G1<snark_pp<ppT>>>
618  A_query = kc_batch_exp(
619  libff::Fr<snark_pp<ppT>>::size_in_bits(),
620  g1_window,
621  g1_window,
622  g1_table,
623  g1_table,
624  rA,
625  rA * alphaA,
626  At,
627  chunks,
628  BaseForm == libff::multi_exp_base_form_special);
629  libff::leave_block("Compute the A-query", false);
630 
631  libff::enter_block("Compute the B-query", false);
632  knowledge_commitment_vector<
633  libff::G2<snark_pp<ppT>>,
634  libff::G1<snark_pp<ppT>>>
635  B_query = kc_batch_exp(
636  libff::Fr<snark_pp<ppT>>::size_in_bits(),
637  g2_window,
638  g1_window,
639  g2_table,
640  g1_table,
641  rB,
642  rB * alphaB,
643  Bt,
644  chunks,
645  BaseForm == libff::multi_exp_base_form_special);
646  libff::leave_block("Compute the B-query", false);
647 
648  libff::enter_block("Compute the C-query", false);
649  knowledge_commitment_vector<
650  libff::G1<snark_pp<ppT>>,
651  libff::G1<snark_pp<ppT>>>
652  C_query = kc_batch_exp(
653  libff::Fr<snark_pp<ppT>>::size_in_bits(),
654  g1_window,
655  g1_window,
656  g1_table,
657  g1_table,
658  rC,
659  rC * alphaC,
660  Ct,
661  chunks,
662  BaseForm == libff::multi_exp_base_form_special);
663  libff::leave_block("Compute the C-query", false);
664 
665  libff::enter_block("Compute the H-query", false);
666  libff::G1_vector<snark_pp<ppT>> H_query = batch_exp(
667  libff::Fr<snark_pp<ppT>>::size_in_bits(), g1_window, g1_table, Ht);
668  if (BaseForm == libff::multi_exp_base_form_special) {
669  libff::batch_to_special<libff::G1<snark_pp<ppT>>>(H_query);
670  }
671  libff::leave_block("Compute the H-query", false);
672 
673  libff::enter_block("Compute the K-query", false);
674  libff::G1_vector<snark_pp<ppT>> K_query = batch_exp(
675  libff::Fr<snark_pp<ppT>>::size_in_bits(), g1_window, g1_table, Kt);
676  if (BaseForm == libff::multi_exp_base_form_special) {
677  libff::batch_to_special<libff::G1<snark_pp<ppT>>>(K_query);
678  }
679  libff::leave_block("Compute the K-query", false);
680 
681  libff::leave_block("Generate knowledge commitments");
682 
683  libff::leave_block("Generate R1CS proving key");
684 
685  libff::enter_block("Generate R1CS verification key");
686  libff::G2<snark_pp<ppT>> alphaA_g2 =
687  alphaA * libff::G2<snark_pp<ppT>>::one();
688  libff::G1<snark_pp<ppT>> alphaB_g1 =
689  alphaB * libff::G1<snark_pp<ppT>>::one();
690  libff::G2<snark_pp<ppT>> alphaC_g2 =
691  alphaC * libff::G2<snark_pp<ppT>>::one();
692  libff::G2<snark_pp<ppT>> gamma_g2 = gamma * libff::G2<snark_pp<ppT>>::one();
693  libff::G1<snark_pp<ppT>> gamma_beta_g1 =
694  (gamma * beta) * libff::G1<snark_pp<ppT>>::one();
695  libff::G2<snark_pp<ppT>> gamma_beta_g2 =
696  (gamma * beta) * libff::G2<snark_pp<ppT>>::one();
697  libff::G2<snark_pp<ppT>> rC_Z_g2 =
698  (rC * qap_inst.Zt) * libff::G2<snark_pp<ppT>>::one();
699 
700  libff::enter_block("Generate extra authentication elements");
701  libff::G1<snark_pp<ppT>> rA_i_Z_g1 = (rA * qap_inst.Zt) * prms.I1;
702  libff::leave_block("Generate extra authentication elements");
703 
704  libff::enter_block(
705  "Copy encoded input coefficients for R1CS verification key");
706  libff::G1<snark_pp<ppT>> A0 = A_query[0].g;
707  libff::G1_vector<snark_pp<ppT>> Ain;
708  Ain.reserve(qap_inst.num_inputs());
709  for (size_t i = 0; i < qap_inst.num_inputs(); ++i) {
710  Ain.emplace_back(A_query[1 + i].g);
711  }
712 
713  libff::leave_block(
714  "Copy encoded input coefficients for R1CS verification key");
715 
716  libff::leave_block("Generate R1CS verification key");
717 
718  libff::leave_block("Call to r1cs_ppzkadsnark_generator");
719 
720  r1cs_ppzkadsnark_verification_key<ppT> vk =
721  r1cs_ppzkadsnark_verification_key<ppT>(
722  alphaA_g2,
723  alphaB_g1,
724  alphaC_g2,
725  gamma_g2,
726  gamma_beta_g1,
727  gamma_beta_g2,
728  rC_Z_g2,
729  A0,
730  Ain);
731  r1cs_ppzkadsnark_proving_key<ppT> pk = r1cs_ppzkadsnark_proving_key<ppT>(
732  std::move(A_query),
733  std::move(B_query),
734  std::move(C_query),
735  std::move(H_query),
736  std::move(K_query),
737  std::move(rA_i_Z_g1),
738  std::move(cs_copy));
739 
740  pk.print_size();
741  vk.print_size();
742 
743  return r1cs_ppzkadsnark_keypair<ppT>(std::move(pk), std::move(vk));
744 }
745 
746 template<typename ppT>
747 r1cs_ppzkadsnark_proof<ppT> r1cs_ppzkadsnark_prover(
748  const r1cs_ppzkadsnark_proving_key<ppT> &pk,
749  const r1cs_ppzkadsnark_primary_input<ppT> &primary_input,
750  const r1cs_ppzkadsnark_auxiliary_input<ppT> &auxiliary_input,
751  const std::vector<r1cs_ppzkadsnark_auth_data<ppT>> &auth_data)
752 {
753  libff::enter_block("Call to r1cs_ppzkadsnark_prover");
754 
755 #ifdef DEBUG
756  assert(pk.constraint_system.is_satisfied(primary_input, auxiliary_input));
757 #endif
758 
759  const libff::Fr<snark_pp<ppT>>
760  d1 = libff::Fr<snark_pp<ppT>>::random_element(),
761  d2 = libff::Fr<snark_pp<ppT>>::random_element(),
762  d3 = libff::Fr<snark_pp<ppT>>::random_element(),
763  dauth = libff::Fr<snark_pp<ppT>>::random_element();
764 
765  libff::enter_block("Compute the polynomial H");
766  const qap_witness<libff::Fr<snark_pp<ppT>>> qap_wit =
767  r1cs_to_qap_witness_map(
768  pk.constraint_system,
769  primary_input,
770  auxiliary_input,
771  d1 + dauth,
772  d2,
773  d3);
774  libff::leave_block("Compute the polynomial H");
775 
776 #ifdef DEBUG
777  const libff::Fr<snark_pp<ppT>> t =
778  libff::Fr<snark_pp<ppT>>::random_element();
779  qap_instance_evaluation<libff::Fr<snark_pp<ppT>>> qap_inst =
780  r1cs_to_qap_instance_map_with_evaluation(pk.constraint_system, t);
781  assert(qap_inst.is_satisfied(qap_wit));
782 #endif
783 
784  knowledge_commitment<libff::G1<snark_pp<ppT>>, libff::G1<snark_pp<ppT>>>
785  g_A =
786  /* pk.A_query[0] + */ d1 * pk.A_query[qap_wit.num_variables() + 1];
787  knowledge_commitment<libff::G2<snark_pp<ppT>>, libff::G1<snark_pp<ppT>>>
788  g_B = pk.B_query[0] +
789  qap_wit.d2 * pk.B_query[qap_wit.num_variables() + 1];
790  knowledge_commitment<libff::G1<snark_pp<ppT>>, libff::G1<snark_pp<ppT>>>
791  g_C = pk.C_query[0] +
792  qap_wit.d3 * pk.C_query[qap_wit.num_variables() + 1];
793 
794  knowledge_commitment<libff::G1<snark_pp<ppT>>, libff::G1<snark_pp<ppT>>>
795  g_Ain = dauth * pk.A_query[qap_wit.num_variables() + 1];
796 
797  libff::G1<snark_pp<ppT>> g_H = libff::G1<snark_pp<ppT>>::zero();
798  libff::G1<snark_pp<ppT>> g_K =
799  (pk.K_query[0] + qap_wit.d1 * pk.K_query[qap_wit.num_variables() + 1] +
800  qap_wit.d2 * pk.K_query[qap_wit.num_variables() + 2] +
801  qap_wit.d3 * pk.K_query[qap_wit.num_variables() + 3]);
802 
803 #ifdef DEBUG
804  for (size_t i = 0; i < qap_wit.num_inputs() + 1; ++i) {
805  assert(pk.A_query[i].g == libff::G1<snark_pp<ppT>>::zero());
806  }
807  assert(pk.A_query.domain_size() == qap_wit.num_variables() + 2);
808  assert(pk.B_query.domain_size() == qap_wit.num_variables() + 2);
809  assert(pk.C_query.domain_size() == qap_wit.num_variables() + 2);
810  assert(pk.H_query.size() == qap_wit.degree() + 1);
811  assert(pk.K_query.size() == qap_wit.num_variables() + 4);
812 #endif
813 
814 #ifdef MULTICORE
815  const size_t chunks =
816  omp_get_max_threads(); // to override, set OMP_NUM_THREADS env var or
817  // call omp_set_num_threads()
818 #else
819  const size_t chunks = 1;
820 #endif
821 
822  libff::enter_block("Compute the proof");
823 
824  libff::enter_block("Compute answer to A-query", false);
825  g_A = g_A +
826  kc_multi_exp_with_mixed_addition<
827  libff::G1<snark_pp<ppT>>,
828  libff::G1<snark_pp<ppT>>,
829  libff::Fr<snark_pp<ppT>>,
830  libff::multi_exp_method_bos_coster>(
831  pk.A_query,
832  1 + qap_wit.num_inputs(),
833  1 + qap_wit.num_variables(),
834  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_inputs(),
835  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
836  chunks);
837  libff::leave_block("Compute answer to A-query", false);
838 
839  libff::enter_block("Compute answer to Ain-query", false);
840  g_Ain = g_Ain +
841  kc_multi_exp_with_mixed_addition<
842  libff::G1<snark_pp<ppT>>,
843  libff::G1<snark_pp<ppT>>,
844  libff::Fr<snark_pp<ppT>>,
845  libff::multi_exp_method_bos_coster>(
846  pk.A_query,
847  1,
848  1 + qap_wit.num_inputs(),
849  qap_wit.coefficients_for_ABCs.begin(),
850  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_inputs(),
851  chunks);
852  // std :: cout << "The input proof term: " << g_Ain << "\n";
853  libff::leave_block("Compute answer to Ain-query", false);
854 
855  libff::enter_block("Compute answer to B-query", false);
856  g_B = g_B +
857  kc_multi_exp_with_mixed_addition<
858  libff::G2<snark_pp<ppT>>,
859  libff::G1<snark_pp<ppT>>,
860  libff::Fr<snark_pp<ppT>>,
861  libff::multi_exp_method_bos_coster>(
862  pk.B_query,
863  1,
864  1 + qap_wit.num_variables(),
865  qap_wit.coefficients_for_ABCs.begin(),
866  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
867  chunks);
868  libff::leave_block("Compute answer to B-query", false);
869 
870  libff::enter_block("Compute answer to C-query", false);
871  g_C = g_C +
872  kc_multi_exp_with_mixed_addition<
873  libff::G1<snark_pp<ppT>>,
874  libff::G1<snark_pp<ppT>>,
875  libff::Fr<snark_pp<ppT>>,
876  libff::multi_exp_method_bos_coster>(
877  pk.C_query,
878  1,
879  1 + qap_wit.num_variables(),
880  qap_wit.coefficients_for_ABCs.begin(),
881  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
882  chunks);
883  libff::leave_block("Compute answer to C-query", false);
884 
885  libff::enter_block("Compute answer to H-query", false);
886  g_H = g_H + libff::multi_exp<
887  libff::G1<snark_pp<ppT>>,
888  libff::Fr<snark_pp<ppT>>,
889  libff::multi_exp_method_BDLO12>(
890  pk.H_query.begin(),
891  pk.H_query.begin() + qap_wit.degree() + 1,
892  qap_wit.coefficients_for_H.begin(),
893  qap_wit.coefficients_for_H.begin() + qap_wit.degree() + 1,
894  chunks);
895  libff::leave_block("Compute answer to H-query", false);
896 
897  libff::enter_block("Compute answer to K-query", false);
898  g_K = g_K +
899  libff::multi_exp_with_mixed_addition<
900  libff::G1<snark_pp<ppT>>,
901  libff::Fr<snark_pp<ppT>>,
902  libff::multi_exp_method_bos_coster>(
903  pk.K_query.begin() + 1,
904  pk.K_query.begin() + 1 + qap_wit.num_variables(),
905  qap_wit.coefficients_for_ABCs.begin(),
906  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
907  chunks);
908  libff::leave_block("Compute answer to K-query", false);
909 
910  libff::enter_block("Compute extra auth terms", false);
911  std::vector<libff::Fr<snark_pp<ppT>>> mus;
912  std::vector<libff::G1<snark_pp<ppT>>> Ains;
913  mus.reserve(qap_wit.num_inputs());
914  Ains.reserve(qap_wit.num_inputs());
915  for (size_t i = 0; i < qap_wit.num_inputs(); i++) {
916  mus.emplace_back(auth_data[i].mu);
917  Ains.emplace_back(pk.A_query[i + 1].g);
918  }
919  libff::G1<snark_pp<ppT>> muA = dauth * pk.rA_i_Z_g1;
920  muA = muA + libff::multi_exp<
921  libff::G1<snark_pp<ppT>>,
922  libff::Fr<snark_pp<ppT>>,
923  libff::multi_exp_method_bos_coster>(
924  Ains.begin(),
925  Ains.begin() + qap_wit.num_inputs(),
926  mus.begin(),
927  mus.begin() + qap_wit.num_inputs(),
928  chunks);
929 
930  // To Do: Decide whether to include relevant parts of auth_data in proof
931  libff::leave_block("Compute extra auth terms", false);
932 
933  libff::leave_block("Compute the proof");
934 
935  libff::leave_block("Call to r1cs_ppzkadsnark_prover");
936 
937  r1cs_ppzkadsnark_proof<ppT> proof = r1cs_ppzkadsnark_proof<ppT>(
938  std::move(g_A),
939  std::move(g_B),
940  std::move(g_C),
941  std::move(g_H),
942  std::move(g_K),
943  std::move(g_Ain),
944  std::move(muA));
945  proof.print_size();
946 
947  return proof;
948 }
949 
950 template<typename ppT>
951 r1cs_ppzkadsnark_processed_verification_key<ppT>
952 r1cs_ppzkadsnark_verifier_process_vk(
953  const r1cs_ppzkadsnark_verification_key<ppT> &vk)
954 {
955  libff::enter_block("Call to r1cs_ppzkadsnark_verifier_process_vk");
956 
957  r1cs_ppzkadsnark_processed_verification_key<ppT> pvk;
958  pvk.pp_G2_one_precomp =
959  snark_pp<ppT>::precompute_G2(libff::G2<snark_pp<ppT>>::one());
960  pvk.vk_alphaA_g2_precomp = snark_pp<ppT>::precompute_G2(vk.alphaA_g2);
961  pvk.vk_alphaB_g1_precomp = snark_pp<ppT>::precompute_G1(vk.alphaB_g1);
962  pvk.vk_alphaC_g2_precomp = snark_pp<ppT>::precompute_G2(vk.alphaC_g2);
963  pvk.vk_rC_Z_g2_precomp = snark_pp<ppT>::precompute_G2(vk.rC_Z_g2);
964  pvk.vk_gamma_g2_precomp = snark_pp<ppT>::precompute_G2(vk.gamma_g2);
965  pvk.vk_gamma_beta_g1_precomp =
966  snark_pp<ppT>::precompute_G1(vk.gamma_beta_g1);
967  pvk.vk_gamma_beta_g2_precomp =
968  snark_pp<ppT>::precompute_G2(vk.gamma_beta_g2);
969 
970  libff::enter_block("Pre-processing for additional auth elements");
971  libff::G2_precomp<snark_pp<ppT>> vk_rC_z_g2_precomp =
972  snark_pp<ppT>::precompute_G2(vk.rC_Z_g2);
973 
974  pvk.A0 = libff::G1<snark_pp<ppT>>(vk.A0);
975  pvk.Ain = libff::G1_vector<snark_pp<ppT>>(vk.Ain);
976 
977  pvk.proof_g_vki_precomp.reserve(pvk.Ain.size());
978  for (size_t i = 0; i < pvk.Ain.size(); i++) {
979  pvk.proof_g_vki_precomp.emplace_back(
980  snark_pp<ppT>::precompute_G1(pvk.Ain[i]));
981  }
982 
983  libff::leave_block("Pre-processing for additional auth elements");
984 
985  libff::leave_block("Call to r1cs_ppzkadsnark_verifier_process_vk");
986 
987  return pvk;
988 }
989 
990 // symmetric
991 template<typename ppT>
992 bool r1cs_ppzkadsnark_online_verifier(
993  const r1cs_ppzkadsnark_processed_verification_key<ppT> &pvk,
994  const r1cs_ppzkadsnark_proof<ppT> &proof,
995  const r1cs_ppzkadsnark_sec_auth_key<ppT> &sak,
996  const std::vector<labelT> &labels)
997 {
998  bool result = true;
999  libff::enter_block("Call to r1cs_ppzkadsnark_online_verifier");
1000 
1001  libff::enter_block("Check if the proof is well-formed");
1002  if (!proof.is_well_formed()) {
1003  if (!libff::inhibit_profiling_info) {
1004  libff::print_indent();
1005  printf("At least one of the proof elements does not lie on the "
1006  "curve.\n");
1007  }
1008  result = false;
1009  }
1010  libff::leave_block("Check if the proof is well-formed");
1011 
1012  libff::enter_block("Checking auth-specific elements");
1013 
1014  libff::enter_block("Checking A1");
1015 
1016  libff::enter_block("Compute PRFs");
1017  std::vector<libff::Fr<snark_pp<ppT>>> lambdas;
1018  lambdas.reserve(labels.size());
1019  for (size_t i = 0; i < labels.size(); i++) {
1020  lambdas.emplace_back(prfCompute<ppT>(sak.S, labels[i]));
1021  }
1022  libff::leave_block("Compute PRFs");
1023  libff::G1<snark_pp<ppT>> prodA = sak.i * proof.g_Aau.g;
1024  prodA = prodA + libff::multi_exp<
1025  libff::G1<snark_pp<ppT>>,
1026  libff::Fr<snark_pp<ppT>>,
1027  libff::multi_exp_method_bos_coster>(
1028  pvk.Ain.begin(),
1029  pvk.Ain.begin() + labels.size(),
1030  lambdas.begin(),
1031  lambdas.begin() + labels.size(),
1032  1);
1033 
1034  bool result_auth = true;
1035 
1036  if (!(prodA == proof.muA)) {
1037  if (!libff::inhibit_profiling_info) {
1038  libff::print_indent();
1039  printf("Authentication check failed.\n");
1040  }
1041  result_auth = false;
1042  }
1043 
1044  libff::leave_block("Checking A1");
1045 
1046  libff::enter_block("Checking A2");
1047  libff::G1_precomp<snark_pp<ppT>> proof_g_Aau_g_precomp =
1048  snark_pp<ppT>::precompute_G1(proof.g_Aau.g);
1049  libff::G1_precomp<snark_pp<ppT>> proof_g_Aau_h_precomp =
1050  snark_pp<ppT>::precompute_G1(proof.g_Aau.h);
1051  libff::Fqk<snark_pp<ppT>> kc_Aau_1 = snark_pp<ppT>::miller_loop(
1052  proof_g_Aau_g_precomp, pvk.vk_alphaA_g2_precomp);
1053  libff::Fqk<snark_pp<ppT>> kc_Aau_2 = snark_pp<ppT>::miller_loop(
1054  proof_g_Aau_h_precomp, pvk.pp_G2_one_precomp);
1055  libff::GT<snark_pp<ppT>> kc_Aau = snark_pp<ppT>::final_exponentiation(
1056  kc_Aau_1 * kc_Aau_2.unitary_inverse());
1057  if (kc_Aau != libff::GT<snark_pp<ppT>>::one()) {
1058  if (!libff::inhibit_profiling_info) {
1059  libff::print_indent();
1060  printf("Knowledge commitment for Aau query incorrect.\n");
1061  }
1062  result_auth = false;
1063  }
1064  libff::leave_block("Checking A2");
1065 
1066  libff::leave_block("Checking auth-specific elements");
1067 
1068  result &= result_auth;
1069 
1070  libff::enter_block("Online pairing computations");
1071  libff::enter_block("Check knowledge commitment for A is valid");
1072  libff::G1_precomp<snark_pp<ppT>> proof_g_A_g_precomp =
1073  snark_pp<ppT>::precompute_G1(proof.g_A.g);
1074  libff::G1_precomp<snark_pp<ppT>> proof_g_A_h_precomp =
1075  snark_pp<ppT>::precompute_G1(proof.g_A.h);
1076  libff::Fqk<snark_pp<ppT>> kc_A_1 = snark_pp<ppT>::miller_loop(
1077  proof_g_A_g_precomp, pvk.vk_alphaA_g2_precomp);
1078  libff::Fqk<snark_pp<ppT>> kc_A_2 =
1079  snark_pp<ppT>::miller_loop(proof_g_A_h_precomp, pvk.pp_G2_one_precomp);
1080  libff::GT<snark_pp<ppT>> kc_A =
1081  snark_pp<ppT>::final_exponentiation(kc_A_1 * kc_A_2.unitary_inverse());
1082  if (kc_A != libff::GT<snark_pp<ppT>>::one()) {
1083  if (!libff::inhibit_profiling_info) {
1084  libff::print_indent();
1085  printf("Knowledge commitment for A query incorrect.\n");
1086  }
1087  result = false;
1088  }
1089  libff::leave_block("Check knowledge commitment for A is valid");
1090 
1091  libff::enter_block("Check knowledge commitment for B is valid");
1092  libff::G2_precomp<snark_pp<ppT>> proof_g_B_g_precomp =
1093  snark_pp<ppT>::precompute_G2(proof.g_B.g);
1094  libff::G1_precomp<snark_pp<ppT>> proof_g_B_h_precomp =
1095  snark_pp<ppT>::precompute_G1(proof.g_B.h);
1096  libff::Fqk<snark_pp<ppT>> kc_B_1 = snark_pp<ppT>::miller_loop(
1097  pvk.vk_alphaB_g1_precomp, proof_g_B_g_precomp);
1098  libff::Fqk<snark_pp<ppT>> kc_B_2 =
1099  snark_pp<ppT>::miller_loop(proof_g_B_h_precomp, pvk.pp_G2_one_precomp);
1100  libff::GT<snark_pp<ppT>> kc_B =
1101  snark_pp<ppT>::final_exponentiation(kc_B_1 * kc_B_2.unitary_inverse());
1102  if (kc_B != libff::GT<snark_pp<ppT>>::one()) {
1103  if (!libff::inhibit_profiling_info) {
1104  libff::print_indent();
1105  printf("Knowledge commitment for B query incorrect.\n");
1106  }
1107  result = false;
1108  }
1109  libff::leave_block("Check knowledge commitment for B is valid");
1110 
1111  libff::enter_block("Check knowledge commitment for C is valid");
1112  libff::G1_precomp<snark_pp<ppT>> proof_g_C_g_precomp =
1113  snark_pp<ppT>::precompute_G1(proof.g_C.g);
1114  libff::G1_precomp<snark_pp<ppT>> proof_g_C_h_precomp =
1115  snark_pp<ppT>::precompute_G1(proof.g_C.h);
1116  libff::Fqk<snark_pp<ppT>> kc_C_1 = snark_pp<ppT>::miller_loop(
1117  proof_g_C_g_precomp, pvk.vk_alphaC_g2_precomp);
1118  libff::Fqk<snark_pp<ppT>> kc_C_2 =
1119  snark_pp<ppT>::miller_loop(proof_g_C_h_precomp, pvk.pp_G2_one_precomp);
1120  libff::GT<snark_pp<ppT>> kc_C =
1121  snark_pp<ppT>::final_exponentiation(kc_C_1 * kc_C_2.unitary_inverse());
1122  if (kc_C != libff::GT<snark_pp<ppT>>::one()) {
1123  if (!libff::inhibit_profiling_info) {
1124  libff::print_indent();
1125  printf("Knowledge commitment for C query incorrect.\n");
1126  }
1127  result = false;
1128  }
1129  libff::leave_block("Check knowledge commitment for C is valid");
1130 
1131  libff::G1<snark_pp<ppT>> Aacc = pvk.A0 + proof.g_Aau.g + proof.g_A.g;
1132 
1133  libff::enter_block("Check QAP divisibility");
1134  libff::G1_precomp<snark_pp<ppT>> proof_g_Aacc_precomp =
1135  snark_pp<ppT>::precompute_G1(Aacc);
1136  libff::G1_precomp<snark_pp<ppT>> proof_g_H_precomp =
1137  snark_pp<ppT>::precompute_G1(proof.g_H);
1138  libff::Fqk<snark_pp<ppT>> QAP_1 =
1139  snark_pp<ppT>::miller_loop(proof_g_Aacc_precomp, proof_g_B_g_precomp);
1140  libff::Fqk<snark_pp<ppT>> QAP_23 = snark_pp<ppT>::double_miller_loop(
1141  proof_g_H_precomp,
1142  pvk.vk_rC_Z_g2_precomp,
1143  proof_g_C_g_precomp,
1144  pvk.pp_G2_one_precomp);
1145  libff::GT<snark_pp<ppT>> QAP =
1146  snark_pp<ppT>::final_exponentiation(QAP_1 * QAP_23.unitary_inverse());
1147  if (QAP != libff::GT<snark_pp<ppT>>::one()) {
1148  if (!libff::inhibit_profiling_info) {
1149  libff::print_indent();
1150  printf("QAP divisibility check failed.\n");
1151  }
1152  result = false;
1153  }
1154  libff::leave_block("Check QAP divisibility");
1155 
1156  libff::enter_block("Check same coefficients were used");
1157  libff::G1_precomp<snark_pp<ppT>> proof_g_K_precomp =
1158  snark_pp<ppT>::precompute_G1(proof.g_K);
1159  libff::G1_precomp<snark_pp<ppT>> proof_g_Aacc_C_precomp =
1160  snark_pp<ppT>::precompute_G1(Aacc + proof.g_C.g);
1161  libff::Fqk<snark_pp<ppT>> K_1 =
1162  snark_pp<ppT>::miller_loop(proof_g_K_precomp, pvk.vk_gamma_g2_precomp);
1163  libff::Fqk<snark_pp<ppT>> K_23 = snark_pp<ppT>::double_miller_loop(
1164  proof_g_Aacc_C_precomp,
1165  pvk.vk_gamma_beta_g2_precomp,
1166  pvk.vk_gamma_beta_g1_precomp,
1167  proof_g_B_g_precomp);
1168  libff::GT<snark_pp<ppT>> K =
1169  snark_pp<ppT>::final_exponentiation(K_1 * K_23.unitary_inverse());
1170  if (K != libff::GT<snark_pp<ppT>>::one()) {
1171  if (!libff::inhibit_profiling_info) {
1172  libff::print_indent();
1173  printf("Same-coefficient check failed.\n");
1174  }
1175  result = false;
1176  }
1177  libff::leave_block("Check same coefficients were used");
1178  libff::leave_block("Online pairing computations");
1179  libff::leave_block("Call to r1cs_ppzkadsnark_online_verifier");
1180 
1181  return result;
1182 }
1183 
1184 template<typename ppT>
1185 bool r1cs_ppzkadsnark_verifier(
1186  const r1cs_ppzkadsnark_verification_key<ppT> &vk,
1187  const r1cs_ppzkadsnark_proof<ppT> &proof,
1188  const r1cs_ppzkadsnark_sec_auth_key<ppT> &sak,
1189  const std::vector<labelT> &labels)
1190 {
1191  libff::enter_block("Call to r1cs_ppzkadsnark_verifier");
1192  r1cs_ppzkadsnark_processed_verification_key<ppT> pvk =
1193  r1cs_ppzkadsnark_verifier_process_vk<ppT>(vk);
1194  bool result =
1195  r1cs_ppzkadsnark_online_verifier<ppT>(pvk, proof, sak, labels);
1196  libff::leave_block("Call to r1cs_ppzkadsnark_verifier");
1197  return result;
1198 }
1199 
1200 // public
1201 template<typename ppT>
1202 bool r1cs_ppzkadsnark_online_verifier(
1203  const r1cs_ppzkadsnark_processed_verification_key<ppT> &pvk,
1204  const std::vector<r1cs_ppzkadsnark_auth_data<ppT>> &auth_data,
1205  const r1cs_ppzkadsnark_proof<ppT> &proof,
1206  const r1cs_ppzkadsnark_pub_auth_key<ppT> &pak,
1207  const std::vector<labelT> &labels)
1208 {
1209  bool result = true;
1210  libff::enter_block("Call to r1cs_ppzkadsnark_online_verifier");
1211 
1212  libff::enter_block("Check if the proof is well-formed");
1213  if (!proof.is_well_formed()) {
1214  if (!libff::inhibit_profiling_info) {
1215  libff::print_indent();
1216  printf("At least one of the proof elements does not lie on the "
1217  "curve.\n");
1218  }
1219  result = false;
1220  }
1221  libff::leave_block("Check if the proof is well-formed");
1222 
1223  libff::enter_block("Checking auth-specific elements");
1224  assert(labels.size() == auth_data.size());
1225 
1226  libff::enter_block("Checking A1");
1227 
1228  libff::enter_block("Checking signatures");
1229  std::vector<libff::G2<snark_pp<ppT>>> Lambdas;
1230  std::vector<r1cs_ppzkadsnark_sigT<ppT>> sigs;
1231  Lambdas.reserve(labels.size());
1232  sigs.reserve(labels.size());
1233  for (size_t i = 0; i < labels.size(); i++) {
1234  Lambdas.emplace_back(auth_data[i].Lambda);
1235  sigs.emplace_back(auth_data[i].sigma);
1236  }
1237  bool result_auth = sigBatchVerif<ppT>(pak.vkp, labels, Lambdas, sigs);
1238  if (!result_auth) {
1239  if (!libff::inhibit_profiling_info) {
1240  libff::print_indent();
1241  printf("Auth sig check failed.\n");
1242  }
1243  }
1244 
1245  libff::leave_block("Checking signatures");
1246 
1247  libff::enter_block("Checking pairings");
1248  // To Do: Decide whether to move pak and lambda preprocessing to offline
1249  std::vector<libff::G2_precomp<snark_pp<ppT>>> g_Lambdas_precomp;
1250  g_Lambdas_precomp.reserve(auth_data.size());
1251  for (size_t i = 0; i < auth_data.size(); i++)
1252  g_Lambdas_precomp.emplace_back(
1253  snark_pp<ppT>::precompute_G2(auth_data[i].Lambda));
1254  libff::G2_precomp<snark_pp<ppT>> g_minusi_precomp =
1255  snark_pp<ppT>::precompute_G2(pak.minusI2);
1256 
1257  libff::enter_block("Computation");
1258  libff::Fqk<snark_pp<ppT>> accum;
1259  if (auth_data.size() % 2 == 1) {
1260  accum = snark_pp<ppT>::miller_loop(
1261  pvk.proof_g_vki_precomp[0], g_Lambdas_precomp[0]);
1262  } else {
1263  accum = libff::Fqk<snark_pp<ppT>>::one();
1264  }
1265  for (size_t i = auth_data.size() % 2; i < labels.size(); i = i + 2) {
1266  accum = accum * snark_pp<ppT>::double_miller_loop(
1267  pvk.proof_g_vki_precomp[i],
1268  g_Lambdas_precomp[i],
1269  pvk.proof_g_vki_precomp[i + 1],
1270  g_Lambdas_precomp[i + 1]);
1271  }
1272  libff::G1_precomp<snark_pp<ppT>> proof_g_muA_precomp =
1273  snark_pp<ppT>::precompute_G1(proof.muA);
1274  libff::G1_precomp<snark_pp<ppT>> proof_g_Aau_precomp =
1275  snark_pp<ppT>::precompute_G1(proof.g_Aau.g);
1276  libff::Fqk<snark_pp<ppT>> accum2 = snark_pp<ppT>::double_miller_loop(
1277  proof_g_muA_precomp,
1278  pvk.pp_G2_one_precomp,
1279  proof_g_Aau_precomp,
1280  g_minusi_precomp);
1281  libff::GT<snark_pp<ppT>> authPair =
1282  snark_pp<ppT>::final_exponentiation(accum * accum2.unitary_inverse());
1283  if (authPair != libff::GT<snark_pp<ppT>>::one()) {
1284  if (!libff::inhibit_profiling_info) {
1285  libff::print_indent();
1286  printf("Auth pairing check failed.\n");
1287  }
1288  result_auth = false;
1289  }
1290  libff::leave_block("Computation");
1291  libff::leave_block("Checking pairings");
1292 
1293  if (!(result_auth)) {
1294  if (!libff::inhibit_profiling_info) {
1295  libff::print_indent();
1296  printf("Authentication check failed.\n");
1297  }
1298  }
1299 
1300  libff::leave_block("Checking A1");
1301 
1302  libff::enter_block("Checking A2");
1303  libff::G1_precomp<snark_pp<ppT>> proof_g_Aau_g_precomp =
1304  snark_pp<ppT>::precompute_G1(proof.g_Aau.g);
1305  libff::G1_precomp<snark_pp<ppT>> proof_g_Aau_h_precomp =
1306  snark_pp<ppT>::precompute_G1(proof.g_Aau.h);
1307  libff::Fqk<snark_pp<ppT>> kc_Aau_1 = snark_pp<ppT>::miller_loop(
1308  proof_g_Aau_g_precomp, pvk.vk_alphaA_g2_precomp);
1309  libff::Fqk<snark_pp<ppT>> kc_Aau_2 = snark_pp<ppT>::miller_loop(
1310  proof_g_Aau_h_precomp, pvk.pp_G2_one_precomp);
1311  libff::GT<snark_pp<ppT>> kc_Aau = snark_pp<ppT>::final_exponentiation(
1312  kc_Aau_1 * kc_Aau_2.unitary_inverse());
1313  if (kc_Aau != libff::GT<snark_pp<ppT>>::one()) {
1314  if (!libff::inhibit_profiling_info) {
1315  libff::print_indent();
1316  printf("Knowledge commitment for Aau query incorrect.\n");
1317  }
1318  result_auth = false;
1319  }
1320  libff::leave_block("Checking A2");
1321 
1322  libff::leave_block("Checking auth-specific elements");
1323 
1324  result &= result_auth;
1325 
1326  libff::enter_block("Online pairing computations");
1327  libff::enter_block("Check knowledge commitment for A is valid");
1328  libff::G1_precomp<snark_pp<ppT>> proof_g_A_g_precomp =
1329  snark_pp<ppT>::precompute_G1(proof.g_A.g);
1330  libff::G1_precomp<snark_pp<ppT>> proof_g_A_h_precomp =
1331  snark_pp<ppT>::precompute_G1(proof.g_A.h);
1332  libff::Fqk<snark_pp<ppT>> kc_A_1 = snark_pp<ppT>::miller_loop(
1333  proof_g_A_g_precomp, pvk.vk_alphaA_g2_precomp);
1334  libff::Fqk<snark_pp<ppT>> kc_A_2 =
1335  snark_pp<ppT>::miller_loop(proof_g_A_h_precomp, pvk.pp_G2_one_precomp);
1336  libff::GT<snark_pp<ppT>> kc_A =
1337  snark_pp<ppT>::final_exponentiation(kc_A_1 * kc_A_2.unitary_inverse());
1338  if (kc_A != libff::GT<snark_pp<ppT>>::one()) {
1339  if (!libff::inhibit_profiling_info) {
1340  libff::print_indent();
1341  printf("Knowledge commitment for A query incorrect.\n");
1342  }
1343  result = false;
1344  }
1345  libff::leave_block("Check knowledge commitment for A is valid");
1346 
1347  libff::enter_block("Check knowledge commitment for B is valid");
1348  libff::G2_precomp<snark_pp<ppT>> proof_g_B_g_precomp =
1349  snark_pp<ppT>::precompute_G2(proof.g_B.g);
1350  libff::G1_precomp<snark_pp<ppT>> proof_g_B_h_precomp =
1351  snark_pp<ppT>::precompute_G1(proof.g_B.h);
1352  libff::Fqk<snark_pp<ppT>> kc_B_1 = snark_pp<ppT>::miller_loop(
1353  pvk.vk_alphaB_g1_precomp, proof_g_B_g_precomp);
1354  libff::Fqk<snark_pp<ppT>> kc_B_2 =
1355  snark_pp<ppT>::miller_loop(proof_g_B_h_precomp, pvk.pp_G2_one_precomp);
1356  libff::GT<snark_pp<ppT>> kc_B =
1357  snark_pp<ppT>::final_exponentiation(kc_B_1 * kc_B_2.unitary_inverse());
1358  if (kc_B != libff::GT<snark_pp<ppT>>::one()) {
1359  if (!libff::inhibit_profiling_info) {
1360  libff::print_indent();
1361  printf("Knowledge commitment for B query incorrect.\n");
1362  }
1363  result = false;
1364  }
1365  libff::leave_block("Check knowledge commitment for B is valid");
1366 
1367  libff::enter_block("Check knowledge commitment for C is valid");
1368  libff::G1_precomp<snark_pp<ppT>> proof_g_C_g_precomp =
1369  snark_pp<ppT>::precompute_G1(proof.g_C.g);
1370  libff::G1_precomp<snark_pp<ppT>> proof_g_C_h_precomp =
1371  snark_pp<ppT>::precompute_G1(proof.g_C.h);
1372  libff::Fqk<snark_pp<ppT>> kc_C_1 = snark_pp<ppT>::miller_loop(
1373  proof_g_C_g_precomp, pvk.vk_alphaC_g2_precomp);
1374  libff::Fqk<snark_pp<ppT>> kc_C_2 =
1375  snark_pp<ppT>::miller_loop(proof_g_C_h_precomp, pvk.pp_G2_one_precomp);
1376  libff::GT<snark_pp<ppT>> kc_C =
1377  snark_pp<ppT>::final_exponentiation(kc_C_1 * kc_C_2.unitary_inverse());
1378  if (kc_C != libff::GT<snark_pp<ppT>>::one()) {
1379  if (!libff::inhibit_profiling_info) {
1380  libff::print_indent();
1381  printf("Knowledge commitment for C query incorrect.\n");
1382  }
1383  result = false;
1384  }
1385  libff::leave_block("Check knowledge commitment for C is valid");
1386 
1387  libff::G1<snark_pp<ppT>> Aacc = pvk.A0 + proof.g_Aau.g + proof.g_A.g;
1388 
1389  libff::enter_block("Check QAP divisibility");
1390  libff::G1_precomp<snark_pp<ppT>> proof_g_Aacc_precomp =
1391  snark_pp<ppT>::precompute_G1(Aacc);
1392  libff::G1_precomp<snark_pp<ppT>> proof_g_H_precomp =
1393  snark_pp<ppT>::precompute_G1(proof.g_H);
1394  libff::Fqk<snark_pp<ppT>> QAP_1 =
1395  snark_pp<ppT>::miller_loop(proof_g_Aacc_precomp, proof_g_B_g_precomp);
1396  libff::Fqk<snark_pp<ppT>> QAP_23 = snark_pp<ppT>::double_miller_loop(
1397  proof_g_H_precomp,
1398  pvk.vk_rC_Z_g2_precomp,
1399  proof_g_C_g_precomp,
1400  pvk.pp_G2_one_precomp);
1401  libff::GT<snark_pp<ppT>> QAP =
1402  snark_pp<ppT>::final_exponentiation(QAP_1 * QAP_23.unitary_inverse());
1403  if (QAP != libff::GT<snark_pp<ppT>>::one()) {
1404  if (!libff::inhibit_profiling_info) {
1405  libff::print_indent();
1406  printf("QAP divisibility check failed.\n");
1407  }
1408  result = false;
1409  }
1410  libff::leave_block("Check QAP divisibility");
1411 
1412  libff::enter_block("Check same coefficients were used");
1413  libff::G1_precomp<snark_pp<ppT>> proof_g_K_precomp =
1414  snark_pp<ppT>::precompute_G1(proof.g_K);
1415  libff::G1_precomp<snark_pp<ppT>> proof_g_Aacc_C_precomp =
1416  snark_pp<ppT>::precompute_G1(Aacc + proof.g_C.g);
1417  libff::Fqk<snark_pp<ppT>> K_1 =
1418  snark_pp<ppT>::miller_loop(proof_g_K_precomp, pvk.vk_gamma_g2_precomp);
1419  libff::Fqk<snark_pp<ppT>> K_23 = snark_pp<ppT>::double_miller_loop(
1420  proof_g_Aacc_C_precomp,
1421  pvk.vk_gamma_beta_g2_precomp,
1422  pvk.vk_gamma_beta_g1_precomp,
1423  proof_g_B_g_precomp);
1424  libff::GT<snark_pp<ppT>> K =
1425  snark_pp<ppT>::final_exponentiation(K_1 * K_23.unitary_inverse());
1426  if (K != libff::GT<snark_pp<ppT>>::one()) {
1427  if (!libff::inhibit_profiling_info) {
1428  libff::print_indent();
1429  printf("Same-coefficient check failed.\n");
1430  }
1431  result = false;
1432  }
1433  libff::leave_block("Check same coefficients were used");
1434  libff::leave_block("Online pairing computations");
1435  libff::leave_block("Call to r1cs_ppzkadsnark_online_verifier");
1436 
1437  return result;
1438 }
1439 
1440 // public
1441 template<typename ppT>
1442 bool r1cs_ppzkadsnark_verifier(
1443  const r1cs_ppzkadsnark_verification_key<ppT> &vk,
1444  const std::vector<r1cs_ppzkadsnark_auth_data<ppT>> &auth_data,
1445  const r1cs_ppzkadsnark_proof<ppT> &proof,
1446  const r1cs_ppzkadsnark_pub_auth_key<ppT> &pak,
1447  const std::vector<labelT> &labels)
1448 {
1449  assert(labels.size() == auth_data.size());
1450  libff::enter_block("Call to r1cs_ppzkadsnark_verifier");
1451  r1cs_ppzkadsnark_processed_verification_key<ppT> pvk =
1452  r1cs_ppzkadsnark_verifier_process_vk<ppT>(vk);
1453  bool result = r1cs_ppzkadsnark_online_verifier<ppT>(
1454  pvk, auth_data, proof, pak, labels);
1455  libff::leave_block("Call to r1cs_ppzkadsnark_verifier");
1456  return result;
1457 }
1458 
1459 } // namespace libsnark
1460 #endif // R1CS_PPZKADSNARK_TCC_
Generated on Wed Jan 25 2023 11:05:58 for Clearmatics Libsnark by   doxygen 1.8.17