zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_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_ZK_USCS_PPZKSNARK_BASIC_VERIFIER_HPP
27 #define CRYPTO3_ZK_USCS_PPZKSNARK_BASIC_VERIFIER_HPP
28 
29 #ifdef MULTICORE
30 #include <omp.h>
31 #endif
32 
37 #include <nil/crypto3/zk/snark/schemes/ppzksnark/uscs_ppzksnark/detail/basic_policy.hpp>
38 
39 namespace nil {
40  namespace crypto3 {
41  namespace zk {
42  namespace snark {
43 
44  using namespace algebra;
45 
46  /*
47  Below are four variants of verifier algorithm for the USCS ppzkSNARK.
48 
49  These are the four cases that arise from the following two choices:
50 
51  (1) The verifier accepts a (non-processed) verification key or, instead, a processed
52  verification key. In the latter case, we call the algorithm an "online verifier".
53 
54  (2) The verifier checks for "weak" input consistency or, instead, "strong" input consistency.
55  Strong input consistency requires that |primary_input| = CS.num_inputs, whereas
56  weak input consistency requires that |primary_input| <= CS.num_inputs (and
57  the primary input is implicitly padded with zeros up to length CS.num_inputs).
58  */
59 
63  template<typename CurveType>
66  using g1_type = typename CurveType::template g1_type<>;
67  using g2_type = typename CurveType::template g2_type<>;
68  public:
71 
73 
75 
76  pvk.pp_G1_one_precomp =
77  precompute_g1<CurveType>(g1_type::value_type::one());
78  pvk.pp_G2_one_precomp =
79  precompute_g2<CurveType>(g2_type::value_type::one());
80 
81  pvk.vk_tilde_g2_precomp = precompute_g2<CurveType>(vk.tilde_g2);
82  pvk.vk_alpha_tilde_g2_precomp = precompute_g2<CurveType>(vk.alpha_tilde_g2);
83  pvk.vk_Z_g2_precomp = precompute_g2<CurveType>(vk.Z_g2);
84 
85  pvk.pairing_of_g1_and_g2 = miller_loop<CurveType>(pvk.pp_G1_one_precomp, pvk.pp_G2_one_precomp);
86 
88 
89  return pvk;
90  }
91  };
92 
93  template<typename CurveType>
96 
98 
99  public:
104 
110  static inline bool process(const verification_key_type &vk,
111  const primary_input_type &primary_input,
112  const proof_type &proof) {
113 
114  return process(
116  primary_input, proof);
117  }
118 
124  static inline bool process(const processed_verification_key_type &pvk,
125  const primary_input_type &primary_input,
126  const proof_type &proof) {
127 
128  assert(pvk.encoded_IC_query.domain_size() >= primary_input.size());
129 
132  primary_input.begin(), primary_input.end(), 0);
133  assert(accumulated_IC.is_fully_accumulated());
134  const typename CurveType::template g1_type<>::value_type &acc = accumulated_IC.first;
135 
136  bool result = true;
137 
138  if (!proof.is_well_formed()) {
139  result = false;
140  }
141 
142  typename pairing_policy::g1_precomputed_type proof_V_g1_with_acc_precomp =
143  precompute_g1<CurveType>(proof.V_g1 + acc);
144  typename pairing_policy::g2_precomputed_type proof_V_g2_precomp =
145  precompute_g2<CurveType>(proof.V_g2);
146  typename CurveType::gt_type::value_type V_1 =
147  miller_loop<CurveType>(proof_V_g1_with_acc_precomp, pvk.pp_G2_one_precomp);
148  typename CurveType::gt_type::value_type V_2 =
149  miller_loop<CurveType>(pvk.pp_G1_one_precomp, proof_V_g2_precomp);
150  typename CurveType::gt_type::value_type V =
151  final_exponentiation<CurveType>(V_1 * V_2.unitary_inversed());
152 
153  if (V != CurveType::gt_type::value_type::one()) {
154  result = false;
155  }
156 
157  typename pairing_policy::g1_precomputed_type proof_H_g1_precomp =
158  precompute_g1<CurveType>(proof.H_g1);
159  typename CurveType::gt_type::value_type SSP_1 =
160  miller_loop<CurveType>(proof_V_g1_with_acc_precomp, proof_V_g2_precomp);
161  typename CurveType::gt_type::value_type SSP_2 =
162  miller_loop<CurveType>(proof_H_g1_precomp, pvk.vk_Z_g2_precomp);
163  typename CurveType::gt_type::value_type SSP = final_exponentiation<CurveType>(
164  SSP_1.unitary_inversed() * SSP_2 * pvk.pairing_of_g1_and_g2);
165 
166  if (SSP != CurveType::gt_type::value_type::one()) {
167  result = false;
168  }
169 
170  typename pairing_policy::g1_precomputed_type proof_V_g1_precomp =
171  precompute_g1<CurveType>(proof.V_g1);
172  typename pairing_policy::g1_precomputed_type proof_alpha_V_g1_precomp =
173  precompute_g1<CurveType>(proof.alpha_V_g1);
174  typename CurveType::gt_type::value_type alpha_V_1 =
175  miller_loop<CurveType>(proof_V_g1_precomp, pvk.vk_alpha_tilde_g2_precomp);
176  typename CurveType::gt_type::value_type alpha_V_2 =
177  miller_loop<CurveType>(proof_alpha_V_g1_precomp, pvk.vk_tilde_g2_precomp);
178  typename CurveType::gt_type::value_type alpha_V =
179  final_exponentiation<CurveType>(alpha_V_1 * alpha_V_2.unitary_inversed());
180 
181  if (alpha_V != CurveType::gt_type::value_type::one()) {
182  result = false;
183  }
184 
185  return result;
186  }
187  };
188 
189  template<typename CurveType>
192 
193  public:
198 
204  static inline bool process(const verification_key_type &vk,
205  const primary_input_type &primary_input,
206  const proof_type &proof) {
209  }
210 
216  static inline bool process(const processed_verification_key_type &pvk,
217  const primary_input_type &primary_input,
218  const proof_type &proof) {
219 
220  bool result = true;
221 
222  if (pvk.encoded_IC_query.domain_size() != primary_input.size()) {
223  result = false;
224  } else {
226  pvk, primary_input, proof);
227  }
228 
229  return result;
230  }
231  };
232  } // namespace snark
233  } // namespace zk
234  } // namespace crypto3
235 } // namespace nil
236 
237 #endif // CRYPTO3_ZK_USCS_PPZKSNARK_BASIC_VERIFIER_HPP
Definition: accumulation_vector.hpp:46
bool is_fully_accumulated() const
Definition: accumulation_vector.hpp:75
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/uscs_ppzksnark/verifier.hpp:64
policy_type::verification_key_type verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:69
policy_type::processed_verification_key_type processed_verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:70
static processed_verification_key_type process(const verification_key_type &vk)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:72
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:87
accumulation_vector< typename CurveType::template g1_type<> > encoded_IC_query
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:100
CurveType::gt_type::value_type pairing_of_g1_and_g2
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:98
pairing_policy::g2_precomputed_type vk_alpha_tilde_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:96
pairing_policy::g2_precomputed_type vk_Z_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:97
pairing_policy::g2_precomputed_type vk_tilde_g2_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:95
pairing_policy::g1_precomputed_type pp_G1_one_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:93
pairing_policy::g2_precomputed_type pp_G2_one_precomp
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:94
Definition: snark/systems/ppzksnark/uscs_ppzksnark/proof.hpp:41
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:42
g2_type::value_type tilde_g2
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:47
g2_type::value_type Z_g2
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:49
g2_type::value_type alpha_tilde_g2
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:48
accumulation_vector< g1_type > encoded_IC_query
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:51
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:190
policy_type::processed_verification_key_type processed_verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:196
policy_type::primary_input_type primary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:194
policy_type::verification_key_type verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:195
policy_type::proof_type proof_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:197
static bool process(const processed_verification_key_type &pvk, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:216
static bool process(const verification_key_type &vk, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:204
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:94
policy_type::processed_verification_key_type processed_verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:102
static bool process(const processed_verification_key_type &pvk, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:124
static bool process(const verification_key_type &vk, const primary_input_type &primary_input, const proof_type &proof)
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:110
policy_type::verification_key_type verification_key_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:101
policy_type::primary_input_type primary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:100
policy_type::proof_type proof_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verifier.hpp:103
Definition: pair.hpp:31
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/detail/basic_policy.hpp:78
uscs_primary_input< typename CurveType::scalar_field_type > primary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/detail/basic_policy.hpp:88