commitment.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 // Copyright (c) 2020-2021 Ilias Khairullin <ilias@nil.foundation>
5 //
6 // MIT License
7 //
8 // Permission is hereby granted, free of charge, to any person obtaining a copy
9 // of this software and associated documentation files (the "Software"), to deal
10 // in the Software without restriction, including without limitation the rights
11 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 // copies of the Software, and to permit persons to whom the Software is
13 // furnished to do so, subject to the following conditions:
14 //
15 // The above copyright notice and this permission notice shall be included in all
16 // copies or substantial portions of the Software.
17 //
18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 // SOFTWARE.
25 //---------------------------------------------------------------------------//
26 // @file This module implements two binding commitment schemes used in the Groth16
27 // aggregation.
28 // The first one is a commitment scheme that commits to a single vector $a$ of
29 // length n in the second base group $G_1$ (for example):
30 // * it requires a structured SRS $v_1$ of the form $(h,h^u,h^{u^2}, ...
31 // ,g^{h^{n-1}})$ with $h \in G_2$ being a random generator of $G_2$ and $u$ a
32 // random scalar (coming from a power of tau ceremony for example)
33 // * it requires a second structured SRS $v_2$ of the form $(h,h^v,h^{v^2},
34 // ...$ with $v$ being a random scalar different than u (coming from another
35 // power of tau ceremony for example)
36 // The Commitment is a tuple $(\prod_{i=0}^{n-1} e(a_i,v_{1,i}),
37 // \prod_{i=0}^{n-1} e(a_i,v_{2,i}))$
38 //
39 // The second one takes two vectors $a \in G_1^n$ and $b \in G_2^n$ and commits
40 // to them using a similar approach as above. It requires an additional SRS
41 // though:
42 // * $v_1$ and $v_2$ stay the same
43 // * An additional tuple $w_1 = (g^{u^n},g^{u^{n+1}},...g^{u^{2n-1}})$ and $w_2 =
44 // (g^{v^n},g^{v^{n+1},...,g^{v^{2n-1}})$ where $g$ is a random generator of
45 // $G_1$
46 // The commitment scheme returns a tuple:
47 // * $\prod_{i=0}^{n-1} e(a_i,v_{1,i})e(w_{1,i},b_i)$
48 // * $\prod_{i=0}^{n-1} e(a_i,v_{2,i})e(w_{2,i},b_i)$
49 //
50 // The second commitment scheme enables to save some KZG verification in the
51 // verifier of the Groth16 verification protocol since we pack two vectors in
52 // one commitment.
53 
54 #ifndef CRYPTO3_R1CS_GG_PPZKSNARK_AGGREGATE_IPP2_COMMITMENT_HPP
55 #define CRYPTO3_R1CS_GG_PPZKSNARK_AGGREGATE_IPP2_COMMITMENT_HPP
56 
57 #include <tuple>
58 #include <vector>
59 #include <type_traits>
60 
61 #include <boost/assert.hpp>
62 #include <boost/iterator/zip_iterator.hpp>
63 #include <boost/accumulators/accumulators.hpp>
64 
66 
68 
69 namespace nil {
70  namespace crypto3 {
71  namespace zk {
72  namespace snark {
74  template<typename CurveType>
76  std::pair<typename CurveType::gt_type::value_type, typename CurveType::gt_type::value_type>;
77 
80  template<typename GroupType>
82  typedef GroupType group_type;
83  typedef typename group_type::curve_type curve_type;
84  typedef typename curve_type::scalar_field_type field_type;
85 
86  typedef typename group_type::value_type group_value_type;
87  typedef typename field_type::value_type field_value_type;
88 
90  std::vector<group_value_type> a;
92  std::vector<group_value_type> b;
93 
98  inline bool has_correct_len(std::size_t n) const {
99  return a.size() == n && n == b.size();
100  }
101 
104  template<
105  typename InputIterator,
106  typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
107  typename std::enable_if<std::is_same<field_value_type, ValueType>::value, bool>::type = true>
109  InputIterator s_last) const {
110  BOOST_ASSERT(has_correct_len(std::distance(s_first, s_last)));
111 
113  std::for_each(boost::make_zip_iterator(boost::make_tuple(s_first, a.begin(), b.begin())),
114  boost::make_zip_iterator(boost::make_tuple(s_last, a.end(), b.end())),
115  [&](const boost::tuple<const field_value_type &, const group_value_type &,
116  const group_value_type &> &t) {
117  result.a.emplace_back(t.template get<1>() * t.template get<0>());
118  result.b.emplace_back(t.template get<2>() * t.template get<0>());
119  });
120 
121  return result;
122  }
123 
125  std::pair<r1cs_gg_ppzksnark_ipp2_commitment_key<group_type>,
127  split(std::size_t at) const {
128  BOOST_ASSERT(a.size() == b.size());
129  BOOST_ASSERT(at > 0 && at < a.size());
130 
133 
134  auto a_it = a.begin();
135  auto b_it = b.begin();
136  while (a_it != a.begin() + at && b_it != b.begin() + at) {
137  result_l.a.emplace_back(*a_it);
138  result_l.b.emplace_back(*b_it);
139  ++a_it;
140  ++b_it;
141  }
142  while (a_it != a.end() && b_it != b.end()) {
143  result_r.a.emplace_back(*a_it);
144  result_r.b.emplace_back(*b_it);
145  ++a_it;
146  ++b_it;
147  }
148 
149  return std::make_pair(result_l, result_r);
150  }
151 
157  const field_value_type &scale) const {
158  BOOST_ASSERT(a.size() == right.a.size());
159  BOOST_ASSERT(b.size() == right.b.size());
160  BOOST_ASSERT(a.size() == b.size());
161 
163 
164  std::for_each(
165  boost::make_zip_iterator(
166  boost::make_tuple(a.begin(), b.begin(), right.a.begin(), right.b.begin())),
167  boost::make_zip_iterator(boost::make_tuple(a.end(), b.end(), right.a.end(), right.b.end())),
168  [&](const boost::tuple<const group_value_type &, const group_value_type &,
169  const group_value_type &, const group_value_type &> &t) {
170  result.a.emplace_back(t.template get<0>() + t.template get<2>() * scale);
171  result.b.emplace_back(t.template get<1>() + t.template get<3>() * scale);
172  });
173 
174  return result;
175  }
176 
180  std::pair<group_value_type, group_value_type> first() const {
181  return std::make_pair(a.front(), b.front());
182  }
183  };
184 
188  template<typename CurveType>
191 
195  template<typename CurveType>
198 
199  template<typename CurveType>
201  typedef CurveType curve_type;
203 
206 
209  typedef typename curve_type::gt_type::value_type gt_value_type;
210 
212 
217  template<typename InputG1Iterator, typename InputG2Iterator,
218  typename ValueType1 = typename std::iterator_traits<InputG1Iterator>::value_type,
219  typename ValueType2 = typename std::iterator_traits<InputG2Iterator>::value_type,
220  typename std::enable_if<std::is_same<g1_value_type, ValueType1>::value, bool>::type = true,
221  typename std::enable_if<std::is_same<g2_value_type, ValueType2>::value, bool>::type = true>
222  static output_type pair(const vkey_type &vkey, const wkey_type &wkey, InputG1Iterator a_first,
223  InputG1Iterator a_last, InputG2Iterator b_first, InputG2Iterator b_last) {
224  BOOST_ASSERT(vkey.has_correct_len(std::distance(a_first, a_last)));
225  BOOST_ASSERT(wkey.has_correct_len(std::distance(b_first, b_last)));
226  BOOST_ASSERT(std::distance(a_first, a_last) == std::distance(b_first, b_last));
227 
228  // (A * v)
229  gt_value_type t1 = gt_value_type::one();
230  std::for_each(boost::make_zip_iterator(boost::make_tuple(a_first, vkey.a.begin())),
231  boost::make_zip_iterator(boost::make_tuple(a_last, vkey.a.end())),
232  [&](const boost::tuple<const g1_value_type &, const g2_value_type &> &t) {
233  t1 = t1 * algebra::pair<curve_type>(t.template get<0>(), t.template get<1>());
234  });
235 
236  // (B * v)
237  gt_value_type t2 = gt_value_type::one();
238  std::for_each(boost::make_zip_iterator(boost::make_tuple(wkey.a.begin(), b_first)),
239  boost::make_zip_iterator(boost::make_tuple(wkey.a.end(), b_last)),
240  [&](const boost::tuple<const g1_value_type &, const g2_value_type &> &t) {
241  t2 = t2 * algebra::pair<curve_type>(t.template get<0>(), t.template get<1>());
242  });
243 
244  gt_value_type u1 = gt_value_type::one();
245  std::for_each(boost::make_zip_iterator(boost::make_tuple(a_first, vkey.b.begin())),
246  boost::make_zip_iterator(boost::make_tuple(a_last, vkey.b.end())),
247  [&](const boost::tuple<const g1_value_type &, const g2_value_type &> &t) {
248  u1 = u1 * algebra::pair<curve_type>(t.template get<0>(), t.template get<1>());
249  });
250 
251  gt_value_type u2 = gt_value_type::one();
252  std::for_each(boost::make_zip_iterator(boost::make_tuple(wkey.b.begin(), b_first)),
253  boost::make_zip_iterator(boost::make_tuple(wkey.b.end(), b_last)),
254  [&](const boost::tuple<const g1_value_type &, const g2_value_type &> &t) {
255  u2 = u2 * algebra::pair<curve_type>(t.template get<0>(), t.template get<1>());
256  });
257 
258  // (A * v)(w * B)
259  return std::make_pair(algebra::final_exponentiation<curve_type>(t1 * t2),
260  algebra::final_exponentiation<curve_type>(u1 * u2));
261  }
262 
267  template<typename InputG1Iterator,
268  typename ValueType1 = typename std::iterator_traits<InputG1Iterator>::value_type,
269  typename std::enable_if<std::is_same<g1_value_type, ValueType1>::value, bool>::type = true>
270  static output_type single(const vkey_type &vkey, InputG1Iterator a_first, InputG1Iterator a_last) {
271  BOOST_ASSERT(vkey.has_correct_len(std::distance(a_first, a_last)));
272 
273  gt_value_type t1 = gt_value_type::one();
274  std::for_each(boost::make_zip_iterator(boost::make_tuple(a_first, vkey.a.begin())),
275  boost::make_zip_iterator(boost::make_tuple(a_last, vkey.a.end())),
276  [&](const boost::tuple<const g1_value_type &, const g2_value_type &> &t) {
277  t1 = t1 * algebra::pair<curve_type>(t.template get<0>(), t.template get<1>());
278  });
279 
280  gt_value_type u1 = gt_value_type::one();
281  std::for_each(boost::make_zip_iterator(boost::make_tuple(a_first, vkey.b.begin())),
282  boost::make_zip_iterator(boost::make_tuple(a_last, vkey.b.end())),
283  [&](const boost::tuple<const g1_value_type &, const g2_value_type &> &t) {
284  u1 = u1 * algebra::pair<curve_type>(t.template get<0>(), t.template get<1>());
285  });
286 
287  return std::make_pair(algebra::final_exponentiation<curve_type>(t1),
288  algebra::final_exponentiation<curve_type>(u1));
289  }
290  };
291  } // namespace snark
292  } // namespace zk
293  } // namespace crypto3
294 } // namespace nil
295 
296 #endif // CRYPTO3_R1CS_GG_PPZKSNARK_AGGREGATE_IPP2_COMMITMENT_HPP
typename std::iterator_traits< Iterator >::value_type ValueType
Definition: algebra/include/nil/crypto3/detail/make_array.hpp:50
std::pair< typename CurveType::gt_type::value_type, typename CurveType::gt_type::value_type > r1cs_gg_ppzksnark_ipp2_commitment_output
Both commitment outputs a pair of $F_q^k$ element.
Definition: commitment.hpp:76
Definition: pair.hpp:31
Definition: pairing_policy.hpp:35
std::pair< r1cs_gg_ppzksnark_ipp2_commitment_key< group_type >, r1cs_gg_ppzksnark_ipp2_commitment_key< group_type > > split(std::size_t at) const
Returns the left and right commitment key part. It makes copy.
Definition: commitment.hpp:127
curve_type::scalar_field_type field_type
Definition: commitment.hpp:84
group_type::value_type group_value_type
Definition: commitment.hpp:86
std::vector< group_value_type > a
Exponent is a.
Definition: commitment.hpp:90
r1cs_gg_ppzksnark_ipp2_commitment_key< group_type > scale(InputIterator s_first, InputIterator s_last) const
Definition: commitment.hpp:108
r1cs_gg_ppzksnark_ipp2_commitment_key< group_type > compress(const r1cs_gg_ppzksnark_ipp2_commitment_key< group_type > &right, const field_value_type &scale) const
Definition: commitment.hpp:156
std::pair< group_value_type, group_value_type > first() const
Definition: commitment.hpp:180
std::vector< group_value_type > b
Exponent is b.
Definition: commitment.hpp:92
group_type::curve_type curve_type
Definition: commitment.hpp:83
bool has_correct_len(std::size_t n) const
Definition: commitment.hpp:98
field_type::value_type field_value_type
Definition: commitment.hpp:87
wkey_type::group_value_type g1_value_type
Definition: commitment.hpp:207
r1cs_gg_ppzksnark_ipp2_wkey< curve_type > wkey_type
Definition: commitment.hpp:204
curve_type::gt_type::value_type gt_value_type
Definition: commitment.hpp:209
r1cs_gg_ppzksnark_ipp2_vkey< curve_type > vkey_type
Definition: commitment.hpp:205
static output_type pair(const vkey_type &vkey, const wkey_type &wkey, InputG1Iterator a_first, InputG1Iterator a_last, InputG2Iterator b_first, InputG2Iterator b_last)
Definition: commitment.hpp:222
algebra::pairing::pairing_policy< curve_type > pairing
Definition: commitment.hpp:202
static output_type single(const vkey_type &vkey, InputG1Iterator a_first, InputG1Iterator a_last)
Definition: commitment.hpp:270
r1cs_gg_ppzksnark_ipp2_commitment_output< curve_type > output_type
Definition: commitment.hpp:211
CurveType curve_type
Definition: commitment.hpp:201
vkey_type::group_value_type g2_value_type
Definition: commitment.hpp:208