zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp
Go to the documentation of this file.
1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2018-2021 Mikhail Komarov <nemo@nil.foundation>
3 // Copyright (c) 2020-2021 Nikita Kaskov <nbering@nil.foundation>
4 //
5 // MIT License
6 //
7 // Permission is hereby granted, free of charge, to any person obtaining a copy
8 // of this software and associated documentation files (the "Software"), to deal
9 // in the Software without restriction, including without limitation the rights
10 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 // copies of the Software, and to permit persons to whom the Software is
12 // furnished to do so, subject to the following conditions:
13 //
14 // The above copyright notice and this permission notice shall be included in all
15 // copies or substantial portions of the Software.
16 //
17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 // SOFTWARE.
24 //---------------------------------------------------------------------------//
25 
26 #ifndef CRYPTO3_R1CS_PPZKSNARK_BASIC_VERIFIER_HPP
27 #define CRYPTO3_R1CS_PPZKSNARK_BASIC_VERIFIER_HPP
28 
30 
34 #include <nil/crypto3/zk/snark/schemes/ppzksnark/r1cs_ppzksnark/detail/basic_policy.hpp>
35 
36 namespace nil {
37  namespace crypto3 {
38  namespace zk {
39  namespace snark {
43  template<typename CurveType>
46 
47  using g2_type = typename CurveType::template g2_type<>;
48  public:
51 
54 
55  processed_verification_key_type processed_verification_key;
56  processed_verification_key.pp_G2_one_precomp =
57  precompute_g2<CurveType>(g2_type::value_type::one());
58  processed_verification_key.vk_alphaA_g2_precomp =
59  precompute_g2<CurveType>(verification_key.alphaA_g2);
60  processed_verification_key.vk_alphaB_g1_precomp =
61  precompute_g1<CurveType>(verification_key.alphaB_g1);
62  processed_verification_key.vk_alphaC_g2_precomp =
63  precompute_g2<CurveType>(verification_key.alphaC_g2);
64  processed_verification_key.vk_rC_Z_g2_precomp =
65  precompute_g2<CurveType>(verification_key.rC_Z_g2);
66  processed_verification_key.vk_gamma_g2_precomp =
67  precompute_g2<CurveType>(verification_key.gamma_g2);
68  processed_verification_key.vk_gamma_beta_g1_precomp =
69  precompute_g1<CurveType>(verification_key.gamma_beta_g1);
70  processed_verification_key.vk_gamma_beta_g2_precomp =
71  precompute_g2<CurveType>(verification_key.gamma_beta_g2);
72 
73  processed_verification_key.encoded_IC_query = verification_key.encoded_IC_query;
74 
75  return processed_verification_key;
76  }
77  };
78 
79  template<typename CurveType>
82 
84  using g1_type = typename CurveType::template g1_type<>;
85  using g2_type = typename CurveType::template g2_type<>;
86  using gt_type = typename CurveType::gt_type;
87  using g1_value_type = typename g1_type::value_type;
88  using g2_value_type = typename g2_type::value_type;
89  using gt_value_type = typename gt_type::value_type;
90  using g1_precomputed_type = typename pairing_policy::g1_precomputed_type;
91  using g2_precomputed_type = typename pairing_policy::g2_precomputed_type;
92 
93  public:
98 
104  static inline bool process(const verification_key_type &verification_key,
105  const primary_input_type &primary_input,
106  const proof_type &proof) {
107  return process(
109  proof);
110  }
111 
117  static inline bool process(const processed_verification_key_type &processed_verification_key,
118  const primary_input_type &primary_input,
119  const proof_type &proof) {
120 
121  assert(processed_verification_key.encoded_IC_query.domain_size() >= primary_input.size());
122 
123  const accumulation_vector<g1_type> accumulated_IC =
124  processed_verification_key.encoded_IC_query.accumulate_chunk(
125  primary_input.begin(), primary_input.end(), 0);
126  const g1_value_type &acc = accumulated_IC.first;
127 
128  bool result = true;
129 
130  if (!proof.is_well_formed()) {
131  result = false;
132  }
133  g1_precomputed_type proof_g_A_g_precomp = precompute_g1<CurveType>(proof.g_A.g);
134  g1_precomputed_type proof_g_A_h_precomp = precompute_g1<CurveType>(proof.g_A.h);
135  typename gt_type::value_type kc_A_1 = miller_loop<CurveType>(
136  proof_g_A_g_precomp, processed_verification_key.vk_alphaA_g2_precomp);
137  typename gt_type::value_type kc_A_2 = miller_loop<CurveType>(
138  proof_g_A_h_precomp, processed_verification_key.pp_G2_one_precomp);
139  gt_value_type kc_A = final_exponentiation<CurveType>(kc_A_1 * kc_A_2.unitary_inversed());
140  if (kc_A != gt_value_type::one()) {
141  result = false;
142  }
143 
144  g2_precomputed_type proof_g_B_g_precomp = precompute_g2<CurveType>(proof.g_B.g);
145  g1_precomputed_type proof_g_B_h_precomp = precompute_g1<CurveType>(proof.g_B.h);
146  typename gt_type::value_type kc_B_1 = miller_loop<CurveType>(
147  processed_verification_key.vk_alphaB_g1_precomp, proof_g_B_g_precomp);
148  typename gt_type::value_type kc_B_2 = miller_loop<CurveType>(
149  proof_g_B_h_precomp, processed_verification_key.pp_G2_one_precomp);
150  gt_value_type kc_B = final_exponentiation<CurveType>(kc_B_1 * kc_B_2.unitary_inversed());
151  if (kc_B != gt_value_type::one()) {
152  result = false;
153  }
154 
155  g1_precomputed_type proof_g_C_g_precomp = precompute_g1<CurveType>(proof.g_C.g);
156  g1_precomputed_type proof_g_C_h_precomp = precompute_g1<CurveType>(proof.g_C.h);
157  typename gt_type::value_type kc_C_1 = miller_loop<CurveType>(
158  proof_g_C_g_precomp, processed_verification_key.vk_alphaC_g2_precomp);
159  typename gt_type::value_type kc_C_2 = miller_loop<CurveType>(
160  proof_g_C_h_precomp, processed_verification_key.pp_G2_one_precomp);
161  gt_value_type kc_C = final_exponentiation<CurveType>(kc_C_1 * kc_C_2.unitary_inversed());
162  if (kc_C != gt_value_type::one()) {
163  result = false;
164  }
165 
166  // check that g^((A+acc)*B)=g^(H*\Prod(t-\sigma)+C)
167  // equivalently, via pairings, that e(g^(A+acc), g^B) = e(g^H, g^Z) + e(g^C, g^1)
168  g1_precomputed_type proof_g_A_g_acc_precomp = precompute_g1<CurveType>(proof.g_A.g + acc);
169  g1_precomputed_type proof_g_H_precomp = precompute_g1<CurveType>(proof.g_H);
170  typename gt_type::value_type QAP_1 =
171  miller_loop<CurveType>(proof_g_A_g_acc_precomp, proof_g_B_g_precomp);
172  typename gt_type::value_type QAP_23 = double_miller_loop<CurveType>(
173  proof_g_H_precomp, processed_verification_key.vk_rC_Z_g2_precomp, proof_g_C_g_precomp,
174  processed_verification_key.pp_G2_one_precomp);
175  gt_value_type QAP = final_exponentiation<CurveType>(QAP_1 * QAP_23.unitary_inversed());
176  if (QAP != gt_value_type::one()) {
177  result = false;
178  }
179 
180  g1_precomputed_type proof_g_K_precomp = precompute_g1<CurveType>(proof.g_K);
181  g1_precomputed_type proof_g_A_g_acc_C_precomp =
182  precompute_g1<CurveType>((proof.g_A.g + acc) + proof.g_C.g);
183  typename gt_type::value_type K_1 = miller_loop<CurveType>(
184  proof_g_K_precomp, processed_verification_key.vk_gamma_g2_precomp);
185  typename gt_type::value_type K_23 = double_miller_loop<CurveType>(
186  proof_g_A_g_acc_C_precomp, processed_verification_key.vk_gamma_beta_g2_precomp,
187  processed_verification_key.vk_gamma_beta_g1_precomp, proof_g_B_g_precomp);
188  gt_value_type K = final_exponentiation<CurveType>(K_1 * K_23.unitary_inversed());
189  if (K != gt_value_type::one()) {
190  result = false;
191  }
192 
193  return result;
194  }
195  };
196 
197  template<typename CurveType>
200 
201  public:
206 
212  static inline bool process(const verification_key_type &verification_key,
213  const primary_input_type &primary_input,
214  const proof_type &proof) {
215  return process(
217  proof);
218  }
219 
225  static inline bool process(const processed_verification_key_type &processed_verification_key,
226  const primary_input_type &primary_input,
227  const proof_type &proof) {
228  bool result = true;
229 
230  if (processed_verification_key.encoded_IC_query.domain_size() != primary_input.size()) {
231  result = false;
232  } else {
234  processed_verification_key, primary_input, proof);
235  }
236 
237  return result;
238  }
239  };
240 
241  // /**
242  // *
243  // * A verifier algorithm for the R1CS ppzkSNARK that:
244  // * (1) accepts a non-processed verification key,
245  // * (2) has weak input consistency, and
246  // * (3) uses affine coordinates for elliptic-curve computations.
247  // */
248  // template<typename CurveType>
249  // class r1cs_ppzksnark_affine_verifier_weak_input_consistency {
250  // typedef detail::r1cs_ppzksnark_policy<CurveType> policy_type;
251 
252  // using pairing_policy = typename CurveType::pairing;
253  // using g1_type = typename CurveType::template g1_type<>;
254  // using g2_type = typename CurveType::template g2_type<>;
255  // using gt_type = typename CurveType::gt_type;
256  // using g1_value_type = typename g1_type::value_type;
257  // using g2_value_type = typename g2_type::value_type;
258  // using gt_value_type = typename gt_type::value_type;
259  // using scalar_field_type = typename CurveType::scalar_field_type;
260  // using g1_precomputed_type = typename pairing_policy::g1_precomputed_type;
261  // using g2_precomputed_type = typename pairing_policy::g2_precomputed_type;
262  // using affine_ate_g1_precomp = typename pairing_policy::affine_ate_g1_precomp;
263  // using affine_ate_g2_precomp = typename pairing_policy::affine_ate_g2_precomp;
264 
265  // public:
266  // typedef typename policy_type::primary_input_type primary_input_type;
267  // typedef typename policy_type::verification_key_type verification_key_type;
268  // typedef typename policy_type::processed_verification_key_type processed_verification_key_type;
269  // typedef typename policy_type::proof_type proof_type;
270 
271  // static inline bool process(const verification_key_type &vk,
272  // const primary_input_type &primary_input,
273  // const proof_type &proof) {
274  // typedef typename CurveType::pairing pairing_policy;
275 
276  // assert(vk.encoded_IC_query.domain_size() >= primary_input.size());
277 
278  // affine_ate_g2_precomp pvk_pp_G2_one_precomp =
279  // affine_ate_precompute_g2<CurveType>(g2_value_type::one());
280  // affine_ate_g2_precomp pvk_vk_alphaA_g2_precomp =
281  // affine_ate_precompute_g2<CurveType>(vk.alphaA_g2);
282  // affine_ate_g1_precomp pvk_vk_alphaB_g1_precomp =
283  // affine_ate_precompute_g1<CurveType>(vk.alphaB_g1);
284  // affine_ate_g2_precomp pvk_vk_alphaC_g2_precomp =
285  // affine_ate_precompute_g2<CurveType>(vk.alphaC_g2);
286  // affine_ate_g2_precomp pvk_vk_rC_Z_g2_precomp =
287  // affine_ate_precompute_g2<CurveType>(vk.rC_Z_g2);
288  // affine_ate_g2_precomp pvk_vk_gamma_g2_precomp =
289  // affine_ate_precompute_g2<CurveType>(vk.gamma_g2);
290  // affine_ate_g1_precomp pvk_vk_gamma_beta_g1_precomp =
291  // affine_ate_precompute_g1<CurveType>(vk.gamma_beta_g1);
292  // affine_ate_g2_precomp pvk_vk_gamma_beta_g2_precomp =
293  // affine_ate_precompute_g2<CurveType>(vk.gamma_beta_g2);
294 
295  // const accumulation_vector<g1_type> accumulated_IC =
296  // vk.encoded_IC_query.accumulate_chunk<scalar_field_type>(primary_input.begin(),
297  // primary_input.end(), 0);
298  // assert(accumulated_IC.is_fully_accumulated());
299  // const g1_value_type &acc = accumulated_IC.first;
300 
301  // bool result = true;
302  // affine_ate_g1_precomp proof_g_A_g_precomp = affine_ate_precompute_g1<CurveType>(proof.g_A.g);
303  // affine_ate_g1_precomp proof_g_A_h_precomp = affine_ate_precompute_g1<CurveType>(proof.g_A.h);
304  // typename gt_type::value_type kc_A_miller = affine_ate_e_over_e_miller_loop<CurveType>(
305  // proof_g_A_g_precomp, pvk_vk_alphaA_g2_precomp, proof_g_A_h_precomp, pvk_pp_G2_one_precomp);
306  // gt_value_type kc_A = final_exponentiation<CurveType>(kc_A_miller);
307 
308  // if (kc_A != gt_value_type::one()) {
309  // result = false;
310  // }
311 
312  // affine_ate_g2_precomp proof_g_B_g_precomp =
313  // affine_ate_precompute_g2<CurveType>(proof.g_B.g);
314  // affine_ate_g1_precomp proof_g_B_h_precomp =
315  // affine_ate_precompute_g1<CurveType>(proof.g_B.h);
316  // typename gt_type::value_type kc_B_miller = affine_ate_e_over_e_miller_loop<CurveType>(
317  // pvk_vk_alphaB_g1_precomp, proof_g_B_g_precomp, proof_g_B_h_precomp, pvk_pp_G2_one_precomp);
318  // gt_value_type kc_B = final_exponentiation<CurveType>(kc_B_miller);
319  // if (kc_B != gt_value_type::one()) {
320  // result = false;
321  // }
322 
323  // affine_ate_g1_precomp proof_g_C_g_precomp =
324  // affine_ate_precompute_g1<CurveType>(proof.g_C.g);
325  // affine_ate_g1_precomp proof_g_C_h_precomp =
326  // affine_ate_precompute_g1<CurveType>(proof.g_C.h);
327  // typename gt_type::value_type kc_C_miller = affine_ate_e_over_e_miller_loop<CurveType>(
328  // proof_g_C_g_precomp, pvk_vk_alphaC_g2_precomp, proof_g_C_h_precomp, pvk_pp_G2_one_precomp);
329  // gt_value_type kc_C = final_exponentiation<CurveType>(kc_C_miller);
330  // if (kc_C != gt_value_type::one()) {
331  // result = false;
332  // }
333 
334  // affine_ate_g1_precomp proof_g_A_g_acc_precomp =
335  // affine_ate_precompute_g1<CurveType>(proof.g_A.g + acc);
336  // affine_ate_g1_precomp proof_g_H_precomp = affine_ate_precompute_g1<CurveType>(proof.g_H);
337  // typename gt_type::value_type QAP_miller =
338  // affine_ate_e_times_e_over_e_miller_loop<CurveType>(
339  // proof_g_H_precomp, pvk_vk_rC_Z_g2_precomp, proof_g_C_g_precomp, pvk_pp_G2_one_precomp,
340  // proof_g_A_g_acc_precomp, proof_g_B_g_precomp);
341  // gt_value_type QAP = final_exponentiation<CurveType>(QAP_miller);
342  // if (QAP != gt_value_type::one()) {
343  // result = false;
344  // }
345 
346  // affine_ate_g1_precomp proof_g_K_precomp = affine_ate_precompute_g1<CurveType>(proof.g_K);
347  // affine_ate_g1_precomp proof_g_A_g_acc_C_precomp =
348  // affine_ate_precompute_g1<CurveType>((proof.g_A.g + acc) + proof.g_C.g);
349  // typename gt_type::value_type K_miller =
350  // affine_ate_e_times_e_over_e_miller_loop<CurveType>(
351  // proof_g_A_g_acc_C_precomp, pvk_vk_gamma_beta_g2_precomp, pvk_vk_gamma_beta_g1_precomp,
352  // proof_g_B_g_precomp, proof_g_K_precomp, pvk_vk_gamma_g2_precomp);
353  // gt_value_type K = final_exponentiation<CurveType>(K_miller);
354  // if (K != gt_value_type::one()) {
355  // result = false;
356  // }
357 
358  // return result;
359  // }
360  // };
361  } // namespace snark
362  } // namespace zk
363  } // namespace crypto3
364 } // namespace nil
365 
366 #endif // CRYPTO3_R1CS_PPZKSNARK_BASIC_VERIFIER_HPP
std::size_t domain_size() const
Definition: accumulation_vector.hpp:79
accumulation_vector< Type > accumulate_chunk(InputIterator begin, InputIterator end, std::size_t offset) const
Definition: accumulation_vector.hpp:94
underlying_value_type first
Definition: accumulation_vector.hpp:52
Definition: snark/proof.hpp:37
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:44
policy_type::processed_verification_key_type processed_verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:50
static processed_verification_key_type process(const verification_key_type &verification_key)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:53
policy_type::verification_key_type verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:49
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:102
pairing_policy::g1_precomputed_type vk_gamma_beta_g1_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:114
pairing_policy::g2_precomputed_type vk_alphaC_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:111
pairing_policy::g1_precomputed_type vk_alphaB_g1_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:110
pairing_policy::g2_precomputed_type pp_G2_one_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:108
accumulation_vector< typename CurveType::template g1_type<> > encoded_IC_query
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:117
pairing_policy::g2_precomputed_type vk_alphaA_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:109
pairing_policy::g2_precomputed_type vk_gamma_beta_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:115
pairing_policy::g2_precomputed_type vk_gamma_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:113
pairing_policy::g2_precomputed_type vk_rC_Z_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:112
Definition: snark/systems/ppzksnark/r1cs_ppzksnark/proof.hpp:43
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:42
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:198
policy_type::verification_key_type verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:203
policy_type::primary_input_type primary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:202
static bool process(const verification_key_type &verification_key, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:212
policy_type::proof_type proof_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:205
policy_type::processed_verification_key_type processed_verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:204
static bool process(const processed_verification_key_type &processed_verification_key, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:225
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:80
policy_type::proof_type proof_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:97
static bool process(const processed_verification_key_type &processed_verification_key, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:117
policy_type::primary_input_type primary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:94
policy_type::verification_key_type verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:95
policy_type::processed_verification_key_type processed_verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:96
static bool process(const verification_key_type &verification_key, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verifier.hpp:104
Definition: pair.hpp:31
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/detail/basic_policy.hpp:78
r1cs_primary_input< typename CurveType::scalar_field_type > primary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/detail/basic_policy.hpp:89
Definition: zk/include/nil/crypto3/zk/snark/verification_key.hpp:35