Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
ecc.test.cpp
Go to the documentation of this file.
1#include <cstdio>
2#include <gmock/gmock.h>
3#include <gtest/gtest.h>
4
5#include <cstdint>
6
7#include "barretenberg/vm2/common/aztec_types.hpp"
8#include "barretenberg/vm2/common/field.hpp"
9#include "barretenberg/vm2/constraining/flavor_settings.hpp"
10#include "barretenberg/vm2/constraining/testing/check_relation.hpp"
11#include "barretenberg/vm2/generated/relations/ecc.hpp"
12#include "barretenberg/vm2/generated/relations/lookups_scalar_mul.hpp"
13#include "barretenberg/vm2/simulation/events/ecc_events.hpp"
14#include "barretenberg/vm2/simulation/events/event_emitter.hpp"
15#include "barretenberg/vm2/simulation/events/to_radix_event.hpp"
16#include "barretenberg/vm2/simulation/gadgets/ecc.hpp"
17#include "barretenberg/vm2/simulation/gadgets/memory.hpp"
18#include "barretenberg/vm2/simulation/standalone/pure_gt.hpp"
19#include "barretenberg/vm2/simulation/standalone/pure_memory.hpp"
20#include "barretenberg/vm2/simulation/standalone/pure_to_radix.hpp"
21#include "barretenberg/vm2/simulation/testing/mock_execution.hpp"
22#include "barretenberg/vm2/simulation/testing/mock_execution_id_manager.hpp"
23#include "barretenberg/vm2/simulation/testing/mock_gt.hpp"
24#include "barretenberg/vm2/simulation/testing/mock_memory.hpp"
25#include "barretenberg/vm2/testing/fixtures.hpp"
26#include "barretenberg/vm2/testing/macros.hpp"
27#include "barretenberg/vm2/tracegen/ecc_trace.hpp"
28#include "barretenberg/vm2/tracegen/execution_trace.hpp"
29#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
30#include "barretenberg/vm2/tracegen/to_radix_trace.hpp"
31
32namespace bb::avm2::constraining {
33namespace {
34
35using ::testing::Return;
36using ::testing::StrictMock;
37
38using tracegen::EccTraceBuilder;
39using tracegen::TestTraceContainer;
40using tracegen::ToRadixTraceBuilder;
41
42using FF = AvmFlavorSettings::FF;
43using C = Column;
44using ecc = bb::avm2::ecc<FF>;
45using scalar_mul = bb::avm2::scalar_mul<FF>;
46using mem_aware_ecc = bb::avm2::ecc_mem<FF>;
47using EccSimulator = simulation::Ecc;
48using ToRadixSimulator = simulation::ToRadix;
49
50using simulation::EccAddEvent;
51using simulation::EccAddMemoryEvent;
52using simulation::EventEmitter;
53using simulation::MemoryStore;
54using simulation::MockExecutionIdManager;
55using simulation::MockGreaterThan;
56using simulation::MockMemory;
57using simulation::NoopEventEmitter;
58using simulation::PureGreaterThan;
59using simulation::PureToRadix;
60using simulation::ScalarMulEvent;
61using simulation::ToRadixEvent;
62using simulation::ToRadixMemoryEvent;
63
64// Known good points for P and Q
65FF p_x("0x04c95d1b26d63d46918a156cae92db1bcbc4072a27ec81dc82ea959abdbcf16a");
66FF p_y("0x035b6dd9e63c1370462c74775765d07fc21fd1093cc988149d3aa763bb3dbb60");
67EmbeddedCurvePoint p(p_x, p_y);
68
69FF q_x("0x009242167ec31949c00cbe441cd36757607406e87844fa2c8c4364a4403e66d7");
70FF q_y("0x0fe3016d64cfa8045609f375284b6b739b5fa282e4cbb75cc7f1687ecc7420e3");
71EmbeddedCurvePoint q(q_x, q_y);
72
73TEST(EccAddConstrainingTest, EccEmptyRow)
74{
75 check_relation<ecc>(testing::empty_trace());
76}
77
78TEST(EccAddConstrainingTest, EccAdd)
79{
80 // R = P + Q;
81 FF r_x("0x2b01df0ef6d941a826bea23bece8243cbcdc159d5e97fbaa2171f028e05ba9b6");
82 FF r_y("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
83 EmbeddedCurvePoint r(r_x, r_y);
84
85 auto trace = TestTraceContainer({ {
86 { C::ecc_add_op, 1 },
87 { C::ecc_double_op, 0 },
88
89 { C::ecc_inv_2_p_y, FF::zero() },
90 { C::ecc_inv_x_diff, (q.x() - p.x()).invert() },
91 { C::ecc_inv_y_diff, (q.y() - p.y()).invert() },
92
93 { C::ecc_lambda, (q.y() - p.y()) / (q.x() - p.x()) },
94
95 // Point P
96 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
97 { C::ecc_p_x, p.x() },
98 { C::ecc_p_y, p.y() },
99
100 // Point Q
101 { C::ecc_q_is_inf, static_cast<int>(q.is_infinity()) },
102 { C::ecc_q_x, q.x() },
103 { C::ecc_q_y, q.y() },
104
105 // Resulting Point
106 { C::ecc_r_x, r.x() },
107 { C::ecc_r_y, r.y() },
108
109 { C::ecc_result_infinity, 0 },
110
111 { C::ecc_sel, 1 },
112 { C::ecc_use_computed_result, 1 },
113 { C::ecc_x_match, 0 },
114 { C::ecc_y_match, 0 },
115
116 } });
117
118 check_relation<ecc>(trace);
119}
120
121TEST(EccAddConstrainingTest, EccDouble)
122{
123 // R = P + P;
124 FF r_x("0x088b996194bb5e6e8e5e49733bb671c3e660cf77254f743f366cc8e33534ee3b");
125 FF r_y("0x2807ffa01c0f522d0be1e1acfb6914ac8eabf1acf420c0629d37beee992e9a0e");
126 EmbeddedCurvePoint r(r_x, r_y);
127
128 auto trace = TestTraceContainer({ {
129 { C::ecc_add_op, 0 },
130 { C::ecc_double_op, 1 },
131
132 { C::ecc_inv_2_p_y, (p.y() * 2).invert() },
133 { C::ecc_inv_x_diff, FF::zero() },
134 { C::ecc_inv_y_diff, FF::zero() },
135
136 { C::ecc_lambda, (p.x() * p.x() * 3) / (p.y() * 2) },
137
138 // Point P
139 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
140 { C::ecc_p_x, p.x() },
141 { C::ecc_p_y, p.y() },
142
143 // Point Q set to point p since this is doubling
144 { C::ecc_q_is_inf, static_cast<int>(p.is_infinity()) },
145 { C::ecc_q_x, p.x() },
146 { C::ecc_q_y, p.y() },
147
148 // Resulting Point
149 { C::ecc_r_x, r.x() },
150 { C::ecc_r_y, r.y() },
151
152 { C::ecc_result_infinity, 0 },
153
154 { C::ecc_sel, 1 },
155 { C::ecc_use_computed_result, 1 },
156 { C::ecc_x_match, 1 },
157 { C::ecc_y_match, 1 },
158
159 } });
160
161 check_relation<ecc>(trace);
162}
163
164// Test case for adding two points with different x-coordinates but the same y-coordinate.
165// This edge case exists because cube roots of unity in BN254 Fr allow multiple x values
166// to cube to the same result: if (x, y) is on Grumpkin (y² = x³ - 17), then (ω·x, y)
167// is also on the curve since ω³ = 1.
168//
169// This test uses simulation + tracegen to verify the full pipeline works.
170TEST(EccAddConstrainingTest, EccAddSameYDifferentX)
171{
172 // Point P - known valid point on Grumpkin
173 FF local_p_x("0x04c95d1b26d63d46918a156cae92db1bcbc4072a27ec81dc82ea959abdbcf16a");
174 FF local_p_y("0x035b6dd9e63c1370462c74775765d07fc21fd1093cc988149d3aa763bb3dbb60");
175 EmbeddedCurvePoint local_p(local_p_x, local_p_y);
176
177 // Point Q - p_x * omega (cube root of unity), same y-coordinate!
178 // omega = 0x0000000000000000b3c4d79d41a917585bfc41088d8daaa78b17ea66b99c90dd
179 FF local_q_x("0x14dd39aa19e1c8b29e0c530a28106a7d64d2213486baba3c86dce51bdddf75bb");
180 FF local_q_y("0x035b6dd9e63c1370462c74775765d07fc21fd1093cc988149d3aa763bb3dbb60");
181 EmbeddedCurvePoint local_q(local_q_x, local_q_y);
182
183 // Verify preconditions: same y, different x
184 ASSERT_NE(local_p.x(), local_q.x());
185 ASSERT_EQ(local_p.y(), local_q.y());
186
187 // Expected result R = P + Q (lambda = 0 since y's are equal)
188 FF local_r_x("0x16bdb7ada0799a3088b9dd3faade12c3f79dbfe9cb1234783a1a7add546398dc");
189 FF local_r_y("0x2d08e098faf58cb97223d13f2a1b87dd6614173f3cefe87ca6a74e3034c244a1");
190 EmbeddedCurvePoint local_r(local_r_x, local_r_y);
191
192 // Use simulation to generate events
193 EventEmitter<EccAddEvent> ecc_add_event_emitter;
194 NoopEventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
195 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
196
197 StrictMock<MockExecutionIdManager> execution_id_manager;
198 PureGreaterThan gt;
199 PureToRadix to_radix_simulator;
200 EccSimulator ecc_simulator(execution_id_manager,
201 gt,
202 to_radix_simulator,
203 ecc_add_event_emitter,
204 scalar_mul_event_emitter,
205 ecc_add_memory_event_emitter);
206
207 // Perform the addition via simulation
208 EmbeddedCurvePoint result = ecc_simulator.add(local_p, local_q);
209 ASSERT_EQ(result, local_r) << "Simulation produced wrong result";
210
211 // Build trace from simulation events
212 TestTraceContainer trace;
213 EccTraceBuilder builder;
214 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
215
216 // Verify PIL constraints pass
217 check_relation<ecc>(trace);
218}
219
220TEST(EccAddConstrainingTest, EccAddResultingInInfinity)
221{
222 // R = P + (-P) = O; , where O is the point at infinity
223 EmbeddedCurvePoint q(p.x(), -p.y());
224 EmbeddedCurvePoint r(0, 0);
225
226 auto trace = TestTraceContainer({ {
227 { C::ecc_add_op, 0 },
228 { C::ecc_double_op, 0 },
229
230 { C::ecc_inv_2_p_y, FF::zero() },
231 { C::ecc_inv_x_diff, FF::zero() },
232 { C::ecc_inv_y_diff, (q.y() - p.y()).invert() },
233
234 { C::ecc_lambda, 0 },
235
236 // Point P
237 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
238 { C::ecc_p_x, p.x() },
239 { C::ecc_p_y, p.y() },
240
241 // Point Q
242 { C::ecc_q_is_inf, static_cast<int>(q.is_infinity()) },
243 { C::ecc_q_x, q.x() },
244 { C::ecc_q_y, q.y() },
245
246 // Resulting Point
247 { C::ecc_r_x, r.x() },
248 { C::ecc_r_y, r.y() },
249
250 { C::ecc_result_infinity, 1 },
251
252 { C::ecc_sel, 1 },
253 { C::ecc_x_match, 1 },
254 { C::ecc_y_match, 0 },
255 } });
256
257 check_relation<ecc>(trace);
258}
259
260TEST(EccAddConstrainingTest, EccAddingToInfinity)
261{
262 EmbeddedCurvePoint p(0, 0);
263
264 // R = O + Q = Q; , where O is the point at infinity
265
266 EmbeddedCurvePoint r(q.x(), q.y());
267
268 auto trace = TestTraceContainer({ {
269 { C::ecc_add_op, 1 },
270 { C::ecc_double_op, 0 },
271
272 { C::ecc_inv_2_p_y, FF::zero() },
273 { C::ecc_inv_x_diff, (q.x() - p.x()).invert() },
274 { C::ecc_inv_y_diff, (q.y() - p.y()).invert() },
275
276 { C::ecc_lambda, (q.y() - p.y()) / (q.x() - p.x()) },
277
278 // Point P
279 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
280 { C::ecc_p_x, p.x() },
281 { C::ecc_p_y, p.y() },
282
283 // Point Q
284 { C::ecc_q_is_inf, static_cast<int>(q.is_infinity()) },
285 { C::ecc_q_x, q.x() },
286 { C::ecc_q_y, q.y() },
287
288 // Resulting Point
289 { C::ecc_r_x, r.x() },
290 { C::ecc_r_y, r.y() },
291
292 { C::ecc_result_infinity, 0 },
293
294 { C::ecc_sel, 1 },
295 { C::ecc_x_match, 0 },
296 { C::ecc_y_match, 0 },
297 } });
298
299 check_relation<ecc>(trace);
300}
301
302TEST(EccAddConstrainingTest, EccAddingInfinity)
303{
304 EmbeddedCurvePoint q(0, 0);
305
306 // R = P + O = P; , where O is the point at infinity
307 EmbeddedCurvePoint r(p.x(), p.y());
308
309 auto trace = TestTraceContainer({ {
310 { C::ecc_add_op, 1 },
311 { C::ecc_double_op, 0 },
312
313 { C::ecc_inv_2_p_y, (p.y() * 2).invert() },
314 { C::ecc_inv_x_diff, (q.x() - p.x()).invert() },
315 { C::ecc_inv_y_diff, (q.y() - p.y()).invert() },
316
317 { C::ecc_lambda, (q.y() - p.y()) / (q.x() - p.x()) },
318
319 // Point P
320 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
321 { C::ecc_p_x, p.x() },
322 { C::ecc_p_y, p.y() },
323
324 // Point Q
325 { C::ecc_q_is_inf, static_cast<int>(q.is_infinity()) },
326 { C::ecc_q_x, q.x() },
327 { C::ecc_q_y, q.y() },
328
329 // Resulting Point
330 { C::ecc_r_x, r.x() },
331 { C::ecc_r_y, r.y() },
332
333 { C::ecc_result_infinity, 0 },
334
335 { C::ecc_sel, 1 },
336 { C::ecc_x_match, 0 },
337 { C::ecc_y_match, 0 },
338
339 } });
340
341 check_relation<ecc>(trace);
342}
343
344TEST(EccAddConstrainingTest, EccDoublingInf)
345{
346 EmbeddedCurvePoint p(0, 0);
347
348 // r = O + O = O; , where O is the point at infinity
349 EmbeddedCurvePoint r(0, 0);
350
351 auto trace = TestTraceContainer({ {
352 { C::ecc_add_op, 0 },
353 { C::ecc_double_op, 1 },
354
355 { C::ecc_inv_2_p_y, FF::zero() },
356 { C::ecc_inv_x_diff, FF::zero() },
357 { C::ecc_inv_y_diff, FF::zero() },
358
359 { C::ecc_lambda, FF::zero() },
360
361 // Point P
362 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
363 { C::ecc_p_x, p.x() },
364 { C::ecc_p_y, p.y() },
365
366 // Point Q
367 { C::ecc_q_is_inf, static_cast<int>(p.is_infinity()) },
368 { C::ecc_q_x, p.x() },
369 { C::ecc_q_y, p.y() },
370
371 // Resulting Point
372 { C::ecc_r_x, r.x() },
373 { C::ecc_r_y, r.y() },
374
375 { C::ecc_result_infinity, 1 },
376
377 { C::ecc_sel, 1 },
378 { C::ecc_x_match, 1 },
379 { C::ecc_y_match, 1 },
380
381 } });
382
383 check_relation<ecc>(trace);
384}
385
386TEST(EccAddConstrainingTest, EccTwoOps)
387{
388 EmbeddedCurvePoint r1 = p + q;
389 EmbeddedCurvePoint r2 = r1 + r1;
390
391 auto trace = TestTraceContainer({ {
392 { C::ecc_add_op, 1 },
393 { C::ecc_double_op, 0 },
394
395 { C::ecc_inv_2_p_y, FF::zero() },
396 { C::ecc_inv_x_diff, (q.x() - p.x()).invert() },
397 { C::ecc_inv_y_diff, (q.y() - p.y()).invert() },
398
399 { C::ecc_lambda, (q.y() - p.y()) / (q.x() - p.x()) },
400
401 // Point P
402 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
403 { C::ecc_p_x, p.x() },
404 { C::ecc_p_y, p.y() },
405
406 // Point Q
407 { C::ecc_q_is_inf, static_cast<int>(q.is_infinity()) },
408 { C::ecc_q_x, q.x() },
409 { C::ecc_q_y, q.y() },
410
411 // Resulting Point
412 { C::ecc_r_x, r1.x() },
413 { C::ecc_r_y, r1.y() },
414
415 { C::ecc_result_infinity, 0 },
416
417 { C::ecc_sel, 1 },
418 { C::ecc_use_computed_result, 1 },
419 { C::ecc_x_match, 0 },
420 { C::ecc_y_match, 0 },
421
422 },
423 {
424 { C::ecc_add_op, 0 },
425 { C::ecc_double_op, 1 },
426
427 { C::ecc_inv_2_p_y, (r1.y() * 2).invert() },
428 { C::ecc_inv_x_diff, FF::zero() },
429 { C::ecc_inv_y_diff, FF::zero() },
430
431 { C::ecc_lambda, (r1.x() * r1.x() * 3) / (r1.y() * 2) },
432
433 // Point P
434 { C::ecc_p_is_inf, static_cast<int>(r1.is_infinity()) },
435 { C::ecc_p_x, r1.x() },
436 { C::ecc_p_y, r1.y() },
437
438 // Point Q set to point p since this is doubling
439 { C::ecc_q_is_inf, static_cast<int>(r1.is_infinity()) },
440 { C::ecc_q_x, r1.x() },
441 { C::ecc_q_y, r1.y() },
442
443 // Resulting Point
444 { C::ecc_r_x, r2.x() },
445 { C::ecc_r_y, r2.y() },
446
447 { C::ecc_result_infinity, 0 },
448
449 { C::ecc_sel, 1 },
450 { C::ecc_use_computed_result, 1 },
451 { C::ecc_x_match, 1 },
452 { C::ecc_y_match, 1 },
453
454 } });
455
456 check_relation<ecc>(trace);
457}
458
459TEST(EccAddConstrainingTest, EccNegativeBadAdd)
460{
461 // R != P + Q;
462
463 FF r_x("0x20f096ae3de9aea007e0b94a0274b2443d6682d1901f6909f284ec967bc169be");
464 FF r_y("0x27948713833bb314e828f2b6f45f408da6564a3ac03b9e430a9c6634bb849ef2");
465 EmbeddedCurvePoint r(r_x, r_y);
466
467 auto trace = TestTraceContainer({ {
468 { C::ecc_add_op, 1 },
469 { C::ecc_double_op, 0 },
470
471 { C::ecc_inv_2_p_y, FF::zero() },
472 { C::ecc_inv_x_diff, (q.x() - p.x()).invert() },
473 { C::ecc_inv_y_diff, (q.y() - p.y()).invert() },
474
475 { C::ecc_lambda, (q.y() - p.y()) / (q.x() - p.x()) },
476
477 // Point P
478 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
479 { C::ecc_p_x, p.x() },
480 { C::ecc_p_y, p.y() },
481
482 // Point Q
483 { C::ecc_q_is_inf, static_cast<int>(q.is_infinity()) },
484 { C::ecc_q_x, q.x() },
485 { C::ecc_q_y, q.y() },
486
487 // Resulting Point
488 { C::ecc_r_x, r.x() },
489 { C::ecc_r_y, r.y() },
490
491 { C::ecc_result_infinity, 0 },
492
493 { C::ecc_sel, 1 },
494 { C::ecc_x_match, 0 },
495 { C::ecc_y_match, 0 },
496
497 } });
498
499 EXPECT_THROW_WITH_MESSAGE(check_relation<ecc>(trace, ecc::SR_OUTPUT_X_COORD), "OUTPUT_X_COORD");
500}
501
502TEST(EccAddConstrainingTest, EccNegativeBadDouble)
503{
504 // R != P + P;
505
506 FF r_x("0x2b01df0ef6d941a826bea23bece8243cbcdc159d5e97fbaa2171f028e05ba9b6");
507 FF r_y("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
508 EmbeddedCurvePoint r(r_x, r_y);
509
510 auto trace = TestTraceContainer({ {
511 { C::ecc_add_op, 0 },
512 { C::ecc_double_op, 1 },
513
514 { C::ecc_inv_2_p_y, (p.y() * 2).invert() },
515 { C::ecc_inv_x_diff, FF::zero() },
516 { C::ecc_inv_y_diff, FF::zero() },
517
518 { C::ecc_lambda, (p.x() * p.x() * 3) / (p.y() * 2) },
519
520 // Point P
521 { C::ecc_p_is_inf, static_cast<int>(p.is_infinity()) },
522 { C::ecc_p_x, p.x() },
523 { C::ecc_p_y, p.y() },
524
525 // Point Q set to point p since this is doubling
526 { C::ecc_q_is_inf, static_cast<int>(p.is_infinity()) },
527 { C::ecc_q_x, p.x() },
528 { C::ecc_q_y, p.y() },
529
530 // Resulting Point
531 { C::ecc_r_x, r.x() },
532 { C::ecc_r_y, r.y() },
533
534 { C::ecc_result_infinity, 0 },
535
536 { C::ecc_sel, 1 },
537 { C::ecc_x_match, 1 },
538 { C::ecc_y_match, 1 },
539
540 } });
541
542 EXPECT_THROW_WITH_MESSAGE(check_relation<ecc>(trace, ecc::SR_OUTPUT_X_COORD), "OUTPUT_X_COORD");
543}
544
545TEST(ScalarMulConstrainingTest, ScalarMulEmptyRow)
546{
547 check_relation<scalar_mul>(testing::empty_trace());
548}
549
550TEST(ScalarMulConstrainingTest, MulByOne)
551{
552 EccTraceBuilder builder;
553
554 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
555 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
556 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
557
558 StrictMock<MockExecutionIdManager> execution_id_manager;
559 StrictMock<MockGreaterThan> gt;
560 PureToRadix to_radix_simulator = PureToRadix();
561 EccSimulator ecc_simulator(execution_id_manager,
562 gt,
563 to_radix_simulator,
564 ecc_add_event_emitter,
565 scalar_mul_event_emitter,
566 ecc_add_memory_event_emitter);
567
568 FF scalar = FF(1);
569 ecc_simulator.scalar_mul(p, scalar);
570
571 TestTraceContainer trace({
572 { { C::precomputed_first_row, 1 } },
573 });
574
575 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
576 EXPECT_EQ(trace.get_num_rows(), /*start_row=*/1 + 254);
577 check_relation<scalar_mul>(trace);
578}
579
580TEST(ScalarMulConstrainingTest, BasicMul)
581{
582 EccTraceBuilder builder;
583
584 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
585 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
586 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
587
588 StrictMock<MockExecutionIdManager> execution_id_manager;
589 StrictMock<MockGreaterThan> gt;
590 PureToRadix to_radix_simulator = PureToRadix();
591 EccSimulator ecc_simulator(execution_id_manager,
592 gt,
593 to_radix_simulator,
594 ecc_add_event_emitter,
595 scalar_mul_event_emitter,
596 ecc_add_memory_event_emitter);
597
598 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
599 ecc_simulator.scalar_mul(p, scalar);
600
601 TestTraceContainer trace({
602 { { C::precomputed_first_row, 1 } },
603 });
604
605 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
606 EXPECT_EQ(trace.get_num_rows(), /*start_row=*/1 + 254);
607 check_relation<scalar_mul>(trace);
608}
609
610// Edge case: Verify that 0 * P = infinity (point at infinity)
611TEST(ScalarMulConstrainingTest, MulByZero)
612{
613 EccTraceBuilder builder;
614
615 EventEmitter<EccAddEvent> ecc_add_event_emitter;
616 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
617 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
618
619 StrictMock<MockExecutionIdManager> execution_id_manager;
620 StrictMock<MockGreaterThan> gt;
621 PureToRadix to_radix_simulator = PureToRadix();
622 EccSimulator ecc_simulator(execution_id_manager,
623 gt,
624 to_radix_simulator,
625 ecc_add_event_emitter,
626 scalar_mul_event_emitter,
627 ecc_add_memory_event_emitter);
628
629 // Multiply by zero - result should be point at infinity
630 FF scalar = FF(0);
631 EmbeddedCurvePoint result = ecc_simulator.scalar_mul(p, scalar);
632
633 // Verify result is infinity
634 ASSERT_TRUE(result.is_infinity());
635
636 TestTraceContainer trace({
637 { { C::precomputed_first_row, 1 } },
638 });
639
640 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
641 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
642
643 EXPECT_EQ(trace.get_num_rows(), /*start_row=*/1 + 254);
644 check_relation<scalar_mul>(trace);
645 check_relation<ecc>(trace);
646}
647
648// Edge case: Verify scalar multiplication works with a large scalar near field modulus
649TEST(ScalarMulConstrainingTest, MulByLargeScalar)
650{
651 EccTraceBuilder builder;
652
653 EventEmitter<EccAddEvent> ecc_add_event_emitter;
654 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
655 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
656
657 StrictMock<MockExecutionIdManager> execution_id_manager;
658 StrictMock<MockGreaterThan> gt;
659 PureToRadix to_radix_simulator = PureToRadix();
660 EccSimulator ecc_simulator(execution_id_manager,
661 gt,
662 to_radix_simulator,
663 ecc_add_event_emitter,
664 scalar_mul_event_emitter,
665 ecc_add_memory_event_emitter);
666
667 // Use a large scalar (p - 1, where p is the field modulus)
668 // BN254 scalar field modulus - 1: 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000000
669 FF scalar = FF("0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593efffffff");
670 EmbeddedCurvePoint result = ecc_simulator.scalar_mul(p, scalar);
671
672 // Verify result is a valid point (not infinity for non-zero scalar with non-infinity point)
673 // The exact result depends on the scalar and point, but it should be deterministic
674 EmbeddedCurvePoint expected_result = p * Fq(scalar);
675 EXPECT_EQ(result, expected_result);
676
677 TestTraceContainer trace({
678 { { C::precomputed_first_row, 1 } },
679 });
680
681 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
682 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
683
684 // Note: Row count varies based on number of ECC operations (depends on scalar bit pattern)
685 check_relation<scalar_mul>(trace);
686 check_relation<ecc>(trace);
687}
688
689TEST(ScalarMulConstrainingTest, MultipleInvocations)
690{
691 EccTraceBuilder builder;
692
693 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
694 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
695 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
696
697 StrictMock<MockExecutionIdManager> execution_id_manager;
698 StrictMock<MockGreaterThan> gt;
699 PureToRadix to_radix_simulator = PureToRadix();
700 EccSimulator ecc_simulator(execution_id_manager,
701 gt,
702 to_radix_simulator,
703 ecc_add_event_emitter,
704 scalar_mul_event_emitter,
705 ecc_add_memory_event_emitter);
706
707 ecc_simulator.scalar_mul(p, FF("0x2b01df0ef6d941a826bea23bece8243cbcdc159d5e97fbaa2171f028e05ba9b6"));
708 ecc_simulator.scalar_mul(q, FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09"));
709
710 TestTraceContainer trace({
711 { { C::precomputed_first_row, 1 } },
712 });
713
714 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
715 EXPECT_EQ(trace.get_num_rows(), /*start_row=*/1 + (254) * 2);
716 check_relation<scalar_mul>(trace);
717}
718
719TEST(ScalarMulConstrainingTest, MulInteractions)
720{
721 EccTraceBuilder builder;
722
723 EventEmitter<EccAddEvent> ecc_add_event_emitter;
724 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
725 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
726 EventEmitter<ToRadixEvent> to_radix_event_emitter;
727 NoopEventEmitter<ToRadixMemoryEvent> to_radix_mem_event_emitter;
728
729 StrictMock<MockExecutionIdManager> execution_id_manager;
730 StrictMock<MockGreaterThan> gt;
731 ToRadixSimulator to_radix_simulator(execution_id_manager, gt, to_radix_event_emitter, to_radix_mem_event_emitter);
732 EccSimulator ecc_simulator(execution_id_manager,
733 gt,
734 to_radix_simulator,
735 ecc_add_event_emitter,
736 scalar_mul_event_emitter,
737 ecc_add_memory_event_emitter);
738
739 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
740 ecc_simulator.scalar_mul(p, scalar);
741
742 TestTraceContainer trace({
743 { { C::precomputed_first_row, 1 } },
744 });
745
746 ToRadixTraceBuilder to_radix_builder;
747 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
748 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
749 to_radix_builder.process(to_radix_event_emitter.dump_events(), trace);
750
751 check_interaction<EccTraceBuilder,
752 lookup_scalar_mul_double_settings,
753 lookup_scalar_mul_add_settings,
754 lookup_scalar_mul_to_radix_settings>(trace);
755}
756
757TEST(ScalarMulConstrainingTest, MulAddInteractionsInfinity)
758{
759 EccTraceBuilder builder;
760
761 EventEmitter<EccAddEvent> ecc_add_event_emitter;
762 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
763 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
764
765 StrictMock<MockExecutionIdManager> execution_id_manager;
766 StrictMock<MockGreaterThan> gt;
767 PureToRadix to_radix_simulator = PureToRadix();
768 EccSimulator ecc_simulator(execution_id_manager,
769 gt,
770 to_radix_simulator,
771 ecc_add_event_emitter,
772 scalar_mul_event_emitter,
773 ecc_add_memory_event_emitter);
774
775 EmbeddedCurvePoint inf = EmbeddedCurvePoint::infinity();
776
777 EmbeddedCurvePoint inf_bb = EmbeddedCurvePoint(avm2::AffinePoint::infinity());
778
779 EmbeddedCurvePoint result = ecc_simulator.scalar_mul(inf_bb, FF(10));
780 ASSERT_TRUE(result.is_infinity());
781 EXPECT_EQ(result.x(), inf.x());
782 EXPECT_EQ(result.y(), inf.y());
783
784 TestTraceContainer trace({
785 { { C::precomputed_first_row, 1 } },
786 });
787
788 auto scalar_mul_events = scalar_mul_event_emitter.dump_events();
789 // Infinity points should be normalised to (0, 0) for any lookups into ecc.pil
790 for (auto& event : scalar_mul_events) {
791 EXPECT_EQ(event.point.x(), inf.x());
792 EXPECT_EQ(event.point.y(), inf.y());
793 }
794
795 builder.process_scalar_mul(scalar_mul_events, trace);
796 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
797
798 check_interaction<EccTraceBuilder, lookup_scalar_mul_double_settings, lookup_scalar_mul_add_settings>(trace);
799
800 check_relation<scalar_mul>(trace);
801 check_relation<ecc>(trace);
802}
803
804TEST(ScalarMulConstrainingTest, NegativeMulAddInteractions)
805{
806 EccTraceBuilder builder;
807
808 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
809 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
810 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
811
812 StrictMock<MockExecutionIdManager> execution_id_manager;
813 StrictMock<MockGreaterThan> gt;
814 PureToRadix to_radix_simulator = PureToRadix();
815 EccSimulator ecc_simulator(execution_id_manager,
816 gt,
817 to_radix_simulator,
818 ecc_add_event_emitter,
819 scalar_mul_event_emitter,
820 ecc_add_memory_event_emitter);
821
822 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
823 ecc_simulator.scalar_mul(p, scalar);
824
825 TestTraceContainer trace({
826 { { C::precomputed_first_row, 1 } },
827 });
828
829 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
830
831 EXPECT_THROW_WITH_MESSAGE((check_interaction<EccTraceBuilder, lookup_scalar_mul_double_settings>(trace)),
832 "Failed.*SCALAR_MUL_DOUBLE. Could not find tuple in destination.");
833 EXPECT_THROW_WITH_MESSAGE((check_interaction<EccTraceBuilder, lookup_scalar_mul_add_settings>(trace)),
834 "Failed.*SCALAR_MUL_ADD. Could not find tuple in destination.");
835}
836
837TEST(ScalarMulConstrainingTest, NegativeMulRadixInteractions)
838{
839 EccTraceBuilder builder;
840
841 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
842 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
843 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
844
845 StrictMock<MockExecutionIdManager> execution_id_manager;
846 StrictMock<MockGreaterThan> gt;
847 PureToRadix to_radix_simulator = PureToRadix();
848 EccSimulator ecc_simulator(execution_id_manager,
849 gt,
850 to_radix_simulator,
851 ecc_add_event_emitter,
852 scalar_mul_event_emitter,
853 ecc_add_memory_event_emitter);
854
855 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
856 ecc_simulator.scalar_mul(p, scalar);
857
858 TestTraceContainer trace({
859 { { C::precomputed_first_row, 1 } },
860 });
861
862 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
863
864 EXPECT_THROW_WITH_MESSAGE((check_interaction<EccTraceBuilder, lookup_scalar_mul_to_radix_settings>(trace)),
865 "Failed.*SCALAR_MUL_TO_RADIX. Could not find tuple in destination.");
866
867 check_relation<scalar_mul>(trace);
868}
869
870TEST(ScalarMulConstrainingTest, NegativeDisableSel)
871{
872 EccTraceBuilder builder;
873
874 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
875 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
876 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
877
878 StrictMock<MockExecutionIdManager> execution_id_manager;
879 StrictMock<MockGreaterThan> gt;
880 PureToRadix to_radix_simulator = PureToRadix();
881 EccSimulator ecc_simulator(execution_id_manager,
882 gt,
883 to_radix_simulator,
884 ecc_add_event_emitter,
885 scalar_mul_event_emitter,
886 ecc_add_memory_event_emitter);
887
888 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
889 ecc_simulator.scalar_mul(p, scalar);
890
891 TestTraceContainer trace({
892 { { C::precomputed_first_row, 1 } },
893 });
894
895 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
896 // Disable the selector in one of the rows between start and end
897 trace.set(Column::scalar_mul_sel, 5, 0);
898 EXPECT_THROW_WITH_MESSAGE(check_relation<scalar_mul>(trace, scalar_mul::SR_TRACE_CONTINUITY), "TRACE_CONTINUITY");
899}
900
901TEST(ScalarMulConstrainingTest, NegativeEnableStartFirstRow)
902{
903 EccTraceBuilder builder;
904
905 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
906 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
907 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
908
909 StrictMock<MockExecutionIdManager> execution_id_manager;
910 StrictMock<MockGreaterThan> gt;
911 PureToRadix to_radix_simulator = PureToRadix();
912 EccSimulator ecc_simulator(execution_id_manager,
913 gt,
914 to_radix_simulator,
915 ecc_add_event_emitter,
916 scalar_mul_event_emitter,
917 ecc_add_memory_event_emitter);
918
919 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
920 ecc_simulator.scalar_mul(p, scalar);
921
922 TestTraceContainer trace({
923 { { C::precomputed_first_row, 1 } },
924 });
925
926 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
927 // Enable the start in the first row
928 trace.set(Column::scalar_mul_start, 0, 1);
929 EXPECT_THROW_WITH_MESSAGE(check_relation<scalar_mul>(trace, scalar_mul::SR_SEL_ON_START_OR_END),
930 "SEL_ON_START_OR_END");
931}
932
933TEST(ScalarMulConstrainingTest, NegativeMutateScalarOnEnd)
934{
935 EccTraceBuilder builder;
936
937 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
938 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
939 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
940
941 StrictMock<MockExecutionIdManager> execution_id_manager;
942 StrictMock<MockGreaterThan> gt;
943 PureToRadix to_radix_simulator = PureToRadix();
944 EccSimulator ecc_simulator(execution_id_manager,
945 gt,
946 to_radix_simulator,
947 ecc_add_event_emitter,
948 scalar_mul_event_emitter,
949 ecc_add_memory_event_emitter);
950
951 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
952 ecc_simulator.scalar_mul(p, scalar);
953
954 TestTraceContainer trace({
955 { { C::precomputed_first_row, 1 } },
956 });
957
958 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
959 // Mutate the scalar on the end row
960 trace.set(Column::scalar_mul_scalar, 254, 27);
961 EXPECT_THROW_WITH_MESSAGE(check_relation<scalar_mul>(trace, scalar_mul::SR_INPUT_CONSISTENCY_SCALAR),
962 "INPUT_CONSISTENCY_SCALAR");
963}
964
965TEST(ScalarMulConstrainingTest, NegativeMutatePointXOnEnd)
966{
967 EccTraceBuilder builder;
968
969 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
970 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
971 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
972
973 StrictMock<MockExecutionIdManager> execution_id_manager;
974 StrictMock<MockGreaterThan> gt;
975 PureToRadix to_radix_simulator = PureToRadix();
976 EccSimulator ecc_simulator(execution_id_manager,
977 gt,
978 to_radix_simulator,
979 ecc_add_event_emitter,
980 scalar_mul_event_emitter,
981 ecc_add_memory_event_emitter);
982
983 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
984 ecc_simulator.scalar_mul(p, scalar);
985
986 TestTraceContainer trace({
987 { { C::precomputed_first_row, 1 } },
988 });
989
990 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
991 // Mutate the point on the end row
992 trace.set(Column::scalar_mul_point_x, 254, q.x());
993
994 EXPECT_THROW_WITH_MESSAGE(check_relation<scalar_mul>(trace, scalar_mul::SR_INPUT_CONSISTENCY_X),
995 "INPUT_CONSISTENCY_X");
996}
997
998TEST(ScalarMulConstrainingTest, NegativeMutatePointYOnEnd)
999{
1000 EccTraceBuilder builder;
1001
1002 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
1003 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
1004 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
1005
1006 StrictMock<MockExecutionIdManager> execution_id_manager;
1007 StrictMock<MockGreaterThan> gt;
1008 PureToRadix to_radix_simulator = PureToRadix();
1009 EccSimulator ecc_simulator(execution_id_manager,
1010 gt,
1011 to_radix_simulator,
1012 ecc_add_event_emitter,
1013 scalar_mul_event_emitter,
1014 ecc_add_memory_event_emitter);
1015
1016 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
1017 ecc_simulator.scalar_mul(p, scalar);
1018
1019 TestTraceContainer trace({
1020 { { C::precomputed_first_row, 1 } },
1021 });
1022
1023 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
1024 // Mutate the point on the end row
1025 trace.set(Column::scalar_mul_point_y, 254, q.y());
1026
1027 EXPECT_THROW_WITH_MESSAGE(check_relation<scalar_mul>(trace, scalar_mul::SR_INPUT_CONSISTENCY_Y),
1028 "INPUT_CONSISTENCY_Y");
1029}
1030
1031TEST(ScalarMulConstrainingTest, NegativeMutatePointInfOnEnd)
1032{
1033 EccTraceBuilder builder;
1034
1035 NoopEventEmitter<EccAddEvent> ecc_add_event_emitter;
1036 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
1037 NoopEventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
1038
1039 StrictMock<MockExecutionIdManager> execution_id_manager;
1040 StrictMock<MockGreaterThan> gt;
1041 PureToRadix to_radix_simulator = PureToRadix();
1042 EccSimulator ecc_simulator(execution_id_manager,
1043 gt,
1044 to_radix_simulator,
1045 ecc_add_event_emitter,
1046 scalar_mul_event_emitter,
1047 ecc_add_memory_event_emitter);
1048
1049 FF scalar = FF("0x0cc4c71e882bc62b7b3d1964a8540cb5211339dfcddd2e095fd444bf1aed4f09");
1050 ecc_simulator.scalar_mul(p, scalar);
1051
1052 TestTraceContainer trace({
1053 { { C::precomputed_first_row, 1 } },
1054 });
1055
1056 builder.process_scalar_mul(scalar_mul_event_emitter.dump_events(), trace);
1057 // Mutate the point on the end row
1058 trace.set(Column::scalar_mul_point_inf, 254, 1);
1059
1060 EXPECT_THROW_WITH_MESSAGE(check_relation<scalar_mul>(trace, scalar_mul::SR_INPUT_CONSISTENCY_INF),
1061 "INPUT_CONSISTENCY_INF");
1062}
1063
1065// Memory Aware Ecc Add
1067
1068TEST(EccAddMemoryConstrainingTest, EccAddMemoryEmptyRow)
1069{
1070 check_relation<mem_aware_ecc>(testing::empty_trace());
1071}
1072
1073TEST(EccAddMemoryConstrainingTest, EccAddMemory)
1074{
1075 TestTraceContainer trace;
1076 EccTraceBuilder builder;
1077 MemoryStore memory;
1078
1079 EventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
1080 EventEmitter<EccAddEvent> ecc_add_event_emitter;
1081 NoopEventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
1082 NoopEventEmitter<ToRadixEvent> to_radix_event_emitter;
1083
1084 StrictMock<MockExecutionIdManager> execution_id_manager;
1085 EXPECT_CALL(execution_id_manager, get_execution_id)
1086 .WillRepeatedly(Return(0)); // Use a fixed execution IDfor the test
1087 PureGreaterThan gt;
1088 PureToRadix to_radix_simulator = PureToRadix();
1089 EccSimulator ecc_simulator(execution_id_manager,
1090 gt,
1091 to_radix_simulator,
1092 ecc_add_event_emitter,
1093 scalar_mul_event_emitter,
1094 ecc_add_memory_event_emitter);
1095
1096 MemoryAddress dst_address = 5;
1097 ecc_simulator.add(memory, p, q, dst_address);
1098 builder.process_add_with_memory(ecc_add_memory_event_emitter.dump_events(), trace);
1099 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
1100
1101 check_relation<mem_aware_ecc>(trace);
1102}
1103
1104TEST(EccAddMemoryConstrainingTest, EccAddMemoryInteractions)
1105{
1106
1107 EccTraceBuilder builder;
1108 MemoryStore memory;
1109
1110 StrictMock<MockExecutionIdManager> execution_id_manager;
1111 EXPECT_CALL(execution_id_manager, get_execution_id)
1112 .WillRepeatedly(Return(0)); // Use a fixed execution IDfor the test
1113 PureGreaterThan gt;
1114 PureToRadix to_radix_simulator = PureToRadix();
1115
1116 EventEmitter<EccAddEvent> ecc_add_event_emitter;
1117 NoopEventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
1118 EventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
1119 NoopEventEmitter<ToRadixEvent> to_radix_event_emitter;
1120 EccSimulator ecc_simulator(execution_id_manager,
1121 gt,
1122 to_radix_simulator,
1123 ecc_add_event_emitter,
1124 scalar_mul_event_emitter,
1125 ecc_add_memory_event_emitter);
1126
1127 EmbeddedCurvePoint result = p + q;
1128
1129 uint32_t dst_address = 0x1000;
1130 // Set the execution and gt traces
1131 TestTraceContainer trace = TestTraceContainer({
1132 // Row 0
1133 {
1134 // Execution
1135 { C::execution_sel, 1 },
1136 { C::execution_sel_exec_dispatch_ecc_add, 1 },
1137 { C::execution_rop_4_, dst_address },
1138 { C::execution_register_0_, p.x() },
1139 { C::execution_register_1_, p.y() },
1140 { C::execution_register_2_, q.x() },
1141 { C::execution_register_3_, q.y() },
1142 // GT - dst out of range check
1143 { C::gt_sel, 1 },
1144 { C::gt_input_a, dst_address + 1 }, // highest write address is dst_address + 1
1145 { C::gt_input_b, AVM_HIGHEST_MEM_ADDRESS },
1146 { C::gt_res, 0 },
1147 // Memory Writes
1148 { C::memory_address, dst_address },
1149 { C::memory_value, result.x() },
1150 { C::memory_sel, 1 },
1151 { C::memory_rw, 1 }, // write
1152 { C::memory_tag, static_cast<uint8_t>(MemoryTag::FF) },
1153 },
1154 {
1155 // Memory Writes
1156 { C::memory_address, dst_address + 1 },
1157 { C::memory_value, result.y() },
1158 { C::memory_sel, 1 },
1159 { C::memory_rw, 1 }, // write
1160 { C::memory_tag, static_cast<uint8_t>(MemoryTag::FF) },
1161 },
1162 });
1163
1164 ecc_simulator.add(memory, p, q, dst_address);
1165
1166 builder.process_add_with_memory(ecc_add_memory_event_emitter.dump_events(), trace);
1167 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
1168
1169 check_all_interactions<EccTraceBuilder>(trace);
1170 check_relation<mem_aware_ecc>(trace);
1171}
1172
1173TEST(EccAddMemoryConstrainingTest, EccAddMemoryInvalidDstRange)
1174{
1175
1176 EccTraceBuilder builder;
1177 MemoryStore memory;
1178
1179 NoopEventEmitter<ToRadixEvent> to_radix_event_emitter;
1180 EventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
1181 EventEmitter<EccAddEvent> ecc_add_event_emitter;
1182 NoopEventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
1183
1184 StrictMock<MockExecutionIdManager> execution_id_manager;
1185 EXPECT_CALL(execution_id_manager, get_execution_id)
1186 .WillRepeatedly(Return(0)); // Use a fixed execution ID for the test
1187 PureGreaterThan gt;
1188 PureToRadix to_radix_simulator = PureToRadix();
1189
1190 EccSimulator ecc_simulator(execution_id_manager,
1191 gt,
1192 to_radix_simulator,
1193 ecc_add_event_emitter,
1194 scalar_mul_event_emitter,
1195 ecc_add_memory_event_emitter);
1196
1197 uint32_t dst_address = AVM_HIGHEST_MEM_ADDRESS; // Invalid address, will result in out of range error
1198 // Set the execution and gt traces
1199 TestTraceContainer trace = TestTraceContainer({
1200 // Row 0
1201 {
1202 // Execution
1203 { C::execution_sel, 1 },
1204 { C::execution_sel_exec_dispatch_ecc_add, 1 },
1205 { C::execution_rop_4_, dst_address },
1206 { C::execution_register_0_, p.x() },
1207 { C::execution_register_1_, p.y() },
1208 { C::execution_register_2_, q.x() },
1209 { C::execution_register_3_, q.y() },
1210 { C::execution_sel_opcode_error, 1 },
1211 // GT - dst out of range check
1212 { C::gt_sel, 1 },
1213 { C::gt_input_a, static_cast<uint64_t>(dst_address) + 1 },
1214 { C::gt_input_b, AVM_HIGHEST_MEM_ADDRESS },
1215 { C::gt_res, 1 },
1216 },
1217 });
1218
1219 EXPECT_THROW_WITH_MESSAGE(ecc_simulator.add(memory, p, q, dst_address), "EccException.* dst address out of range");
1220
1221 builder.process_add_with_memory(ecc_add_memory_event_emitter.dump_events(), trace);
1222 EXPECT_EQ(ecc_add_event_emitter.get_events().size(), 0); // Expect 0 add events since error in ecc_mem
1223
1224 check_all_interactions<EccTraceBuilder>(trace);
1225 check_relation<mem_aware_ecc>(trace);
1226}
1227
1228TEST(EccAddMemoryConstrainingTest, EccAddMemoryPointError)
1229{
1230
1231 EccTraceBuilder builder;
1232 MemoryStore memory;
1233 EventEmitter<EccAddEvent> ecc_add_event_emitter;
1234 NoopEventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
1235 EventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
1236
1237 StrictMock<MockExecutionIdManager> execution_id_manager;
1238 EXPECT_CALL(execution_id_manager, get_execution_id)
1239 .WillRepeatedly(Return(0)); // Use a fixed execution IDfor the test
1240 PureGreaterThan gt;
1241 PureToRadix to_radix_simulator = PureToRadix();
1242
1243 EccSimulator ecc_simulator(execution_id_manager,
1244 gt,
1245 to_radix_simulator,
1246 ecc_add_event_emitter,
1247 scalar_mul_event_emitter,
1248 ecc_add_memory_event_emitter);
1249
1250 // Point P is not on the curve
1251 FF p_x("0x0000000000063d46918a156cae92db1bcbc4072a27ec81dc82ea959abdbcf16a");
1252 FF p_y("0x00000000000c1370462c74775765d07fc21fd1093cc988149d3aa763bb3dbb60");
1253 EmbeddedCurvePoint p(p_x, p_y);
1254
1255 uint32_t dst_address = 0x1000;
1256
1257 EXPECT_CALL(execution_id_manager, get_execution_id()).WillOnce(::testing::Return(0));
1258 // Set the execution and gt traces
1259 TestTraceContainer trace = TestTraceContainer({
1260 // Row 0
1261 {
1262 // Execution
1263 { C::execution_sel, 1 },
1264 { C::execution_sel_exec_dispatch_ecc_add, 1 },
1265 { C::execution_rop_4_, dst_address },
1266 { C::execution_register_0_, p.x() },
1267 { C::execution_register_1_, p.y() },
1268 { C::execution_register_2_, q.x() },
1269 { C::execution_register_3_, q.y() },
1270 { C::execution_sel_opcode_error, 1 }, // Indicate an error in the operation
1271 // GT - dst out of range check
1272 { C::gt_sel, 1 },
1273 { C::gt_input_a, dst_address + 1 }, // highest write address is dst_address + 1
1274 { C::gt_input_b, AVM_HIGHEST_MEM_ADDRESS },
1275 { C::gt_res, 0 },
1276 },
1277 });
1278
1279 EXPECT_THROW(ecc_simulator.add(memory, p, q, dst_address), simulation::EccException);
1280
1281 builder.process_add_with_memory(ecc_add_memory_event_emitter.dump_events(), trace);
1282 // Expect no events to be emitted since the operation failed
1283 EXPECT_EQ(ecc_add_event_emitter.get_events().size(), 0);
1284
1285 check_all_interactions<EccTraceBuilder>(trace);
1286 check_relation<mem_aware_ecc>(trace);
1287}
1288
1289TEST(EccAddMemoryConstrainingTest, InfinityRepresentations)
1290{
1291 EccTraceBuilder builder;
1292 MemoryStore memory;
1293
1294 EventEmitter<EccAddEvent> ecc_add_event_emitter;
1295 EventEmitter<ScalarMulEvent> scalar_mul_event_emitter;
1296 EventEmitter<EccAddMemoryEvent> ecc_add_memory_event_emitter;
1297
1298 StrictMock<MockExecutionIdManager> execution_id_manager;
1299 EXPECT_CALL(execution_id_manager, get_execution_id)
1300 .WillRepeatedly(Return(0)); // Use a fixed execution ID for the test
1301 PureGreaterThan gt;
1302 PureToRadix to_radix_simulator = PureToRadix();
1303 EccSimulator ecc_simulator(execution_id_manager,
1304 gt,
1305 to_radix_simulator,
1306 ecc_add_event_emitter,
1307 scalar_mul_event_emitter,
1308 ecc_add_memory_event_emitter);
1309 MemoryAddress dst_address = 5;
1310
1311 // Point P is infinity
1312 EmbeddedCurvePoint inf = EmbeddedCurvePoint::infinity();
1313 // EmbeddedCurvePoint always sets extractable coordinates as (0,0) and the underlying point as
1314 // AffinePoint::infinity() for input infinity points.
1315 EmbeddedCurvePoint inf_bb = EmbeddedCurvePoint(avm2::AffinePoint::infinity());
1316 EXPECT_EQ(inf_bb, inf);
1317 TestTraceContainer trace;
1318
1319 // The circuit correctly assigns double_op = true when doubling inf:
1320 ecc_simulator.add(memory, inf, inf_bb, dst_address);
1321
1322 builder.process_add(ecc_add_event_emitter.dump_events(), trace);
1323 check_relation<ecc>(trace);
1324 EXPECT_EQ(trace.get(C::ecc_double_op, 0), 1);
1325
1326 ecc_simulator.add(memory, inf, inf_bb, dst_address);
1327
1328 // Set memory reads:
1329 trace.set(0,
1330 { { // Execution
1331 { C::execution_sel, 1 },
1332 { C::execution_sel_exec_dispatch_ecc_add, 1 },
1333 { C::execution_rop_6_, dst_address + 3 },
1334 { C::execution_register_0_, inf.x() },
1335 { C::execution_register_1_, inf.y() },
1336 { C::execution_register_2_, inf.is_infinity() ? 1 : 0 },
1337 { C::execution_register_3_, inf_bb.x() },
1338 { C::execution_register_4_, inf_bb.y() },
1339 { C::execution_register_5_, inf_bb.is_infinity() ? 1 : 0 },
1340 // GT - dst out of range check
1341 { C::gt_sel, 1 },
1342 { C::gt_input_a, dst_address + 2 },
1343 { C::gt_input_b, AVM_HIGHEST_MEM_ADDRESS },
1344 { C::gt_res, 0 } } });
1345
1346 builder.process_add_with_memory(ecc_add_memory_event_emitter.dump_events(), trace);
1347
1348 // The derived is_inf column must be true if the coordinates are (0, 0):
1349 trace.set(C::ecc_add_mem_p_is_inf, 0, 0);
1350 EXPECT_THROW_WITH_MESSAGE(check_relation<mem_aware_ecc>(trace, mem_aware_ecc::SR_P_CURVE_EQN), "P_CURVE_EQN");
1351
1352 // If is_inf is set, the coordinates must be (0, 0):
1353 trace.set(C::ecc_add_mem_q_x, 0, 1);
1354 trace.set(C::ecc_add_mem_q_y, 0, 2);
1355 EXPECT_THROW_WITH_MESSAGE(check_relation<mem_aware_ecc>(trace, mem_aware_ecc::SR_Q_INF_X_CHECK), "Q_INF_X_CHECK");
1356 EXPECT_THROW_WITH_MESSAGE(check_relation<mem_aware_ecc>(trace, mem_aware_ecc::SR_Q_INF_Y_CHECK), "Q_INF_Y_CHECK");
1357}
1358
1359} // namespace
1360} // namespace bb::avm2::constraining
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessageRegex)
Definition assert.hpp:193
AVM_HIGHEST_MEM_ADDRESS
#define AVM_HIGHEST_MEM_ADDRESS
Definition aztec_constants.hpp:44
aztec_types.hpp
check_relation.hpp
bb::avm2::ecc_mem
Definition ecc_mem.hpp:35
bb::avm2::ecc::SR_OUTPUT_X_COORD
static constexpr size_t SR_OUTPUT_X_COORD
Definition ecc.hpp:45
bb::avm2::scalar_mul
Definition scalar_mul.hpp:34
bb::avm2::scalar_mul::SR_INPUT_CONSISTENCY_X
static constexpr size_t SR_INPUT_CONSISTENCY_X
Definition scalar_mul.hpp:42
bb::avm2::scalar_mul::SR_TRACE_CONTINUITY
static constexpr size_t SR_TRACE_CONTINUITY
Definition scalar_mul.hpp:40
bb::avm2::scalar_mul::SR_INPUT_CONSISTENCY_INF
static constexpr size_t SR_INPUT_CONSISTENCY_INF
Definition scalar_mul.hpp:44
bb::avm2::scalar_mul::SR_INPUT_CONSISTENCY_Y
static constexpr size_t SR_INPUT_CONSISTENCY_Y
Definition scalar_mul.hpp:43
bb::avm2::scalar_mul::SR_SEL_ON_START_OR_END
static constexpr size_t SR_SEL_ON_START_OR_END
Definition scalar_mul.hpp:39
bb::avm2::scalar_mul::SR_INPUT_CONSISTENCY_SCALAR
static constexpr size_t SR_INPUT_CONSISTENCY_SCALAR
Definition scalar_mul.hpp:45
bb::avm2::tracegen::AluTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::AluEvent >::Container &events, TraceContainer &trace)
Process the ALU events and populate the ALU relevant columns in the trace.
Definition alu_trace.cpp:410
bb::avm2::tracegen::TraceContainer::get
const FF & get(Column col, uint32_t row) const
Definition trace_container.cpp:23
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:39
bb::group_elements::affine_element::infinity
static constexpr affine_element infinity()
Definition affine_element_impl.hpp:80
builder
AluTraceBuilder builder
Definition alu.test.cpp:124
execution_id_manager
ExecutionIdManager execution_id_manager
Definition data_copy.test.cpp:51
gt
GreaterThan gt
Definition data_copy.test.cpp:56
trace
TestTraceContainer trace
Definition data_copy.test.cpp:63
expected_result
bool expected_result
Definition field_gt.test.cpp:54
ecc_events.hpp
ecc_trace.hpp
event_emitter.hpp
execution_trace.hpp
flavor_settings.hpp
lookups_scalar_mul.hpp
mock_execution.hpp
mock_execution_id_manager.hpp
mock_gt.hpp
mock_memory.hpp
bb::avm2::constraining::check_interaction
void check_interaction(tracegen::TestTraceContainer &trace)
Definition check_relation.hpp:77
bb::avm2::constraining::TEST
TEST(AvmFixedVKTests, FixedVKCommitments)
Test that the fixed VK commitments agree with the ones computed from precomputed columns.
Definition avm_fixed_vk.test.cpp:52
bb::avm2::testing::empty_trace
TestTraceContainer empty_trace()
Definition fixtures.cpp:153
bb::avm2::lookup_scalar_mul_double_settings
lookup_settings< lookup_scalar_mul_double_settings_ > lookup_scalar_mul_double_settings
Definition lookups_scalar_mul.hpp:65
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
bb::avm2::EmbeddedCurvePoint
StandardAffinePoint< AvmFlavorSettings::EmbeddedCurve::AffineElement > EmbeddedCurvePoint
Definition field.hpp:12
bb::avm2::Fq
AvmFlavorSettings::G1::Fq Fq
Definition field.hpp:11
bb::avm2::lookup_scalar_mul_to_radix_settings
lookup_settings< lookup_scalar_mul_to_radix_settings_ > lookup_scalar_mul_to_radix_settings
Definition lookups_scalar_mul.hpp:38
bb::avm2::lookup_scalar_mul_add_settings
lookup_settings< lookup_scalar_mul_add_settings_ > lookup_scalar_mul_add_settings
Definition lookups_scalar_mul.hpp:93
bb::avm2::MemoryAddress
uint32_t MemoryAddress
Definition memory_types.hpp:11
event
simulation::PublicDataTreeReadWriteEvent event
Definition public_data_tree_trace.cpp:33
pure_gt.hpp
pure_memory.hpp
pure_to_radix.hpp
memory
MemoryStore memory
Definition keccakf1600.test.cpp:36
test_trace_container.hpp
to_radix_event.hpp
to_radix_trace.hpp