Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
r1cs_ppzksnark.tcc
Go to the documentation of this file.
1 /** @file
2 *****************************************************************************
3 
4 Implementation of interfaces for a ppzkSNARK for R1CS.
5 
6 See r1cs_ppzksnark.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_PPZKSNARK_TCC_
15 #define R1CS_PPZKSNARK_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_ppzksnark_proving_key<ppT>::operator==(
38  const r1cs_ppzksnark_proving_key<ppT> &other) const
39 {
40  return (
41  this->A_query == other.A_query && this->B_query == other.B_query &&
42  this->C_query == other.C_query && this->H_query == other.H_query &&
43  this->K_query == other.K_query &&
44  this->constraint_system == other.constraint_system);
45 }
46 
47 template<typename ppT>
48 std::ostream &operator<<(
49  std::ostream &out, const r1cs_ppzksnark_proving_key<ppT> &pk)
50 {
51  out << pk.A_query;
52  out << pk.B_query;
53  out << pk.C_query;
54  out << pk.H_query;
55  out << pk.K_query;
56  out << pk.constraint_system;
57 
58  return out;
59 }
60 
61 template<typename ppT>
62 std::istream &operator>>(std::istream &in, r1cs_ppzksnark_proving_key<ppT> &pk)
63 {
64  in >> pk.A_query;
65  in >> pk.B_query;
66  in >> pk.C_query;
67  in >> pk.H_query;
68  in >> pk.K_query;
69  in >> pk.constraint_system;
70 
71  return in;
72 }
73 
74 template<typename ppT>
75 bool r1cs_ppzksnark_verification_key<ppT>::operator==(
76  const r1cs_ppzksnark_verification_key<ppT> &other) const
77 {
78  return (
79  this->alphaA_g2 == other.alphaA_g2 &&
80  this->alphaB_g1 == other.alphaB_g1 &&
81  this->alphaC_g2 == other.alphaC_g2 &&
82  this->gamma_g2 == other.gamma_g2 &&
83  this->gamma_beta_g1 == other.gamma_beta_g1 &&
84  this->gamma_beta_g2 == other.gamma_beta_g2 &&
85  this->rC_Z_g2 == other.rC_Z_g2 &&
86  this->encoded_IC_query == other.encoded_IC_query);
87 }
88 
89 template<typename ppT>
90 std::ostream &operator<<(
91  std::ostream &out, const r1cs_ppzksnark_verification_key<ppT> &vk)
92 {
93  out << vk.alphaA_g2 << OUTPUT_NEWLINE;
94  out << vk.alphaB_g1 << OUTPUT_NEWLINE;
95  out << vk.alphaC_g2 << OUTPUT_NEWLINE;
96  out << vk.gamma_g2 << OUTPUT_NEWLINE;
97  out << vk.gamma_beta_g1 << OUTPUT_NEWLINE;
98  out << vk.gamma_beta_g2 << OUTPUT_NEWLINE;
99  out << vk.rC_Z_g2 << OUTPUT_NEWLINE;
100  out << vk.encoded_IC_query << OUTPUT_NEWLINE;
101 
102  return out;
103 }
104 
105 template<typename ppT>
106 std::istream &operator>>(
107  std::istream &in, r1cs_ppzksnark_verification_key<ppT> &vk)
108 {
109  in >> vk.alphaA_g2;
110  libff::consume_OUTPUT_NEWLINE(in);
111  in >> vk.alphaB_g1;
112  libff::consume_OUTPUT_NEWLINE(in);
113  in >> vk.alphaC_g2;
114  libff::consume_OUTPUT_NEWLINE(in);
115  in >> vk.gamma_g2;
116  libff::consume_OUTPUT_NEWLINE(in);
117  in >> vk.gamma_beta_g1;
118  libff::consume_OUTPUT_NEWLINE(in);
119  in >> vk.gamma_beta_g2;
120  libff::consume_OUTPUT_NEWLINE(in);
121  in >> vk.rC_Z_g2;
122  libff::consume_OUTPUT_NEWLINE(in);
123  in >> vk.encoded_IC_query;
124  libff::consume_OUTPUT_NEWLINE(in);
125 
126  return in;
127 }
128 
129 template<typename ppT>
130 bool r1cs_ppzksnark_processed_verification_key<ppT>::operator==(
131  const r1cs_ppzksnark_processed_verification_key<ppT> &other) const
132 {
133  return (
134  this->pp_G2_one_precomp == other.pp_G2_one_precomp &&
135  this->vk_alphaA_g2_precomp == other.vk_alphaA_g2_precomp &&
136  this->vk_alphaB_g1_precomp == other.vk_alphaB_g1_precomp &&
137  this->vk_alphaC_g2_precomp == other.vk_alphaC_g2_precomp &&
138  this->vk_rC_Z_g2_precomp == other.vk_rC_Z_g2_precomp &&
139  this->vk_gamma_g2_precomp == other.vk_gamma_g2_precomp &&
140  this->vk_gamma_beta_g1_precomp == other.vk_gamma_beta_g1_precomp &&
141  this->vk_gamma_beta_g2_precomp == other.vk_gamma_beta_g2_precomp &&
142  this->encoded_IC_query == other.encoded_IC_query);
143 }
144 
145 template<typename ppT>
146 std::ostream &operator<<(
147  std::ostream &out,
148  const r1cs_ppzksnark_processed_verification_key<ppT> &pvk)
149 {
150  out << pvk.pp_G2_one_precomp << OUTPUT_NEWLINE;
151  out << pvk.vk_alphaA_g2_precomp << OUTPUT_NEWLINE;
152  out << pvk.vk_alphaB_g1_precomp << OUTPUT_NEWLINE;
153  out << pvk.vk_alphaC_g2_precomp << OUTPUT_NEWLINE;
154  out << pvk.vk_rC_Z_g2_precomp << OUTPUT_NEWLINE;
155  out << pvk.vk_gamma_g2_precomp << OUTPUT_NEWLINE;
156  out << pvk.vk_gamma_beta_g1_precomp << OUTPUT_NEWLINE;
157  out << pvk.vk_gamma_beta_g2_precomp << OUTPUT_NEWLINE;
158  out << pvk.encoded_IC_query << OUTPUT_NEWLINE;
159 
160  return out;
161 }
162 
163 template<typename ppT>
164 std::istream &operator>>(
165  std::istream &in, r1cs_ppzksnark_processed_verification_key<ppT> &pvk)
166 {
167  in >> pvk.pp_G2_one_precomp;
168  libff::consume_OUTPUT_NEWLINE(in);
169  in >> pvk.vk_alphaA_g2_precomp;
170  libff::consume_OUTPUT_NEWLINE(in);
171  in >> pvk.vk_alphaB_g1_precomp;
172  libff::consume_OUTPUT_NEWLINE(in);
173  in >> pvk.vk_alphaC_g2_precomp;
174  libff::consume_OUTPUT_NEWLINE(in);
175  in >> pvk.vk_rC_Z_g2_precomp;
176  libff::consume_OUTPUT_NEWLINE(in);
177  in >> pvk.vk_gamma_g2_precomp;
178  libff::consume_OUTPUT_NEWLINE(in);
179  in >> pvk.vk_gamma_beta_g1_precomp;
180  libff::consume_OUTPUT_NEWLINE(in);
181  in >> pvk.vk_gamma_beta_g2_precomp;
182  libff::consume_OUTPUT_NEWLINE(in);
183  in >> pvk.encoded_IC_query;
184  libff::consume_OUTPUT_NEWLINE(in);
185 
186  return in;
187 }
188 
189 template<typename ppT>
190 bool r1cs_ppzksnark_proof<ppT>::operator==(
191  const r1cs_ppzksnark_proof<ppT> &other) const
192 {
193  return (
194  this->g_A == other.g_A && this->g_B == other.g_B &&
195  this->g_C == other.g_C && this->g_H == other.g_H &&
196  this->g_K == other.g_K);
197 }
198 
199 template<typename ppT>
200 std::ostream &operator<<(
201  std::ostream &out, const r1cs_ppzksnark_proof<ppT> &proof)
202 {
203  out << proof.g_A << OUTPUT_NEWLINE;
204  out << proof.g_B << OUTPUT_NEWLINE;
205  out << proof.g_C << OUTPUT_NEWLINE;
206  out << proof.g_H << OUTPUT_NEWLINE;
207  out << proof.g_K << OUTPUT_NEWLINE;
208 
209  return out;
210 }
211 
212 template<typename ppT>
213 std::istream &operator>>(std::istream &in, r1cs_ppzksnark_proof<ppT> &proof)
214 {
215  in >> proof.g_A;
216  libff::consume_OUTPUT_NEWLINE(in);
217  in >> proof.g_B;
218  libff::consume_OUTPUT_NEWLINE(in);
219  in >> proof.g_C;
220  libff::consume_OUTPUT_NEWLINE(in);
221  in >> proof.g_H;
222  libff::consume_OUTPUT_NEWLINE(in);
223  in >> proof.g_K;
224  libff::consume_OUTPUT_NEWLINE(in);
225 
226  return in;
227 }
228 
229 template<typename ppT>
230 r1cs_ppzksnark_verification_key<ppT> r1cs_ppzksnark_verification_key<
231  ppT>::dummy_verification_key(const size_t input_size)
232 {
233  r1cs_ppzksnark_verification_key<ppT> result;
234  result.alphaA_g2 = libff::Fr<ppT>::random_element() * libff::G2<ppT>::one();
235  result.alphaB_g1 = libff::Fr<ppT>::random_element() * libff::G1<ppT>::one();
236  result.alphaC_g2 = libff::Fr<ppT>::random_element() * libff::G2<ppT>::one();
237  result.gamma_g2 = libff::Fr<ppT>::random_element() * libff::G2<ppT>::one();
238  result.gamma_beta_g1 =
239  libff::Fr<ppT>::random_element() * libff::G1<ppT>::one();
240  result.gamma_beta_g2 =
241  libff::Fr<ppT>::random_element() * libff::G2<ppT>::one();
242  result.rC_Z_g2 = libff::Fr<ppT>::random_element() * libff::G2<ppT>::one();
243 
244  libff::G1<ppT> base =
245  libff::Fr<ppT>::random_element() * libff::G1<ppT>::one();
246  libff::G1_vector<ppT> v;
247  for (size_t i = 0; i < input_size; ++i) {
248  v.emplace_back(
249  libff::Fr<ppT>::random_element() * libff::G1<ppT>::one());
250  }
251 
252  result.encoded_IC_query =
253  accumulation_vector<libff::G1<ppT>>(std::move(base), std::move(v));
254 
255  return result;
256 }
257 
258 template<typename ppT, libff::multi_exp_base_form BaseForm>
259 r1cs_ppzksnark_keypair<ppT> r1cs_ppzksnark_generator(
260  const r1cs_ppzksnark_constraint_system<ppT> &cs)
261 {
262  libff::enter_block("Call to r1cs_ppzksnark_generator");
263 
264  /* make the B_query "lighter" if possible */
265  r1cs_ppzksnark_constraint_system<ppT> cs_copy(cs);
266  cs_copy.swap_AB_if_beneficial();
267 
268  /* draw random element at which the QAP is evaluated */
269  const libff::Fr<ppT> t = libff::Fr<ppT>::random_element();
270 
271  qap_instance_evaluation<libff::Fr<ppT>> qap_inst =
272  r1cs_to_qap_instance_map_with_evaluation(cs_copy, t);
273 
274  libff::print_indent();
275  printf("* QAP number of variables: %zu\n", qap_inst.num_variables());
276  libff::print_indent();
277  printf("* QAP pre degree: %zu\n", cs_copy.constraints.size());
278  libff::print_indent();
279  printf("* QAP degree: %zu\n", qap_inst.degree());
280  libff::print_indent();
281  printf("* QAP number of input variables: %zu\n", qap_inst.num_inputs());
282 
283  libff::enter_block("Compute query densities");
284  size_t non_zero_At = 0, non_zero_Bt = 0, non_zero_Ct = 0, non_zero_Ht = 0;
285  for (size_t i = 0; i < qap_inst.num_variables() + 1; ++i) {
286  if (!qap_inst.At[i].is_zero()) {
287  ++non_zero_At;
288  }
289  if (!qap_inst.Bt[i].is_zero()) {
290  ++non_zero_Bt;
291  }
292  if (!qap_inst.Ct[i].is_zero()) {
293  ++non_zero_Ct;
294  }
295  }
296  for (size_t i = 0; i < qap_inst.degree() + 1; ++i) {
297  if (!qap_inst.Ht[i].is_zero()) {
298  ++non_zero_Ht;
299  }
300  }
301  libff::leave_block("Compute query densities");
302 
303  libff::Fr_vector<ppT> At =
304  std::move(qap_inst.At); // qap_inst.At is now in unspecified state, but
305  // we do not use it later
306  libff::Fr_vector<ppT> Bt =
307  std::move(qap_inst.Bt); // qap_inst.Bt is now in unspecified state, but
308  // we do not use it later
309  libff::Fr_vector<ppT> Ct =
310  std::move(qap_inst.Ct); // qap_inst.Ct is now in unspecified state, but
311  // we do not use it later
312  libff::Fr_vector<ppT> Ht =
313  std::move(qap_inst.Ht); // qap_inst.Ht is now in unspecified state, but
314  // we do not use it later
315 
316  /* append Zt to At,Bt,Ct with */
317  At.emplace_back(qap_inst.Zt);
318  Bt.emplace_back(qap_inst.Zt);
319  Ct.emplace_back(qap_inst.Zt);
320 
321  const libff::Fr<ppT> alphaA = libff::Fr<ppT>::random_element(),
322  alphaB = libff::Fr<ppT>::random_element(),
323  alphaC = libff::Fr<ppT>::random_element(),
324  rA = libff::Fr<ppT>::random_element(),
325  rB = libff::Fr<ppT>::random_element(),
326  beta = libff::Fr<ppT>::random_element(),
327  gamma = libff::Fr<ppT>::random_element();
328  const libff::Fr<ppT> rC = rA * rB;
329 
330  // consrtuct the same-coefficient-check query (must happen before zeroing
331  // out the prefix of At)
332  libff::Fr_vector<ppT> Kt;
333  Kt.reserve(qap_inst.num_variables() + 4);
334  for (size_t i = 0; i < qap_inst.num_variables() + 1; ++i) {
335  Kt.emplace_back(beta * (rA * At[i] + rB * Bt[i] + rC * Ct[i]));
336  }
337  Kt.emplace_back(beta * rA * qap_inst.Zt);
338  Kt.emplace_back(beta * rB * qap_inst.Zt);
339  Kt.emplace_back(beta * rC * qap_inst.Zt);
340 
341  /* zero out prefix of At and stick it into IC coefficients */
342  libff::Fr_vector<ppT> IC_coefficients;
343  IC_coefficients.reserve(qap_inst.num_inputs() + 1);
344  for (size_t i = 0; i < qap_inst.num_inputs() + 1; ++i) {
345  IC_coefficients.emplace_back(At[i]);
346  assert(!IC_coefficients[i].is_zero());
347  At[i] = libff::Fr<ppT>::zero();
348  }
349 
350  const size_t g1_exp_count =
351  2 * (non_zero_At - qap_inst.num_inputs() + non_zero_Ct) + non_zero_Bt +
352  non_zero_Ht + Kt.size();
353  const size_t g2_exp_count = non_zero_Bt;
354 
355  size_t g1_window = libff::get_exp_window_size<libff::G1<ppT>>(g1_exp_count);
356  size_t g2_window = libff::get_exp_window_size<libff::G2<ppT>>(g2_exp_count);
357  libff::print_indent();
358  printf("* G1 window: %zu\n", g1_window);
359  libff::print_indent();
360  printf("* G2 window: %zu\n", g2_window);
361 
362 #ifdef MULTICORE
363  const size_t chunks =
364  omp_get_max_threads(); // to override, set OMP_NUM_THREADS env var or
365  // call omp_set_num_threads()
366 #else
367  const size_t chunks = 1;
368 #endif
369 
370  libff::enter_block("Generating G1 multiexp table");
371  libff::window_table<libff::G1<ppT>> g1_table = get_window_table(
372  libff::Fr<ppT>::size_in_bits(), g1_window, libff::G1<ppT>::one());
373  libff::leave_block("Generating G1 multiexp table");
374 
375  libff::enter_block("Generating G2 multiexp table");
376  libff::window_table<libff::G2<ppT>> g2_table = get_window_table(
377  libff::Fr<ppT>::size_in_bits(), g2_window, libff::G2<ppT>::one());
378  libff::leave_block("Generating G2 multiexp table");
379 
380  libff::enter_block("Generate R1CS proving key");
381 
382  libff::enter_block("Generate knowledge commitments");
383  libff::enter_block("Compute the A-query", false);
384  knowledge_commitment_vector<libff::G1<ppT>, libff::G1<ppT>> A_query =
385  kc_batch_exp(
386  libff::Fr<ppT>::size_in_bits(),
387  g1_window,
388  g1_window,
389  g1_table,
390  g1_table,
391  rA,
392  rA * alphaA,
393  At,
394  chunks,
395  BaseForm == libff::multi_exp_base_form_special);
396  libff::leave_block("Compute the A-query", false);
397 
398  libff::enter_block("Compute the B-query", false);
399  knowledge_commitment_vector<libff::G2<ppT>, libff::G1<ppT>> B_query =
400  kc_batch_exp(
401  libff::Fr<ppT>::size_in_bits(),
402  g2_window,
403  g1_window,
404  g2_table,
405  g1_table,
406  rB,
407  rB * alphaB,
408  Bt,
409  chunks,
410  BaseForm == libff::multi_exp_base_form_special);
411  libff::leave_block("Compute the B-query", false);
412 
413  libff::enter_block("Compute the C-query", false);
414  knowledge_commitment_vector<libff::G1<ppT>, libff::G1<ppT>> C_query =
415  kc_batch_exp(
416  libff::Fr<ppT>::size_in_bits(),
417  g1_window,
418  g1_window,
419  g1_table,
420  g1_table,
421  rC,
422  rC * alphaC,
423  Ct,
424  chunks,
425  BaseForm == libff::multi_exp_base_form_special);
426  libff::leave_block("Compute the C-query", false);
427 
428  libff::enter_block("Compute the H-query", false);
429  libff::G1_vector<ppT> H_query =
430  batch_exp(libff::Fr<ppT>::size_in_bits(), g1_window, g1_table, Ht);
431  if (BaseForm == libff::multi_exp_base_form_special) {
432  libff::batch_to_special<libff::G1<ppT>>(H_query);
433  }
434  libff::leave_block("Compute the H-query", false);
435 
436  libff::enter_block("Compute the K-query", false);
437  libff::G1_vector<ppT> K_query =
438  batch_exp(libff::Fr<ppT>::size_in_bits(), g1_window, g1_table, Kt);
439  if (BaseForm == libff::multi_exp_base_form_special) {
440  libff::batch_to_special<libff::G1<ppT>>(K_query);
441  }
442  libff::leave_block("Compute the K-query", false);
443 
444  libff::leave_block("Generate knowledge commitments");
445 
446  libff::leave_block("Generate R1CS proving key");
447 
448  libff::enter_block("Generate R1CS verification key");
449  libff::G2<ppT> alphaA_g2 = alphaA * libff::G2<ppT>::one();
450  libff::G1<ppT> alphaB_g1 = alphaB * libff::G1<ppT>::one();
451  libff::G2<ppT> alphaC_g2 = alphaC * libff::G2<ppT>::one();
452  libff::G2<ppT> gamma_g2 = gamma * libff::G2<ppT>::one();
453  libff::G1<ppT> gamma_beta_g1 = (gamma * beta) * libff::G1<ppT>::one();
454  libff::G2<ppT> gamma_beta_g2 = (gamma * beta) * libff::G2<ppT>::one();
455  libff::G2<ppT> rC_Z_g2 = (rC * qap_inst.Zt) * libff::G2<ppT>::one();
456 
457  libff::enter_block("Encode IC query for R1CS verification key");
458  libff::G1<ppT> encoded_IC_base =
459  (rA * IC_coefficients[0]) * libff::G1<ppT>::one();
460  libff::Fr_vector<ppT> multiplied_IC_coefficients;
461  multiplied_IC_coefficients.reserve(qap_inst.num_inputs());
462  for (size_t i = 1; i < qap_inst.num_inputs() + 1; ++i) {
463  multiplied_IC_coefficients.emplace_back(rA * IC_coefficients[i]);
464  }
465  libff::G1_vector<ppT> encoded_IC_values = batch_exp(
466  libff::Fr<ppT>::size_in_bits(),
467  g1_window,
468  g1_table,
469  multiplied_IC_coefficients);
470 
471  libff::leave_block("Encode IC query for R1CS verification key");
472  libff::leave_block("Generate R1CS verification key");
473 
474  libff::leave_block("Call to r1cs_ppzksnark_generator");
475 
476  accumulation_vector<libff::G1<ppT>> encoded_IC_query(
477  std::move(encoded_IC_base), std::move(encoded_IC_values));
478 
479  r1cs_ppzksnark_verification_key<ppT> vk =
480  r1cs_ppzksnark_verification_key<ppT>(
481  alphaA_g2,
482  alphaB_g1,
483  alphaC_g2,
484  gamma_g2,
485  gamma_beta_g1,
486  gamma_beta_g2,
487  rC_Z_g2,
488  encoded_IC_query);
489  r1cs_ppzksnark_proving_key<ppT> pk = r1cs_ppzksnark_proving_key<ppT>(
490  std::move(A_query),
491  std::move(B_query),
492  std::move(C_query),
493  std::move(H_query),
494  std::move(K_query),
495  std::move(cs_copy));
496 
497  pk.print_size();
498  vk.print_size();
499 
500  return r1cs_ppzksnark_keypair<ppT>(std::move(pk), std::move(vk));
501 }
502 
503 template<
504  typename ppT,
505  libff::multi_exp_method Method,
506  libff::multi_exp_base_form BaseForm>
507 r1cs_ppzksnark_proof<ppT> r1cs_ppzksnark_prover(
508  const r1cs_ppzksnark_proving_key<ppT> &pk,
509  const r1cs_ppzksnark_primary_input<ppT> &primary_input,
510  const r1cs_ppzksnark_auxiliary_input<ppT> &auxiliary_input)
511 {
512  libff::enter_block("Call to r1cs_ppzksnark_prover");
513 
514 #ifdef DEBUG
515  assert(pk.constraint_system.is_satisfied(primary_input, auxiliary_input));
516 #endif
517 
518  const libff::Fr<ppT> d1 = libff::Fr<ppT>::random_element(),
519  d2 = libff::Fr<ppT>::random_element(),
520  d3 = libff::Fr<ppT>::random_element();
521 
522  libff::enter_block("Compute the polynomial H");
523  const qap_witness<libff::Fr<ppT>> qap_wit = r1cs_to_qap_witness_map(
524  pk.constraint_system, primary_input, auxiliary_input, d1, d2, d3);
525  libff::leave_block("Compute the polynomial H");
526 
527 #ifdef DEBUG
528  const libff::Fr<ppT> t = libff::Fr<ppT>::random_element();
529  qap_instance_evaluation<libff::Fr<ppT>> qap_inst =
530  r1cs_to_qap_instance_map_with_evaluation(pk.constraint_system, t);
531  assert(qap_inst.is_satisfied(qap_wit));
532 #endif
533 
534  knowledge_commitment<libff::G1<ppT>, libff::G1<ppT>> g_A =
535  pk.A_query[0] + qap_wit.d1 * pk.A_query[qap_wit.num_variables() + 1];
536  knowledge_commitment<libff::G2<ppT>, libff::G1<ppT>> g_B =
537  pk.B_query[0] + qap_wit.d2 * pk.B_query[qap_wit.num_variables() + 1];
538  knowledge_commitment<libff::G1<ppT>, libff::G1<ppT>> g_C =
539  pk.C_query[0] + qap_wit.d3 * pk.C_query[qap_wit.num_variables() + 1];
540 
541  libff::G1<ppT> g_H = libff::G1<ppT>::zero();
542  libff::G1<ppT> g_K =
543  (pk.K_query[0] + qap_wit.d1 * pk.K_query[qap_wit.num_variables() + 1] +
544  qap_wit.d2 * pk.K_query[qap_wit.num_variables() + 2] +
545  qap_wit.d3 * pk.K_query[qap_wit.num_variables() + 3]);
546 
547 #ifdef DEBUG
548  for (size_t i = 0; i < qap_wit.num_inputs() + 1; ++i) {
549  assert(pk.A_query[i].g == libff::G1<ppT>::zero());
550  }
551  assert(pk.A_query.domain_size() == qap_wit.num_variables() + 2);
552  assert(pk.B_query.domain_size() == qap_wit.num_variables() + 2);
553  assert(pk.C_query.domain_size() == qap_wit.num_variables() + 2);
554  assert(pk.H_query.size() == qap_wit.degree() + 1);
555  assert(pk.K_query.size() == qap_wit.num_variables() + 4);
556 #endif
557 
558 #ifdef MULTICORE
559  const size_t chunks =
560  omp_get_max_threads(); // to override, set OMP_NUM_THREADS env var or
561  // call omp_set_num_threads()
562 #else
563  const size_t chunks = 1;
564 #endif
565 
566  libff::enter_block("Compute the proof");
567 
568  libff::enter_block("Compute answer to A-query", false);
569  g_A = g_A +
570  kc_multi_exp_with_mixed_addition<
571  libff::G1<ppT>,
572  libff::G1<ppT>,
573  libff::Fr<ppT>,
574  Method,
575  BaseForm>(
576  pk.A_query,
577  1,
578  1 + qap_wit.num_variables(),
579  qap_wit.coefficients_for_ABCs.begin(),
580  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
581  chunks);
582  libff::leave_block("Compute answer to A-query", false);
583 
584  libff::enter_block("Compute answer to B-query", false);
585  g_B = g_B +
586  kc_multi_exp_with_mixed_addition<
587  libff::G2<ppT>,
588  libff::G1<ppT>,
589  libff::Fr<ppT>,
590  Method,
591  BaseForm>(
592  pk.B_query,
593  1,
594  1 + qap_wit.num_variables(),
595  qap_wit.coefficients_for_ABCs.begin(),
596  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
597  chunks);
598  libff::leave_block("Compute answer to B-query", false);
599 
600  libff::enter_block("Compute answer to C-query", false);
601  g_C = g_C +
602  kc_multi_exp_with_mixed_addition<
603  libff::G1<ppT>,
604  libff::G1<ppT>,
605  libff::Fr<ppT>,
606  Method,
607  BaseForm>(
608  pk.C_query,
609  1,
610  1 + qap_wit.num_variables(),
611  qap_wit.coefficients_for_ABCs.begin(),
612  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
613  chunks);
614  libff::leave_block("Compute answer to C-query", false);
615 
616  libff::enter_block("Compute answer to H-query", false);
617  g_H = g_H +
618  libff::multi_exp<libff::G1<ppT>, libff::Fr<ppT>, Method, BaseForm>(
619  pk.H_query.begin(),
620  pk.H_query.begin() + qap_wit.degree() + 1,
621  qap_wit.coefficients_for_H.begin(),
622  qap_wit.coefficients_for_H.begin() + qap_wit.degree() + 1,
623  chunks);
624  libff::leave_block("Compute answer to H-query", false);
625 
626  libff::enter_block("Compute answer to K-query", false);
627  g_K = g_K +
628  libff::multi_exp_filter_one_zero<
629  libff::G1<ppT>,
630  libff::Fr<ppT>,
631  Method,
632  BaseForm>(
633  pk.K_query.begin() + 1,
634  pk.K_query.begin() + 1 + qap_wit.num_variables(),
635  qap_wit.coefficients_for_ABCs.begin(),
636  qap_wit.coefficients_for_ABCs.begin() + qap_wit.num_variables(),
637  chunks);
638  libff::leave_block("Compute answer to K-query", false);
639 
640  libff::leave_block("Compute the proof");
641 
642  libff::leave_block("Call to r1cs_ppzksnark_prover");
643 
644  r1cs_ppzksnark_proof<ppT> proof = r1cs_ppzksnark_proof<ppT>(
645  std::move(g_A),
646  std::move(g_B),
647  std::move(g_C),
648  std::move(g_H),
649  std::move(g_K));
650  proof.print_size();
651 
652  return proof;
653 }
654 
655 template<typename ppT>
656 r1cs_ppzksnark_processed_verification_key<ppT> r1cs_ppzksnark_verifier_process_vk(
657  const r1cs_ppzksnark_verification_key<ppT> &vk)
658 {
659  libff::enter_block("Call to r1cs_ppzksnark_verifier_process_vk");
660 
661  r1cs_ppzksnark_processed_verification_key<ppT> pvk;
662  pvk.pp_G2_one_precomp = ppT::precompute_G2(libff::G2<ppT>::one());
663  pvk.vk_alphaA_g2_precomp = ppT::precompute_G2(vk.alphaA_g2);
664  pvk.vk_alphaB_g1_precomp = ppT::precompute_G1(vk.alphaB_g1);
665  pvk.vk_alphaC_g2_precomp = ppT::precompute_G2(vk.alphaC_g2);
666  pvk.vk_rC_Z_g2_precomp = ppT::precompute_G2(vk.rC_Z_g2);
667  pvk.vk_gamma_g2_precomp = ppT::precompute_G2(vk.gamma_g2);
668  pvk.vk_gamma_beta_g1_precomp = ppT::precompute_G1(vk.gamma_beta_g1);
669  pvk.vk_gamma_beta_g2_precomp = ppT::precompute_G2(vk.gamma_beta_g2);
670 
671  pvk.encoded_IC_query = vk.encoded_IC_query;
672 
673  libff::leave_block("Call to r1cs_ppzksnark_verifier_process_vk");
674 
675  return pvk;
676 }
677 
678 template<typename ppT>
679 bool r1cs_ppzksnark_online_verifier_weak_IC(
680  const r1cs_ppzksnark_processed_verification_key<ppT> &pvk,
681  const r1cs_ppzksnark_primary_input<ppT> &primary_input,
682  const r1cs_ppzksnark_proof<ppT> &proof)
683 {
684  libff::enter_block("Call to r1cs_ppzksnark_online_verifier_weak_IC");
685  assert(pvk.encoded_IC_query.domain_size() >= primary_input.size());
686 
687  libff::enter_block("Compute input-dependent part of A");
688  const accumulation_vector<libff::G1<ppT>> accumulated_IC =
689  pvk.encoded_IC_query.template accumulate_chunk<libff::Fr<ppT>>(
690  primary_input.begin(), primary_input.end(), 0);
691  const libff::G1<ppT> &acc = accumulated_IC.first;
692  libff::leave_block("Compute input-dependent part of A");
693 
694  bool result = true;
695 
696  libff::enter_block("Check if the proof is well-formed");
697  if (!proof.is_well_formed()) {
698  if (!libff::inhibit_profiling_info) {
699  libff::print_indent();
700  printf("At least one of the proof elements does not lie on the "
701  "curve.\n");
702  }
703  result = false;
704  }
705  libff::leave_block("Check if the proof is well-formed");
706 
707  libff::enter_block("Online pairing computations");
708  libff::enter_block("Check knowledge commitment for A is valid");
709  libff::G1_precomp<ppT> proof_g_A_g_precomp =
710  ppT::precompute_G1(proof.g_A.g);
711  libff::G1_precomp<ppT> proof_g_A_h_precomp =
712  ppT::precompute_G1(proof.g_A.h);
713  libff::Fqk<ppT> kc_A_1 =
714  ppT::miller_loop(proof_g_A_g_precomp, pvk.vk_alphaA_g2_precomp);
715  libff::Fqk<ppT> kc_A_2 =
716  ppT::miller_loop(proof_g_A_h_precomp, pvk.pp_G2_one_precomp);
717  libff::GT<ppT> kc_A =
718  ppT::final_exponentiation(kc_A_1 * kc_A_2.unitary_inverse());
719  if (kc_A != libff::GT<ppT>::one()) {
720  if (!libff::inhibit_profiling_info) {
721  libff::print_indent();
722  printf("Knowledge commitment for A query incorrect.\n");
723  }
724  result = false;
725  }
726  libff::leave_block("Check knowledge commitment for A is valid");
727 
728  libff::enter_block("Check knowledge commitment for B is valid");
729  libff::G2_precomp<ppT> proof_g_B_g_precomp =
730  ppT::precompute_G2(proof.g_B.g);
731  libff::G1_precomp<ppT> proof_g_B_h_precomp =
732  ppT::precompute_G1(proof.g_B.h);
733  libff::Fqk<ppT> kc_B_1 =
734  ppT::miller_loop(pvk.vk_alphaB_g1_precomp, proof_g_B_g_precomp);
735  libff::Fqk<ppT> kc_B_2 =
736  ppT::miller_loop(proof_g_B_h_precomp, pvk.pp_G2_one_precomp);
737  libff::GT<ppT> kc_B =
738  ppT::final_exponentiation(kc_B_1 * kc_B_2.unitary_inverse());
739  if (kc_B != libff::GT<ppT>::one()) {
740  if (!libff::inhibit_profiling_info) {
741  libff::print_indent();
742  printf("Knowledge commitment for B query incorrect.\n");
743  }
744  result = false;
745  }
746  libff::leave_block("Check knowledge commitment for B is valid");
747 
748  libff::enter_block("Check knowledge commitment for C is valid");
749  libff::G1_precomp<ppT> proof_g_C_g_precomp =
750  ppT::precompute_G1(proof.g_C.g);
751  libff::G1_precomp<ppT> proof_g_C_h_precomp =
752  ppT::precompute_G1(proof.g_C.h);
753  libff::Fqk<ppT> kc_C_1 =
754  ppT::miller_loop(proof_g_C_g_precomp, pvk.vk_alphaC_g2_precomp);
755  libff::Fqk<ppT> kc_C_2 =
756  ppT::miller_loop(proof_g_C_h_precomp, pvk.pp_G2_one_precomp);
757  libff::GT<ppT> kc_C =
758  ppT::final_exponentiation(kc_C_1 * kc_C_2.unitary_inverse());
759  if (kc_C != libff::GT<ppT>::one()) {
760  if (!libff::inhibit_profiling_info) {
761  libff::print_indent();
762  printf("Knowledge commitment for C query incorrect.\n");
763  }
764  result = false;
765  }
766  libff::leave_block("Check knowledge commitment for C is valid");
767 
768  libff::enter_block("Check QAP divisibility");
769  // check that g^((A+acc)*B)=g^(H*\Prod(t-\sigma)+C)
770  // equivalently, via pairings, that e(g^(A+acc), g^B) = e(g^H, g^Z) + e(g^C,
771  // g^1)
772  libff::G1_precomp<ppT> proof_g_A_g_acc_precomp =
773  ppT::precompute_G1(proof.g_A.g + acc);
774  libff::G1_precomp<ppT> proof_g_H_precomp = ppT::precompute_G1(proof.g_H);
775  libff::Fqk<ppT> QAP_1 =
776  ppT::miller_loop(proof_g_A_g_acc_precomp, proof_g_B_g_precomp);
777  libff::Fqk<ppT> QAP_23 = ppT::double_miller_loop(
778  proof_g_H_precomp,
779  pvk.vk_rC_Z_g2_precomp,
780  proof_g_C_g_precomp,
781  pvk.pp_G2_one_precomp);
782  libff::GT<ppT> QAP =
783  ppT::final_exponentiation(QAP_1 * QAP_23.unitary_inverse());
784  if (QAP != libff::GT<ppT>::one()) {
785  if (!libff::inhibit_profiling_info) {
786  libff::print_indent();
787  printf("QAP divisibility check failed.\n");
788  }
789  result = false;
790  }
791  libff::leave_block("Check QAP divisibility");
792 
793  libff::enter_block("Check same coefficients were used");
794  libff::G1_precomp<ppT> proof_g_K_precomp = ppT::precompute_G1(proof.g_K);
795  libff::G1_precomp<ppT> proof_g_A_g_acc_C_precomp =
796  ppT::precompute_G1((proof.g_A.g + acc) + proof.g_C.g);
797  libff::Fqk<ppT> K_1 =
798  ppT::miller_loop(proof_g_K_precomp, pvk.vk_gamma_g2_precomp);
799  libff::Fqk<ppT> K_23 = ppT::double_miller_loop(
800  proof_g_A_g_acc_C_precomp,
801  pvk.vk_gamma_beta_g2_precomp,
802  pvk.vk_gamma_beta_g1_precomp,
803  proof_g_B_g_precomp);
804  libff::GT<ppT> K = ppT::final_exponentiation(K_1 * K_23.unitary_inverse());
805  if (K != libff::GT<ppT>::one()) {
806  if (!libff::inhibit_profiling_info) {
807  libff::print_indent();
808  printf("Same-coefficient check failed.\n");
809  }
810  result = false;
811  }
812  libff::leave_block("Check same coefficients were used");
813  libff::leave_block("Online pairing computations");
814  libff::leave_block("Call to r1cs_ppzksnark_online_verifier_weak_IC");
815 
816  return result;
817 }
818 
819 template<typename ppT>
820 bool r1cs_ppzksnark_verifier_weak_IC(
821  const r1cs_ppzksnark_verification_key<ppT> &vk,
822  const r1cs_ppzksnark_primary_input<ppT> &primary_input,
823  const r1cs_ppzksnark_proof<ppT> &proof)
824 {
825  libff::enter_block("Call to r1cs_ppzksnark_verifier_weak_IC");
826  r1cs_ppzksnark_processed_verification_key<ppT> pvk =
827  r1cs_ppzksnark_verifier_process_vk<ppT>(vk);
828  bool result =
829  r1cs_ppzksnark_online_verifier_weak_IC<ppT>(pvk, primary_input, proof);
830  libff::leave_block("Call to r1cs_ppzksnark_verifier_weak_IC");
831  return result;
832 }
833 
834 template<typename ppT>
835 bool r1cs_ppzksnark_online_verifier_strong_IC(
836  const r1cs_ppzksnark_processed_verification_key<ppT> &pvk,
837  const r1cs_ppzksnark_primary_input<ppT> &primary_input,
838  const r1cs_ppzksnark_proof<ppT> &proof)
839 {
840  bool result = true;
841  libff::enter_block("Call to r1cs_ppzksnark_online_verifier_strong_IC");
842 
843  if (pvk.encoded_IC_query.domain_size() != primary_input.size()) {
844  libff::print_indent();
845  printf(
846  "Input length differs from expected (got %zu, expected %zu).\n",
847  primary_input.size(),
848  pvk.encoded_IC_query.domain_size());
849  result = false;
850  } else {
851  result =
852  r1cs_ppzksnark_online_verifier_weak_IC(pvk, primary_input, proof);
853  }
854 
855  libff::leave_block("Call to r1cs_ppzksnark_online_verifier_strong_IC");
856  return result;
857 }
858 
859 template<typename ppT>
860 bool r1cs_ppzksnark_verifier_strong_IC(
861  const r1cs_ppzksnark_verification_key<ppT> &vk,
862  const r1cs_ppzksnark_primary_input<ppT> &primary_input,
863  const r1cs_ppzksnark_proof<ppT> &proof)
864 {
865  libff::enter_block("Call to r1cs_ppzksnark_verifier_strong_IC");
866  r1cs_ppzksnark_processed_verification_key<ppT> pvk =
867  r1cs_ppzksnark_verifier_process_vk<ppT>(vk);
868  bool result = r1cs_ppzksnark_online_verifier_strong_IC<ppT>(
869  pvk, primary_input, proof);
870  libff::leave_block("Call to r1cs_ppzksnark_verifier_strong_IC");
871  return result;
872 }
873 
874 template<typename ppT>
875 bool r1cs_ppzksnark_affine_verifier_weak_IC(
876  const r1cs_ppzksnark_verification_key<ppT> &vk,
877  const r1cs_ppzksnark_primary_input<ppT> &primary_input,
878  const r1cs_ppzksnark_proof<ppT> &proof)
879 {
880  libff::enter_block("Call to r1cs_ppzksnark_affine_verifier_weak_IC");
881  assert(vk.encoded_IC_query.domain_size() >= primary_input.size());
882 
883  libff::affine_ate_G2_precomp<ppT> pvk_pp_G2_one_precomp =
884  ppT::affine_ate_precompute_G2(libff::G2<ppT>::one());
885  libff::affine_ate_G2_precomp<ppT> pvk_vk_alphaA_g2_precomp =
886  ppT::affine_ate_precompute_G2(vk.alphaA_g2);
887  libff::affine_ate_G1_precomp<ppT> pvk_vk_alphaB_g1_precomp =
888  ppT::affine_ate_precompute_G1(vk.alphaB_g1);
889  libff::affine_ate_G2_precomp<ppT> pvk_vk_alphaC_g2_precomp =
890  ppT::affine_ate_precompute_G2(vk.alphaC_g2);
891  libff::affine_ate_G2_precomp<ppT> pvk_vk_rC_Z_g2_precomp =
892  ppT::affine_ate_precompute_G2(vk.rC_Z_g2);
893  libff::affine_ate_G2_precomp<ppT> pvk_vk_gamma_g2_precomp =
894  ppT::affine_ate_precompute_G2(vk.gamma_g2);
895  libff::affine_ate_G1_precomp<ppT> pvk_vk_gamma_beta_g1_precomp =
896  ppT::affine_ate_precompute_G1(vk.gamma_beta_g1);
897  libff::affine_ate_G2_precomp<ppT> pvk_vk_gamma_beta_g2_precomp =
898  ppT::affine_ate_precompute_G2(vk.gamma_beta_g2);
899 
900  libff::enter_block("Compute input-dependent part of A");
901  const accumulation_vector<libff::G1<ppT>> accumulated_IC =
902  vk.encoded_IC_query.template accumulate_chunk<libff::Fr<ppT>>(
903  primary_input.begin(), primary_input.end(), 0);
904  assert(accumulated_IC.is_fully_accumulated());
905  const libff::G1<ppT> &acc = accumulated_IC.first;
906  libff::leave_block("Compute input-dependent part of A");
907 
908  bool result = true;
909  libff::enter_block("Check knowledge commitment for A is valid");
910  libff::affine_ate_G1_precomp<ppT> proof_g_A_g_precomp =
911  ppT::affine_ate_precompute_G1(proof.g_A.g);
912  libff::affine_ate_G1_precomp<ppT> proof_g_A_h_precomp =
913  ppT::affine_ate_precompute_G1(proof.g_A.h);
914  libff::Fqk<ppT> kc_A_miller = ppT::affine_ate_e_over_e_miller_loop(
915  proof_g_A_g_precomp,
916  pvk_vk_alphaA_g2_precomp,
917  proof_g_A_h_precomp,
918  pvk_pp_G2_one_precomp);
919  libff::GT<ppT> kc_A = ppT::final_exponentiation(kc_A_miller);
920 
921  if (kc_A != libff::GT<ppT>::one()) {
922  libff::print_indent();
923  printf("Knowledge commitment for A query incorrect.\n");
924  result = false;
925  }
926  libff::leave_block("Check knowledge commitment for A is valid");
927 
928  libff::enter_block("Check knowledge commitment for B is valid");
929  libff::affine_ate_G2_precomp<ppT> proof_g_B_g_precomp =
930  ppT::affine_ate_precompute_G2(proof.g_B.g);
931  libff::affine_ate_G1_precomp<ppT> proof_g_B_h_precomp =
932  ppT::affine_ate_precompute_G1(proof.g_B.h);
933  libff::Fqk<ppT> kc_B_miller = ppT::affine_ate_e_over_e_miller_loop(
934  pvk_vk_alphaB_g1_precomp,
935  proof_g_B_g_precomp,
936  proof_g_B_h_precomp,
937  pvk_pp_G2_one_precomp);
938  libff::GT<ppT> kc_B = ppT::final_exponentiation(kc_B_miller);
939  if (kc_B != libff::GT<ppT>::one()) {
940  libff::print_indent();
941  printf("Knowledge commitment for B query incorrect.\n");
942  result = false;
943  }
944  libff::leave_block("Check knowledge commitment for B is valid");
945 
946  libff::enter_block("Check knowledge commitment for C is valid");
947  libff::affine_ate_G1_precomp<ppT> proof_g_C_g_precomp =
948  ppT::affine_ate_precompute_G1(proof.g_C.g);
949  libff::affine_ate_G1_precomp<ppT> proof_g_C_h_precomp =
950  ppT::affine_ate_precompute_G1(proof.g_C.h);
951  libff::Fqk<ppT> kc_C_miller = ppT::affine_ate_e_over_e_miller_loop(
952  proof_g_C_g_precomp,
953  pvk_vk_alphaC_g2_precomp,
954  proof_g_C_h_precomp,
955  pvk_pp_G2_one_precomp);
956  libff::GT<ppT> kc_C = ppT::final_exponentiation(kc_C_miller);
957  if (kc_C != libff::GT<ppT>::one()) {
958  libff::print_indent();
959  printf("Knowledge commitment for C query incorrect.\n");
960  result = false;
961  }
962  libff::leave_block("Check knowledge commitment for C is valid");
963 
964  libff::enter_block("Check QAP divisibility");
965  libff::affine_ate_G1_precomp<ppT> proof_g_A_g_acc_precomp =
966  ppT::affine_ate_precompute_G1(proof.g_A.g + acc);
967  libff::affine_ate_G1_precomp<ppT> proof_g_H_precomp =
968  ppT::affine_ate_precompute_G1(proof.g_H);
969  libff::Fqk<ppT> QAP_miller = ppT::affine_ate_e_times_e_over_e_miller_loop(
970  proof_g_H_precomp,
971  pvk_vk_rC_Z_g2_precomp,
972  proof_g_C_g_precomp,
973  pvk_pp_G2_one_precomp,
974  proof_g_A_g_acc_precomp,
975  proof_g_B_g_precomp);
976  libff::GT<ppT> QAP = ppT::final_exponentiation(QAP_miller);
977  if (QAP != libff::GT<ppT>::one()) {
978  libff::print_indent();
979  printf("QAP divisibility check failed.\n");
980  result = false;
981  }
982  libff::leave_block("Check QAP divisibility");
983 
984  libff::enter_block("Check same coefficients were used");
985  libff::affine_ate_G1_precomp<ppT> proof_g_K_precomp =
986  ppT::affine_ate_precompute_G1(proof.g_K);
987  libff::affine_ate_G1_precomp<ppT> proof_g_A_g_acc_C_precomp =
988  ppT::affine_ate_precompute_G1((proof.g_A.g + acc) + proof.g_C.g);
989  libff::Fqk<ppT> K_miller = ppT::affine_ate_e_times_e_over_e_miller_loop(
990  proof_g_A_g_acc_C_precomp,
991  pvk_vk_gamma_beta_g2_precomp,
992  pvk_vk_gamma_beta_g1_precomp,
993  proof_g_B_g_precomp,
994  proof_g_K_precomp,
995  pvk_vk_gamma_g2_precomp);
996  libff::GT<ppT> K = ppT::final_exponentiation(K_miller);
997  if (K != libff::GT<ppT>::one()) {
998  libff::print_indent();
999  printf("Same-coefficient check failed.\n");
1000  result = false;
1001  }
1002  libff::leave_block("Check same coefficients were used");
1003 
1004  libff::leave_block("Call to r1cs_ppzksnark_affine_verifier_weak_IC");
1005 
1006  return result;
1007 }
1008 
1009 } // namespace libsnark
1010 #endif // R1CS_PPZKSNARK_TCC_
Generated on Wed Jan 25 2023 11:05:58 for Clearmatics Libsnark by   doxygen 1.8.17