r1cs_gg_ppzksnark/prover.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_GG_PPZKSNARK_BASIC_PROVER_HPP
27 #define CRYPTO3_ZK_R1CS_GG_PPZKSNARK_BASIC_PROVER_HPP
28 
29 #ifdef MULTICORE
30 #include <omp.h>
31 #endif
32 
36 
41 
42 namespace nil {
43  namespace crypto3 {
44  namespace zk {
45  namespace snark {
46  template<typename CurveType, ProvingMode Mode = ProvingMode::Basic>
48 
57  template<typename CurveType>
60 
61  typedef typename CurveType::scalar_field_type scalar_field_type;
62  typedef typename CurveType::template g1_type<> g1_type;
63  typedef typename CurveType::template g2_type<> g2_type;
64  typedef typename CurveType::gt_type gt_type;
65 
66  public:
71 
73  const primary_input_type &primary_input,
74  const auxiliary_input_type &auxiliary_input) {
75 
76  BOOST_ASSERT(proving_key.constraint_system.is_satisfied(primary_input, auxiliary_input));
77 
78  const qap_witness<scalar_field_type> qap_wit =
80  proving_key.constraint_system, primary_input, auxiliary_input,
81  scalar_field_type::value_type::zero(), scalar_field_type::value_type::zero(),
82  scalar_field_type::value_type::zero());
83 
84  /* We are dividing degree 2(d-1) polynomial by degree d polynomial
85  and not adding a PGHR-style ZK-patch, so our H is degree d-2 */
86  // BOOST_ASSERT(!qap_wit.coefficients_for_H[qap_wit.degree - 2].is_zero());
87  BOOST_ASSERT(qap_wit.coefficients_for_H[qap_wit.degree - 1].is_zero());
88  BOOST_ASSERT(qap_wit.coefficients_for_H[qap_wit.degree].is_zero());
89 
90  /* Choose two random field elements for prover zero-knowledge. */
91  const typename scalar_field_type::value_type r = algebra::random_element<scalar_field_type>();
92  const typename scalar_field_type::value_type s = algebra::random_element<scalar_field_type>();
93 #ifdef MULTICORE
94  const std::size_t chunks = omp_get_max_threads(); // to override, set OMP_NUM_THREADS env
95  // var or call omp_set_num_threads()
96 #else
97  const std::size_t chunks = 1;
98 #endif
99 
100  // TODO: sort out indexing
101  std::vector<typename scalar_field_type::value_type> const_padded_assignment(
102  1, scalar_field_type::value_type::one());
103  const_padded_assignment.insert(const_padded_assignment.end(),
104  qap_wit.coefficients_for_ABCs.begin(),
105  qap_wit.coefficients_for_ABCs.end());
106 
107  typename g1_type::value_type evaluation_At =
108  algebra::multiexp_with_mixed_addition<algebra::policies::multiexp_method_BDLO12>(
109  proving_key.A_query.begin(),
110  proving_key.A_query.begin() + qap_wit.num_variables + 1,
111  const_padded_assignment.begin(),
112  const_padded_assignment.begin() + qap_wit.num_variables + 1,
113  chunks);
114 
116  kc_multiexp_with_mixed_addition<algebra::policies::multiexp_method_BDLO12>(
117  proving_key.B_query,
118  0,
119  qap_wit.num_variables + 1,
120  const_padded_assignment.begin(),
121  const_padded_assignment.begin() + qap_wit.num_variables + 1,
122  chunks);
123 
124  typename g1_type::value_type evaluation_Ht =
125  algebra::multiexp<algebra::policies::multiexp_method_BDLO12>(
126  proving_key.H_query.begin(),
127  proving_key.H_query.begin() + (qap_wit.degree - 1),
128  qap_wit.coefficients_for_H.begin(),
129  qap_wit.coefficients_for_H.begin() + (qap_wit.degree - 1),
130  chunks);
131 
132  typename g1_type::value_type evaluation_Lt =
133  algebra::multiexp_with_mixed_addition<algebra::policies::multiexp_method_BDLO12>(
134  proving_key.L_query.begin(),
135  proving_key.L_query.end(),
136  const_padded_assignment.begin() + qap_wit.num_inputs + 1,
137  const_padded_assignment.begin() + qap_wit.num_variables + 1,
138  chunks);
139 
140  /* A = alpha + sum_i(a_i*A_i(t)) + r*delta */
141  typename g1_type::value_type g1_A =
142  proving_key.alpha_g1 + evaluation_At + r * proving_key.delta_g1;
143 
144  /* B = beta + sum_i(a_i*B_i(t)) + s*delta */
145  typename g1_type::value_type g1_B =
146  proving_key.beta_g1 + evaluation_Bt.h + s * proving_key.delta_g1;
147  typename g2_type::value_type g2_B =
148  proving_key.beta_g2 + evaluation_Bt.g + s * proving_key.delta_g2;
149 
150  /* C = sum_i(a_i*((beta*A_i(t) + alpha*B_i(t) + C_i(t)) + H(t)*Z(t))/delta) + A*s + r*b -
151  * r*s*delta
152  */
153  typename g1_type::value_type g1_C =
154  evaluation_Ht + evaluation_Lt + s * g1_A + r * g1_B - (r * s) * proving_key.delta_g1;
155 
156  return proof_type(std::move(g1_A), std::move(g2_B), std::move(g1_C));
157  }
158  };
159  } // namespace snark
160  } // namespace zk
161  } // namespace crypto3
162 } // namespace nil
163 
164 #endif // CRYPTO3_ZK_R1CS_GG_PPZKSNARK_BASIC_PROVER_HPP
Definition: proving_key.hpp:37
static proof_type process(const proving_key_type &proving_key, const primary_input_type &primary_input, const auxiliary_input_type &auxiliary_input)
Definition: r1cs_gg_ppzksnark/prover.hpp:72
policy_type::primary_input_type primary_input_type
Definition: r1cs_gg_ppzksnark/prover.hpp:67
policy_type::proving_key_type proving_key_type
Definition: r1cs_gg_ppzksnark/prover.hpp:69
policy_type::proof_type proof_type
Definition: r1cs_gg_ppzksnark/prover.hpp:70
policy_type::auxiliary_input_type auxiliary_input_type
Definition: r1cs_gg_ppzksnark/prover.hpp:68
Definition: r1cs_gg_ppzksnark/prover.hpp:47
OutputIterator move(const SinglePassRange &rng, OutputIterator result)
Definition: move.hpp:45
ProvingMode
Definition: modes.hpp:33
Definition: pair.hpp:31
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_gg_ppzksnark/detail/basic_policy.hpp:78
r1cs_auxiliary_input< typename curve_type::scalar_field_type > auxiliary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_gg_ppzksnark/detail/basic_policy.hpp:92
r1cs_primary_input< typename curve_type::scalar_field_type > primary_input_type
Definition: zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_gg_ppzksnark/detail/basic_policy.hpp:90
Definition: knowledge_commitment.hpp:49
std::size_t num_inputs
Definition: qap.hpp:317
std::size_t num_variables
Definition: qap.hpp:315
std::vector< field_value_type > coefficients_for_H
Definition: qap.hpp:322
std::vector< field_value_type > coefficients_for_ABCs
Definition: qap.hpp:321
std::size_t degree
Definition: qap.hpp:316
Definition: snark/systems/ppzksnark/r1cs_gg_ppzksnark/proof.hpp:40
Definition: systems/ppzksnark/r1cs_gg_ppzksnark/proving_key.hpp:39
static qap_witness< FieldType > witness_map(const r1cs_constraint_system< FieldType > &cs, const r1cs_primary_input< FieldType > &primary_input, const r1cs_auxiliary_input< FieldType > &auxiliary_input, const typename FieldType::value_type &d1, const typename FieldType::value_type &d2, const typename FieldType::value_type &d3)
Definition: r1cs_to_qap.hpp:221