Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
biggroup.test.cpp
Go to the documentation of this file.
1#include "../biggroup/biggroup.hpp"
2#include "../bigfield/bigfield.hpp"
3#include "../bool/bool.hpp"
4#include "../field/field.hpp"
5#include "barretenberg/circuit_checker/circuit_checker.hpp"
6#include "barretenberg/common/test.hpp"
7#include "barretenberg/numeric/random/engine.hpp"
8#include "barretenberg/stdlib/primitives/circuit_builders/circuit_builders.hpp"
9#include "barretenberg/stdlib/primitives/curves/bn254.hpp"
10#include "barretenberg/transcript/origin_tag.hpp"
11#include <vector>
12
13using namespace bb;
14
15namespace {
16auto& engine = numeric::get_debug_randomness();
17}
18
19template <typename T>
20concept HasGoblinBuilder = IsMegaBuilder<typename T::Curve::Builder>;
21
22// One can only define a TYPED_TEST with a single template paramter.
23// Our workaround is to pass parameters of the following type.
24template <typename _Curve, bool _use_bigfield = false> struct TestType {
25 public:
26 using Curve = _Curve;
27 static const bool use_bigfield = _use_bigfield;
28 using element_ct =
29 typename std::conditional<_use_bigfield, typename Curve::g1_bigfr_ct, typename Curve::Group>::type;
30 // the field of scalars acting on element_ct
31 using scalar_ct =
32 typename std::conditional<_use_bigfield, typename Curve::bigfr_ct, typename Curve::ScalarField>::type;
33};
34
35STANDARD_TESTING_TAGS
36template <typename TestType> class stdlib_biggroup : public testing::Test {
37 using Curve = typename TestType::Curve;
38 using element_ct = typename TestType::element_ct;
39 using scalar_ct = typename TestType::scalar_ct;
40
41 using fq = typename Curve::BaseFieldNative;
42 using fr = typename Curve::ScalarFieldNative;
43 using g1 = typename Curve::GroupNative;
44 using affine_element = typename g1::affine_element;
45 using element = typename g1::element;
46
47 using Builder = typename Curve::Builder;
48 using witness_ct = stdlib::witness_t<Builder>;
49 using bool_ct = stdlib::bool_t<Builder>;
50
51 static constexpr auto EXPECT_CIRCUIT_CORRECTNESS = [](Builder& builder, bool expected_result = true) {
52 info("num gates = ", builder.get_estimated_num_finalized_gates());
53 EXPECT_EQ(CircuitChecker::check(builder), expected_result);
54 };
55
56 public:
57 static void test_basic_tag_logic()
58 {
59 Builder builder;
60 affine_element input_a(element::random_element());
61
62 element_ct a = element_ct::from_witness(&builder, input_a);
63 a.set_origin_tag(next_submitted_value_origin_tag);
64 // Tag is preserved after being set
65 EXPECT_EQ(a.get_origin_tag(), next_submitted_value_origin_tag);
66
67 // Tags from members are merged
68 bool_ct pif = bool_ct(witness_ct(&builder, 0));
69 pif.set_origin_tag(next_challenge_tag);
70 a.x.set_origin_tag(submitted_value_origin_tag);
71 a.y.set_origin_tag(challenge_origin_tag);
72 a.set_point_at_infinity(pif);
73 EXPECT_EQ(a.get_origin_tag(), first_second_third_merged_tag);
74
75#ifndef NDEBUG
76 affine_element input_b(element::random_element());
77 // Working with instant death tagged element causes an exception
78 element_ct b = element_ct::from_witness(&builder, input_b);
79 b.set_origin_tag(instant_death_tag);
80
81 EXPECT_THROW(b + b, std::runtime_error);
82#endif
83 }
84 static void test_add()
85 {
86 Builder builder;
87 size_t num_repetitions = 10;
88 for (size_t i = 0; i < num_repetitions; ++i) {
89 affine_element input_a(element::random_element());
90 affine_element input_b(element::random_element());
91
92 element_ct a = element_ct::from_witness(&builder, input_a);
93 element_ct b = element_ct::from_witness(&builder, input_b);
94
95 // Set different tags in a and b
96 a.set_origin_tag(submitted_value_origin_tag);
97 b.set_origin_tag(challenge_origin_tag);
98
99 uint64_t before = builder.get_estimated_num_finalized_gates();
100 element_ct c = a + b;
101 uint64_t after = builder.get_estimated_num_finalized_gates();
102
103 // Check that the resulting tag is the union of inputs' tgs
104 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
105 if (i == num_repetitions - 1) {
106 std::cout << "num gates per add = " << after - before << std::endl;
107 benchmark_info(Builder::NAME_STRING, "Biggroup", "ADD", "Gate Count", after - before);
108 }
109
110 affine_element c_expected(element(input_a) + element(input_b));
111
112 uint256_t c_x_u256 = c.x.get_value().lo;
113 uint256_t c_y_u256 = c.y.get_value().lo;
114
115 fq c_x_result(c_x_u256);
116 fq c_y_result(c_y_u256);
117
118 EXPECT_EQ(c_x_result, c_expected.x);
119 EXPECT_EQ(c_y_result, c_expected.y);
120 }
121
122 EXPECT_CIRCUIT_CORRECTNESS(builder);
123 }
124
125 static void test_add_points_at_infinity()
126 {
127 Builder builder;
128 size_t num_repetitions = 1;
129 for (size_t i = 0; i < num_repetitions; ++i) {
130 affine_element input_a(element::random_element());
131 affine_element input_b(element::random_element());
132 input_b.self_set_infinity();
133 element_ct a = element_ct::from_witness(&builder, input_a);
134 // create copy of a with different witness
135 element_ct a_alternate = element_ct::from_witness(&builder, input_a);
136 element_ct a_negated = element_ct::from_witness(&builder, -input_a);
137 element_ct b = element_ct::from_witness(&builder, input_b);
138
139 // Set different tags on all elements
140 a.set_origin_tag(submitted_value_origin_tag);
141 b.set_origin_tag(challenge_origin_tag);
142 a_alternate.set_origin_tag(next_challenge_tag);
143 // We can't use next_submitted_value tag here or it will break, so construct a tag manually
144 const auto second_round_challenge_tag =
145 OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/false);
146 a_negated.set_origin_tag(second_round_challenge_tag);
147
148 element_ct c = a + b;
149 element_ct d = b + a;
150 element_ct e = b + b;
151 element_ct f = a + a;
152 element_ct g = a + a_alternate;
153 element_ct h = a + a_negated;
154
155 // Check the resulting tags are correct unions of input tags
156 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
157 EXPECT_EQ(d.get_origin_tag(), first_two_merged_tag);
158 EXPECT_EQ(e.get_origin_tag(), challenge_origin_tag);
159 EXPECT_EQ(f.get_origin_tag(), submitted_value_origin_tag);
160 EXPECT_EQ(g.get_origin_tag(), first_and_third_merged_tag);
161 EXPECT_EQ(h.get_origin_tag(), OriginTag(submitted_value_origin_tag, second_round_challenge_tag));
162
163 affine_element c_expected = affine_element(element(input_a) + element(input_b));
164 affine_element d_expected = affine_element(element(input_b) + element(input_a));
165 affine_element e_expected = affine_element(element(input_b) + element(input_b));
166 affine_element f_expected = affine_element(element(input_a) + element(input_a));
167 affine_element g_expected = affine_element(element(input_a) + element(input_a));
168 affine_element h_expected = affine_element(element(input_a) + element(-input_a));
169
170 EXPECT_EQ(c.get_value(), c_expected);
171 EXPECT_EQ(d.get_value(), d_expected);
172 EXPECT_EQ(e.get_value(), e_expected);
173 EXPECT_EQ(f.get_value(), f_expected);
174 EXPECT_EQ(g.get_value(), g_expected);
175 EXPECT_EQ(h.get_value(), h_expected);
176 }
177
178 EXPECT_CIRCUIT_CORRECTNESS(builder);
179 }
184 static void test_standard_form_of_point_at_infinity()
185 {
186 Builder builder;
187 size_t num_repetitions = 5;
188 for (size_t i = 0; i < num_repetitions; ++i) {
189 // Check both constant and witness case
190 element_ct input_a(element::random_element());
191 element_ct input_b = element_ct::from_witness(&builder, element::random_element());
192 input_a.set_point_at_infinity(true);
193 input_b.set_point_at_infinity(true);
194
195 // Set tags
196 input_a.set_origin_tag(submitted_value_origin_tag);
197 input_b.set_origin_tag(challenge_origin_tag);
198
199 auto standard_a = input_a.get_standard_form();
200 auto standard_b = input_b.get_standard_form();
201
202 // Check that tags are preserved
203
204 EXPECT_EQ(standard_a.get_origin_tag(), submitted_value_origin_tag);
205 EXPECT_EQ(standard_b.get_origin_tag(), challenge_origin_tag);
206
207 EXPECT_EQ(standard_a.is_point_at_infinity().get_value(), true);
208 EXPECT_EQ(standard_b.is_point_at_infinity().get_value(), true);
209
210 fq standard_a_x = standard_a.x.get_value().lo;
211 fq standard_a_y = standard_a.y.get_value().lo;
212
213 fq standard_b_x = standard_b.x.get_value().lo;
214 fq standard_b_y = standard_b.y.get_value().lo;
215
216 EXPECT_EQ(standard_a_x, 0);
217 EXPECT_EQ(standard_a_y, 0);
218 EXPECT_EQ(standard_b_x, 0);
219 EXPECT_EQ(standard_b_y, 0);
220 }
221
222 EXPECT_CIRCUIT_CORRECTNESS(builder);
223 }
224 static void test_sub()
225 {
226 Builder builder;
227 size_t num_repetitions = 10;
228 for (size_t i = 0; i < num_repetitions; ++i) {
229 affine_element input_a(element::random_element());
230 affine_element input_b(element::random_element());
231
232 element_ct a = element_ct::from_witness(&builder, input_a);
233 element_ct b = element_ct::from_witness(&builder, input_b);
234
235 // Set tags
236 a.set_origin_tag(submitted_value_origin_tag);
237 b.set_origin_tag(challenge_origin_tag);
238
239 element_ct c = a - b;
240
241 // Check tags have merged
242 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
243
244 affine_element c_expected(element(input_a) - element(input_b));
245
246 uint256_t c_x_u256 = c.x.get_value().lo;
247 uint256_t c_y_u256 = c.y.get_value().lo;
248
249 fq c_x_result(c_x_u256);
250 fq c_y_result(c_y_u256);
251
252 EXPECT_EQ(c_x_result, c_expected.x);
253 EXPECT_EQ(c_y_result, c_expected.y);
254 }
255
256 EXPECT_CIRCUIT_CORRECTNESS(builder);
257 }
258
259 static void test_sub_points_at_infinity()
260 {
261 Builder builder;
262 size_t num_repetitions = 1;
263 for (size_t i = 0; i < num_repetitions; ++i) {
264 affine_element input_a(element::random_element());
265 affine_element input_b(element::random_element());
266 input_b.self_set_infinity();
267 element_ct a = element_ct::from_witness(&builder, input_a);
268 // create copy of a with different witness
269 element_ct a_alternate = element_ct::from_witness(&builder, input_a);
270 element_ct a_negated = element_ct::from_witness(&builder, -input_a);
271 element_ct b = element_ct::from_witness(&builder, input_b);
272
273 // Set different tags on all elements
274 a.set_origin_tag(submitted_value_origin_tag);
275 b.set_origin_tag(challenge_origin_tag);
276 a_alternate.set_origin_tag(next_challenge_tag);
277 // We can't use next_submitted_value tag here or it will break, so construct a tag manually
278 const auto second_round_challenge_tag =
279 OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/false);
280 a_negated.set_origin_tag(second_round_challenge_tag);
281
282 element_ct c = a - b;
283 element_ct d = b - a;
284 element_ct e = b - b;
285 element_ct f = a - a;
286 element_ct g = a - a_alternate;
287 element_ct h = a - a_negated;
288
289 // Check the resulting tags are correct unions of input tags
290 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
291 EXPECT_EQ(d.get_origin_tag(), first_two_merged_tag);
292 EXPECT_EQ(e.get_origin_tag(), challenge_origin_tag);
293 EXPECT_EQ(f.get_origin_tag(), submitted_value_origin_tag);
294 EXPECT_EQ(g.get_origin_tag(), first_and_third_merged_tag);
295 EXPECT_EQ(h.get_origin_tag(), OriginTag(submitted_value_origin_tag, second_round_challenge_tag));
296
297 affine_element c_expected = affine_element(element(input_a) - element(input_b));
298 affine_element d_expected = affine_element(element(input_b) - element(input_a));
299 affine_element e_expected = affine_element(element(input_b) - element(input_b));
300 affine_element f_expected = affine_element(element(input_a) - element(input_a));
301 affine_element g_expected = affine_element(element(input_a) - element(input_a));
302 affine_element h_expected = affine_element(element(input_a) - element(-input_a));
303
304 EXPECT_EQ(c.get_value(), c_expected);
305 EXPECT_EQ(d.get_value(), d_expected);
306 EXPECT_EQ(e.get_value(), e_expected);
307 EXPECT_EQ(f.get_value(), f_expected);
308 EXPECT_EQ(g.get_value(), g_expected);
309 EXPECT_EQ(h.get_value(), h_expected);
310 }
311
312 EXPECT_CIRCUIT_CORRECTNESS(builder);
313 }
314
315 static void test_dbl()
316 {
317 Builder builder;
318 size_t num_repetitions = 10;
319 for (size_t i = 0; i < num_repetitions; ++i) {
320 affine_element input_a(element::random_element());
321
322 element_ct a = element_ct::from_witness(&builder, input_a);
323
324 a.set_origin_tag(submitted_value_origin_tag);
325
326 element_ct c = a.dbl();
327
328 // Check that the tag is preserved
329 EXPECT_EQ(c.get_origin_tag(), submitted_value_origin_tag);
330
331 affine_element c_expected(element(input_a).dbl());
332
333 uint256_t c_x_u256 = c.x.get_value().lo;
334 uint256_t c_y_u256 = c.y.get_value().lo;
335
336 fq c_x_result(c_x_u256);
337 fq c_y_result(c_y_u256);
338
339 EXPECT_EQ(c_x_result, c_expected.x);
340 EXPECT_EQ(c_y_result, c_expected.y);
341 }
342
343 EXPECT_CIRCUIT_CORRECTNESS(builder);
344 }
345
346 static void test_conditional_negate()
347 {
348 Builder builder;
349 size_t num_repetitions = 10;
350 for (size_t i = 0; i < num_repetitions; ++i) {
351 affine_element input_a(element::random_element());
352 element_ct a = element_ct::from_witness(&builder, input_a);
353 a.set_origin_tag(submitted_value_origin_tag);
354
355 // decide randomly whether to negate or not
356 bool negate = (engine.get_random_uint32() % 2) == 1;
357 bool_ct negate_ct = bool_ct(witness_ct(&builder, negate ? 1 : 0));
358 negate_ct.set_origin_tag(challenge_origin_tag);
359
360 element_ct c = a.conditional_negate(negate_ct);
361
362 // Check the resulting tag is preserved
363 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
364
365 affine_element c_expected = negate ? affine_element(-element(input_a)) : input_a;
366 EXPECT_EQ(c.get_value(), c_expected);
367 }
368
369 EXPECT_CIRCUIT_CORRECTNESS(builder);
370 }
371
372 static void test_conditional_select()
373 {
374 Builder builder;
375 size_t num_repetitions = 10;
376 for (size_t i = 0; i < num_repetitions; ++i) {
377 affine_element input_a(element::random_element());
378 affine_element input_b(element::random_element());
379 bool select_a = (engine.get_random_uint32() % 2) == 1;
380 bool_ct select_a_ct = bool_ct(witness_ct(&builder, select_a ? 1 : 0));
381 element_ct a = element_ct::from_witness(&builder, input_a);
382 element_ct b = element_ct::from_witness(&builder, input_b);
383
384 // Set different tags in a and b and the predicate
385 a.set_origin_tag(submitted_value_origin_tag);
386 b.set_origin_tag(challenge_origin_tag);
387 select_a_ct.set_origin_tag(next_challenge_tag);
388
389 element_ct c = a.conditional_select(b, select_a_ct);
390
391 // Check that the resulting tag is the union of inputs' tags
392 EXPECT_EQ(c.get_origin_tag(), first_second_third_merged_tag);
393
394 affine_element c_expected = select_a ? input_b : input_a;
395 EXPECT_EQ(c.get_value(), c_expected);
396 }
397
398 EXPECT_CIRCUIT_CORRECTNESS(builder);
399 }
400
401 static void test_incomplete_assert_equal_success()
402 {
403 // Case 1: Should pass because the points are identical
404 {
405 Builder builder;
406 size_t num_repetitions = 10;
407 for (size_t i = 0; i < num_repetitions; ++i) {
408 affine_element input_a(element::random_element());
409 element_ct a = element_ct::from_witness(&builder, input_a);
410 element_ct b = element_ct::from_witness(&builder, input_a);
411
412 // Set different tags in a and b
413 a.set_origin_tag(submitted_value_origin_tag);
414 b.set_origin_tag(challenge_origin_tag);
415
416 a.incomplete_assert_equal(b, "elements don't match");
417 }
418 EXPECT_CIRCUIT_CORRECTNESS(builder);
419 }
420 // Case 2: Should pass because the points are identical and at infinity
421 {
422 Builder builder;
423 size_t num_repetitions = 10;
424 for (size_t i = 0; i < num_repetitions; ++i) {
425 affine_element input_a(element::random_element());
426 element_ct a = element_ct::from_witness(&builder, input_a);
427 element_ct b = element_ct::from_witness(&builder, input_a);
428
429 // Set different tags in a and b
430 a.set_origin_tag(submitted_value_origin_tag);
431 b.set_origin_tag(challenge_origin_tag);
432
433 a.set_point_at_infinity(bool_ct(witness_ct(&builder, true)));
434 b.set_point_at_infinity(bool_ct(witness_ct(&builder, true)));
435
436 a.incomplete_assert_equal(b, "elements don't match");
437 }
438 EXPECT_CIRCUIT_CORRECTNESS(builder);
439 }
440 // Case 3: Self-assertion (point equals itself)
441 {
442 Builder builder;
443 affine_element input(element::random_element());
444 element_ct a = element_ct::from_witness(&builder, input);
445
446 a.incomplete_assert_equal(a, "self assertion test");
447
448 EXPECT_CIRCUIT_CORRECTNESS(builder);
449 }
450 }
451
452 static void test_incomplete_assert_equal_failure()
453 {
454 // Case 1: Should fail because the points are different
455 {
456 Builder builder;
457 affine_element input_a(element::random_element());
458 affine_element input_b(element::random_element());
459 // Ensure inputs are different
460 while (input_a == input_b) {
461 input_b = element::random_element();
462 }
463 element_ct a = element_ct::from_witness(&builder, input_a);
464 element_ct b = element_ct::from_witness(&builder, input_b);
465
466 // Set different tags in a and b
467 a.set_origin_tag(submitted_value_origin_tag);
468 b.set_origin_tag(challenge_origin_tag);
469
470 a.incomplete_assert_equal(b, "elements don't match");
471
472 // Circuit should fail (Circuit checker doesn't fail because it doesn't actually check copy constraints,
473 // it only checks gate constraints)
474 EXPECT_EQ(builder.failed(), true);
475 EXPECT_EQ(builder.err(), "elements don't match (x coordinate)");
476 }
477 // Case 2: Should fail because the points have same x but different y
478 {
479 Builder builder;
480 affine_element input_a(element::random_element());
481 affine_element input_b(element::random_element());
482 // Ensure inputs are different
483 while (input_a == input_b) {
484 input_b = element::random_element();
485 }
486 element_ct a = element_ct::from_witness(&builder, input_a);
487 element_ct b = element_ct::from_witness(&builder, input_b);
488
489 // Set different tags in a and b
490 a.set_origin_tag(submitted_value_origin_tag);
491 b.set_origin_tag(challenge_origin_tag);
492
493 // Make the x-coordinates equal, so we should get an error message about y-coordinates
494 b.x = a.x;
495 a.incomplete_assert_equal(b, "elements don't match");
496
497 // Circuit should fail
498 EXPECT_EQ(builder.failed(), true);
499 EXPECT_EQ(builder.err(), "elements don't match (y coordinate)");
500 }
501 // Case 3: Infinity flag mismatch (one point at infinity, one not)
502 {
503 Builder builder;
504 affine_element input_a(element::random_element());
505 affine_element input_b(element::random_element());
506
507 element_ct a = element_ct::from_witness(&builder, input_a);
508 element_ct b = element_ct::from_witness(&builder, input_b);
509
510 // Set only one point at infinity
511 a.set_point_at_infinity(bool_ct(witness_ct(&builder, true))); // at infinity
512 b.set_point_at_infinity(bool_ct(witness_ct(&builder, false))); // not at infinity
513
514 a.incomplete_assert_equal(b, "infinity flag mismatch test");
515
516 EXPECT_EQ(builder.failed(), true);
517 EXPECT_EQ(builder.err(), "infinity flag mismatch test (infinity flag)");
518 }
519 }
520
521 static void test_incomplete_assert_equal_edge_cases()
522 {
523 Builder builder;
524 // Check that two points at infinity with different x,y coords fail the equality check
525 affine_element input_a(element::random_element());
526 affine_element input_b(element::random_element());
527
528 // Ensure inputs are different
529 while (input_a == input_b) {
530 input_b = element::random_element();
531 }
532 element_ct a = element_ct::from_witness(&builder, input_a);
533 element_ct b = element_ct::from_witness(&builder, input_b);
534
535 const bool_ct is_infinity = bool_ct(witness_ct(&builder, 1));
536 a.set_point_at_infinity(is_infinity);
537 b.set_point_at_infinity(is_infinity);
538
539 // Set different tags in a and b
540 a.set_origin_tag(submitted_value_origin_tag);
541 b.set_origin_tag(challenge_origin_tag);
542
543 a.incomplete_assert_equal(b, "points at infinity with different x,y should not be equal");
544
545 // Circuit should fail
546 EXPECT_EQ(builder.failed(), true);
547 EXPECT_EQ(builder.err(), "points at infinity with different x,y should not be equal (x coordinate)");
548 }
549
550 static void test_montgomery_ladder()
551 {
552 Builder builder;
553 size_t num_repetitions = 1;
554 for (size_t i = 0; i < num_repetitions; ++i) {
555 affine_element input_a(element::random_element());
556 affine_element input_b(element::random_element());
557
558 element_ct a = element_ct::from_witness(&builder, input_a);
559 element_ct b = element_ct::from_witness(&builder, input_b);
560
561 // Set tags
562 a.set_origin_tag(submitted_value_origin_tag);
563 b.set_origin_tag(challenge_origin_tag);
564
565 element_ct c = a.montgomery_ladder(b);
566
567 // Check that the resulting tag is a union of tags
568 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
569
570 affine_element c_expected(element(input_a).dbl() + element(input_b));
571
572 uint256_t c_x_u256 = c.x.get_value().lo;
573 uint256_t c_y_u256 = c.y.get_value().lo;
574
575 fq c_x_result(c_x_u256);
576 fq c_y_result(c_y_u256);
577
578 EXPECT_EQ(c_x_result, c_expected.x);
579 EXPECT_EQ(c_y_result, c_expected.y);
580 }
581
582 EXPECT_CIRCUIT_CORRECTNESS(builder);
583 }
584
585 static void test_mul()
586 {
587 Builder builder;
588 size_t num_repetitions = 1;
589 for (size_t i = 0; i < num_repetitions; ++i) {
590 affine_element input(element::random_element());
591 fr scalar(fr::random_element());
592 if (uint256_t(scalar).get_bit(0)) {
593 scalar -= fr(1); // make sure to add skew
594 }
595 element_ct P = element_ct::from_witness(&builder, input);
596 scalar_ct x = scalar_ct::from_witness(&builder, scalar);
597
598 // Set input tags
599 x.set_origin_tag(challenge_origin_tag);
600 P.set_origin_tag(submitted_value_origin_tag);
601
602 std::cerr << "gates before mul " << builder.get_estimated_num_finalized_gates() << std::endl;
603 element_ct c = P * x;
604 std::cerr << "builder aftr mul " << builder.get_estimated_num_finalized_gates() << std::endl;
605 affine_element c_expected(element(input) * scalar);
606
607 // Check the result of the multiplication has a tag that's the union of inputs' tags
608 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
609 fq c_x_result(c.x.get_value().lo);
610 fq c_y_result(c.y.get_value().lo);
611
612 EXPECT_EQ(c_x_result, c_expected.x);
613 EXPECT_EQ(c_y_result, c_expected.y);
614 }
615
616 EXPECT_CIRCUIT_CORRECTNESS(builder);
617 }
618
619 // Test short scalar mul with variable even bit length. For efficiency, it's split into two tests.
620 static void test_short_scalar_mul_2_126()
621 {
622 Builder builder;
623 const size_t max_num_bits = 128;
624
625 // We only test even bit lengths, because `bn254_endo_batch_mul` used in 'scalar_mul' can't handle odd lengths.
626 for (size_t i = 2; i < max_num_bits; i += 2) {
627 affine_element input(element::random_element());
628 // Get a random 256 integer
629 uint256_t scalar_raw = engine.get_random_uint256();
630 // Produce a length =< i scalar.
631 scalar_raw = scalar_raw >> (256 - i);
632 fr scalar = fr(scalar_raw);
633
634 // Avoid multiplication by 0 that may occur when `i` is small
635 if (scalar == fr(0)) {
636 scalar += 1;
637 };
638
639 element_ct P = element_ct::from_witness(&builder, input);
640 scalar_ct x = scalar_ct::from_witness(&builder, scalar);
641
642 // Set input tags
643 x.set_origin_tag(challenge_origin_tag);
644 P.set_origin_tag(submitted_value_origin_tag);
645
646 std::cerr << "gates before mul " << builder.get_estimated_num_finalized_gates() << std::endl;
647 // Multiply using specified scalar length
648 element_ct c = P.scalar_mul(x, i);
649 std::cerr << "builder aftr mul " << builder.get_estimated_num_finalized_gates() << std::endl;
650 affine_element c_expected(element(input) * scalar);
651
652 // Check the result of the multiplication has a tag that's the union of inputs' tags
653 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
654 fq c_x_result(c.x.get_value().lo);
655 fq c_y_result(c.y.get_value().lo);
656
657 EXPECT_EQ(c_x_result, c_expected.x);
658
659 EXPECT_EQ(c_y_result, c_expected.y);
660 }
661
662 EXPECT_CIRCUIT_CORRECTNESS(builder);
663 }
664
665 static void test_short_scalar_mul_128_252()
666 {
667 Builder builder;
668 const size_t max_num_bits = 254;
669
670 // We only test even bit lengths, because `bn254_endo_batch_mul` used in 'scalar_mul' can't handle odd lengths.
671 for (size_t i = 128; i < max_num_bits; i += 2) {
672 affine_element input(element::random_element());
673 // Get a random 256-bit integer
674 uint256_t scalar_raw = engine.get_random_uint256();
675 // Produce a length =< i scalar.
676 scalar_raw = scalar_raw >> (256 - i);
677 fr scalar = fr(scalar_raw);
678
679 element_ct P = element_ct::from_witness(&builder, input);
680 scalar_ct x = scalar_ct::from_witness(&builder, scalar);
681
682 // Set input tags
683 x.set_origin_tag(challenge_origin_tag);
684 P.set_origin_tag(submitted_value_origin_tag);
685
686 std::cerr << "gates before mul " << builder.get_estimated_num_finalized_gates() << std::endl;
687 // Multiply using specified scalar length
688 element_ct c = P.scalar_mul(x, i);
689 std::cerr << "builder aftr mul " << builder.get_estimated_num_finalized_gates() << std::endl;
690 affine_element c_expected(element(input) * scalar);
691
692 // Check the result of the multiplication has a tag that's the union of inputs' tags
693 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
694 fq c_x_result(c.x.get_value().lo);
695 fq c_y_result(c.y.get_value().lo);
696
697 EXPECT_EQ(c_x_result, c_expected.x);
698
699 EXPECT_EQ(c_y_result, c_expected.y);
700 }
701
702 EXPECT_CIRCUIT_CORRECTNESS(builder);
703 }
704
705 static void test_short_scalar_mul_infinity()
706 {
707 // We check that a point at infinity preserves `is_point_at_infinity()` flag after being multiplied against a
708 // short scalar and also check that the number of gates in this case is equal to the number of gates spent on a
709 // finite point.
710
711 // Populate test points.
712 std::vector<element> points(2);
713
714 points[0] = element::infinity();
715 points[1] = element::random_element();
716 // Containter for gate counts.
717 std::vector<size_t> gates(2);
718
719 // We initialize this flag as `true`, because the first result is expected to be the point at infinity.
720 bool expect_infinity = true;
721
722 for (auto [point, num_gates] : zip_view(points, gates)) {
723 Builder builder;
724
725 const size_t max_num_bits = 128;
726 // Get a random 256-bit integer
727 uint256_t scalar_raw = engine.get_random_uint256();
728 // Produce a length =< max_num_bits scalar.
729 scalar_raw = scalar_raw >> (256 - max_num_bits);
730 fr scalar = fr(scalar_raw);
731
732 element_ct P = element_ct::from_witness(&builder, point);
733 scalar_ct x = scalar_ct::from_witness(&builder, scalar);
734
735 // Set input tags
736 x.set_origin_tag(challenge_origin_tag);
737 P.set_origin_tag(submitted_value_origin_tag);
738
739 std::cerr << "gates before mul " << builder.get_estimated_num_finalized_gates() << std::endl;
740 element_ct c = P.scalar_mul(x, max_num_bits);
741 std::cerr << "builder aftr mul " << builder.get_estimated_num_finalized_gates() << std::endl;
742 num_gates = builder.get_estimated_num_finalized_gates();
743 // Check the result of the multiplication has a tag that's the union of inputs' tags
744 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
745
746 EXPECT_EQ(c.is_point_at_infinity().get_value(), expect_infinity);
747 EXPECT_CIRCUIT_CORRECTNESS(builder);
748 // The second point is finite, hence we flip the flag
749 expect_infinity = false;
750 }
751 // Check that the numbers of gates are equal in both cases.
752 EXPECT_EQ(gates[0], gates[1]);
753 }
754
755 static void test_twin_mul()
756 {
757 Builder builder;
758 size_t num_repetitions = 1;
759 for (size_t i = 0; i < num_repetitions; ++i) {
760 affine_element input_a(element::random_element());
761 affine_element input_b(element::random_element());
762 fr scalar_a(fr::random_element());
763 fr scalar_b(fr::random_element());
764 if ((uint256_t(scalar_a).get_bit(0) & 1) == 1) {
765 scalar_a -= fr(1); // skew bit is 1
766 }
767 if ((uint256_t(scalar_b).get_bit(0) & 1) == 0) {
768 scalar_b += fr(1); // skew bit is 0
769 }
770 element_ct P_a = element_ct::from_witness(&builder, input_a);
771 scalar_ct x_a = scalar_ct::from_witness(&builder, scalar_a);
772 element_ct P_b = element_ct::from_witness(&builder, input_b);
773 scalar_ct x_b = scalar_ct::from_witness(&builder, scalar_b);
774
775 // Set tags
776 P_a.set_origin_tag(submitted_value_origin_tag);
777 x_a.set_origin_tag(challenge_origin_tag);
778 P_b.set_origin_tag(next_submitted_value_origin_tag);
779 x_b.set_origin_tag(next_challenge_tag);
780
781 element_ct c = element_ct::batch_mul({ P_a, P_b }, { x_a, x_b });
782
783 // Check that the resulting tag is a union of all tags
784 EXPECT_EQ(c.get_origin_tag(), first_to_fourth_merged_tag);
785 element input_c = (element(input_a) * scalar_a);
786 element input_d = (element(input_b) * scalar_b);
787 affine_element expected(input_c + input_d);
788 fq c_x_result(c.x.get_value().lo);
789 fq c_y_result(c.y.get_value().lo);
790
791 EXPECT_EQ(c_x_result, expected.x);
792 EXPECT_EQ(c_y_result, expected.y);
793 }
794 EXPECT_CIRCUIT_CORRECTNESS(builder);
795 }
796
797 static void test_triple_mul()
798 {
799 Builder builder;
800 size_t num_repetitions = 1;
801 for (size_t i = 0; i < num_repetitions; ++i) {
802 affine_element input_a(element::random_element());
803 affine_element input_b(element::random_element());
804 affine_element input_c(element::random_element());
805 fr scalar_a(fr::random_element());
806 fr scalar_b(fr::random_element());
807 fr scalar_c(fr::random_element());
808 if ((uint256_t(scalar_a).get_bit(0) & 1) == 1) {
809 scalar_a -= fr(1); // skew bit is 1
810 }
811 if ((uint256_t(scalar_b).get_bit(0) & 1) == 0) {
812 scalar_b += fr(1); // skew bit is 0
813 }
814 OriginTag tag_union{};
815
816 element_ct P_a = element_ct::from_witness(&builder, input_a);
817 // Set all element tags to submitted tags from sequential rounds
818 P_a.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/0, /*is_submitted=*/true));
819 tag_union = OriginTag(tag_union, P_a.get_origin_tag());
820
821 scalar_ct x_a = scalar_ct::from_witness(&builder, scalar_a);
822 // Set all scalar tags to challenge tags from sequential rounds
823 x_a.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/0, /*is_submitted=*/false));
824 tag_union = OriginTag(tag_union, x_a.get_origin_tag());
825
826 element_ct P_b = element_ct::from_witness(&builder, input_b);
827 P_b.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/1, /*is_submitted=*/true));
828 tag_union = OriginTag(tag_union, P_b.get_origin_tag());
829
830 scalar_ct x_b = scalar_ct::from_witness(&builder, scalar_b);
831 x_b.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/1, /*is_submitted=*/false));
832 tag_union = OriginTag(tag_union, x_b.get_origin_tag());
833
834 element_ct P_c = element_ct::from_witness(&builder, input_c);
835 P_c.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/true));
836 tag_union = OriginTag(tag_union, P_c.get_origin_tag());
837
838 scalar_ct x_c = scalar_ct::from_witness(&builder, scalar_c);
839 x_c.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/false));
840 tag_union = OriginTag(tag_union, x_c.get_origin_tag());
841
842 element_ct c = element_ct::batch_mul({ P_a, P_b, P_c }, { x_a, x_b, x_c });
843 // Check that the result tag is a union of inputs' tags
844 EXPECT_EQ(c.get_origin_tag(), tag_union);
845 element input_e = (element(input_a) * scalar_a);
846 element input_f = (element(input_b) * scalar_b);
847 element input_g = (element(input_c) * scalar_c);
848
849 affine_element expected(input_e + input_f + input_g);
850 fq c_x_result(c.x.get_value().lo);
851 fq c_y_result(c.y.get_value().lo);
852
853 EXPECT_EQ(c_x_result, expected.x);
854 EXPECT_EQ(c_y_result, expected.y);
855 }
856
857 EXPECT_CIRCUIT_CORRECTNESS(builder);
858 }
859
860 static void test_quad_mul()
861 {
862 Builder builder;
863 size_t num_repetitions = 1;
864 for (size_t i = 0; i < num_repetitions; ++i) {
865 affine_element input_a(element::random_element());
866 affine_element input_b(element::random_element());
867 affine_element input_c(element::random_element());
868 affine_element input_d(element::random_element());
869 fr scalar_a(fr::random_element());
870 fr scalar_b(fr::random_element());
871 fr scalar_c(fr::random_element());
872 fr scalar_d(fr::random_element());
873 if ((uint256_t(scalar_a).get_bit(0) & 1) == 1) {
874 scalar_a -= fr(1); // skew bit is 1
875 }
876 if ((uint256_t(scalar_b).get_bit(0) & 1) == 0) {
877 scalar_b += fr(1); // skew bit is 0
878 }
879 OriginTag tag_union{};
880
881 element_ct P_a = element_ct::from_witness(&builder, input_a);
882
883 // Set element tags to sequential submitted tags
884 P_a.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/0, /*is_submitted=*/true));
885 tag_union = OriginTag(tag_union, P_a.get_origin_tag());
886
887 // Set element tags to sequential challenge tags
888 scalar_ct x_a = scalar_ct::from_witness(&builder, scalar_a);
889 x_a.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/0, /*is_submitted=*/false));
890 tag_union = OriginTag(tag_union, x_a.get_origin_tag());
891
892 element_ct P_b = element_ct::from_witness(&builder, input_b);
893 P_b.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/1, /*is_submitted=*/true));
894 tag_union = OriginTag(tag_union, P_b.get_origin_tag());
895
896 scalar_ct x_b = scalar_ct::from_witness(&builder, scalar_b);
897 x_b.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/1, /*is_submitted=*/false));
898 tag_union = OriginTag(tag_union, x_b.get_origin_tag());
899
900 element_ct P_c = element_ct::from_witness(&builder, input_c);
901 P_c.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/true));
902 tag_union = OriginTag(tag_union, P_c.get_origin_tag());
903
904 scalar_ct x_c = scalar_ct::from_witness(&builder, scalar_c);
905 x_c.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/false));
906 tag_union = OriginTag(tag_union, x_c.get_origin_tag());
907
908 element_ct P_d = element_ct::from_witness(&builder, input_d);
909 P_d.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/3, /*is_submitted=*/true));
910 tag_union = OriginTag(tag_union, P_d.get_origin_tag());
911
912 scalar_ct x_d = scalar_ct::from_witness(&builder, scalar_d);
913 x_d.set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/3, /*is_submitted=*/false));
914 tag_union = OriginTag(tag_union, x_d.get_origin_tag());
915
916 element_ct c = element_ct::batch_mul({ P_a, P_b, P_c, P_d }, { x_a, x_b, x_c, x_d });
917
918 // Check that the tag of the batched product is the union of inputs' tags
919 EXPECT_EQ(c.get_origin_tag(), tag_union);
920 element input_e = (element(input_a) * scalar_a);
921 element input_f = (element(input_b) * scalar_b);
922 element input_g = (element(input_c) * scalar_c);
923 element input_h = (element(input_d) * scalar_d);
924
925 affine_element expected(input_e + input_f + input_g + input_h);
926 fq c_x_result(c.x.get_value().lo);
927 fq c_y_result(c.y.get_value().lo);
928
929 EXPECT_EQ(c_x_result, expected.x);
930 EXPECT_EQ(c_y_result, expected.y);
931 }
932
933 EXPECT_CIRCUIT_CORRECTNESS(builder);
934 }
935
936 static void test_one()
937 {
938 Builder builder;
939 size_t num_repetitions = 1;
940 for (size_t i = 0; i < num_repetitions; ++i) {
941 fr scalar_a(fr::random_element());
942 if ((uint256_t(scalar_a).get_bit(0) & 1) == 1) {
943 scalar_a -= fr(1); // skew bit is 1
944 }
945 element_ct P_a = element_ct::one(&builder);
946
947 // Set origin tag for element to submitted value in round 0
948 P_a.set_origin_tag(submitted_value_origin_tag);
949 scalar_ct x_a = scalar_ct::from_witness(&builder, scalar_a);
950
951 // Set origin tag for scalar to challenge in round 0
952 x_a.set_origin_tag(challenge_origin_tag);
953 element_ct c = P_a * x_a;
954
955 // Check that the resulting tag is a union
956 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
957 affine_element expected(g1::one * scalar_a);
958 fq c_x_result(c.x.get_value().lo);
959 fq c_y_result(c.y.get_value().lo);
960
961 EXPECT_EQ(c_x_result, expected.x);
962 EXPECT_EQ(c_y_result, expected.y);
963 }
964
965 EXPECT_CIRCUIT_CORRECTNESS(builder);
966 }
967
968 static void test_batch_mul()
969 {
970 // TODO(https://github.com/AztecProtocol/barretenberg/issues/1043): this test will fail with num_points is 1
971 // (and this case gets hit sometimes when handling points at infinity).
972 const size_t num_points = 5;
973 Builder builder;
974 std::vector<affine_element> points;
975 std::vector<fr> scalars;
976 for (size_t i = 0; i < num_points; ++i) {
977 points.push_back(affine_element(element::random_element()));
978 scalars.push_back(fr::random_element());
979 }
980
981 std::vector<element_ct> circuit_points;
982 std::vector<scalar_ct> circuit_scalars;
983 OriginTag tag_union{};
984 for (size_t i = 0; i < num_points; ++i) {
985 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
986
987 // Set tag to submitted value tag at round i
988 circuit_points[i].set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
989 tag_union = OriginTag(tag_union, circuit_points[i].get_origin_tag());
990 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
991
992 // Set tag to challenge tag at round i
993 circuit_scalars[i].set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
994 tag_union = OriginTag(tag_union, circuit_scalars[i].get_origin_tag());
995 }
996
997 element_ct result_point = element_ct::batch_mul(circuit_points, circuit_scalars);
998
999 // Check the resulting tag is a union of inputs' tags
1000 EXPECT_EQ(result_point.get_origin_tag(), tag_union);
1001
1002 element expected_point = g1::one;
1003 expected_point.self_set_infinity();
1004 for (size_t i = 0; i < num_points; ++i) {
1005 expected_point += (element(points[i]) * scalars[i]);
1006 }
1007
1008 expected_point = expected_point.normalize();
1009 fq result_x(result_point.x.get_value().lo);
1010 fq result_y(result_point.y.get_value().lo);
1011
1012 EXPECT_EQ(result_x, expected_point.x);
1013 EXPECT_EQ(result_y, expected_point.y);
1014
1015 EXPECT_CIRCUIT_CORRECTNESS(builder);
1016 }
1017
1018 static void test_batch_mul_edgecase_equivalence()
1019 {
1020 const size_t num_points = 5;
1021 Builder builder;
1022 std::vector<affine_element> points;
1023 std::vector<fr> scalars;
1024 for (size_t i = 0; i < num_points; ++i) {
1025 points.push_back(affine_element(element::random_element()));
1026 scalars.push_back(fr::random_element());
1027 }
1028
1029 std::vector<element_ct> circuit_points;
1030 std::vector<scalar_ct> circuit_scalars;
1031
1032 OriginTag tag_union{};
1033 for (size_t i = 0; i < num_points; ++i) {
1034 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1035
1036 // Set tag to submitted value tag at round i
1037 circuit_points[i].set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1038 tag_union = OriginTag(tag_union, circuit_points[i].get_origin_tag());
1039 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1040
1041 // Set tag to challenge tag at round i
1042 circuit_scalars[i].set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1043 tag_union = OriginTag(tag_union, circuit_scalars[i].get_origin_tag());
1044 }
1045
1046 element_ct result_point2 =
1047 element_ct::batch_mul(circuit_points, circuit_scalars, /*max_num_bits=*/0, /*with_edgecases=*/true);
1048
1049 // Check that the result tag is a union of inputs' tags
1050 EXPECT_EQ(result_point2.get_origin_tag(), tag_union);
1051 element expected_point = g1::one;
1052 expected_point.self_set_infinity();
1053 for (size_t i = 0; i < num_points; ++i) {
1054 expected_point += (element(points[i]) * scalars[i]);
1055 }
1056
1057 expected_point = expected_point.normalize();
1058
1059 fq result2_x(result_point2.x.get_value().lo);
1060 fq result2_y(result_point2.y.get_value().lo);
1061
1062 EXPECT_EQ(result2_x, expected_point.x);
1063 EXPECT_EQ(result2_y, expected_point.y);
1064
1065 EXPECT_CIRCUIT_CORRECTNESS(builder);
1066 }
1067
1068 static void test_batch_mul_edge_case_set1()
1069 {
1070 const auto test_repeated_points = [](const uint32_t num_points) {
1071 // batch P + ... + P = m*P
1072 info("num points: ", num_points);
1073 std::vector<affine_element> points;
1074 std::vector<fr> scalars;
1075 for (size_t idx = 0; idx < num_points; idx++) {
1076 points.push_back(affine_element::one());
1077 scalars.push_back(1);
1078 }
1079
1080 Builder builder;
1081 ASSERT_EQ(points.size(), scalars.size());
1082
1083 std::vector<element_ct> circuit_points;
1084 std::vector<scalar_ct> circuit_scalars;
1085
1086 OriginTag tag_union{};
1087 for (size_t i = 0; i < num_points; ++i) {
1088 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1089
1090 // Set tag to submitted value tag at round i
1091 circuit_points[i].set_origin_tag(
1092 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1093 tag_union = OriginTag(tag_union, circuit_points[i].get_origin_tag());
1094 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1095
1096 // Set tag to challenge tag at round i
1097 circuit_scalars[i].set_origin_tag(
1098 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1099 tag_union = OriginTag(tag_union, circuit_scalars[i].get_origin_tag());
1100 }
1101 element_ct result_point =
1102 element_ct::batch_mul(circuit_points, circuit_scalars, /*max_num_bits=*/0, /*with_edgecases=*/true);
1103
1104 // Check that the result tag is a union of inputs' tags
1105 EXPECT_EQ(result_point.get_origin_tag(), tag_union);
1106
1107 auto expected_point = element::infinity();
1108 for (const auto& point : points) {
1109 expected_point += point;
1110 }
1111 expected_point = expected_point.normalize();
1112
1113 fq result_x(result_point.x.get_value().lo);
1114 fq result_y(result_point.y.get_value().lo);
1115
1116 EXPECT_EQ(result_x, expected_point.x);
1117 EXPECT_EQ(result_y, expected_point.y);
1118
1119 EXPECT_CIRCUIT_CORRECTNESS(builder);
1120 };
1121 test_repeated_points(2);
1122 test_repeated_points(3);
1123 test_repeated_points(4);
1124 test_repeated_points(5);
1125 test_repeated_points(6);
1126 test_repeated_points(7);
1127 }
1128 static void test_batch_mul_edge_case_set2()
1129 {
1130 {
1131 // batch oo + P = P
1132 std::vector<affine_element> points;
1133 points.push_back(affine_element::infinity());
1134 points.push_back(affine_element(element::random_element()));
1135 std::vector<fr> scalars;
1136 scalars.push_back(1);
1137 scalars.push_back(1);
1138
1139 Builder builder;
1140 ASSERT_EQ(points.size(), scalars.size());
1141 const size_t num_points = points.size();
1142
1143 std::vector<element_ct> circuit_points;
1144 std::vector<scalar_ct> circuit_scalars;
1145
1146 OriginTag tag_union{};
1147 for (size_t i = 0; i < num_points; ++i) {
1148 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1149
1150 // Set tag to submitted value tag at round i
1151 circuit_points[i].set_origin_tag(
1152 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1153 tag_union = OriginTag(tag_union, circuit_points[i].get_origin_tag());
1154 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1155
1156 // Set tag to challenge tag at round i
1157 circuit_scalars[i].set_origin_tag(
1158 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1159 tag_union = OriginTag(tag_union, circuit_scalars[i].get_origin_tag());
1160 }
1161
1162 element_ct result_point =
1163 element_ct::batch_mul(circuit_points, circuit_scalars, /*max_num_bits=*/0, /*with_edgecases=*/true);
1164
1165 // Check that the result tag is a union of inputs' tags
1166 EXPECT_EQ(result_point.get_origin_tag(), tag_union);
1167
1168 element expected_point = points[1];
1169 expected_point = expected_point.normalize();
1170
1171 fq result_x(result_point.x.get_value().lo);
1172 fq result_y(result_point.y.get_value().lo);
1173
1174 EXPECT_EQ(result_x, expected_point.x);
1175 EXPECT_EQ(result_y, expected_point.y);
1176
1177 EXPECT_CIRCUIT_CORRECTNESS(builder);
1178 }
1179 {
1180 // batch 0 * P1 + P2 = P2
1181 std::vector<affine_element> points;
1182 points.push_back(affine_element(element::random_element()));
1183 points.push_back(affine_element(element::random_element()));
1184 std::vector<fr> scalars;
1185 scalars.push_back(0);
1186 scalars.push_back(1);
1187
1188 Builder builder;
1189 ASSERT_EQ(points.size(), scalars.size());
1190 const size_t num_points = points.size();
1191
1192 std::vector<element_ct> circuit_points;
1193 std::vector<scalar_ct> circuit_scalars;
1194 OriginTag tag_union{};
1195 for (size_t i = 0; i < num_points; ++i) {
1196 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1197
1198 // Set tag to submitted value tag at round i
1199 circuit_points[i].set_origin_tag(
1200 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1201 tag_union = OriginTag(tag_union, circuit_points[i].get_origin_tag());
1202 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1203
1204 // Set tag to challenge tag at round i
1205 circuit_scalars[i].set_origin_tag(
1206 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1207 tag_union = OriginTag(tag_union, circuit_scalars[i].get_origin_tag());
1208 }
1209
1210 element_ct result_point =
1211 element_ct::batch_mul(circuit_points, circuit_scalars, /*max_num_bits=*/0, /*with_edgecases=*/true);
1212
1213 // Check that the result tag is a union of inputs' tags
1214 EXPECT_EQ(result_point.get_origin_tag(), tag_union);
1215
1216 element expected_point = points[1];
1217 expected_point = expected_point.normalize();
1218
1219 fq result_x(result_point.x.get_value().lo);
1220 fq result_y(result_point.y.get_value().lo);
1221
1222 EXPECT_EQ(result_x, expected_point.x);
1223 EXPECT_EQ(result_y, expected_point.y);
1224
1225 EXPECT_CIRCUIT_CORRECTNESS(builder);
1226 }
1227 }
1228
1229 static void test_chain_add()
1230 {
1231 Builder builder = Builder();
1232 size_t num_repetitions = 10;
1233 for (size_t i = 0; i < num_repetitions; ++i) {
1234 affine_element input_a(element::random_element());
1235 affine_element input_b(element::random_element());
1236 affine_element input_c(element::random_element());
1237
1238 element_ct a = element_ct::from_witness(&builder, input_a);
1239 element_ct b = element_ct::from_witness(&builder, input_b);
1240 element_ct c = element_ct::from_witness(&builder, input_c);
1241
1242 auto acc = element_ct::chain_add_start(a, b);
1243 auto acc_out = element_ct::chain_add(c, acc);
1244
1245 auto lambda_prev = (input_b.y - input_a.y) / (input_b.x - input_a.x);
1246 auto x3_prev = lambda_prev * lambda_prev - input_b.x - input_a.x;
1247 auto y3_prev = lambda_prev * (input_a.x - x3_prev) - input_a.y;
1248 auto lambda = (y3_prev - input_c.y) / (x3_prev - input_c.x);
1249 auto x3 = lambda * lambda - x3_prev - input_c.x;
1250
1251 uint256_t x3_u256 = acc_out.x3_prev.get_value().lo;
1252 uint256_t lambda_u256 = acc_out.lambda_prev.get_value().lo;
1253
1254 fq x3_result(x3_u256);
1255 fq lambda_result(lambda_u256);
1256
1257 EXPECT_EQ(x3_result, x3);
1258 EXPECT_EQ(lambda_result, lambda);
1259 }
1260
1261 EXPECT_CIRCUIT_CORRECTNESS(builder);
1262 }
1263
1264 static void test_multiple_montgomery_ladder()
1265 {
1266 Builder builder = Builder();
1267 size_t num_repetitions = 10;
1268 for (size_t i = 0; i < num_repetitions; ++i) {
1269 affine_element acc_small(element::random_element());
1270 element_ct acc_big = element_ct::from_witness(&builder, acc_small);
1271
1272 std::vector<typename element_ct::chain_add_accumulator> to_add;
1273 for (size_t j = 0; j < i; ++j) {
1274 affine_element add_1_small_0(element::random_element());
1275 element_ct add_1_big_0 = element_ct::from_witness(&builder, add_1_small_0);
1276 affine_element add_2_small_0(element::random_element());
1277 element_ct add_2_big_0 = element_ct::from_witness(&builder, add_2_small_0);
1278 typename element_ct::chain_add_accumulator add_1 =
1279 element_ct::chain_add_start(add_1_big_0, add_2_big_0);
1280 to_add.emplace_back(add_1);
1281 }
1282 acc_big.multiple_montgomery_ladder(to_add);
1283 }
1284
1285 EXPECT_CIRCUIT_CORRECTNESS(builder);
1286 }
1287
1288 static void test_compute_naf()
1289 {
1290 Builder builder = Builder();
1291 size_t max_num_bits = 254;
1292 // Our design of NAF and the way it is used assumes the even length of scalars.
1293 for (size_t length = 2; length < max_num_bits; length += 2) {
1294
1295 fr scalar_val;
1296
1297 uint256_t scalar_raw = engine.get_random_uint256();
1298 scalar_raw = scalar_raw >> (256 - length);
1299
1300 scalar_val = fr(scalar_raw);
1301
1302 // NAF with short scalars doesn't handle 0
1303 if (scalar_val == fr(0)) {
1304 scalar_val += 1;
1305 };
1306 scalar_ct scalar = scalar_ct::from_witness(&builder, scalar_val);
1307 // Set tag for scalar
1308 scalar.set_origin_tag(submitted_value_origin_tag);
1309 auto naf = element_ct::compute_naf(scalar, length);
1310
1311 for (const auto& bit : naf) {
1312 // Check that the tag is propagated to bits
1313 EXPECT_EQ(bit.get_origin_tag(), submitted_value_origin_tag);
1314 }
1315 // scalar = -naf[254] + \sum_{i=0}^{253}(1-2*naf[i]) 2^{253-i}
1316 fr reconstructed_val(0);
1317 for (size_t i = 0; i < length; i++) {
1318 reconstructed_val += (fr(1) - fr(2) * fr(naf[i].get_value())) * fr(uint256_t(1) << (length - 1 - i));
1319 };
1320 reconstructed_val -= fr(naf[length].get_value());
1321 EXPECT_EQ(scalar_val, reconstructed_val);
1322 }
1323
1324 EXPECT_CIRCUIT_CORRECTNESS(builder);
1325 }
1326
1327 static void test_compute_wnaf()
1328 {
1329 Builder builder = Builder();
1330
1331 fr scalar_val = fr::random_element();
1332 scalar_ct scalar = scalar_ct::from_witness(&builder, scalar_val);
1333 // Assign origin tag to scalar
1334 scalar.set_origin_tag(submitted_value_origin_tag);
1335
1336 const auto result = element_ct::compute_wnaf(scalar);
1337 // Check that wnaf entries propagate tag
1338 for (const auto& wnaf_entry : result) {
1339 EXPECT_EQ(wnaf_entry.get_origin_tag(), submitted_value_origin_tag);
1340 }
1341
1342 EXPECT_CIRCUIT_CORRECTNESS(builder);
1343 }
1344
1345 static void test_wnaf_batch_mul()
1346 {
1347 Builder builder;
1348 size_t num_repetitions = 1;
1349 for (size_t i = 0; i < num_repetitions; ++i) {
1350 affine_element input(element::random_element());
1351 fr scalar(fr::random_element());
1352 if ((uint256_t(scalar).get_bit(0) & 1) == 1) {
1353 scalar -= fr(1); // make sure to add skew
1354 }
1355 element_ct P = element_ct::from_witness(&builder, input);
1356 scalar_ct x = scalar_ct::from_witness(&builder, scalar);
1357
1358 // Set 2 different origin tags
1359 P.set_origin_tag(submitted_value_origin_tag);
1360 x.set_origin_tag(challenge_origin_tag);
1361
1362 std::cerr << "gates before mul " << builder.get_estimated_num_finalized_gates() << std::endl;
1363 element_ct c = element_ct::wnaf_batch_mul({ P }, { x });
1364
1365 // Check that the final tag is a union of inputs' tags
1366 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
1367 std::cerr << "builder aftr mul " << builder.get_estimated_num_finalized_gates() << std::endl;
1368 affine_element c_expected(element(input) * scalar);
1369
1370 fq c_x_result(c.x.get_value().lo);
1371 fq c_y_result(c.y.get_value().lo);
1372
1373 EXPECT_EQ(c_x_result, c_expected.x);
1374 EXPECT_EQ(c_y_result, c_expected.y);
1375 }
1376
1377 EXPECT_CIRCUIT_CORRECTNESS(builder);
1378 }
1379
1380 static void test_wnaf_batch_mul_edge_cases()
1381 {
1382 {
1383 // batch P + P = 2P
1384 std::vector<affine_element> points;
1385 points.push_back(affine_element::one());
1386 points.push_back(affine_element::one());
1387 std::vector<fr> scalars;
1388 scalars.push_back(1);
1389 scalars.push_back(1);
1390
1391 Builder builder;
1392 ASSERT_EQ(points.size(), scalars.size());
1393 const size_t num_points = points.size();
1394
1395 std::vector<element_ct> circuit_points;
1396 std::vector<scalar_ct> circuit_scalars;
1397 OriginTag union_tag{};
1398 for (size_t i = 0; i < num_points; ++i) {
1399 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1400 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1401 // Set tags for points to the submitted value tag for round i and for scalars to challenge tag for the
1402 // same round
1403 circuit_points[i].set_origin_tag(
1404 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1405 circuit_scalars[i].set_origin_tag(
1406 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1407 union_tag =
1408 OriginTag(union_tag, circuit_points[i].get_origin_tag(), circuit_scalars[i].get_origin_tag());
1409 }
1410
1411 element_ct result_point = element_ct::wnaf_batch_mul(circuit_points, circuit_scalars);
1412
1413 // Check that the results' tag is a union of inputs' tags
1414 EXPECT_EQ(result_point.get_origin_tag(), union_tag);
1415
1416 element expected_point = points[0] + points[1];
1417 expected_point = expected_point.normalize();
1418
1419 fq result_x(result_point.x.get_value().lo);
1420 fq result_y(result_point.y.get_value().lo);
1421
1422 EXPECT_EQ(result_x, expected_point.x);
1423 EXPECT_EQ(result_y, expected_point.y);
1424
1425 EXPECT_CIRCUIT_CORRECTNESS(builder);
1426 }
1427 {
1428 // batch oo + P = P
1429 std::vector<affine_element> points;
1430 points.push_back(affine_element::infinity());
1431 points.push_back(affine_element(element::random_element()));
1432 std::vector<fr> scalars;
1433 scalars.push_back(1);
1434 scalars.push_back(1);
1435
1436 Builder builder;
1437 ASSERT_EQ(points.size(), scalars.size());
1438 const size_t num_points = points.size();
1439
1440 std::vector<element_ct> circuit_points;
1441 std::vector<scalar_ct> circuit_scalars;
1442 OriginTag union_tag{};
1443 for (size_t i = 0; i < num_points; ++i) {
1444 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1445 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1446 // Set tags for points to the submitted value tag for round i and for scalars to challenge tag for the
1447 // same round
1448 circuit_points[i].set_origin_tag(
1449 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1450 circuit_scalars[i].set_origin_tag(
1451 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1452 union_tag =
1453 OriginTag(union_tag, circuit_points[i].get_origin_tag(), circuit_scalars[i].get_origin_tag());
1454 }
1455 element_ct result_point = element_ct::wnaf_batch_mul(circuit_points, circuit_scalars);
1456
1457 // Check resulting tag is a union of inputs' tags
1458 EXPECT_EQ(result_point.get_origin_tag(), union_tag);
1459
1460 element expected_point = points[1];
1461 expected_point = expected_point.normalize();
1462
1463 fq result_x(result_point.x.get_value().lo);
1464 fq result_y(result_point.y.get_value().lo);
1465
1466 EXPECT_EQ(result_x, expected_point.x);
1467 EXPECT_EQ(result_y, expected_point.y);
1468
1469 EXPECT_CIRCUIT_CORRECTNESS(builder);
1470 }
1471 {
1472 // batch 0 * P1 + P2 = P2
1473 std::vector<affine_element> points;
1474 points.push_back(affine_element(element::random_element()));
1475 points.push_back(affine_element(element::random_element()));
1476 std::vector<fr> scalars;
1477 scalars.push_back(0);
1478 scalars.push_back(1);
1479
1480 Builder builder;
1481 ASSERT_EQ(points.size(), scalars.size());
1482 const size_t num_points = points.size();
1483
1484 std::vector<element_ct> circuit_points;
1485 std::vector<scalar_ct> circuit_scalars;
1486 OriginTag union_tag{};
1487 for (size_t i = 0; i < num_points; ++i) {
1488 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1489 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1490 // Set tags for points to the submitted value tag for round i and for scalars to challenge tag for the
1491 // same round
1492 circuit_points[i].set_origin_tag(
1493 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1494 circuit_scalars[i].set_origin_tag(
1495 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1496 union_tag =
1497 OriginTag(union_tag, circuit_points[i].get_origin_tag(), circuit_scalars[i].get_origin_tag());
1498 }
1499
1500 element_ct result_point = element_ct::wnaf_batch_mul(circuit_points, circuit_scalars);
1501
1502 // Check that the resulting tag is a union of inputs' tags
1503 EXPECT_EQ(result_point.get_origin_tag(), union_tag);
1504
1505 element expected_point = points[1];
1506 expected_point = expected_point.normalize();
1507
1508 fq result_x(result_point.x.get_value().lo);
1509 fq result_y(result_point.y.get_value().lo);
1510
1511 EXPECT_EQ(result_x, expected_point.x);
1512 EXPECT_EQ(result_y, expected_point.y);
1513
1514 EXPECT_CIRCUIT_CORRECTNESS(builder);
1515 }
1516 }
1517
1518 static void test_batch_mul_short_scalars()
1519 {
1520 const size_t num_points = 11;
1521 Builder builder;
1522 std::vector<affine_element> points;
1523 std::vector<fr> scalars;
1524 for (size_t i = 0; i < num_points; ++i) {
1525 points.push_back(affine_element(element::random_element()));
1526 uint256_t scalar_raw = fr::random_element();
1527 scalar_raw.data[2] = 0ULL;
1528 scalar_raw.data[3] = 0ULL;
1529 scalars.push_back(fr(scalar_raw));
1530 }
1531 std::vector<element_ct> circuit_points;
1532 std::vector<scalar_ct> circuit_scalars;
1533 OriginTag union_tag{};
1534 for (size_t i = 0; i < num_points; ++i) {
1535 circuit_points.push_back(element_ct::from_witness(&builder, points[i]));
1536 circuit_scalars.push_back(scalar_ct::from_witness(&builder, scalars[i]));
1537 // Set tags for points to the submitted value tag for round i and for scalars to challenge tag for the same
1538 // round
1539 circuit_points[i].set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1540 circuit_scalars[i].set_origin_tag(OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1541 union_tag = OriginTag(union_tag, circuit_points[i].get_origin_tag(), circuit_scalars[i].get_origin_tag());
1542 }
1543
1544 element_ct result_point = element_ct::batch_mul(circuit_points, circuit_scalars, 128);
1545
1546 // Check that the resulting tag is a union of inputs' tags
1547 EXPECT_EQ(result_point.get_origin_tag(), union_tag);
1548
1549 element expected_point = g1::one;
1550 expected_point.self_set_infinity();
1551 for (size_t i = 0; i < num_points; ++i) {
1552 expected_point += (element(points[i]) * scalars[i]);
1553 }
1554
1555 expected_point = expected_point.normalize();
1556 fq result_x(result_point.x.get_value().lo);
1557 fq result_y(result_point.y.get_value().lo);
1558
1559 EXPECT_EQ(result_x, expected_point.x);
1560 EXPECT_EQ(result_y, expected_point.y);
1561
1562 EXPECT_CIRCUIT_CORRECTNESS(builder);
1563 }
1564
1565 static void test_wnaf_batch_mul_128_bit()
1566 {
1567 Builder builder = Builder();
1568 size_t num_repetitions = 1;
1569 for (size_t i = 0; i < num_repetitions; ++i) {
1570 affine_element input(element::random_element());
1571 uint256_t scalar_u256(0, 0, 0, 0);
1572 scalar_u256.data[0] = engine.get_random_uint64();
1573 scalar_u256.data[1] = engine.get_random_uint64();
1574 fr scalar(scalar_u256);
1575 if ((uint256_t(scalar).get_bit(0) & 1) == 1) {
1576 scalar -= fr(1); // make sure to add skew
1577 }
1578 element_ct P = element_ct::from_witness(&builder, input);
1579 scalar_ct x = scalar_ct::from_witness(&builder, scalar);
1580
1581 // Set different tags to element and scalar
1582 P.set_origin_tag(submitted_value_origin_tag);
1583 x.set_origin_tag(challenge_origin_tag);
1584
1585 std::cerr << "gates before mul " << builder.get_estimated_num_finalized_gates() << std::endl;
1586 // Note: need >136 bits to complete this when working over bigfield
1587 element_ct c = element_ct::template wnaf_batch_mul<128>({ P }, { x });
1588 std::cerr << "builder aftr mul " << builder.get_estimated_num_finalized_gates() << std::endl;
1589
1590 // Check the result's tag is a union of inputs' tags
1591 EXPECT_EQ(c.get_origin_tag(), first_two_merged_tag);
1592
1593 affine_element c_expected(element(input) * scalar);
1594
1595 fq c_x_result(c.x.get_value().lo);
1596 fq c_y_result(c.y.get_value().lo);
1597
1598 EXPECT_EQ(c_x_result, c_expected.x);
1599 EXPECT_EQ(c_y_result, c_expected.y);
1600 }
1601
1602 EXPECT_CIRCUIT_CORRECTNESS(builder);
1603 }
1604
1605 static void test_wnaf_batch_4()
1606 {
1607 Builder builder = Builder();
1608 size_t num_repetitions = 1;
1609 for (size_t i = 0; i < num_repetitions; ++i) {
1610 const auto get_128_bit_scalar = []() {
1611 uint256_t scalar_u256(0, 0, 0, 0);
1612 scalar_u256.data[0] = engine.get_random_uint64();
1613 scalar_u256.data[1] = engine.get_random_uint64();
1614 fr scalar(scalar_u256);
1615 return scalar;
1616 };
1617 affine_element input1(element::random_element());
1618 affine_element input2(element::random_element());
1619 affine_element input3(element::random_element());
1620 affine_element input4(element::random_element());
1621
1622 element_ct P1 = element_ct::from_witness(&builder, input1);
1623 element_ct P2 = element_ct::from_witness(&builder, input2);
1624 element_ct P3 = element_ct::from_witness(&builder, input3);
1625 element_ct P4 = element_ct::from_witness(&builder, input4);
1626 // Set elements' tags to submitted value tags from sequential rounds
1627 std::vector<OriginTag> element_tags = {
1628 OriginTag(/*parent_index=*/0, /*child_index=*/0, /*is_submitted=*/true),
1629 OriginTag(/*parent_index=*/0, /*child_index=*/1, /*is_submitted=*/true),
1630 OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/true),
1631 OriginTag(/*parent_index=*/0, /*child_index=*/3, /*is_submitted=*/true)
1632 };
1633 P1.set_origin_tag(element_tags[0]);
1634 P2.set_origin_tag(element_tags[1]);
1635 P3.set_origin_tag(element_tags[2]);
1636 P4.set_origin_tag(element_tags[3]);
1637
1638 fr scalar1 = get_128_bit_scalar();
1639 fr scalar2 = get_128_bit_scalar();
1640 fr scalar3 = get_128_bit_scalar();
1641 fr scalar4 = get_128_bit_scalar();
1642
1643 scalar_ct x1 = scalar_ct::from_witness(&builder, scalar1);
1644 scalar_ct x2 = scalar_ct::from_witness(&builder, scalar2);
1645 scalar_ct x3 = scalar_ct::from_witness(&builder, scalar3);
1646 scalar_ct x4 = scalar_ct::from_witness(&builder, scalar4);
1647
1648 // Set scalars' tags to challenge tags from sequential rounds
1649 std::vector<OriginTag> scalar_tags = {
1650 OriginTag(/*parent_index=*/0, /*child_index=*/0, /*is_submitted=*/false),
1651 OriginTag(/*parent_index=*/0, /*child_index=*/1, /*is_submitted=*/false),
1652 OriginTag(/*parent_index=*/0, /*child_index=*/2, /*is_submitted=*/false),
1653 OriginTag(/*parent_index=*/0, /*child_index=*/3, /*is_submitted=*/false)
1654 };
1655 x1.set_origin_tag(scalar_tags[0]);
1656 x2.set_origin_tag(scalar_tags[1]);
1657 x3.set_origin_tag(scalar_tags[2]);
1658 x4.set_origin_tag(scalar_tags[3]);
1659
1660 OriginTag union_tag{};
1661 for (size_t j = 0; j < element_tags.size(); j++) {
1662 union_tag = OriginTag(union_tag, element_tags[j], scalar_tags[j]);
1663 }
1664
1665 std::cerr << "gates before mul " << builder.get_estimated_num_finalized_gates() << std::endl;
1666 element_ct c = element_ct::batch_mul({ P1, P2, P3, P4 }, { x1, x2, x3, x4 }, 128);
1667 std::cerr << "builder aftr mul " << builder.get_estimated_num_finalized_gates() << std::endl;
1668
1669 // Check that the resulting tag is a union of inputs' tags
1670 EXPECT_EQ(c.get_origin_tag(), union_tag);
1671 element out = input1 * scalar1;
1672 out += (input2 * scalar2);
1673 out += (input3 * scalar3);
1674 out += (input4 * scalar4);
1675 affine_element c_expected(out);
1676
1677 fq c_x_result(c.x.get_value().lo);
1678 fq c_y_result(c.y.get_value().lo);
1679
1680 EXPECT_EQ(c_x_result, c_expected.x);
1681 EXPECT_EQ(c_y_result, c_expected.y);
1682 }
1683
1684 EXPECT_CIRCUIT_CORRECTNESS(builder);
1685 }
1686
1687 static void test_bn254_endo_batch_mul()
1688 {
1689 const size_t num_big_points = 2;
1690 const size_t num_small_points = 1;
1691 Builder builder;
1692 std::vector<affine_element> big_points;
1693 std::vector<fr> big_scalars;
1694 std::vector<affine_element> small_points;
1695 std::vector<fr> small_scalars;
1696
1697 for (size_t i = 0; i < num_big_points; ++i) {
1698 big_points.push_back(affine_element(element::random_element()));
1699 big_scalars.push_back(fr::random_element());
1700 }
1701 for (size_t i = 0; i < num_small_points; ++i) {
1702 small_points.push_back(affine_element(element::random_element()));
1703 uint256_t scalar_raw = fr::random_element();
1704 scalar_raw.data[2] = 0ULL;
1705 scalar_raw.data[3] = 0ULL;
1706 small_scalars.push_back(fr(scalar_raw));
1707 }
1708
1709 std::vector<element_ct> big_circuit_points;
1710 std::vector<scalar_ct> big_circuit_scalars;
1711 std::vector<element_ct> small_circuit_points;
1712 std::vector<scalar_ct> small_circuit_scalars;
1713 OriginTag union_tag{};
1714 for (size_t i = 0; i < num_big_points; ++i) {
1715 big_circuit_points.push_back(element_ct::from_witness(&builder, big_points[i]));
1716 big_circuit_scalars.push_back(scalar_ct::from_witness(&builder, big_scalars[i]));
1717 // Set tags for points to the submitted value tag for round i and for scalars to challenge tag for the same
1718 // round
1719 big_circuit_points[i].set_origin_tag(
1720 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/true));
1721 big_circuit_scalars[i].set_origin_tag(
1722 OriginTag(/*parent_index=*/0, /*child_index=*/i, /*is_submitted=*/false));
1723 union_tag =
1724 OriginTag(union_tag, big_circuit_points[i].get_origin_tag(), big_circuit_scalars[i].get_origin_tag());
1725 }
1726 for (size_t i = 0; i < num_small_points; ++i) {
1727 small_circuit_points.push_back(element_ct::from_witness(&builder, small_points[i]));
1728 small_circuit_scalars.push_back(scalar_ct::from_witness(&builder, small_scalars[i]));
1729 // Set tags for points to the submitted value tag for round i and for scalars to challenge tag for the same
1730 // round
1731 small_circuit_points[i].set_origin_tag(
1732 OriginTag(/*parent_index=*/0, /*child_index=*/i + num_big_points, /*is_submitted=*/true));
1733 small_circuit_scalars[i].set_origin_tag(
1734 OriginTag(/*parent_index=*/0, /*child_index=*/i + num_big_points, /*is_submitted=*/false));
1735 union_tag = OriginTag(
1736 union_tag, small_circuit_points[i].get_origin_tag(), small_circuit_scalars[i].get_origin_tag());
1737 }
1738
1739 element_ct result_point = element_ct::bn254_endo_batch_mul(
1740 big_circuit_points, big_circuit_scalars, small_circuit_points, small_circuit_scalars, 128);
1741
1742 // Check that the resulting tag is a union of input tags
1743 EXPECT_EQ(result_point.get_origin_tag(), union_tag);
1744
1745 element expected_point = g1::one;
1746 expected_point.self_set_infinity();
1747 for (size_t i = 0; i < num_big_points; ++i) {
1748 expected_point += (element(big_points[i]) * big_scalars[i]);
1749 }
1750 for (size_t i = 0; i < num_small_points; ++i) {
1751 expected_point += (element(small_points[i]) * small_scalars[i]);
1752 }
1753
1754 expected_point = expected_point.normalize();
1755 fq result_x(result_point.x.get_value().lo);
1756 fq result_y(result_point.y.get_value().lo);
1757
1758 EXPECT_EQ(result_x, expected_point.x);
1759 EXPECT_EQ(result_y, expected_point.y);
1760
1761 EXPECT_CIRCUIT_CORRECTNESS(builder);
1762 }
1763
1764 static void test_mixed_mul_bn254_endo()
1765 {
1766 Builder builder;
1767 size_t num_repetitions = 1;
1768
1769 const auto get_small_scalar = []() {
1770 fr t1 = fr::random_element();
1771 t1 = t1.from_montgomery_form();
1772 t1.data[2] = 0;
1773 t1.data[3] = 0;
1774 return t1.to_montgomery_form();
1775 };
1776 for (size_t i = 0; i < num_repetitions; ++i) {
1777 std::vector<element_ct> small_points(25);
1778 std::vector<element_ct> big_points(5);
1779 std::vector<element_ct> double_points(11);
1780 std::vector<scalar_ct> small_scalars(25);
1781 std::vector<scalar_ct> big_scalars(5);
1782 std::vector<scalar_ct> double_scalars(11);
1783
1784 std::vector<affine_element> small_points_w(25);
1785 std::vector<affine_element> big_points_w(5);
1786 std::vector<affine_element> double_points_w(11);
1787 std::vector<fr> small_scalars_w(25);
1788 std::vector<fr> big_scalars_w(5);
1789 std::vector<fr> double_scalars_w(11);
1790
1791 for (size_t i = 0; i < 25; ++i) {
1792 small_points_w[i] = affine_element(element::random_element());
1793 small_scalars_w[i] = get_small_scalar();
1794 small_points[i] = element_ct::from_witness(&builder, small_points_w[i]);
1795 small_scalars[i] = scalar_ct::from_witness(&builder, small_scalars_w[i]);
1796 }
1797 for (size_t i = 0; i < 5; ++i) {
1798 big_points_w[i] = affine_element(element::random_element());
1799 big_scalars_w[i] = fr::random_element();
1800 big_points[i] = element_ct::from_witness(&builder, big_points_w[i]);
1801 big_scalars[i] = scalar_ct::from_witness(&builder, big_scalars_w[i]);
1802 }
1803 for (size_t i = 0; i < 11; ++i) {
1804 double_points_w[i] = affine_element(element::random_element());
1805 double_scalars_w[i] = get_small_scalar();
1806 double_points[i] = element_ct::from_witness(&builder, double_points_w[i]);
1807 double_scalars[i] = scalar_ct::from_witness(&builder, double_scalars_w[i]);
1808 }
1809
1810 fr omega = get_small_scalar();
1811
1812 const auto double_opening_result = element_ct::batch_mul(double_points, double_scalars, 128);
1813 small_points.push_back(double_opening_result);
1814 small_scalars.push_back(scalar_ct::from_witness(&builder, omega));
1815
1816 auto opening_result =
1817 element_ct::bn254_endo_batch_mul(big_points, big_scalars, small_points, small_scalars, 128);
1818
1819 opening_result = opening_result + double_opening_result;
1820 opening_result = opening_result.normalize();
1821
1822 element expected = g1::one;
1823 expected.self_set_infinity();
1824 for (size_t i = 0; i < 11; ++i) {
1825 expected += (double_points_w[i] * double_scalars_w[i]);
1826 }
1827 expected *= (omega + 1);
1828 for (size_t i = 0; i < 25; ++i) {
1829 expected += (small_points_w[i] * small_scalars_w[i]);
1830 }
1831 for (size_t i = 0; i < 5; ++i) {
1832 expected += (big_points_w[i] * big_scalars_w[i]);
1833 }
1834 expected = expected.normalize();
1835
1836 fq result_x(opening_result.x.get_value().lo);
1837 fq result_y(opening_result.y.get_value().lo);
1838
1839 EXPECT_EQ(result_x, expected.x);
1840 EXPECT_EQ(result_y, expected.y);
1841 }
1842
1843 EXPECT_CIRCUIT_CORRECTNESS(builder);
1844 };
1845};
1846
1847enum UseBigfield { No, Yes };
1848using TestTypes = testing::Types<TestType<stdlib::bn254<bb::UltraCircuitBuilder>, UseBigfield::Yes>,
1849 TestType<stdlib::bn254<bb::MegaCircuitBuilder>, UseBigfield::No>>;
1850
1851TYPED_TEST_SUITE(stdlib_biggroup, TestTypes);
1852
1853TYPED_TEST(stdlib_biggroup, basic_tag_logic)
1854{
1855 TestFixture::test_basic_tag_logic();
1856}
1857TYPED_TEST(stdlib_biggroup, add)
1858{
1859
1860 TestFixture::test_add();
1861}
1862TYPED_TEST(stdlib_biggroup, add_points_at_infinity)
1863{
1864 TestFixture::test_add_points_at_infinity();
1865}
1866TYPED_TEST(stdlib_biggroup, standard_form_of_point_at_infinity)
1867{
1868 TestFixture::test_standard_form_of_point_at_infinity();
1869}
1870TYPED_TEST(stdlib_biggroup, sub)
1871{
1872 TestFixture::test_sub();
1873}
1874TYPED_TEST(stdlib_biggroup, sub_points_at_infinity)
1875{
1876
1877 TestFixture::test_sub_points_at_infinity();
1878}
1879TYPED_TEST(stdlib_biggroup, dbl)
1880{
1881 TestFixture::test_dbl();
1882}
1883TYPED_TEST(stdlib_biggroup, conditional_negate)
1884{
1885 TestFixture::test_conditional_negate();
1886}
1887TYPED_TEST(stdlib_biggroup, conditional_select)
1888{
1889 TestFixture::test_conditional_select();
1890}
1891TYPED_TEST(stdlib_biggroup, incomplete_assert_equal)
1892{
1893 TestFixture::test_incomplete_assert_equal_success();
1894}
1895TYPED_TEST(stdlib_biggroup, incomplete_assert_equal_fails)
1896{
1897 TestFixture::test_incomplete_assert_equal_failure();
1898}
1899TYPED_TEST(stdlib_biggroup, incomplete_assert_equal_edge_cases)
1900{
1901 TestFixture::test_incomplete_assert_equal_edge_cases();
1902}
1903TYPED_TEST(stdlib_biggroup, montgomery_ladder)
1904{
1905 if constexpr (HasGoblinBuilder<TypeParam>) {
1906 GTEST_SKIP() << "https://github.com/AztecProtocol/barretenberg/issues/1290";
1907 } else {
1908 TestFixture::test_montgomery_ladder();
1909 };
1910}
1911HEAVY_TYPED_TEST(stdlib_biggroup, mul)
1912{
1913 TestFixture::test_mul();
1914}
1915
1916HEAVY_TYPED_TEST(stdlib_biggroup, short_scalar_mul_2_126_bits)
1917{
1918 if constexpr (HasGoblinBuilder<TypeParam>) {
1919 GTEST_SKIP();
1920 } else {
1921 TestFixture::test_short_scalar_mul_2_126();
1922 }
1923}
1924HEAVY_TYPED_TEST(stdlib_biggroup, short_scalar_mul_128_252_bits)
1925{
1926 if constexpr (HasGoblinBuilder<TypeParam>) {
1927 GTEST_SKIP();
1928 } else {
1929 TestFixture::test_short_scalar_mul_128_252();
1930 }
1931}
1932
1933HEAVY_TYPED_TEST(stdlib_biggroup, short_scalar_mul_infinity)
1934{
1935 if constexpr (HasGoblinBuilder<TypeParam>) {
1936 GTEST_SKIP();
1937 } else {
1938 TestFixture::test_short_scalar_mul_infinity();
1939 }
1940}
1941
1942HEAVY_TYPED_TEST(stdlib_biggroup, twin_mul)
1943{
1944 if constexpr (HasGoblinBuilder<TypeParam>) {
1945 GTEST_SKIP() << "https://github.com/AztecProtocol/barretenberg/issues/1290";
1946 } else {
1947 TestFixture::test_twin_mul();
1948 };
1949}
1950HEAVY_TYPED_TEST(stdlib_biggroup, triple_mul)
1951{
1952 if constexpr (HasGoblinBuilder<TypeParam>) {
1953 GTEST_SKIP() << "https://github.com/AztecProtocol/barretenberg/issues/1290";
1954 } else {
1955 TestFixture::test_triple_mul();
1956 };
1957}
1958HEAVY_TYPED_TEST(stdlib_biggroup, quad_mul)
1959{
1960 if constexpr (HasGoblinBuilder<TypeParam>) {
1961 GTEST_SKIP() << "https://github.com/AztecProtocol/barretenberg/issues/1290";
1962 } else {
1963 TestFixture::test_quad_mul();
1964 };
1965}
1966HEAVY_TYPED_TEST(stdlib_biggroup, one)
1967{
1968 TestFixture::test_one();
1969}
1970HEAVY_TYPED_TEST(stdlib_biggroup, batch_mul)
1971{
1972 TestFixture::test_batch_mul();
1973}
1974
1975HEAVY_TYPED_TEST(stdlib_biggroup, batch_mul_edgecase_equivalence)
1976{
1977 if constexpr (HasGoblinBuilder<TypeParam>) {
1978 GTEST_SKIP();
1979 } else {
1980 TestFixture::test_batch_mul_edgecase_equivalence();
1981 }
1982}
1983HEAVY_TYPED_TEST(stdlib_biggroup, batch_mul_edge_case_set1)
1984{
1985 TestFixture::test_batch_mul_edge_case_set1();
1986}
1987
1988HEAVY_TYPED_TEST(stdlib_biggroup, batch_mul_edge_case_set2)
1989{
1990 TestFixture::test_batch_mul_edge_case_set2();
1991}
1992HEAVY_TYPED_TEST(stdlib_biggroup, chain_add)
1993{
1994
1995 if constexpr (HasGoblinBuilder<TypeParam>) {
1996 GTEST_SKIP() << "https://github.com/AztecProtocol/barretenberg/issues/1290";
1997 } else {
1998 TestFixture::test_chain_add();
1999 };
2000}
2001HEAVY_TYPED_TEST(stdlib_biggroup, multiple_montgomery_ladder)
2002{
2003
2004 if constexpr (HasGoblinBuilder<TypeParam>) {
2005 GTEST_SKIP() << "https://github.com/AztecProtocol/barretenberg/issues/1290";
2006 } else {
2007 TestFixture::test_multiple_montgomery_ladder();
2008 };
2009}
2010
2011HEAVY_TYPED_TEST(stdlib_biggroup, compute_naf)
2012{
2013 // ULTRATODO: make this work for secp curves
2014 if constexpr ((TypeParam::Curve::type == CurveType::BN254) && !HasGoblinBuilder<TypeParam>) {
2015 size_t num_repetitions = 1;
2016 for (size_t i = 0; i < num_repetitions; i++) {
2017 TestFixture::test_compute_naf();
2018 }
2019 } else {
2020 GTEST_SKIP();
2021 }
2022}
2023
2024/* These tests only work for Ultra Circuit Constructor */
2025HEAVY_TYPED_TEST(stdlib_biggroup, wnaf_batch_mul)
2026{
2027 if constexpr (TypeParam::Curve::type == CurveType::BN254 && HasGoblinBuilder<TypeParam>) {
2028 GTEST_SKIP();
2029 } else {
2030 TestFixture::test_compute_wnaf();
2031 };
2032}
2033
2034/* These tests only work for Ultra Circuit Constructor */
2035HEAVY_TYPED_TEST(stdlib_biggroup, wnaf_batch_mul_edge_cases)
2036{
2037 if constexpr (TypeParam::Curve::type == CurveType::BN254 && HasGoblinBuilder<TypeParam>) {
2038 GTEST_SKIP();
2039 } else {
2040 TestFixture::test_compute_wnaf();
2041 };
2042}
2043
2044/* the following test was only developed as a test of Ultra Circuit Constructor. It fails for Standard in the
2045 case where Fr is a bigfield. */
2046HEAVY_TYPED_TEST(stdlib_biggroup, compute_wnaf)
2047{
2048 if constexpr (TypeParam::Curve::type == CurveType::BN254 && HasGoblinBuilder<TypeParam>) {
2049 GTEST_SKIP();
2050 } else {
2051 TestFixture::test_compute_wnaf();
2052 }
2053}
2054
2055/* batch_mul with specified value of max_num_bits does not work for a biggroup formed over a big scalar field.
2056 We skip such cases in the next group of tests. */
2057HEAVY_TYPED_TEST(stdlib_biggroup, batch_mul_short_scalars)
2058{
2059 if constexpr (TypeParam::use_bigfield) {
2060 GTEST_SKIP();
2061 } else {
2062 if constexpr (TypeParam::Curve::type == CurveType::BN254 && HasGoblinBuilder<TypeParam>) {
2063 GTEST_SKIP();
2064 } else {
2065 TestFixture::test_batch_mul_short_scalars();
2066 };
2067 }
2068}
2069HEAVY_TYPED_TEST(stdlib_biggroup, wnaf_batch_mul_128_bit)
2070{
2071 if constexpr (TypeParam::use_bigfield) {
2072 GTEST_SKIP();
2073 } else {
2074 if constexpr (TypeParam::Curve::type == CurveType::BN254 && HasGoblinBuilder<TypeParam>) {
2075 GTEST_SKIP();
2076 } else {
2077 TestFixture::test_wnaf_batch_mul_128_bit();
2078 };
2079 }
2080}
2081HEAVY_TYPED_TEST(stdlib_biggroup, wnaf_batch_4)
2082{
2083 if constexpr (TypeParam::use_bigfield) {
2084 GTEST_SKIP();
2085 } else {
2086 TestFixture::test_wnaf_batch_4();
2087 }
2088}
2089
2090/* The following tests are specific to BN254 and don't work when Fr is a bigfield */
2091HEAVY_TYPED_TEST(stdlib_biggroup, bn254_endo_batch_mul)
2092{
2093 if constexpr (TypeParam::Curve::type == CurveType::BN254 && !TypeParam::use_bigfield) {
2094 if constexpr (HasGoblinBuilder<TypeParam>) {
2095 GTEST_SKIP();
2096 } else {
2097 TestFixture::test_bn254_endo_batch_mul();
2098 };
2099 } else {
2100 GTEST_SKIP();
2101 }
2102}
2103HEAVY_TYPED_TEST(stdlib_biggroup, mixed_mul_bn254_endo)
2104{
2105 if constexpr (TypeParam::Curve::type == CurveType::BN254 && !TypeParam::use_bigfield) {
2106 if constexpr (HasGoblinBuilder<TypeParam>) {
2107 GTEST_SKIP();
2108 } else {
2109 TestFixture::test_mixed_mul_bn254_endo();
2110 };
2111 } else {
2112 GTEST_SKIP();
2113 }
2114}
TestTypes
testing::Types< TestType< stdlib::bn254< bb::UltraCircuitBuilder >, UseBigfield::Yes >, TestType< stdlib::bn254< bb::MegaCircuitBuilder >, UseBigfield::No > > TestTypes
Definition biggroup.test.cpp:1849
UseBigfield
UseBigfield
Definition biggroup.test.cpp:1847
circuit_builders.hpp
circuit_checker.hpp
bb::TranslatorCircuitChecker::check
static bool check(const Builder &circuit)
Check the witness satisifies the circuit.
Definition translator_circuit_checker.cpp:20
bb::group_elements::affine_element::infinity
static affine_element infinity()
Definition affine_element_impl.hpp:95
bb::group_elements::affine_element::self_set_infinity
constexpr void self_set_infinity() noexcept
Definition affine_element_impl.hpp:110
bb::group_elements::affine_element::x
Fq x
Definition affine_element.hpp:201
bb::group_elements::affine_element::y
Fq y
Definition affine_element.hpp:202
bb::group_elements::affine_element::one
static constexpr affine_element one() noexcept
Definition affine_element.hpp:49
bb::group_elements::element::self_set_infinity
BB_INLINE constexpr void self_set_infinity() noexcept
Definition element_impl.hpp:511
bb::group::affine_element
group_elements::affine_element< Fq, Fr, Params > affine_element
Definition group.hpp:42
bb::group::one
static constexpr element one
Definition group.hpp:46
bb::group::element
group_elements::element< Fq, Fr, Params > element
Definition group.hpp:41
bb::numeric::uint256_t
Definition uint256.hpp:32
bb::numeric::uint256_t::data
uint64_t data[4]
Definition uint256.hpp:207
bb::stdlib::bool_t
Implements boolean logic in-circuit.
Definition bool.hpp:59
bb::stdlib::bool_t::set_origin_tag
void set_origin_tag(const OriginTag &new_tag) const
Definition bool.hpp:128
bb::stdlib::witness_t
Definition witness.hpp:16
stdlib_biggroup
Definition biggroup.test.cpp:36
stdlib_biggroup::test_sub_points_at_infinity
static void test_sub_points_at_infinity()
Definition biggroup.test.cpp:259
stdlib_biggroup::test_batch_mul_edgecase_equivalence
static void test_batch_mul_edgecase_equivalence()
Definition biggroup.test.cpp:1018
stdlib_biggroup::test_one
static void test_one()
Definition biggroup.test.cpp:936
stdlib_biggroup::test_twin_mul
static void test_twin_mul()
Definition biggroup.test.cpp:755
stdlib_biggroup::test_batch_mul_short_scalars
static void test_batch_mul_short_scalars()
Definition biggroup.test.cpp:1518
stdlib_biggroup::test_add_points_at_infinity
static void test_add_points_at_infinity()
Definition biggroup.test.cpp:125
stdlib_biggroup::test_compute_naf
static void test_compute_naf()
Definition biggroup.test.cpp:1288
stdlib_biggroup::element
typename g1::element element
Definition biggroup.test.cpp:45
stdlib_biggroup::test_multiple_montgomery_ladder
static void test_multiple_montgomery_ladder()
Definition biggroup.test.cpp:1264
stdlib_biggroup::test_conditional_negate
static void test_conditional_negate()
Definition biggroup.test.cpp:346
stdlib_biggroup::test_conditional_select
static void test_conditional_select()
Definition biggroup.test.cpp:372
stdlib_biggroup::test_add
static void test_add()
Definition biggroup.test.cpp:84
stdlib_biggroup::fr
typename Curve::ScalarFieldNative fr
Definition biggroup.test.cpp:42
stdlib_biggroup::test_batch_mul_edge_case_set2
static void test_batch_mul_edge_case_set2()
Definition biggroup.test.cpp:1128
stdlib_biggroup::element_ct
typename TestType::element_ct element_ct
Definition biggroup.test.cpp:38
stdlib_biggroup::test_mixed_mul_bn254_endo
static void test_mixed_mul_bn254_endo()
Definition biggroup.test.cpp:1764
stdlib_biggroup::test_montgomery_ladder
static void test_montgomery_ladder()
Definition biggroup.test.cpp:550
stdlib_biggroup::test_quad_mul
static void test_quad_mul()
Definition biggroup.test.cpp:860
stdlib_biggroup::test_bn254_endo_batch_mul
static void test_bn254_endo_batch_mul()
Definition biggroup.test.cpp:1687
stdlib_biggroup::test_mul
static void test_mul()
Definition biggroup.test.cpp:585
stdlib_biggroup::affine_element
typename g1::affine_element affine_element
Definition biggroup.test.cpp:44
stdlib_biggroup::test_short_scalar_mul_128_252
static void test_short_scalar_mul_128_252()
Definition biggroup.test.cpp:665
stdlib_biggroup::Curve
typename TestType::Curve Curve
Definition biggroup.test.cpp:37
stdlib_biggroup::test_incomplete_assert_equal_edge_cases
static void test_incomplete_assert_equal_edge_cases()
Definition biggroup.test.cpp:521
stdlib_biggroup::test_basic_tag_logic
static void test_basic_tag_logic()
Definition biggroup.test.cpp:57
stdlib_biggroup::Builder
typename Curve::Builder Builder
Definition biggroup.test.cpp:47
stdlib_biggroup::test_dbl
static void test_dbl()
Definition biggroup.test.cpp:315
stdlib_biggroup::scalar_ct
typename TestType::scalar_ct scalar_ct
Definition biggroup.test.cpp:39
stdlib_biggroup::bool_ct
stdlib::bool_t< Builder > bool_ct
Definition biggroup.test.cpp:49
stdlib_biggroup::test_triple_mul
static void test_triple_mul()
Definition biggroup.test.cpp:797
stdlib_biggroup::test_batch_mul_edge_case_set1
static void test_batch_mul_edge_case_set1()
Definition biggroup.test.cpp:1068
stdlib_biggroup::test_wnaf_batch_mul_128_bit
static void test_wnaf_batch_mul_128_bit()
Definition biggroup.test.cpp:1565
stdlib_biggroup::test_short_scalar_mul_infinity
static void test_short_scalar_mul_infinity()
Definition biggroup.test.cpp:705
stdlib_biggroup::test_incomplete_assert_equal_success
static void test_incomplete_assert_equal_success()
Definition biggroup.test.cpp:401
stdlib_biggroup::test_incomplete_assert_equal_failure
static void test_incomplete_assert_equal_failure()
Definition biggroup.test.cpp:452
stdlib_biggroup::witness_ct
stdlib::witness_t< Builder > witness_ct
Definition biggroup.test.cpp:48
stdlib_biggroup::test_standard_form_of_point_at_infinity
static void test_standard_form_of_point_at_infinity()
Check that converting a point at infinity into standard form ensures the coordinates are zeroes.
Definition biggroup.test.cpp:184
stdlib_biggroup::test_wnaf_batch_mul
static void test_wnaf_batch_mul()
Definition biggroup.test.cpp:1345
stdlib_biggroup::g1
typename Curve::GroupNative g1
Definition biggroup.test.cpp:43
stdlib_biggroup::test_wnaf_batch_mul_edge_cases
static void test_wnaf_batch_mul_edge_cases()
Definition biggroup.test.cpp:1380
stdlib_biggroup::test_compute_wnaf
static void test_compute_wnaf()
Definition biggroup.test.cpp:1327
stdlib_biggroup::test_wnaf_batch_4
static void test_wnaf_batch_4()
Definition biggroup.test.cpp:1605
stdlib_biggroup::fq
typename Curve::BaseFieldNative fq
Definition biggroup.test.cpp:41
stdlib_biggroup::test_short_scalar_mul_2_126
static void test_short_scalar_mul_2_126()
Definition biggroup.test.cpp:620
stdlib_biggroup::test_chain_add
static void test_chain_add()
Definition biggroup.test.cpp:1229
stdlib_biggroup::test_batch_mul
static void test_batch_mul()
Definition biggroup.test.cpp:968
stdlib_biggroup::test_sub
static void test_sub()
Definition biggroup.test.cpp:224
stdlib_biggroup::EXPECT_CIRCUIT_CORRECTNESS
static constexpr auto EXPECT_CIRCUIT_CORRECTNESS
Definition biggroup.test.cpp:51
zip_view
Definition zip_view.hpp:166
benchmark_info
void benchmark_info(Args...)
Info used to store circuit statistics during CI/CD with concrete structure. Writes straight to log.
Definition log.hpp:109
info
void info(Args... args)
Definition log.hpp:74
builder
AluTraceBuilder builder
Definition alu.test.cpp:123
a
FF a
Definition field_gt.test.cpp:52
b
FF b
Definition field_gt.test.cpp:53
expected_result
bool expected_result
Definition field_gt.test.cpp:54
length
uint8_t const size_t length
Definition data_store.hpp:9
engine
auto & engine
Definition graph_description_protogalaxy.test.cpp:15
bb::numeric::get_debug_randomness
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:190
bb
Entry point for Barretenberg command-line interface.
Definition acir_format_getters.cpp:6
bb::TYPED_TEST_SUITE
TYPED_TEST_SUITE(ShpleminiTest, TestSettings)
bb::TYPED_TEST
TYPED_TEST(ShpleminiTest, CorrectnessOfMultivariateClaimBatching)
Definition shplemini.test.cpp:47
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
origin_tag.hpp
This file contains part of the logic for the Origin Tag mechanism that tracks the use of in-circuit p...
STANDARD_TESTING_TAGS
#define STANDARD_TESTING_TAGS
Definition origin_tag.hpp:26
TestType::element_ct
typename std::conditional< _use_bigfield, typename Curve::g1_bigfr_ct, typename Curve::Group >::type element_ct
Definition biggroup.test.cpp:29
TestType::scalar_ct
typename std::conditional< _use_bigfield, typename Curve::bigfr_ct, typename Curve::ScalarField >::type scalar_ct
Definition biggroup.test.cpp:32
TestType::use_bigfield
static const bool use_bigfield
Definition biggroup.test.cpp:27
bb::field::to_montgomery_form
BB_INLINE constexpr field to_montgomery_form() const noexcept
Definition field_impl.hpp:283
bb::field< Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:676
bb::field::from_montgomery_form
BB_INLINE constexpr field from_montgomery_form() const noexcept
Definition field_impl.hpp:301
HEAVY_TYPED_TEST
#define HEAVY_TYPED_TEST(x, y)
Definition test.hpp:11