uscs_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_USCS_PPZKSNARK_BASIC_GENERATOR_HPP
27 #define CRYPTO3_ZK_USCS_PPZKSNARK_BASIC_GENERATOR_HPP
28 
30 
35 #include <nil/crypto3/zk/snark/schemes/ppzksnark/uscs_ppzksnark/detail/basic_policy.hpp>
36 
37 namespace nil {
38  namespace crypto3 {
39  namespace zk {
40  namespace snark {
41 
48  template<typename CurveType>
51 
52  using g1_type = typename CurveType::template g1_type<>;
53  using g2_type = typename CurveType::template g2_type<>;
54  using scalar_field_type = typename CurveType::scalar_field_type;
55 
56  public:
60 
64 
67 
68  static inline keypair_type process(const constraint_system_type &constraint_system) {
69 
70  /* draw random element at which the SSP is evaluated */
71 
72  const typename scalar_field_type::value_type t =
73  algebra::random_element<scalar_field_type>();
74 
75  /* perform USCS-to-SSP reduction */
76 
79  scalar_field_type>::instance_map_with_evaluation(constraint_system, t);
80 
81  /* construct various tables of typename FieldType::value_type elements */
82 
83  std::vector<typename scalar_field_type::value_type> Vt_table = std::move(
84  ssp_inst.Vt); // ssp_inst.Vt is now in unspecified state, but we do not use it later
85  std::vector<typename scalar_field_type::value_type> Ht_table = std::move(
86  ssp_inst.Ht); // ssp_inst.Ht is now in unspecified state, but we do not use it later
87 
88  Vt_table.emplace_back(ssp_inst.Zt);
89 
90  std::vector<typename scalar_field_type::value_type> Xt_table =
91  std::vector<typename scalar_field_type::value_type>(
92  Vt_table.begin(), Vt_table.begin() + ssp_inst.num_inputs + 1);
93  std::vector<typename scalar_field_type::value_type> Vt_table_minus_Xt_table =
94  std::vector<typename scalar_field_type::value_type>(
95  Vt_table.begin() + ssp_inst.num_inputs + 1, Vt_table.end());
96 
97  /* sanity checks */
98 
99  assert(Vt_table.size() == ssp_inst.num_variables + 2);
100  assert(Ht_table.size() == ssp_inst.degree + 1);
101  assert(Xt_table.size() == ssp_inst.num_inputs + 1);
102  assert(Vt_table_minus_Xt_table.size() ==
103  ssp_inst.num_variables + 2 - ssp_inst.num_inputs - 1);
104  for (std::size_t i = 0; i < ssp_inst.num_inputs + 1; ++i) {
105  assert(!Xt_table[i].is_zero());
106  }
107 
108  const typename scalar_field_type::value_type alpha =
109  algebra::random_element<scalar_field_type>();
110 
111  const std::size_t g1_exp_count =
112  Vt_table.size() + Vt_table_minus_Xt_table.size() + Ht_table.size();
113  const std::size_t g2_exp_count = Vt_table_minus_Xt_table.size();
114 
115  std::size_t g1_window = algebra::get_exp_window_size<g1_type>(g1_exp_count);
116  std::size_t g2_window = algebra::get_exp_window_size<g2_type>(g2_exp_count);
117 
118  algebra::window_table<g1_type> g1_table = algebra::get_window_table<g1_type>(
119  scalar_field_type::value_bits, g1_window, g1_type::value_type::one());
120 
121  algebra::window_table<g2_type> g2_table = algebra::get_window_table<g2_type>(
122  scalar_field_type::value_bits, g2_window, g2_type::value_type::one());
123 
124  typename std::vector<typename g1_type::value_type> V_g1_query = algebra::batch_exp<g1_type, scalar_field_type>(
125  scalar_field_type::value_bits, g1_window, g1_table, Vt_table_minus_Xt_table);
126 #ifdef USE_MIXED_ADDITION
127  algebra::batch_to_special<g1_type>(V_g1_query);
128 #endif
129 
130  typename std::vector<typename g1_type::value_type> alpha_V_g1_query =
131  algebra::batch_exp_with_coeff<g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_table, alpha,
132  Vt_table_minus_Xt_table);
133 #ifdef USE_MIXED_ADDITION
134  algebra::batch_to_special<g1_type>(alpha_V_g1_query);
135 #endif
136 
137  typename std::vector<typename g1_type::value_type> H_g1_query =
138  algebra::batch_exp<g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_table, Ht_table);
139 #ifdef USE_MIXED_ADDITION
140  algebra::batch_to_special<g1_type>(H_g1_query);
141 #endif
142 
143  typename std::vector<typename g2_type::value_type> V_g2_query =
144  algebra::batch_exp<g2_type, scalar_field_type>(scalar_field_type::value_bits, g2_window, g2_table, Vt_table);
145 #ifdef USE_MIXED_ADDITION
146  algebra::batch_to_special<g2_type>(V_g2_query);
147 #endif
148  const typename scalar_field_type::value_type tilde =
149  algebra::random_element<scalar_field_type>();
150  typename g2_type::value_type tilde_g2 =
151  tilde * g2_type::value_type::one();
152  typename g2_type::value_type alpha_tilde_g2 =
153  (alpha * tilde) * g2_type::value_type::one();
154  typename g2_type::value_type Z_g2 =
155  ssp_inst.Zt * g2_type::value_type::one();
156 
157  typename g1_type::value_type encoded_IC_base =
158  Xt_table[0] * g1_type::value_type::one();
159  typename std::vector<typename g1_type::value_type> encoded_IC_values =
160  algebra::batch_exp<g1_type, scalar_field_type>(scalar_field_type::value_bits, g1_window, g1_table,
161  std::vector<typename scalar_field_type::value_type>(
162  Xt_table.begin() + 1, Xt_table.end()));
163 
164  accumulation_vector<g1_type> encoded_IC_query(std::move(encoded_IC_base),
165  std::move(encoded_IC_values));
166 
168  verification_key_type(tilde_g2, alpha_tilde_g2, Z_g2, encoded_IC_query);
169 
170  constraint_system_type cs_copy = constraint_system;
172  std::move(alpha_V_g1_query),
173  std::move(H_g1_query),
174  std::move(V_g2_query),
175  std::move(cs_copy));
176 
177  return keypair_type(std::move(pk), std::move(vk));
178  }
179  };
180  } // namespace snark
181  } // namespace zk
182  } // namespace crypto3
183 } // namespace nil
184 
185 #endif // CRYPTO3_ZK_USCS_PPZKSNARK_BASIC_GENERATOR_HPP
Definition: uscs_ppzksnark/generator.hpp:49
policy_type::proof_type proof_type
Definition: uscs_ppzksnark/generator.hpp:66
policy_type::auxiliary_input_type auxiliary_input_type
Definition: uscs_ppzksnark/generator.hpp:59
policy_type::keypair_type keypair_type
Definition: uscs_ppzksnark/generator.hpp:65
policy_type::primary_input_type primary_input_type
Definition: uscs_ppzksnark/generator.hpp:58
static keypair_type process(const constraint_system_type &constraint_system)
Definition: uscs_ppzksnark/generator.hpp:68
policy_type::processed_verification_key_type processed_verification_key_type
Definition: uscs_ppzksnark/generator.hpp:63
policy_type::verification_key_type verification_key_type
Definition: uscs_ppzksnark/generator.hpp:62
policy_type::constraint_system_type constraint_system_type
Definition: uscs_ppzksnark/generator.hpp:57
policy_type::proving_key_type proving_key_type
Definition: uscs_ppzksnark/generator.hpp:61
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/verification_key.hpp:87
Definition: snark/systems/ppzksnark/uscs_ppzksnark/proof.hpp:41
Definition: systems/ppzksnark/uscs_ppzksnark/proving_key.hpp:39
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_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/uscs_ppzksnark/detail/basic_policy.hpp:78
uscs_auxiliary_input< typename CurveType::scalar_field_type > auxiliary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/detail/basic_policy.hpp:90
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
uscs_ppzksnark_keypair< proving_key_type, verification_key_type > keypair_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/uscs_ppzksnark/detail/basic_policy.hpp:122
std::vector< typename FieldType::value_type > Vt
Definition: ssp.hpp:168
std::vector< typename FieldType::value_type > Ht
Definition: ssp.hpp:168
std::size_t num_variables
Definition: ssp.hpp:160
std::size_t num_inputs
Definition: ssp.hpp:162
std::size_t degree
Definition: ssp.hpp:161
FieldType::value_type Zt
Definition: ssp.hpp:170