r1cs_se_ppzksnark/generator.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_R1CS_SE_PPZKSNARK_BASIC_GENERATOR_HPP
27 #define CRYPTO3_ZK_R1CS_SE_PPZKSNARK_BASIC_GENERATOR_HPP
28 
29 #ifdef MULTICORE
30 #include <omp.h>
31 #endif
32 
34 
36 #include <nil/crypto3/zk/snark/schemes/ppzksnark/r1cs_se_ppzksnark/detail/basic_policy.hpp>
37 
38 namespace nil {
39  namespace crypto3 {
40  namespace zk {
41  namespace snark {
42 
49  template<typename CurveType>
52 
53  using g1_type = typename CurveType::template g1_type<>;
54  using g2_type = typename CurveType::template g2_type<>;
55 
56  public:
57  typedef CurveType curve_type;
58 
60 
63 
65 
66  static inline keypair_type process(const constraint_system_type &constraint_system) {
67 
72  const std::shared_ptr<math::evaluation_domain<typename CurveType::scalar_field_type>> domain =
74  constraint_system);
75  typename CurveType::scalar_field_type::value_type t;
76  do {
77  t = algebra::random_element<typename CurveType::scalar_field_type>();
78  } while (domain->compute_vanishing_polynomial(t).is_zero());
79 
82  typename CurveType::scalar_field_type>::instance_map_with_evaluation(constraint_system,
83  t);
84 
85  std::size_t non_zero_At = 0;
86  for (std::size_t i = 0; i < sap_inst.num_variables + 1; ++i) {
87  if (!sap_inst.At[i].is_zero()) {
88  ++non_zero_At;
89  }
90  }
91 
92  std::vector<typename CurveType::scalar_field_type::value_type> At = std::move(sap_inst.At);
93  std::vector<typename CurveType::scalar_field_type::value_type> Ct = std::move(sap_inst.Ct);
94  std::vector<typename CurveType::scalar_field_type::value_type> Ht = std::move(sap_inst.Ht);
100  const typename CurveType::scalar_field_type::value_type
101  alpha = algebra::random_element<typename CurveType::scalar_field_type>(),
102  beta = algebra::random_element<typename CurveType::scalar_field_type>(),
103  gamma = algebra::random_element<typename CurveType::scalar_field_type>();
104  const typename g1_type::value_type G =
105  algebra::random_element<g1_type>();
106  const typename g2_type::value_type H =
107  algebra::random_element<g2_type>();
108 
109  std::size_t G_exp_count = sap_inst.num_inputs + 1 // verifier_query
110  + non_zero_At // A_query
111  + sap_inst.degree +
112  1 // G_gamma2_Z_t
113  // C_query_1
114  + sap_inst.num_variables - sap_inst.num_inputs +
115  sap_inst.num_variables + 1, // C_query_2
116  G_window = algebra::get_exp_window_size<g1_type>(G_exp_count);
117 
119  algebra::get_window_table<g1_type>(CurveType::scalar_field_type::value_bits, G_window, G);
120 
121  typename g2_type::value_type H_gamma = gamma * H;
122  std::size_t H_gamma_exp_count = non_zero_At, // B_query
123  H_gamma_window =
124  algebra::get_exp_window_size<g2_type>(H_gamma_exp_count);
125  algebra::window_table<g2_type> H_gamma_table = algebra::get_window_table<g2_type>(
126  CurveType::scalar_field_type::value_bits, H_gamma_window, H_gamma);
127 
128  typename g1_type::value_type G_alpha = alpha * G;
129  typename g2_type::value_type H_beta = beta * H;
130 
131  std::vector<typename CurveType::scalar_field_type::value_type> tmp_exponents;
132  tmp_exponents.reserve(sap_inst.num_inputs + 1);
133  for (std::size_t i = 0; i <= sap_inst.num_inputs; ++i) {
134  tmp_exponents.emplace_back(gamma * Ct[i] + (alpha + beta) * At[i]);
135  }
136  typename std::vector<typename g1_type::value_type> verifier_query =
137  algebra::batch_exp<g1_type, typename CurveType::scalar_field_type>(
138  CurveType::scalar_field_type::value_bits, G_window, G_table, tmp_exponents);
139  tmp_exponents.clear();
140 
141  tmp_exponents.reserve(sap_inst.num_variables + 1);
142  for (std::size_t i = 0; i < At.size(); i++) {
143  tmp_exponents.emplace_back(gamma * At[i]);
144  }
145 
146  typename std::vector<typename g1_type::value_type> A_query =
147  algebra::batch_exp<g1_type, typename CurveType::scalar_field_type>(
148  CurveType::scalar_field_type::value_bits, G_window, G_table, tmp_exponents);
149  tmp_exponents.clear();
150 #ifdef USE_MIXED_ADDITION
151  algebra::batch_to_special<g1_type>(A_query);
152 #endif
153  typename std::vector<typename g2_type::value_type> B_query =
154  algebra::batch_exp<g2_type, typename CurveType::scalar_field_type>(
155  CurveType::scalar_field_type::value_bits, H_gamma_window, H_gamma_table, At);
156 #ifdef USE_MIXED_ADDITION
157  algebra::batch_to_special<g2_type>(B_query);
158 #endif
159  typename g1_type::value_type G_gamma = gamma * G;
160  typename g1_type::value_type G_gamma_Z = sap_inst.Zt * G_gamma;
161  typename g2_type::value_type H_gamma_Z = sap_inst.Zt * H_gamma;
162  typename g1_type::value_type G_ab_gamma_Z = (alpha + beta) * G_gamma_Z;
163  typename g1_type::value_type G_gamma2_Z2 = (sap_inst.Zt * gamma) * G_gamma_Z;
164 
165  tmp_exponents.reserve(sap_inst.degree + 1);
166 
167  /* Compute the vector G_gamma2_Z_t := Z(t) * t^i * gamma^2 * G */
168  typename CurveType::scalar_field_type::value_type gamma2_Z_t = sap_inst.Zt * gamma.squared();
169  for (std::size_t i = 0; i < sap_inst.degree + 1; ++i) {
170  tmp_exponents.emplace_back(gamma2_Z_t);
171  gamma2_Z_t *= t;
172  }
173  typename std::vector<typename g1_type::value_type> G_gamma2_Z_t =
174  algebra::batch_exp<g1_type, typename CurveType::scalar_field_type>(
175  CurveType::scalar_field_type::value_bits, G_window, G_table, tmp_exponents);
176  tmp_exponents.clear();
177 #ifdef USE_MIXED_ADDITION
178  algebra::batch_to_special<g1_type>(G_gamma2_Z_t);
179 #endif
180  tmp_exponents.reserve(sap_inst.num_variables - sap_inst.num_inputs);
181  for (std::size_t i = sap_inst.num_inputs + 1; i <= sap_inst.num_variables; ++i) {
182  tmp_exponents.emplace_back(gamma * (gamma * Ct[i] + (alpha + beta) * At[i]));
183  }
184  typename std::vector<typename g1_type::value_type> C_query_1 =
185  algebra::batch_exp<g1_type, typename CurveType::scalar_field_type>(
186  CurveType::scalar_field_type::value_bits, G_window, G_table, tmp_exponents);
187  tmp_exponents.clear();
188 #ifdef USE_MIXED_ADDITION
189  algebra::batch_to_special<g1_type>(C_query_1);
190 #endif
191 
192  tmp_exponents.reserve(sap_inst.num_variables + 1);
193  typename CurveType::scalar_field_type::value_type double_gamma2_Z = gamma * gamma * sap_inst.Zt;
194  double_gamma2_Z = double_gamma2_Z + double_gamma2_Z;
195  for (std::size_t i = 0; i <= sap_inst.num_variables; ++i) {
196  tmp_exponents.emplace_back(double_gamma2_Z * At[i]);
197  }
198  typename std::vector<typename g1_type::value_type> C_query_2 =
199  algebra::batch_exp<g1_type, typename CurveType::scalar_field_type>(
200  CurveType::scalar_field_type::value_bits, G_window, G_table, tmp_exponents);
201  tmp_exponents.clear();
202 #ifdef USE_MIXED_ADDITION
203  algebra::batch_to_special<g1_type>(C_query_2);
204 #endif
205 
207  verification_key_type(H, G_alpha, H_beta, G_gamma, H_gamma, std::move(verifier_query));
208 
209  constraint_system_type cs_copy(constraint_system);
210 
211  proving_key_type pk =
212  proving_key_type(std::move(A_query), std::move(B_query), std::move(C_query_1),
213  std::move(C_query_2), G_gamma_Z, H_gamma_Z, G_ab_gamma_Z, G_gamma2_Z2,
214  std::move(G_gamma2_Z_t), std::move(cs_copy));
215 
216  return {std::move(pk), std::move(vk)};
217  }
218  };
219  } // namespace snark
220  } // namespace zk
221  } // namespace crypto3
222 } // namespace nil
223 
224 #endif // CRYPTO3_ZK_R1CS_SE_PPZKSNARK_BASIC_GENERATOR_HPP
Definition: r1cs_se_ppzksnark/generator.hpp:50
policy_type::constraint_system_type constraint_system_type
Definition: r1cs_se_ppzksnark/generator.hpp:59
policy_type::verification_key_type verification_key_type
Definition: r1cs_se_ppzksnark/generator.hpp:62
static keypair_type process(const constraint_system_type &constraint_system)
Definition: r1cs_se_ppzksnark/generator.hpp:66
policy_type::proving_key_type proving_key_type
Definition: r1cs_se_ppzksnark/generator.hpp:61
policy_type::keypair_type keypair_type
Definition: r1cs_se_ppzksnark/generator.hpp:64
CurveType curve_type
Definition: r1cs_se_ppzksnark/generator.hpp:57
Definition: systems/ppzksnark/r1cs_se_ppzksnark/proving_key.hpp:39
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_se_ppzksnark/verification_key.hpp:40
static std::shared_ptr< math::evaluation_domain< FieldType > > get_domain(const r1cs_constraint_system< FieldType > &cs)
Definition: r1cs_to_sap.hpp:81
std::vector< std::vector< typename GroupType::value_type > > window_table
Definition: multiexp.hpp:116
OutputIterator move(const SinglePassRange &rng, OutputIterator result)
Definition: move.hpp:45
Definition: pair.hpp:31
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_se_ppzksnark/detail/basic_policy.hpp:82
r1cs_se_ppzksnark_keypair< proving_key_type, verification_key_type > keypair_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_se_ppzksnark/detail/basic_policy.hpp:126
std::vector< typename FieldType::value_type > At
Definition: sap.hpp:183
std::size_t num_inputs
Definition: sap.hpp:177
FieldType::value_type Zt
Definition: sap.hpp:185
std::vector< typename FieldType::value_type > Ct
Definition: sap.hpp:183
std::size_t degree
Definition: sap.hpp:176
std::size_t num_variables
Definition: sap.hpp:175
std::vector< typename FieldType::value_type > Ht
Definition: sap.hpp:183