Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
eccvm_circuit_builder.test.cpp
Go to the documentation of this file.
5#include <gtest/gtest.h>
6
7using namespace bb;
8using G1 = bb::g1;
9using Fr = typename G1::Fr;
10
11namespace {
13
19void add_hiding_op_for_test(const std::shared_ptr<ECCOpQueue>& op_queue)
20{
22 // Prepend an eq op with random coordinates - same as production
23 op_queue->append_hiding_op(Fq::random_element(), Fq::random_element());
24}
25} // namespace
26
27TEST(ECCVMCircuitBuilderTests, BaseCase)
28{
29 auto generators = G1::derive_generators("test generators", 3);
30 typename G1::element a = generators[0];
31 typename G1::element b = generators[1];
32 typename G1::element c = generators[2];
33 typename G1::element point_at_infinity = G1::point_at_infinity;
36 Fr zero_scalar = 0;
37
39
40 op_queue->add_accumulate(a);
41 op_queue->mul_accumulate(a, x);
42 op_queue->mul_accumulate(b, x);
43 op_queue->mul_accumulate(b, y);
44 op_queue->add_accumulate(a);
45 op_queue->mul_accumulate(b, x);
46 op_queue->add_accumulate(b);
47 op_queue->eq_and_reset();
48 op_queue->add_accumulate(c);
49 op_queue->mul_accumulate(a, x);
50 op_queue->mul_accumulate(point_at_infinity, x);
51 op_queue->mul_accumulate(b, x);
52 op_queue->eq_and_reset();
53 op_queue->mul_accumulate(a, x);
54 op_queue->mul_accumulate(b, x);
55 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
56 op_queue->mul_accumulate(c, x);
57 op_queue->eq_and_reset();
58 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
59 op_queue->mul_accumulate(point_at_infinity, x);
60 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
61 op_queue->add_accumulate(a);
62 op_queue->eq_and_reset();
63 op_queue->add_accumulate(a);
64 op_queue->add_accumulate(point_at_infinity);
65 op_queue->eq_and_reset();
66 op_queue->add_accumulate(point_at_infinity);
67 op_queue->eq_and_reset();
68 op_queue->mul_accumulate(point_at_infinity, x);
69 op_queue->mul_accumulate(point_at_infinity, -x);
70 op_queue->eq_and_reset();
71 op_queue->add_accumulate(a);
72 op_queue->mul_accumulate(point_at_infinity, x);
73 op_queue->mul_accumulate(point_at_infinity, -x);
74 op_queue->add_accumulate(a);
75 op_queue->add_accumulate(a);
76 op_queue->eq_and_reset();
77 op_queue->merge();
78 add_hiding_op_for_test(op_queue);
79 ECCVMCircuitBuilder circuit{ op_queue };
80 bool result = ECCVMTraceChecker::check(circuit);
81 EXPECT_EQ(result, true);
82}
83
84TEST(ECCVMCircuitBuilderTests, NoOp)
85{
87 add_hiding_op_for_test(op_queue);
88
89 ECCVMCircuitBuilder circuit{ op_queue };
90 bool result = ECCVMTraceChecker::check(circuit, &engine);
91 EXPECT_EQ(result, true);
92}
93
94TEST(ECCVMCircuitBuilderTests, Add)
95{
97
98 auto generators = G1::derive_generators("test generators", 3);
99 typename G1::element a = generators[0];
100
101 op_queue->add_accumulate(a);
102 op_queue->merge();
103 add_hiding_op_for_test(op_queue);
104
105 ECCVMCircuitBuilder circuit{ op_queue };
106 bool result = ECCVMTraceChecker::check(circuit, &engine);
107 EXPECT_EQ(result, true);
108}
109
110TEST(ECCVMCircuitBuilderTests, Mul)
111{
113
114 auto generators = G1::derive_generators("test generators", 3);
115 typename G1::element a = generators[0];
117
118 op_queue->mul_accumulate(a, x);
119 op_queue->merge();
120 add_hiding_op_for_test(op_queue);
121
122 ECCVMCircuitBuilder circuit{ op_queue };
123 bool result = ECCVMTraceChecker::check(circuit, &engine);
124 EXPECT_EQ(result, true);
125}
126
127TEST(ECCVMCircuitBuilderTests, MulInfinity)
128{
130
131 auto generators = G1::derive_generators("test generators", 3);
132 typename G1::element a = generators[0];
134 G1::element b = -a * x;
135
136 op_queue->add_accumulate(b);
137 op_queue->mul_accumulate(a, x);
138 op_queue->eq_and_reset();
139 op_queue->merge();
140 add_hiding_op_for_test(op_queue);
141
142 ECCVMCircuitBuilder circuit{ op_queue };
143 bool result = ECCVMTraceChecker::check(circuit);
144 EXPECT_EQ(result, true);
145}
146
147// Validate we do not trigger edge cases of addition formulae when we have identical mul inputs
148TEST(ECCVMCircuitBuilderTests, MulOverIdenticalInputs)
149{
151
152 auto generators = G1::derive_generators("test generators", 3);
153 typename G1::element a = generators[0];
155 op_queue->mul_accumulate(a, x);
156 op_queue->mul_accumulate(a, x);
157 op_queue->eq_and_reset();
158 op_queue->merge();
159 add_hiding_op_for_test(op_queue);
160
161 ECCVMCircuitBuilder circuit{ op_queue };
162 bool result = ECCVMTraceChecker::check(circuit);
163 EXPECT_EQ(result, true);
164}
165
166TEST(ECCVMCircuitBuilderTests, MSMProducesInfinity)
167{
169
170 auto generators = G1::derive_generators("test generators", 3);
171 typename G1::element a = generators[0];
173 op_queue->add_accumulate(a);
174 op_queue->mul_accumulate(a, x);
175 op_queue->mul_accumulate(a, -x);
176 op_queue->eq_and_reset();
177 op_queue->merge();
178 add_hiding_op_for_test(op_queue);
179
180 ECCVMCircuitBuilder circuit{ op_queue };
181 bool result = ECCVMTraceChecker::check(circuit);
182 EXPECT_EQ(result, true);
183}
184
185TEST(ECCVMCircuitBuilderTests, MSMOverPointAtInfinity)
186{
188
189 auto generators = G1::derive_generators("test generators", 3);
190 typename G1::element point_at_infinity = G1::point_at_infinity;
191 typename G1::element b = generators[0];
193 Fr zero_scalar = 0;
194
195 // validate including points at infinity in a multiscalar multiplication does not effect result
196 {
197 op_queue->mul_accumulate(b, x);
198 op_queue->mul_accumulate(point_at_infinity, x);
199 op_queue->eq_and_reset();
200 op_queue->merge();
201 add_hiding_op_for_test(op_queue);
202
203 ECCVMCircuitBuilder circuit{ op_queue };
204 bool result = ECCVMTraceChecker::check(circuit);
205 EXPECT_EQ(result, true);
206 }
207 // validate multiplying a point at infinity by nonzero scalar produces point at infinity
208 {
209 op_queue->mul_accumulate(point_at_infinity, x);
210 op_queue->eq_and_reset();
211 op_queue->merge();
212
213 ECCVMCircuitBuilder circuit{ op_queue };
214 bool result = ECCVMTraceChecker::check(circuit);
215 EXPECT_EQ(result, true);
216 }
217 // validate multiplying a point by zero produces point at infinity
218 {
219 op_queue->mul_accumulate(b, zero_scalar);
220 op_queue->eq_and_reset();
221 op_queue->merge();
222
223 ECCVMCircuitBuilder circuit{ op_queue };
224 bool result = ECCVMTraceChecker::check(circuit);
225 EXPECT_EQ(result, true);
226 }
227 // validate multiplying a point at infinity by zero produces a point at infinity
228 {
229 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
230 op_queue->eq_and_reset();
231 op_queue->merge();
232
233 ECCVMCircuitBuilder circuit{ op_queue };
234 bool result = ECCVMTraceChecker::check(circuit);
235 EXPECT_EQ(result, true);
236 }
237 // validate an MSM made entirely of points at infinity / zero scalars produces a point at infinity
238 {
239 op_queue->mul_accumulate(point_at_infinity, x);
240 op_queue->mul_accumulate(b, zero_scalar);
241 op_queue->eq_and_reset();
242 op_queue->merge();
243
244 ECCVMCircuitBuilder circuit{ op_queue };
245 bool result = ECCVMTraceChecker::check(circuit);
246 EXPECT_EQ(result, true);
247 }
248}
249
250TEST(ECCVMCircuitBuilderTests, ShortMul)
251{
253
254 auto generators = G1::derive_generators("test generators", 3);
255
256 typename G1::element a = generators[0];
257 uint256_t small_x = 0;
258 // make sure scalar is less than 127 bits to fit in z1
259 small_x.data[0] = engine.get_random_uint64();
260 small_x.data[1] = engine.get_random_uint64() & 0xFFFFFFFFFFFFULL;
261 Fr x = small_x;
262
263 op_queue->mul_accumulate(a, x);
264 op_queue->eq_and_reset();
265 op_queue->merge();
266 add_hiding_op_for_test(op_queue);
267
268 ECCVMCircuitBuilder circuit{ op_queue };
269 bool result = ECCVMTraceChecker::check(circuit, &engine);
270 EXPECT_EQ(result, true);
271}
272
273TEST(ECCVMCircuitBuilderTests, EqFails)
274{
276
277 auto generators = G1::derive_generators("test generators", 3);
278 typename G1::element a = generators[0];
280
281 op_queue->mul_accumulate(a, x);
282 // Tamper with the eq op such that the expected value is incorect
283 op_queue->add_erroneous_equality_op_for_testing();
284 op_queue->merge();
285 add_hiding_op_for_test(op_queue);
286
287 ECCVMCircuitBuilder circuit{ op_queue };
288 bool result = ECCVMTraceChecker::check(circuit, &engine);
289 EXPECT_EQ(result, false);
290}
291
292TEST(ECCVMCircuitBuilderTests, EmptyRow)
293{
295
296 op_queue->empty_row_for_testing();
297 op_queue->merge();
298 add_hiding_op_for_test(op_queue);
299
300 ECCVMCircuitBuilder circuit{ op_queue };
301 bool result = ECCVMTraceChecker::check(circuit, &engine);
302 EXPECT_EQ(result, true);
303}
304
305TEST(ECCVMCircuitBuilderTests, EmptyRowBetweenOps)
306{
308
309 auto generators = G1::derive_generators("test generators", 3);
310 typename G1::element a = generators[0];
312
313 op_queue->mul_accumulate(a, x);
314 op_queue->empty_row_for_testing();
315 op_queue->eq_and_reset();
316 op_queue->merge();
317 add_hiding_op_for_test(op_queue);
318
319 ECCVMCircuitBuilder circuit{ op_queue };
320 bool result = ECCVMTraceChecker::check(circuit, &engine);
321 EXPECT_EQ(result, true);
322}
323
324TEST(ECCVMCircuitBuilderTests, EndWithEq)
325{
327
328 auto generators = G1::derive_generators("test generators", 3);
329 typename G1::element a = generators[0];
331
332 op_queue->mul_accumulate(a, x);
333 op_queue->eq_and_reset();
334 op_queue->merge();
335 add_hiding_op_for_test(op_queue);
336
337 ECCVMCircuitBuilder circuit{ op_queue };
338 bool result = ECCVMTraceChecker::check(circuit, &engine);
339 EXPECT_EQ(result, true);
340}
341
342TEST(ECCVMCircuitBuilderTests, EndWithAdd)
343{
345
346 auto generators = G1::derive_generators("test generators", 3);
347 typename G1::element a = generators[0];
349
350 op_queue->mul_accumulate(a, x);
351 op_queue->eq_and_reset();
352 op_queue->add_accumulate(a);
353 op_queue->merge();
354 add_hiding_op_for_test(op_queue);
355
356 ECCVMCircuitBuilder circuit{ op_queue };
357 bool result = ECCVMTraceChecker::check(circuit, &engine);
358 EXPECT_EQ(result, true);
359}
360
361TEST(ECCVMCircuitBuilderTests, EndWithMul)
362{
364
365 auto generators = G1::derive_generators("test generators", 3);
366 typename G1::element a = generators[0];
368
369 op_queue->add_accumulate(a);
370 op_queue->eq_and_reset();
371 op_queue->mul_accumulate(a, x);
372 op_queue->merge();
373 add_hiding_op_for_test(op_queue);
374
375 ECCVMCircuitBuilder circuit{ op_queue };
376 bool result = ECCVMTraceChecker::check(circuit, &engine);
377 EXPECT_EQ(result, true);
378}
379
380TEST(ECCVMCircuitBuilderTests, EndWithNoop)
381{
383
384 auto generators = G1::derive_generators("test generators", 3);
385 typename G1::element a = generators[0];
387
388 op_queue->add_accumulate(a);
389 op_queue->eq_and_reset();
390 op_queue->mul_accumulate(a, x);
391
392 op_queue->empty_row_for_testing();
393 op_queue->merge();
394 add_hiding_op_for_test(op_queue);
395
396 ECCVMCircuitBuilder circuit{ op_queue };
397 bool result = ECCVMTraceChecker::check(circuit, &engine);
398 EXPECT_EQ(result, true);
399}
400
401TEST(ECCVMCircuitBuilderTests, MSM)
402{
403 static constexpr size_t max_num_msms = 9;
404 auto generators = G1::derive_generators("test generators", max_num_msms);
405
406 const auto compute_msms = [&](const size_t num_msms, auto& op_queue) {
408 std::vector<Fr> scalars;
409 typename G1::element expected = G1::point_at_infinity;
410 for (size_t i = 0; i < num_msms; ++i) {
411 points.emplace_back(generators[i]);
412 scalars.emplace_back(Fr::random_element(&engine));
413 expected += (points[i] * scalars[i]);
414 op_queue->mul_accumulate(points[i], scalars[i]);
415 }
416 op_queue->eq_and_reset();
417 op_queue->merge();
418 };
419
420 // single msms
421 for (size_t j = 1; j < max_num_msms; ++j) {
423
424 compute_msms(j, op_queue);
425 add_hiding_op_for_test(op_queue);
426 ECCVMCircuitBuilder circuit{ op_queue };
427 bool result = ECCVMTraceChecker::check(circuit);
428 EXPECT_EQ(result, true);
429 }
430 // chain msms
432
433 for (size_t j = 1; j < 9; ++j) {
434 compute_msms(j, op_queue);
435 }
436 add_hiding_op_for_test(op_queue);
437 ECCVMCircuitBuilder circuit{ op_queue };
438 bool result = ECCVMTraceChecker::check(circuit, &engine);
439 EXPECT_EQ(result, true);
440}
441
442TEST(ECCVMCircuitBuilderTests, EqAgainstPointAtInfinity)
443{
445
446 auto generators = G1::derive_generators("test generators", 3);
447 typename G1::element a = generators[0];
448 a.self_set_infinity();
449
450 op_queue->add_accumulate(a);
451 op_queue->eq_and_reset();
452 op_queue->merge();
453 add_hiding_op_for_test(op_queue);
454
455 ECCVMCircuitBuilder circuit{ op_queue };
456 bool result = ECCVMTraceChecker::check(circuit);
457 EXPECT_EQ(result, true);
458}
459
460TEST(ECCVMCircuitBuilderTests, AddPointAtInfinity)
461{
463
464 auto generators = G1::derive_generators("test generators", 3);
465 typename G1::element a = generators[0];
466 typename G1::element b = generators[0];
467 b.self_set_infinity();
468
469 op_queue->add_accumulate(a);
470 op_queue->add_accumulate(b);
471 op_queue->eq_and_reset();
472 op_queue->merge();
473 add_hiding_op_for_test(op_queue);
474
475 ECCVMCircuitBuilder circuit{ op_queue };
476 bool result = ECCVMTraceChecker::check(circuit);
477 EXPECT_EQ(result, true);
478}
479
480TEST(ECCVMCircuitBuilderTests, AddProducesPointAtInfinity)
481{
483
484 auto generators = G1::derive_generators("test generators", 3);
485 typename G1::element a = generators[0];
486
487 op_queue->add_accumulate(a);
488 op_queue->add_accumulate(-a);
489 op_queue->eq_and_reset();
490 op_queue->merge();
491 add_hiding_op_for_test(op_queue);
492
493 ECCVMCircuitBuilder circuit{ op_queue };
494 bool result = ECCVMTraceChecker::check(circuit);
495 EXPECT_EQ(result, true);
496}
497
498TEST(ECCVMCircuitBuilderTests, AddProducesDouble)
499{
501
502 auto generators = G1::derive_generators("test generators", 3);
503 typename G1::element a = generators[0];
504
505 op_queue->add_accumulate(a);
506 op_queue->add_accumulate(a);
507 op_queue->eq_and_reset();
508 op_queue->merge();
509 add_hiding_op_for_test(op_queue);
510
511 ECCVMCircuitBuilder circuit{ op_queue };
512 bool result = ECCVMTraceChecker::check(circuit);
513 EXPECT_EQ(result, true);
514}
515
533TEST(ECCVMCircuitBuilderTests, InfinityFailure)
534{
535 using G1 = g1::affine_element;
536 using Fr = fr;
537
538 auto P1 = G1::infinity();
539
540 // Add the same operations to the ECC op queue; the native computation is performed under the hood.
542
543 for (size_t i = 0; i < 1; i++) {
544 op_queue->mul_accumulate(P1, Fr(0));
545 }
546 op_queue->merge();
547 add_hiding_op_for_test(op_queue);
548
549 auto eccvm_builder = ECCVMCircuitBuilder(op_queue);
550
551 // Note: With the hiding op at index 0, the mul op is at index 1, so we check row 2
552 auto transcript_rows = ECCVMTranscriptBuilder::compute_rows(op_queue->get_eccvm_ops(), 1);
553
554 // check that the corresponding op is mul (now at row 2 due to hiding op at row 1)
555 bool row_op_code_correct = transcript_rows[2].opcode == 4;
556 // row.base_x populate the transcript polynomial transcript_Px in ECCVM Flavor
557 bool failure = Fr(transcript_rows[2].base_x) == Fr(0);
558
559 bool circuit_checked = ECCVMTraceChecker::check(eccvm_builder);
560
561 EXPECT_TRUE(failure && row_op_code_correct && circuit_checked);
562}
568TEST(ECCVMCircuitBuilderTests, ScalarEdgeCase)
569{
571
572 auto generators = G1::derive_generators("test generators", 1);
573 typename G1::element a = generators[0];
574
575 // Test with scalar = 2^128 (edge case for scalar decomposition)
576 Fr two_to_the_128 = Fr(uint256_t(1) << 128);
577 op_queue->mul_accumulate(a, two_to_the_128);
578
579 op_queue->merge();
580 add_hiding_op_for_test(op_queue);
581
582 ECCVMCircuitBuilder circuit{ op_queue };
583 bool result = ECCVMTraceChecker::check(circuit, &engine);
584 EXPECT_EQ(result, true);
585}
static bool check(ECCVMCircuitBuilder &, numeric::RNG *engine_ptr=nullptr)
static std::vector< TranscriptRow > compute_rows(const std::vector< ECCVMOperation > &vm_operations, const uint32_t total_number_of_muls)
Computes the ECCVM transcript rows.
bb::fq BaseField
Definition bn254.hpp:19
group_elements::affine_element< Fq, Fr, Params > affine_element
Definition group.hpp:42
static constexpr element point_at_infinity
Definition group.hpp:47
group_elements::element< Fq, Fr, Params > element
Definition group.hpp:41
Fr_ Fr
Definition group.hpp:40
static std::vector< affine_element > derive_generators(const std::vector< uint8_t > &domain_separator_bytes, const size_t num_generators, const size_t starting_index=0)
Derives generator points via hash-to-curve.
Definition group.hpp:87
virtual uint64_t get_random_uint64()=0
FF a
FF b
typename G1::Fr Fr
numeric::RNG & engine
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:190
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
group< fq, fr, Bn254G1Params > g1
Definition g1.hpp:33
field< Bn254FrParams > fr
Definition fr.hpp:174
TEST(BoomerangMegaCircuitBuilder, BasicCircuit)
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
Curve::AffineElement G1
static field random_element(numeric::RNG *engine=nullptr) noexcept