Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
scalar_multiplication.test.cpp
Go to the documentation of this file.
1
12#include "barretenberg/ecc/scalar_multiplication/scalar_multiplication.hpp"
13#include "barretenberg/common/mem.hpp"
14#include "barretenberg/common/test.hpp"
15#include "barretenberg/numeric/random/engine.hpp"
16#include "barretenberg/srs/global_crs.hpp"
17
18#include <cstddef>
19#include <vector>
20
21using namespace bb;
22
23namespace {
24auto& engine = numeric::get_debug_randomness();
25}
26
27template <typename Curve> class ScalarMultiplicationTests : public ::testing::Test {
28 public:
29 static void SetUpTestSuite() { bb::srs::init_file_crs_factory(bb::srs::bb_crs_path()); }
30};
31
32using Curves = ::testing::Types<curve::BN254, curve::Grumpkin>;
33
34TYPED_TEST_SUITE(ScalarMultiplicationTests, Curves);
35
36TYPED_TEST(ScalarMultiplicationTests, EndomorphismSplit)
37{
38 using Curve = TypeParam;
39 using Group = typename Curve::Group;
40 using Element = typename Curve::Element;
41 using AffineElement = typename Curve::AffineElement;
42 using Fr = typename Curve::ScalarField;
43 using Fq = typename Curve::BaseField;
44
45 Fr scalar = Fr::random_element();
46
47 Element expected = Group::one * scalar;
48
49 Fr k1{ 0, 0, 0, 0 };
50 Fr k2{ 0, 0, 0, 0 };
51 Fr::split_into_endomorphism_scalars(scalar, k1, k2);
52
53 Element result;
54 Element t1 = Group::affine_one * k1;
55 AffineElement generator = Group::affine_one;
56 Fq beta = Fq::cube_root_of_unity();
57 generator.x = generator.x * beta;
58 generator.y = -generator.y;
59 Element t2 = generator * k2;
60 result = t1 + t2;
61
62 EXPECT_EQ(result == expected, true);
63}
64
65TYPED_TEST(ScalarMultiplicationTests, OversizedInputs)
66{
67 using Curve = TypeParam;
68 if constexpr (std::is_same_v<Curve, curve::Grumpkin>) {
69 // Grumpkin has at most 1 << 18 points; the test is not valid for it.
70 GTEST_SKIP() << "Skipping test for grumpkin";
71 }
72 using Element = typename Curve::Element;
73 using AffineElement = typename Curve::AffineElement;
74 using Fr = typename Curve::ScalarField;
75 using Fq = typename Curve::BaseField;
76
77 // for point ranges with more than 1 << 20 points, we split into chunks of smaller multi-exps.
78 // Check that this is done correctly
79 size_t target_degree = 1200000;
80 std::span<AffineElement> monomials = srs::get_crs_factory<Curve>()->get_crs(target_degree)->get_monomial_points();
81
82 Fr* scalars = (Fr*)(aligned_alloc(64, sizeof(Fr) * target_degree));
83
84 Fr source_scalar = Fr::random_element();
85 Fr accumulator = source_scalar;
86 for (size_t i = 0; i < target_degree; ++i) {
87 accumulator *= source_scalar;
88 Fr::__copy(accumulator, scalars[i]);
89 }
90
91 Element first = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ target_degree } }, monomials);
92 first = first.normalize();
93
94 for (size_t i = 0; i < target_degree; ++i) {
95 scalars[i].self_neg();
96 }
97
98 Element second = scalar_multiplication::pippenger<Curve>(
99 PolynomialSpan<const typename Curve::ScalarField>{ 0, { scalars, /*size*/ target_degree } }, monomials);
100 second = second.normalize();
101
102 EXPECT_EQ((first.z == second.z), true);
103 EXPECT_EQ((first.z == Fq::one()), true);
104 EXPECT_EQ((first.x == second.x), true);
105 EXPECT_EQ((first.y == -second.y), true);
106
107 aligned_free(scalars);
108}
109
110TYPED_TEST(ScalarMultiplicationTests, UndersizedInputs)
111{
112 using Curve = TypeParam;
113 using Element = typename Curve::Element;
114 using AffineElement = typename Curve::AffineElement;
115 using Fr = typename Curve::ScalarField;
116
117 // we fall back to traditional scalar multiplication algorithm for small input sizes.
118 // Check this is done correctly
119 size_t num_points = 17;
120
121 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr) * num_points);
122
123 AffineElement* points = (AffineElement*)aligned_alloc(32, sizeof(AffineElement) * (num_points * 2 + 1));
124
125 for (size_t i = 0; i < num_points; ++i) {
126 scalars[i] = Fr::random_element();
127 points[i] = AffineElement(Element::random_element());
128 }
129
130 Element expected;
131 expected.self_set_infinity();
132 for (size_t i = 0; i < num_points; ++i) {
133 Element temp = points[i] * scalars[i];
134 expected += temp;
135 }
136 expected = expected.normalize();
137
138 Element result = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ num_points } },
139 { points, /*size*/ num_points * 2 });
140 result = result.normalize();
141
142 aligned_free(scalars);
143 aligned_free(points);
144
145 EXPECT_EQ(result == expected, true);
146}
147
148TYPED_TEST(ScalarMultiplicationTests, PippengerSmall)
149{
150 using Curve = TypeParam;
151 using Element = typename Curve::Element;
152 using AffineElement = typename Curve::AffineElement;
153 using Fr = typename Curve::ScalarField;
154
155 constexpr size_t num_points = 8192;
156
157 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr) * num_points);
158
159 AffineElement* points = (AffineElement*)aligned_alloc(32, sizeof(AffineElement) * (num_points * 2 + 1));
160
161 for (size_t i = 0; i < num_points; ++i) {
162 scalars[i] = Fr::random_element();
163 points[i] = AffineElement(Element::random_element());
164 }
165
166 Element expected;
167 expected.self_set_infinity();
168 for (size_t i = 0; i < num_points; ++i) {
169 Element temp = points[i] * scalars[i];
170 expected += temp;
171 }
172 expected = expected.normalize();
173
174 Element result = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ num_points } },
175 { points, /*size*/ num_points });
176 result = result.normalize();
177
178 aligned_free(scalars);
179 aligned_free(points);
180
181 EXPECT_EQ(result == expected, true);
182}
183
184TYPED_TEST(ScalarMultiplicationTests, PippengerEdgeCaseDbl)
185{
186 using Curve = TypeParam;
187 using Element = typename Curve::Element;
188 using AffineElement = typename Curve::AffineElement;
189 using Fr = typename Curve::ScalarField;
190
191 constexpr size_t num_points = 128;
192
193 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr) * num_points);
194
195 AffineElement* points = (AffineElement*)aligned_alloc(32, sizeof(AffineElement) * (num_points * 2 + 1));
196
197 AffineElement point = AffineElement(Element::random_element());
198 for (size_t i = 0; i < num_points; ++i) {
199 scalars[i] = Fr::random_element();
200 points[i] = point;
201 }
202
203 Element expected;
204 expected.self_set_infinity();
205 for (size_t i = 0; i < num_points; ++i) {
206 Element temp = points[i] * scalars[i];
207 expected += temp;
208 }
209 if (!expected.is_point_at_infinity()) {
210 expected = expected.normalize();
211 }
212 Element result = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ num_points } },
213 { points, /*size*/ num_points * 2 });
214 result = result.normalize();
215
216 aligned_free(scalars);
217 aligned_free(points);
218
219 EXPECT_EQ(result == expected, true);
220}
221
222TYPED_TEST(ScalarMultiplicationTests, PippengerShortInputs)
223{
224 using Curve = TypeParam;
225 using Element = typename Curve::Element;
226 using AffineElement = typename Curve::AffineElement;
227 using Fr = typename Curve::ScalarField;
228
229 constexpr size_t num_points = 8192;
230
231 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr) * num_points);
232
233 std::vector<AffineElement> points(num_points);
234
235 for (size_t i = 0; i < num_points; ++i) {
236 points[i] = AffineElement(Element::random_element());
237 }
238 for (size_t i = 0; i < (num_points / 4); ++i) {
239 scalars[i * 4].data[0] = engine.get_random_uint32();
240 scalars[i * 4].data[1] = engine.get_random_uint32();
241 scalars[i * 4].data[2] = engine.get_random_uint32();
242 scalars[i * 4].data[3] = engine.get_random_uint32();
243 scalars[i * 4] = scalars[i * 4].to_montgomery_form();
244 scalars[i * 4 + 1].data[0] = 0;
245 scalars[i * 4 + 1].data[1] = 0;
246 scalars[i * 4 + 1].data[2] = 0;
247 scalars[i * 4 + 1].data[3] = 0;
248 scalars[i * 4 + 1] = scalars[i * 4 + 1].to_montgomery_form();
249 scalars[i * 4 + 2].data[0] = engine.get_random_uint32();
250 scalars[i * 4 + 2].data[1] = engine.get_random_uint32();
251 scalars[i * 4 + 2].data[2] = 0;
252 scalars[i * 4 + 2].data[3] = 0;
253 scalars[i * 4 + 2] = scalars[i * 4 + 2].to_montgomery_form();
254 scalars[i * 4 + 3].data[0] = (engine.get_random_uint32() & 0x07ULL);
255 scalars[i * 4 + 3].data[1] = 0;
256 scalars[i * 4 + 3].data[2] = 0;
257 scalars[i * 4 + 3].data[3] = 0;
258 scalars[i * 4 + 3] = scalars[i * 4 + 3].to_montgomery_form();
259 }
260
261 Element expected;
262 expected.self_set_infinity();
263 for (size_t i = 0; i < num_points; ++i) {
264 Element temp = points[i] * scalars[i];
265 expected += temp;
266 }
267 expected = expected.normalize();
268
269 Element result = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ num_points } }, points);
270 result = result.normalize();
271
272 aligned_free(scalars);
273
274 EXPECT_EQ(result == expected, true);
275}
276
277TYPED_TEST(ScalarMultiplicationTests, PippengerUnsafe)
278{
279 using Curve = TypeParam;
280 using Element = typename Curve::Element;
281 using AffineElement = typename Curve::AffineElement;
282 using Fr = typename Curve::ScalarField;
283
284 constexpr size_t num_points = 8192;
285
286 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr) * num_points);
287
288 std::vector<AffineElement> points(num_points);
289
290 for (size_t i = 0; i < num_points; ++i) {
291 scalars[i] = Fr::random_element();
292 points[i] = AffineElement(Element::random_element());
293 }
294
295 Element expected;
296 expected.self_set_infinity();
297 for (size_t i = 0; i < num_points; ++i) {
298 Element temp = points[i] * scalars[i];
299 expected += temp;
300 }
301 expected = expected.normalize();
302 Element result = scalar_multiplication::pippenger_unsafe<Curve>({ 0, { scalars, /*size*/ num_points } }, points);
303 result = result.normalize();
304
305 aligned_free(scalars);
306
307 EXPECT_EQ(result == expected, true);
308}
309
310TYPED_TEST(ScalarMultiplicationTests, PippengerUnsafeShortInputs)
311{
312 using Curve = TypeParam;
313 using Element = typename Curve::Element;
314 using AffineElement = typename Curve::AffineElement;
315 using Fr = typename Curve::ScalarField;
316
317 constexpr size_t num_points = 8192;
318
319 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr) * num_points);
320
321 AffineElement* points = (AffineElement*)aligned_alloc(32, sizeof(AffineElement) * (num_points * 2 + 1));
322
323 for (size_t i = 0; i < num_points; ++i) {
324 points[i] = AffineElement(Element::random_element());
325 }
326 for (size_t i = 0; i < (num_points / 4); ++i) {
327 scalars[i * 4].data[0] = engine.get_random_uint32();
328 scalars[i * 4].data[1] = engine.get_random_uint32();
329 scalars[i * 4].data[2] = engine.get_random_uint32();
330 scalars[i * 4].data[3] = engine.get_random_uint32();
331 scalars[i * 4] = scalars[i * 4].to_montgomery_form();
332 scalars[i * 4 + 1].data[0] = 0;
333 scalars[i * 4 + 1].data[1] = 0;
334 scalars[i * 4 + 1].data[2] = 0;
335 scalars[i * 4 + 1].data[3] = 0;
336 scalars[i * 4 + 1] = scalars[i * 4 + 1].to_montgomery_form();
337 scalars[i * 4 + 2].data[0] = engine.get_random_uint32();
338 scalars[i * 4 + 2].data[1] = engine.get_random_uint32();
339 scalars[i * 4 + 2].data[2] = 0;
340 scalars[i * 4 + 2].data[3] = 0;
341 scalars[i * 4 + 2] = scalars[i * 4 + 2].to_montgomery_form();
342 scalars[i * 4 + 3].data[0] = (engine.get_random_uint32() & 0x07ULL);
343 scalars[i * 4 + 3].data[1] = 0;
344 scalars[i * 4 + 3].data[2] = 0;
345 scalars[i * 4 + 3].data[3] = 0;
346 scalars[i * 4 + 3] = scalars[i * 4 + 3].to_montgomery_form();
347 }
348
349 Element expected;
350 expected.self_set_infinity();
351 for (size_t i = 0; i < num_points; ++i) {
352 Element temp = points[i] * scalars[i];
353 expected += temp;
354 }
355 expected = expected.normalize();
356
357 Element result = scalar_multiplication::pippenger_unsafe<Curve>({ 0, { scalars, /*size*/ num_points } },
358 { points, num_points * 2 + 1 });
359 result = result.normalize();
360
361 aligned_free(scalars);
362 aligned_free(points);
363
364 EXPECT_EQ(result == expected, true);
365}
366
367TYPED_TEST(ScalarMultiplicationTests, PippengerOne)
368{
369 using Curve = TypeParam;
370 using Element = typename Curve::Element;
371 using AffineElement = typename Curve::AffineElement;
372 using Fr = typename Curve::ScalarField;
373
374 size_t num_points = 1;
375
376 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr) * 1);
377
378 AffineElement* points = (AffineElement*)aligned_alloc(32, sizeof(AffineElement) * (num_points * 2 + 1));
379
380 for (size_t i = 0; i < num_points; ++i) {
381 scalars[i] = Fr::random_element();
382 points[i] = AffineElement(Element::random_element());
383 }
384
385 Element expected;
386 expected.self_set_infinity();
387 for (size_t i = 0; i < num_points; ++i) {
388 Element temp = points[i] * scalars[i];
389 expected += temp;
390 }
391 expected = expected.normalize();
392
393 Element result = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ num_points } },
394 { points, /*size*/ num_points * 2 });
395 result = result.normalize();
396
397 aligned_free(scalars);
398 aligned_free(points);
399
400 EXPECT_EQ(result == expected, true);
401}
402
403TYPED_TEST(ScalarMultiplicationTests, PippengerZeroPoints)
404{
405 using Curve = TypeParam;
406 using Element = typename Curve::Element;
407 using AffineElement = typename Curve::AffineElement;
408 using Fr = typename Curve::ScalarField;
409
410 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr));
411
412 AffineElement* points = (AffineElement*)aligned_alloc(32, sizeof(AffineElement) * (2 + 1));
413
414 Element result = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ 0 } }, { points, /*size*/ 0 });
415
416 aligned_free(scalars);
417 aligned_free(points);
418
419 EXPECT_EQ(result.is_point_at_infinity(), true);
420}
421
422TYPED_TEST(ScalarMultiplicationTests, PippengerMulByZero)
423{
424 using Curve = TypeParam;
425 using Group = typename Curve::Group;
426 using Element = typename Curve::Element;
427 using AffineElement = typename Curve::AffineElement;
428 using Fr = typename Curve::ScalarField;
429
430 Fr* scalars = (Fr*)aligned_alloc(32, sizeof(Fr));
431
432 AffineElement* points = (AffineElement*)aligned_alloc(32, sizeof(AffineElement) * (2 + 1));
433
434 scalars[0] = Fr::zero();
435 points[0] = Group::affine_one;
436 Element result = scalar_multiplication::pippenger<Curve>({ 0, { scalars, /*size*/ 1 } }, { points, /*size*/ 2 });
437
438 aligned_free(scalars);
439 aligned_free(points);
440
441 EXPECT_EQ(result.is_point_at_infinity(), true);
442}
bb::curve::Grumpkin::Element
typename Group::element Element
Definition grumpkin.hpp:63
bb::curve::Grumpkin::Group
typename grumpkin::g1 Group
Definition grumpkin.hpp:62
bb::curve::Grumpkin::AffineElement
typename Group::affine_element AffineElement
Definition grumpkin.hpp:64
bb::numeric::RNG::get_random_uint32
virtual uint32_t get_random_uint32()=0
engine
numeric::RNG & engine
Definition eccvm_transcript.test.cpp:282
global_crs.hpp
bb::numeric::get_debug_randomness
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:245
bb::srs::bb_crs_path
std::filesystem::path bb_crs_path()
Definition global_crs.cpp:14
bb::srs::init_file_crs_factory
void init_file_crs_factory(const std::filesystem::path &path)
Definition global_crs.hpp:14
bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
bb::TYPED_TEST_SUITE
TYPED_TEST_SUITE(CommitmentKeyTest, Curves)
bb::TYPED_TEST
TYPED_TEST(CommitmentKeyTest, CommitToZeroPoly)
Definition commitment_key.test.cpp:217
bb::Curves
::testing::Types< curve::BN254, curve::Grumpkin > Curves
Definition commitment_key.test.cpp:214
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
scalar_multiplication.hpp
Element
Curve::Element Element
Definition small_msm_matrix.bench.cpp:40
bb::field< Bn254FrParams >::cube_root_of_unity
static constexpr field cube_root_of_unity()
Definition field_declarations.hpp:255
bb::field< Bn254FrParams >::one
static constexpr field one()
Definition field_declarations.hpp:279
bb::field::to_montgomery_form
BB_INLINE constexpr field to_montgomery_form() const noexcept
Definition field_impl.hpp:287
bb::field< Bn254FrParams >::split_into_endomorphism_scalars
static void split_into_endomorphism_scalars(const field &k, field &k1, field &k2)
Full-width endomorphism decomposition: k ≡ k1 - k2·λ (mod r). Modifies the field elements k1 and k2.
Definition field_declarations.hpp:473
bb::field::self_neg
BB_INLINE constexpr void self_neg() &noexcept
Definition field_impl.hpp:199
bb::field< Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:802
bb::field< Bn254FrParams >::__copy
static BB_INLINE void __copy(const field &a, field &r) noexcept
Definition field_declarations.hpp:543
bb::field< Bn254FrParams >::zero
static constexpr field zero()
Definition field_declarations.hpp:277