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.
1#include "barretenberg/crypto/generators/generator_data.hpp"
2#include "barretenberg/crypto/pedersen_commitment/pedersen.hpp"
3#include "barretenberg/eccvm/eccvm_flavor.hpp"
4#include "barretenberg/eccvm/eccvm_trace_checker.hpp"
5#include <gtest/gtest.h>
6
7using namespace bb;
8using G1 = bb::g1;
9using Fr = typename G1::Fr;
10
11namespace {
12auto& engine = numeric::get_debug_randomness();
13} // namespace
14
15TEST(ECCVMCircuitBuilderTests, BaseCase)
16{
17 auto generators = G1::derive_generators("test generators", 3);
18 typename G1::element a = generators[0];
19 typename G1::element b = generators[1];
20 typename G1::element c = generators[2];
21 typename G1::element point_at_infinity = G1::point_at_infinity;
22 Fr x = Fr::random_element(&engine);
23 Fr y = Fr::random_element(&engine);
24 Fr zero_scalar = 0;
25
26 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
27
28 op_queue->add_accumulate(a);
29 op_queue->mul_accumulate(a, x);
30 op_queue->mul_accumulate(b, x);
31 op_queue->mul_accumulate(b, y);
32 op_queue->add_accumulate(a);
33 op_queue->mul_accumulate(b, x);
34 op_queue->add_accumulate(b);
35 op_queue->eq_and_reset();
36 op_queue->add_accumulate(c);
37 op_queue->mul_accumulate(a, x);
38 op_queue->mul_accumulate(point_at_infinity, x);
39 op_queue->mul_accumulate(b, x);
40 op_queue->eq_and_reset();
41 op_queue->mul_accumulate(a, x);
42 op_queue->mul_accumulate(b, x);
43 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
44 op_queue->mul_accumulate(c, x);
45 op_queue->eq_and_reset();
46 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
47 op_queue->mul_accumulate(point_at_infinity, x);
48 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
49 op_queue->add_accumulate(a);
50 op_queue->eq_and_reset();
51 op_queue->add_accumulate(a);
52 op_queue->add_accumulate(point_at_infinity);
53 op_queue->eq_and_reset();
54 op_queue->add_accumulate(point_at_infinity);
55 op_queue->eq_and_reset();
56 op_queue->mul_accumulate(point_at_infinity, x);
57 op_queue->mul_accumulate(point_at_infinity, -x);
58 op_queue->eq_and_reset();
59 op_queue->add_accumulate(a);
60 op_queue->mul_accumulate(point_at_infinity, x);
61 op_queue->mul_accumulate(point_at_infinity, -x);
62 op_queue->add_accumulate(a);
63 op_queue->add_accumulate(a);
64 op_queue->eq_and_reset();
65 op_queue->merge();
66 ECCVMCircuitBuilder circuit{ op_queue };
67 bool result = ECCVMTraceChecker::check(circuit);
68 EXPECT_EQ(result, true);
69}
70
71TEST(ECCVMCircuitBuilderTests, NoOp)
72{
73 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
74
75 ECCVMCircuitBuilder circuit{ op_queue };
76 bool result = ECCVMTraceChecker::check(circuit, &engine);
77 EXPECT_EQ(result, true);
78}
79
80TEST(ECCVMCircuitBuilderTests, Add)
81{
82 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
83
84 auto generators = G1::derive_generators("test generators", 3);
85 typename G1::element a = generators[0];
86
87 op_queue->add_accumulate(a);
88 op_queue->merge();
89
90 ECCVMCircuitBuilder circuit{ op_queue };
91 bool result = ECCVMTraceChecker::check(circuit, &engine);
92 EXPECT_EQ(result, true);
93}
94
95TEST(ECCVMCircuitBuilderTests, Mul)
96{
97 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
98
99 auto generators = G1::derive_generators("test generators", 3);
100 typename G1::element a = generators[0];
101 Fr x = Fr::random_element(&engine);
102
103 op_queue->mul_accumulate(a, x);
104 op_queue->merge();
105
106 ECCVMCircuitBuilder circuit{ op_queue };
107 bool result = ECCVMTraceChecker::check(circuit, &engine);
108 EXPECT_EQ(result, true);
109}
110
111TEST(ECCVMCircuitBuilderTests, MulInfinity)
112{
113 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
114
115 auto generators = G1::derive_generators("test generators", 3);
116 typename G1::element a = generators[0];
117 Fr x = Fr::random_element(&engine);
118 G1::element b = -a * x;
119 // G1::affine_element c = G1::affine_point_at_infinity;
120 op_queue->add_accumulate(b);
121 op_queue->mul_accumulate(a, x);
122 op_queue->eq_and_reset();
123 op_queue->merge();
124
125 ECCVMCircuitBuilder circuit{ op_queue };
126 bool result = ECCVMTraceChecker::check(circuit);
127 EXPECT_EQ(result, true);
128}
129
130// Validate we do not trigger edge cases of addition formulae when we have identical mul inputs
131TEST(ECCVMCircuitBuilderTests, MulOverIdenticalInputs)
132{
133 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
134
135 auto generators = G1::derive_generators("test generators", 3);
136 typename G1::element a = generators[0];
137 Fr x = Fr::random_element(&engine);
138 op_queue->mul_accumulate(a, x);
139 op_queue->mul_accumulate(a, x);
140 op_queue->eq_and_reset();
141 op_queue->merge();
142
143 ECCVMCircuitBuilder circuit{ op_queue };
144 bool result = ECCVMTraceChecker::check(circuit);
145 EXPECT_EQ(result, true);
146}
147
148TEST(ECCVMCircuitBuilderTests, MSMProducesInfinity)
149{
150 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
151
152 auto generators = G1::derive_generators("test generators", 3);
153 typename G1::element a = generators[0];
154 Fr x = Fr::random_element(&engine);
155 op_queue->add_accumulate(a);
156 op_queue->mul_accumulate(a, x);
157 op_queue->mul_accumulate(a, -x);
158 op_queue->eq_and_reset();
159 op_queue->merge();
160
161 ECCVMCircuitBuilder circuit{ op_queue };
162 bool result = ECCVMTraceChecker::check(circuit);
163 EXPECT_EQ(result, true);
164}
165
166TEST(ECCVMCircuitBuilderTests, MSMOverPointAtInfinity)
167{
168 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
169
170 auto generators = G1::derive_generators("test generators", 3);
171 typename G1::element point_at_infinity = G1::point_at_infinity;
172 typename G1::element b = generators[0];
173 Fr x = Fr::random_element(&engine);
174 Fr zero_scalar = 0;
175
176 // validate including points at infinity in a multiscalar multiplication does not effect result
177 {
178 op_queue->mul_accumulate(b, x);
179 op_queue->mul_accumulate(point_at_infinity, x);
180 op_queue->eq_and_reset();
181 op_queue->merge();
182
183 ECCVMCircuitBuilder circuit{ op_queue };
184 bool result = ECCVMTraceChecker::check(circuit);
185 EXPECT_EQ(result, true);
186 }
187 // validate multiplying a point at infinity by nonzero scalar produces point at infinity
188 {
189 op_queue->mul_accumulate(point_at_infinity, x);
190 op_queue->eq_and_reset();
191 op_queue->merge();
192
193 ECCVMCircuitBuilder circuit{ op_queue };
194 bool result = ECCVMTraceChecker::check(circuit);
195 EXPECT_EQ(result, true);
196 }
197 // validate multiplying a point by zero produces point at infinity
198 {
199 op_queue->mul_accumulate(b, zero_scalar);
200 op_queue->eq_and_reset();
201 op_queue->merge();
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 zero produces a point at infinity
208 {
209 op_queue->mul_accumulate(point_at_infinity, zero_scalar);
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 an MSM made entirely of points at infinity / zero scalars produces a point at infinity
218 {
219 op_queue->mul_accumulate(point_at_infinity, x);
220 op_queue->mul_accumulate(b, zero_scalar);
221 op_queue->eq_and_reset();
222 op_queue->merge();
223
224 ECCVMCircuitBuilder circuit{ op_queue };
225 bool result = ECCVMTraceChecker::check(circuit);
226 EXPECT_EQ(result, true);
227 }
228}
229
230TEST(ECCVMCircuitBuilderTests, ShortMul)
231{
232 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
233
234 auto generators = G1::derive_generators("test generators", 3);
235
236 typename G1::element a = generators[0];
237 uint256_t small_x = 0;
238 // make sure scalar is less than 127 bits to fit in z1
239 small_x.data[0] = engine.get_random_uint64();
240 small_x.data[1] = engine.get_random_uint64() & 0xFFFFFFFFFFFFULL;
241 Fr x = small_x;
242
243 op_queue->mul_accumulate(a, x);
244 op_queue->eq_and_reset();
245 op_queue->merge();
246
247 ECCVMCircuitBuilder circuit{ op_queue };
248 bool result = ECCVMTraceChecker::check(circuit, &engine);
249 EXPECT_EQ(result, true);
250}
251
252TEST(ECCVMCircuitBuilderTests, EqFails)
253{
254 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
255
256 auto generators = G1::derive_generators("test generators", 3);
257 typename G1::element a = generators[0];
258 Fr x = Fr::random_element(&engine);
259
260 op_queue->mul_accumulate(a, x);
261 // Tamper with the eq op such that the expected value is incorect
262 op_queue->add_erroneous_equality_op_for_testing();
263 op_queue->merge();
264
265 ECCVMCircuitBuilder circuit{ op_queue };
266 bool result = ECCVMTraceChecker::check(circuit, &engine);
267 EXPECT_EQ(result, false);
268}
269
270TEST(ECCVMCircuitBuilderTests, EmptyRow)
271{
272 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
273
274 op_queue->empty_row_for_testing();
275 op_queue->merge();
276
277 ECCVMCircuitBuilder circuit{ op_queue };
278 bool result = ECCVMTraceChecker::check(circuit, &engine);
279 EXPECT_EQ(result, true);
280}
281
282TEST(ECCVMCircuitBuilderTests, EmptyRowBetweenOps)
283{
284 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
285
286 auto generators = G1::derive_generators("test generators", 3);
287 typename G1::element a = generators[0];
288 Fr x = Fr::random_element(&engine);
289
290 op_queue->mul_accumulate(a, x);
291 op_queue->empty_row_for_testing();
292 op_queue->eq_and_reset();
293 op_queue->merge();
294
295 ECCVMCircuitBuilder circuit{ op_queue };
296 bool result = ECCVMTraceChecker::check(circuit, &engine);
297 EXPECT_EQ(result, true);
298}
299
300TEST(ECCVMCircuitBuilderTests, EndWithEq)
301{
302 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
303
304 auto generators = G1::derive_generators("test generators", 3);
305 typename G1::element a = generators[0];
306 Fr x = Fr::random_element(&engine);
307
308 op_queue->mul_accumulate(a, x);
309 op_queue->eq_and_reset();
310 op_queue->merge();
311
312 ECCVMCircuitBuilder circuit{ op_queue };
313 bool result = ECCVMTraceChecker::check(circuit, &engine);
314 EXPECT_EQ(result, true);
315}
316
317TEST(ECCVMCircuitBuilderTests, EndWithAdd)
318{
319 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
320
321 auto generators = G1::derive_generators("test generators", 3);
322 typename G1::element a = generators[0];
323 Fr x = Fr::random_element(&engine);
324
325 op_queue->mul_accumulate(a, x);
326 op_queue->eq_and_reset();
327 op_queue->add_accumulate(a);
328 op_queue->merge();
329
330 ECCVMCircuitBuilder circuit{ op_queue };
331 bool result = ECCVMTraceChecker::check(circuit, &engine);
332 EXPECT_EQ(result, true);
333}
334
335TEST(ECCVMCircuitBuilderTests, EndWithMul)
336{
337 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
338
339 auto generators = G1::derive_generators("test generators", 3);
340 typename G1::element a = generators[0];
341 Fr x = Fr::random_element(&engine);
342
343 op_queue->add_accumulate(a);
344 op_queue->eq_and_reset();
345 op_queue->mul_accumulate(a, x);
346 op_queue->merge();
347
348 ECCVMCircuitBuilder circuit{ op_queue };
349 bool result = ECCVMTraceChecker::check(circuit, &engine);
350 EXPECT_EQ(result, true);
351}
352
353TEST(ECCVMCircuitBuilderTests, EndWithNoop)
354{
355 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
356
357 auto generators = G1::derive_generators("test generators", 3);
358 typename G1::element a = generators[0];
359 Fr x = Fr::random_element(&engine);
360
361 op_queue->add_accumulate(a);
362 op_queue->eq_and_reset();
363 op_queue->mul_accumulate(a, x);
364
365 op_queue->empty_row_for_testing();
366 op_queue->merge();
367
368 ECCVMCircuitBuilder circuit{ op_queue };
369 bool result = ECCVMTraceChecker::check(circuit, &engine);
370 EXPECT_EQ(result, true);
371}
372
373TEST(ECCVMCircuitBuilderTests, MSM)
374{
375 static constexpr size_t max_num_msms = 9;
376 auto generators = G1::derive_generators("test generators", max_num_msms);
377
378 const auto compute_msms = [&](const size_t num_msms, auto& op_queue) {
379 std::vector<typename G1::element> points;
380 std::vector<Fr> scalars;
381 typename G1::element expected = G1::point_at_infinity;
382 for (size_t i = 0; i < num_msms; ++i) {
383 points.emplace_back(generators[i]);
384 scalars.emplace_back(Fr::random_element(&engine));
385 expected += (points[i] * scalars[i]);
386 op_queue->mul_accumulate(points[i], scalars[i]);
387 }
388 op_queue->eq_and_reset();
389 op_queue->merge();
390 };
391
392 // single msms
393 for (size_t j = 1; j < max_num_msms; ++j) {
394 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
395
396 compute_msms(j, op_queue);
397 ECCVMCircuitBuilder circuit{ op_queue };
398 bool result = ECCVMTraceChecker::check(circuit);
399 EXPECT_EQ(result, true);
400 }
401 // chain msms
402 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
403
404 for (size_t j = 1; j < 9; ++j) {
405 compute_msms(j, op_queue);
406 }
407 ECCVMCircuitBuilder circuit{ op_queue };
408 bool result = ECCVMTraceChecker::check(circuit, &engine);
409 EXPECT_EQ(result, true);
410}
411
412TEST(ECCVMCircuitBuilderTests, EqAgainstPointAtInfinity)
413{
414 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
415
416 auto generators = G1::derive_generators("test generators", 3);
417 typename G1::element a = generators[0];
418 a.self_set_infinity();
419
420 op_queue->add_accumulate(a);
421 op_queue->eq_and_reset();
422 op_queue->merge();
423
424 ECCVMCircuitBuilder circuit{ op_queue };
425 bool result = ECCVMTraceChecker::check(circuit);
426 EXPECT_EQ(result, true);
427}
428
429TEST(ECCVMCircuitBuilderTests, AddPointAtInfinity)
430{
431 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
432
433 auto generators = G1::derive_generators("test generators", 3);
434 typename G1::element a = generators[0];
435 typename G1::element b = generators[0];
436 b.self_set_infinity();
437
438 op_queue->add_accumulate(a);
439 op_queue->add_accumulate(b);
440 op_queue->eq_and_reset();
441 op_queue->merge();
442
443 ECCVMCircuitBuilder circuit{ op_queue };
444 bool result = ECCVMTraceChecker::check(circuit);
445 EXPECT_EQ(result, true);
446}
447
448TEST(ECCVMCircuitBuilderTests, AddProducesPointAtInfinity)
449{
450 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
451
452 auto generators = G1::derive_generators("test generators", 3);
453 typename G1::element a = generators[0];
454
455 op_queue->add_accumulate(a);
456 op_queue->add_accumulate(-a);
457 op_queue->eq_and_reset();
458 op_queue->merge();
459
460 ECCVMCircuitBuilder circuit{ op_queue };
461 bool result = ECCVMTraceChecker::check(circuit);
462 EXPECT_EQ(result, true);
463}
464
465TEST(ECCVMCircuitBuilderTests, AddProducesDouble)
466{
467 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
468
469 auto generators = G1::derive_generators("test generators", 3);
470 typename G1::element a = generators[0];
471
472 op_queue->add_accumulate(a);
473 op_queue->add_accumulate(a);
474 op_queue->eq_and_reset();
475 op_queue->merge();
476
477 ECCVMCircuitBuilder circuit{ op_queue };
478 bool result = ECCVMTraceChecker::check(circuit);
479 EXPECT_EQ(result, true);
480}
481
499TEST(ECCVMCircuitBuilderTests, InfinityFailure)
500{
501 using G1 = g1::affine_element;
502 using Fr = fr;
503
504 auto P1 = G1::infinity();
505
506 // Add the same operations to the ECC op queue; the native computation is performed under the hood.
507 std::shared_ptr<ECCOpQueue> op_queue = std::make_shared<ECCOpQueue>();
508
509 for (size_t i = 0; i < 1; i++) {
510 op_queue->mul_accumulate(P1, Fr(0));
511 }
512 op_queue->merge();
513
514 auto eccvm_builder = ECCVMCircuitBuilder(op_queue);
515
516 auto transcript_rows = ECCVMTranscriptBuilder::compute_rows(op_queue->get_eccvm_ops(), 1);
517
518 // check that the corresponding op is mul
519 bool row_op_code_correct = transcript_rows[1].opcode == 4;
520 // row.base_x populate the transcript polynomial transcript_Px in ECCVM Flavor
521 bool failure = Fr(transcript_rows[1].base_x) == Fr(0);
522
523 bool circuit_checked = ECCVMTraceChecker::check(eccvm_builder);
524
525 EXPECT_TRUE(failure && row_op_code_correct && circuit_checked);
526}
bb::ECCVMTraceChecker::check
static bool check(ECCVMCircuitBuilder &, numeric::RNG *engine_ptr=nullptr)
Definition eccvm_trace_checker.cpp:18
bb::ECCVMTranscriptBuilder::compute_rows
static std::vector< TranscriptRow > compute_rows(const std::vector< ECCVMOperation > &vm_operations, const uint32_t total_number_of_muls)
Computes the ECCVM transcript rows.
Definition transcript_builder.hpp:137
bb::group::affine_element
group_elements::affine_element< Fq, Fr, Params > affine_element
Definition group.hpp:42
bb::group::point_at_infinity
static constexpr element point_at_infinity
Definition group.hpp:47
bb::group::element
group_elements::element< Fq, Fr, Params > element
Definition group.hpp:41
bb::group::Fr
Fr_ Fr
Definition group.hpp:40
bb::group::derive_generators
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
bb::numeric::RNG::get_random_uint64
virtual uint64_t get_random_uint64()=0
bb::numeric::uint256_t
Definition uint256.hpp:32
bb::numeric::uint256_t::data
uint64_t data[4]
Definition uint256.hpp:208
a
FF a
Definition field_gt.test.cpp:51
b
FF b
Definition field_gt.test.cpp:52
pedersen.hpp
Fr
typename G1::Fr Fr
Definition eccvm_circuit_builder.test.cpp:9
eccvm_flavor.hpp
eccvm_trace_checker.hpp
engine
numeric::RNG & engine
Definition eccvm_transcript.test.cpp:282
generator_data.hpp
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::g1
group< fq, fr, Bn254G1Params > g1
Definition g1.hpp:33
bb::TEST
TEST(MegaCircuitBuilder, CopyConstructor)
Definition mega_circuit_builder.test.cpp:14
bb::fr
field< Bn254FrParams > fr
Definition fr.hpp:174
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
G1
Curve::AffineElement G1
Definition pippenger.bench.cpp:29
bb::field< Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:665