Electroneum
multiexp.cpp
Go to the documentation of this file.
1 // Copyright (c) 2018, The Monero Project
2 //
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without modification, are
6 // permitted provided that the following conditions are met:
7 //
8 // 1. Redistributions of source code must retain the above copyright notice, this list of
9 // conditions and the following disclaimer.
10 //
11 // 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 // of conditions and the following disclaimer in the documentation and/or other
13 // materials provided with the distribution.
14 //
15 // 3. Neither the name of the copyright holder nor the names of its contributors may be
16 // used to endorse or promote products derived from this software without specific
17 // prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
20 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
21 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
22 // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
26 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
27 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 
29 #include "gtest/gtest.h"
30 
31 #include "crypto/crypto.h"
32 #include "ringct/rctOps.h"
33 #include "ringct/multiexp.h"
34 
35 static const rct::key TESTSCALAR = rct::skGen();
36 static const rct::key TESTPOW2SCALAR = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
37 static const rct::key TESTSMALLSCALAR = {{5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
38 static const rct::key TESTPOINT = rct::scalarmultBase(rct::skGen());
39 
40 static rct::key basic(const std::vector<rct::MultiexpData> &data)
41 {
42  ge_p3 res_p3 = ge_p3_identity;
43  for (const auto &d: data)
44  {
45  ge_cached cached;
46  ge_p3 p3;
47  ge_p1p1 p1;
48  ge_scalarmult_p3(&p3, d.scalar.bytes, &d.point);
49  ge_p3_to_cached(&cached, &p3);
50  ge_add(&p1, &res_p3, &cached);
51  ge_p1p1_to_p3(&res_p3, &p1);
52  }
53  rct::key res;
54  ge_p3_tobytes(res.bytes, &res_p3);
55  return res;
56 }
57 
58 static ge_p3 get_p3(const rct::key &point)
59 {
60  ge_p3 p3;
61  EXPECT_TRUE(ge_frombytes_vartime(&p3, point.bytes) == 0);
62  return p3;
63 }
64 
65 TEST(multiexp, bos_coster_empty)
66 {
67  std::vector<rct::MultiexpData> data;
68  data.push_back({rct::zero(), get_p3(rct::identity())});
69  ASSERT_TRUE(basic(data) == bos_coster_heap_conv_robust(data));
70 }
71 
72 TEST(multiexp, straus_empty)
73 {
74  std::vector<rct::MultiexpData> data;
75  data.push_back({rct::zero(), get_p3(rct::identity())});
76  ASSERT_TRUE(basic(data) == straus(data));
77 }
78 
79 TEST(multiexp, pippenger_empty)
80 {
81  std::vector<rct::MultiexpData> data;
82  data.push_back({rct::zero(), get_p3(rct::identity())});
83  ASSERT_TRUE(basic(data) == pippenger(data));
84 }
85 
86 TEST(multiexp, bos_coster_zero_and_non_zero)
87 {
88  std::vector<rct::MultiexpData> data;
89  data.push_back({rct::zero(), get_p3(TESTPOINT)});
90  data.push_back({TESTSCALAR, get_p3(TESTPOINT)});
91  ASSERT_TRUE(basic(data) == bos_coster_heap_conv_robust(data));
92 }
93 
94 TEST(multiexp, straus_zero_and_non_zero)
95 {
96  std::vector<rct::MultiexpData> data;
97  data.push_back({rct::zero(), get_p3(TESTPOINT)});
98  data.push_back({TESTSCALAR, get_p3(TESTPOINT)});
99  ASSERT_TRUE(basic(data) == straus(data));
100 }
101 
102 TEST(multiexp, pippenger_zero_and_non_zero)
103 {
104  std::vector<rct::MultiexpData> data;
105  data.push_back({rct::zero(), get_p3(TESTPOINT)});
106  data.push_back({TESTSCALAR, get_p3(TESTPOINT)});
107  ASSERT_TRUE(basic(data) == pippenger(data));
108 }
109 
110 TEST(multiexp, bos_coster_pow2_scalar)
111 {
112  std::vector<rct::MultiexpData> data;
113  data.push_back({TESTPOW2SCALAR, get_p3(TESTPOINT)});
114  data.push_back({TESTSMALLSCALAR, get_p3(TESTPOINT)});
115  ASSERT_TRUE(basic(data) == bos_coster_heap_conv_robust(data));
116 }
117 
118 TEST(multiexp, straus_pow2_scalar)
119 {
120  std::vector<rct::MultiexpData> data;
121  data.push_back({TESTPOW2SCALAR, get_p3(TESTPOINT)});
122  data.push_back({TESTSMALLSCALAR, get_p3(TESTPOINT)});
123  ASSERT_TRUE(basic(data) == straus(data));
124 }
125 
126 TEST(multiexp, pippenger_pow2_scalar)
127 {
128  std::vector<rct::MultiexpData> data;
129  data.push_back({TESTPOW2SCALAR, get_p3(TESTPOINT)});
130  data.push_back({TESTSMALLSCALAR, get_p3(TESTPOINT)});
131  ASSERT_TRUE(basic(data) == pippenger(data));
132 }
133 
134 TEST(multiexp, bos_coster_only_zeroes)
135 {
136  std::vector<rct::MultiexpData> data;
137  for (int n = 0; n < 16; ++n)
138  data.push_back({rct::zero(), get_p3(TESTPOINT)});
139  ASSERT_TRUE(basic(data) == bos_coster_heap_conv_robust(data));
140 }
141 
142 TEST(multiexp, straus_only_zeroes)
143 {
144  std::vector<rct::MultiexpData> data;
145  for (int n = 0; n < 16; ++n)
146  data.push_back({rct::zero(), get_p3(TESTPOINT)});
147  ASSERT_TRUE(basic(data) == straus(data));
148 }
149 
150 TEST(multiexp, pippenger_only_zeroes)
151 {
152  std::vector<rct::MultiexpData> data;
153  for (int n = 0; n < 16; ++n)
154  data.push_back({rct::zero(), get_p3(TESTPOINT)});
155  ASSERT_TRUE(basic(data) == pippenger(data));
156 }
157 
158 TEST(multiexp, bos_coster_only_identities)
159 {
160  std::vector<rct::MultiexpData> data;
161  for (int n = 0; n < 16; ++n)
162  data.push_back({TESTSCALAR, get_p3(rct::identity())});
163  ASSERT_TRUE(basic(data) == bos_coster_heap_conv_robust(data));
164 }
165 
166 TEST(multiexp, straus_only_identities)
167 {
168  std::vector<rct::MultiexpData> data;
169  for (int n = 0; n < 16; ++n)
170  data.push_back({TESTSCALAR, get_p3(rct::identity())});
171  ASSERT_TRUE(basic(data) == straus(data));
172 }
173 
174 TEST(multiexp, pippenger_only_identities)
175 {
176  std::vector<rct::MultiexpData> data;
177  for (int n = 0; n < 16; ++n)
178  data.push_back({TESTSCALAR, get_p3(rct::identity())});
179  ASSERT_TRUE(basic(data) == pippenger(data));
180 }
181 
182 TEST(multiexp, bos_coster_random)
183 {
184  std::vector<rct::MultiexpData> data;
185  for (int n = 0; n < 32; ++n)
186  {
187  data.push_back({rct::skGen(), get_p3(rct::scalarmultBase(rct::skGen()))});
188  ASSERT_TRUE(basic(data) == bos_coster_heap_conv_robust(data));
189  }
190 }
191 
192 TEST(multiexp, straus_random)
193 {
194  std::vector<rct::MultiexpData> data;
195  for (int n = 0; n < 32; ++n)
196  {
197  data.push_back({rct::skGen(), get_p3(rct::scalarmultBase(rct::skGen()))});
198  ASSERT_TRUE(basic(data) == straus(data));
199  }
200 }
201 
202 TEST(multiexp, pippenger_random)
203 {
204  std::vector<rct::MultiexpData> data;
205  for (int n = 0; n < 32; ++n)
206  {
207  data.push_back({rct::skGen(), get_p3(rct::scalarmultBase(rct::skGen()))});
208  ASSERT_TRUE(basic(data) == pippenger(data));
209  }
210 }
211 
212 TEST(multiexp, straus_cached)
213 {
214  static constexpr size_t N = 256;
215  std::vector<rct::MultiexpData> P(N);
216  for (size_t n = 0; n < N; ++n)
217  {
218  P[n].scalar = rct::zero();
219  ASSERT_TRUE(ge_frombytes_vartime(&P[n].point, rct::scalarmultBase(rct::skGen()).bytes) == 0);
220  }
221  std::shared_ptr<rct::straus_cached_data> cache = rct::straus_init_cache(P);
222  for (size_t n = 0; n < N/16; ++n)
223  {
224  std::vector<rct::MultiexpData> data;
225  size_t sz = 1 + crypto::rand<size_t>() % (N-1);
226  for (size_t s = 0; s < sz; ++s)
227  {
228  data.push_back({rct::skGen(), P[s].point});
229  }
230  ASSERT_TRUE(basic(data) == straus(data, cache));
231  }
232 }
233 
234 TEST(multiexp, pippenger_cached)
235 {
236  static constexpr size_t N = 256;
237  std::vector<rct::MultiexpData> P(N);
238  for (size_t n = 0; n < N; ++n)
239  {
240  P[n].scalar = rct::zero();
241  ASSERT_TRUE(ge_frombytes_vartime(&P[n].point, rct::scalarmultBase(rct::skGen()).bytes) == 0);
242  }
243  std::shared_ptr<rct::pippenger_cached_data> cache = rct::pippenger_init_cache(P);
244  for (size_t n = 0; n < N/16; ++n)
245  {
246  std::vector<rct::MultiexpData> data;
247  size_t sz = 1 + crypto::rand<size_t>() % (N-1);
248  for (size_t s = 0; s < sz; ++s)
249  {
250  data.push_back({rct::skGen(), P[s].point});
251  }
252  ASSERT_TRUE(basic(data) == pippenger(data, cache));
253  }
254 }
const char * res
Definition: hmac_keccak.cpp:41
std::shared_ptr< straus_cached_data > straus_init_cache(const std::vector< MultiexpData > &data, size_t N=0)
rct::key straus(const std::vector< MultiexpData > &data, const std::shared_ptr< straus_cached_data > &cache=NULL, size_t STEP=0)
#define EXPECT_TRUE(condition)
Definition: gtest.h:1859
rct::key pippenger(const std::vector< MultiexpData > &data, const std::shared_ptr< pippenger_cached_data > &cache=NULL, size_t cache_size=0, size_t c=0)
std::shared_ptr< pippenger_cached_data > pippenger_init_cache(const std::vector< MultiexpData > &data, size_t start_offset=0, size_t N=0)
void ge_scalarmult_p3(ge_p3 *, const unsigned char *, const ge_p3 *)
#define ge_p1p1_to_p3
Definition: ge.h:63
#define ge_add
Definition: ge.h:69
void skGen(key &sk)
Definition: rctOps.cpp:253
#define ge_p3_to_cached
Definition: ge.h:61
#define ge_p3_tobytes
Definition: ge.h:55
void scalarmultBase(key &aG, const key &a)
Definition: rctOps.cpp:350
rct::key bos_coster_heap_conv_robust(std::vector< MultiexpData > data)
unsigned char bytes[32]
Definition: rctTypes.h:86
key identity()
Definition: rctOps.h:73
#define ASSERT_TRUE(condition)
Definition: gtest.h:1865
const ge_p3 ge_p3_identity
TEST(multiexp, bos_coster_empty)
Definition: multiexp.cpp:65
int ge_frombytes_vartime(ge_p3 *, const unsigned char *)
key zero()
Definition: rctOps.h:70