r1cs_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_R1CS_PPZKSNARK_BASIC_GENERATOR_HPP
27 #define CRYPTO3_R1CS_PPZKSNARK_BASIC_GENERATOR_HPP
28 
29 #ifdef MULTICORE
30 #include <omp.h>
31 #endif
32 
34 
39 #include <nil/crypto3/zk/snark/schemes/ppzksnark/r1cs_ppzksnark/detail/basic_policy.hpp>
40 
41 namespace nil {
42  namespace crypto3 {
43  namespace zk {
44  namespace snark {
45  template<typename CurveType>
48 
49  public:
53 
57 
60 
61  static inline keypair_type process(const constraint_system_type &constraint_system) {
62 
63  typedef typename CurveType::scalar_field_type scalar_field_type;
64  typedef typename CurveType::template g1_type<> g1_type;
65  typedef typename CurveType::template g2_type<> g2_type;
66 
67  /* make the B_query "lighter" if possible */
68  constraint_system_type cs_copy(constraint_system);
69  cs_copy.swap_AB_if_beneficial();
70 
71  /* draw random element at which the QAP is evaluated */
72  const typename scalar_field_type::value_type t = algebra::random_element<scalar_field_type>();
73 
76 
77  std::size_t non_zero_At = 0, non_zero_Bt = 0, non_zero_Ct = 0, non_zero_Ht = 0;
78  for (std::size_t i = 0; i < qap_inst.num_variables + 1; ++i) {
79  if (!qap_inst.At[i].is_zero()) {
80  ++non_zero_At;
81  }
82  if (!qap_inst.Bt[i].is_zero()) {
83  ++non_zero_Bt;
84  }
85  if (!qap_inst.Ct[i].is_zero()) {
86  ++non_zero_Ct;
87  }
88  }
89  for (std::size_t i = 0; i < qap_inst.degree + 1; ++i) {
90  if (!qap_inst.Ht[i].is_zero()) {
91  ++non_zero_Ht;
92  }
93  }
94 
95  std::vector<typename scalar_field_type::value_type> At = std::move(
96  qap_inst.At); // qap_inst.At is now in unspecified state, but we do not use it later
97  std::vector<typename scalar_field_type::value_type> Bt = std::move(
98  qap_inst.Bt); // qap_inst.Bt is now in unspecified state, but we do not use it later
99  std::vector<typename scalar_field_type::value_type> Ct = std::move(
100  qap_inst.Ct); // qap_inst.Ct is now in unspecified state, but we do not use it later
101  std::vector<typename scalar_field_type::value_type> Ht = std::move(
102  qap_inst.Ht); // qap_inst.Ht is now in unspecified state, but we do not use it later
103 
104  /* append Zt to At,Bt,Ct with */
105  At.emplace_back(qap_inst.Zt);
106  Bt.emplace_back(qap_inst.Zt);
107  Ct.emplace_back(qap_inst.Zt);
108 
109  const typename scalar_field_type::value_type alphaA =
110  algebra::random_element<scalar_field_type>(),
111  alphaB =
112  algebra::random_element<scalar_field_type>(),
113  alphaC =
114  algebra::random_element<scalar_field_type>(),
115  rA = algebra::random_element<scalar_field_type>(),
116  rB = algebra::random_element<scalar_field_type>(),
117  beta =
118  algebra::random_element<scalar_field_type>(),
119  gamma =
120  algebra::random_element<scalar_field_type>();
121  const typename scalar_field_type::value_type rC = rA * rB;
122 
123  // consrtuct the same-coefficient-check query (must happen before zeroing out the prefix of
124  // At)
125  std::vector<typename scalar_field_type::value_type> Kt;
126  Kt.reserve(qap_inst.num_variables + 4);
127  for (std::size_t i = 0; i < qap_inst.num_variables + 1; ++i) {
128  Kt.emplace_back(beta * (rA * At[i] + rB * Bt[i] + rC * Ct[i]));
129  }
130  Kt.emplace_back(beta * rA * qap_inst.Zt);
131  Kt.emplace_back(beta * rB * qap_inst.Zt);
132  Kt.emplace_back(beta * rC * qap_inst.Zt);
133 
134  /* zero out prefix of At and stick it into IC coefficients */
135  std::vector<typename scalar_field_type::value_type> IC_coefficients;
136  IC_coefficients.reserve(qap_inst.num_inputs + 1);
137  for (std::size_t i = 0; i < qap_inst.num_inputs + 1; ++i) {
138  IC_coefficients.emplace_back(At[i]);
139  assert(!IC_coefficients[i].is_zero());
140  At[i] = scalar_field_type::value_type::zero();
141  }
142 
143  const std::size_t g1_exp_count = 2 * (non_zero_At - qap_inst.num_inputs + non_zero_Ct) +
144  non_zero_Bt + non_zero_Ht + Kt.size();
145  const std::size_t g2_exp_count = non_zero_Bt;
146 
147  std::size_t g1_window = algebra::get_exp_window_size<g1_type>(g1_exp_count);
148  std::size_t g2_window = algebra::get_exp_window_size<g2_type>(g2_exp_count);
149 
150 #ifdef MULTICORE
151  const std::size_t chunks = omp_get_max_threads(); // to override, set OMP_NUM_THREADS env
152  // var or call omp_set_num_threads()
153 #else
154  const std::size_t chunks = 1;
155 #endif
156 
157  algebra::window_table<g1_type> g1_table = algebra::get_window_table<g1_type>(
158  scalar_field_type::value_bits, g1_window, g1_type::value_type::one());
159 
160  algebra::window_table<g2_type> g2_table = algebra::get_window_table<g2_type>(
161  scalar_field_type::value_bits, g2_window, g2_type::value_type::one());
162 
164  kc_batch_exp<g1_type, g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_window, g1_table,
165  g1_table, rA, rA * alphaA, At, chunks);
166 
168  kc_batch_exp<g2_type, g1_type, scalar_field_type>(scalar_field_type::value_bits, g2_window, g1_window, g2_table, g1_table, rB,
169  rB * alphaB, Bt, chunks);
170 
172  kc_batch_exp<g1_type, g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_window, g1_table, g1_table, rC,
173  rC * alphaC, Ct, chunks);
174 
175  typename std::vector<typename g1_type::value_type> H_query =
176  algebra::batch_exp<g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_table, Ht);
177 #ifdef USE_MIXED_ADDITION
178  algebra::batch_to_special<g1_type>(H_query);
179 #endif
180 
181  typename std::vector<typename g1_type::value_type> K_query =
182  algebra::batch_exp<g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_table, Kt);
183 #ifdef USE_MIXED_ADDITION
184  algebra::batch_to_special<g1_type>(K_query);
185 #endif
186 
187  typename g2_type::value_type alphaA_g2 = alphaA * g2_type::value_type::one();
188  typename g1_type::value_type alphaB_g1 = alphaB * g1_type::value_type::one();
189  typename g2_type::value_type alphaC_g2 = alphaC * g2_type::value_type::one();
190  typename g2_type::value_type gamma_g2 = gamma * g2_type::value_type::one();
191  typename g1_type::value_type gamma_beta_g1 = (gamma * beta) * g1_type::value_type::one();
192  typename g2_type::value_type gamma_beta_g2 = (gamma * beta) * g2_type::value_type::one();
193  typename g2_type::value_type rC_Z_g2 = (rC * qap_inst.Zt) * g2_type::value_type::one();
194 
195  typename g1_type::value_type encoded_IC_base =
196  (rA * IC_coefficients[0]) * g1_type::value_type::one();
197  std::vector<typename scalar_field_type::value_type> multiplied_IC_coefficients;
198  multiplied_IC_coefficients.reserve(qap_inst.num_inputs);
199  for (std::size_t i = 1; i < qap_inst.num_inputs + 1; ++i) {
200  multiplied_IC_coefficients.emplace_back(rA * IC_coefficients[i]);
201  }
202  typename std::vector<typename g1_type::value_type> encoded_IC_values =
203  algebra::batch_exp<g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_table, multiplied_IC_coefficients);
204 
205  accumulation_vector<g1_type> encoded_IC_query(std::move(encoded_IC_base),
206  std::move(encoded_IC_values));
207 
209  verification_key_type(alphaA_g2, alphaB_g1, alphaC_g2, gamma_g2, gamma_beta_g1,
210  gamma_beta_g2, rC_Z_g2, encoded_IC_query);
212  std::move(B_query),
213  std::move(C_query),
214  std::move(H_query),
215  std::move(K_query),
216  std::move(cs_copy));
217 
218 
219  return keypair_type(std::move(pk), std::move(vk));
220  }
221  };
222  } // namespace snark
223  } // namespace zk
224  } // namespace crypto3
225 } // namespace nil
226 
227 #endif // CRYPTO3_R1CS_PPZKSNARK_BASIC_GENERATOR_HPP
Definition: r1cs_ppzksnark/generator.hpp:46
static keypair_type process(const constraint_system_type &constraint_system)
Definition: r1cs_ppzksnark/generator.hpp:61
policy_type::keypair_type keypair_type
Definition: r1cs_ppzksnark/generator.hpp:58
policy_type::proof_type proof_type
Definition: r1cs_ppzksnark/generator.hpp:59
policy_type::primary_input_type primary_input_type
Definition: r1cs_ppzksnark/generator.hpp:51
policy_type::proving_key_type proving_key_type
Definition: r1cs_ppzksnark/generator.hpp:54
policy_type::auxiliary_input_type auxiliary_input_type
Definition: r1cs_ppzksnark/generator.hpp:52
policy_type::processed_verification_key_type processed_verification_key_type
Definition: r1cs_ppzksnark/generator.hpp:56
policy_type::constraint_system_type constraint_system_type
Definition: r1cs_ppzksnark/generator.hpp:50
policy_type::verification_key_type verification_key_type
Definition: r1cs_ppzksnark/generator.hpp:55
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:102
Definition: snark/systems/ppzksnark/r1cs_ppzksnark/proof.hpp:43
Definition: systems/ppzksnark/r1cs_ppzksnark/proving_key.hpp:47
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/verification_key.hpp:42
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
bool is_zero(const Range &a)
Definition: basic_operations.hpp:43
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
r1cs_ppzksnark_keypair< proving_key_type, verification_key_type > keypair_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/detail/basic_policy.hpp:123
r1cs_auxiliary_input< typename CurveType::scalar_field_type > auxiliary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_ppzksnark/detail/basic_policy.hpp:91
std::vector< field_value_type > Ct
Definition: qap.hpp:196
std::size_t degree
Definition: qap.hpp:189
std::size_t num_inputs
Definition: qap.hpp:190
std::vector< field_value_type > Bt
Definition: qap.hpp:196
std::vector< field_value_type > At
Definition: qap.hpp:196
field_value_type Zt
Definition: qap.hpp:198
std::size_t num_variables
Definition: qap.hpp:188
std::vector< field_value_type > Ht
Definition: qap.hpp:196
void swap_AB_if_beneficial()
Definition: r1cs.hpp:191
static qap_instance_evaluation< FieldType > instance_map_with_evaluation(const r1cs_constraint_system< FieldType > &cs, const typename FieldType::value_type &t)
Definition: r1cs_to_qap.hpp:140
Definition: sparse_vector.hpp:48