Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
execution_discard.test.cpp
Go to the documentation of this file.
1#include <gmock/gmock.h>
2#include <gtest/gtest.h>
3
4#include <cstdint>
5
6#include "barretenberg/vm2/constraining/flavor_settings.hpp"
7#include "barretenberg/vm2/constraining/testing/check_relation.hpp"
8#include "barretenberg/vm2/generated/relations/discard.hpp"
9#include "barretenberg/vm2/testing/fixtures.hpp"
10#include "barretenberg/vm2/testing/macros.hpp"
11#include "barretenberg/vm2/tracegen/lib/lookup_builder.hpp"
12#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
13
14namespace bb::avm2::constraining {
15namespace {
16
17using tracegen::TestTraceContainer;
18using FF = AvmFlavorSettings::FF;
19using C = Column;
20using execution_discard = bb::avm2::discard<FF>;
21
22TEST(ExecutionDiscardConstrainingTest, EmptyRow)
23{
24 check_relation<execution_discard>(testing::empty_trace());
25}
26
27TEST(ExecutionDiscardConstrainingTest, DiscardIffDyingContext)
28{
29 // Test that discard=1 <=> dying_context_id!=0
30 TestTraceContainer trace({
31 { { C::precomputed_first_row, 1 } },
32 // discard=0 => dying_context_id=0
33 { { C::execution_sel, 1 },
34 { C::execution_discard, 0 },
35 { C::execution_dying_context_id, 0 },
36 { C::execution_dying_context_id_inv, 0 } },
37 // discard=1 => dying_context_id!=0
38 { { C::execution_sel, 1 },
39 { C::execution_discard, 1 },
40 { C::execution_dying_context_id, 42 },
41 { C::execution_dying_context_id_inv, FF(42).invert() } },
42 { { C::execution_sel, 1 } },
43 { { C::execution_sel, 0 } },
44 });
45
46 // Only check subrelations 3 and 4 (discard/dying_context_id relationship)
47 check_relation<execution_discard>(
48 trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT, execution_discard::SR_DISCARD_IF_FAILURE);
49
50 // Negative test: discard=1 but dying_context_id=0
51 trace.set(C::execution_dying_context_id, 2, 0);
52 trace.set(C::execution_dying_context_id_inv, 2, 0);
53 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT),
54 "DISCARD_IFF_DYING_CONTEXT");
55
56 // Reset before next test
57 trace.set(C::execution_dying_context_id, 1, 0);
58 trace.set(C::execution_dying_context_id_inv, 1, 0);
59 trace.set(C::execution_dying_context_id, 2, 42);
60 trace.set(C::execution_dying_context_id_inv, 2, FF(42).invert());
61
62 // Negative test: discard=0 but dying_context_id!=0
63 trace.set(C::execution_dying_context_id, 1, 42);
64 trace.set(C::execution_dying_context_id_inv, 1, FF(42).invert());
65 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT),
66 "DISCARD_IFF_DYING_CONTEXT");
67}
68
69TEST(ExecutionDiscardConstrainingTest, DiscardFailureMustDiscard)
70{
71 // Test that sel_failure=1 => discard=1
72 TestTraceContainer trace({
73 { { C::precomputed_first_row, 1 } },
74 // Failure with discard
75 { { C::execution_sel, 1 },
76 { C::execution_sel_failure, 1 },
77 { C::execution_discard, 1 },
78 { C::execution_dying_context_id, 42 },
79 { C::execution_dying_context_id_inv, FF(42).invert() } },
80 // No failure, no discard
81 { { C::execution_sel, 1 },
82 { C::execution_sel_failure, 0 },
83 { C::execution_discard, 0 },
84 { C::execution_dying_context_id, 0 },
85 { C::execution_dying_context_id_inv, 0 } },
86 // Discard doesn't imply failure
87 { { C::execution_sel, 1 },
88 { C::execution_sel_failure, 0 },
89 { C::execution_discard, 1 },
90 { C::execution_dying_context_id, 0 } },
91 { { C::execution_sel, 1 } },
92 { { C::execution_sel, 0 } },
93 });
94
95 // Only check subrelation 5 (failure must discard)
96 check_relation<execution_discard>(trace, execution_discard::SR_DISCARD_IF_FAILURE);
97
98 // Negative test: failure but no discard
99 trace.set(C::execution_discard, 1, 0);
100 trace.set(C::execution_dying_context_id, 1, 0);
101 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_DISCARD_IF_FAILURE),
102 "DISCARD_IF_FAILURE");
103}
104
105TEST(ExecutionDiscardConstrainingTest, DiscardIsDyingContextCheck)
106{
107 // Test the is_dying_context calculation
108 TestTraceContainer trace({
109 { { C::precomputed_first_row, 1 } },
110 // context_id=5, dying_context_id=5 => is_dying_context=1
111 { { C::execution_sel, 1 },
112 { C::execution_context_id, 5 },
113 { C::execution_discard, 1 },
114 { C::execution_dying_context_id, 5 },
115 { C::execution_is_dying_context, 1 },
116 { C::execution_dying_context_diff_inv, 0 } },
117 // context_id=3, dying_context_id=5 => is_dying_context=0, diff_inv=(3-5)^(-1)=(-2)^(-1)
118 { { C::execution_sel, 1 },
119 { C::execution_context_id, 3 },
120 { C::execution_discard, 1 },
121 { C::execution_dying_context_id, 5 },
122 { C::execution_dying_context_id_inv, FF(5).invert() },
123 { C::execution_is_dying_context, 0 },
124 { C::execution_dying_context_diff_inv, FF(3 - 5).invert() } },
125 // discard=0 case (is_dying_context should be 0)
126 { { C::execution_sel, 1 },
127 { C::execution_context_id, 7 },
128 { C::execution_discard, 0 },
129 { C::execution_dying_context_id, 0 },
130 { C::execution_is_dying_context, 0 },
131 { C::execution_dying_context_diff_inv, FF(7 - 0).invert() } },
132 { { C::execution_sel, 0 } },
133 });
134
135 check_relation<execution_discard>(trace, execution_discard::SR_IS_DYING_CONTEXT_CHECK);
136
137 // Negative test: wrong is_dying_context when equal
138 trace.set(C::execution_is_dying_context, 1, 0);
139 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_IS_DYING_CONTEXT_CHECK),
140 "IS_DYING_CONTEXT_CHECK");
141
142 // Negative test: wrong is_dying_context when not equal
143 trace.set(C::execution_is_dying_context, 1, 1); // Reset
144 trace.set(C::execution_is_dying_context, 2, 1);
145 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_IS_DYING_CONTEXT_CHECK),
146 "IS_DYING_CONTEXT_CHECK");
147}
148
149TEST(ExecutionDiscardConstrainingTest, DiscardPropagationOfZeroDiscard)
150{
151 TestTraceContainer trace({
152 { { C::precomputed_first_row, 1 } },
153 {
154 { C::execution_sel, 1 },
155 { C::execution_discard, 0 },
156 { C::execution_dying_context_id, 0 },
157 { C::execution_sel_exit_call, 0 },
158 { C::execution_has_parent_ctx, 1 },
159 { C::execution_sel_failure, 0 },
160 { C::execution_is_dying_context, 0 },
161 { C::execution_sel_enter_call, 0 },
162 { C::execution_enqueued_call_end, 0 },
163 },
164 // Propagates to next row
165 { { C::execution_sel, 1 },
166 { C::execution_discard, 0 },
167 { C::execution_dying_context_id, 0 },
168 { C::execution_dying_context_id_inv, 0 },
169 { C::execution_enqueued_call_end, 0 } },
170 // Last row gets propagated discard values. Propagation doesn't apply to next row because last=1.
171 { { C::execution_sel, 1 }, { C::execution_discard, 0 }, { C::execution_dying_context_id, 0 } },
172 { { C::execution_sel, 0 } },
173 });
174
175 check_relation<execution_discard>(
176 trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
177
178 // Negative test: doesn't propagate but it should.
179 trace.set(C::execution_discard, 2, 42);
180 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace,
181 execution_discard::SR_DISCARD_IFF_DYING_CONTEXT,
182 execution_discard::SR_DYING_CONTEXT_PROPAGATION),
183 "DISCARD_IFF_DYING_CONTEXT");
184
185 // Second try: adapt dying_context_id to make SR_DISCARD_IFF_DYING_CONTEXT valid.
186 trace.set(C::execution_dying_context_id, 2, 1);
187 trace.set(C::execution_dying_context_id_inv, 2, 1);
188 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace,
189 execution_discard::SR_DISCARD_IFF_DYING_CONTEXT,
190 execution_discard::SR_DYING_CONTEXT_PROPAGATION),
191 "DYING_CONTEXT_PROPAGATION");
192}
193
194TEST(ExecutionDiscardConstrainingTest, DiscardPropagationOfNonzeroDiscard)
195{
196 TestTraceContainer trace({
197 { { C::precomputed_first_row, 1 } },
198 // Normal propagation case
199 { { C::execution_sel, 1 },
200 { C::execution_discard, 1 },
201 { C::execution_dying_context_id, 42 },
202 { C::execution_dying_context_id_inv, FF(42).invert() },
203 { C::execution_sel_exit_call, 0 },
204 { C::execution_has_parent_ctx, 1 },
205 { C::execution_sel_failure, 0 },
206 { C::execution_is_dying_context, 0 },
207 { C::execution_sel_enter_call, 0 },
208 { C::execution_enqueued_call_end, 0 } },
209 // Propagates to next row
210 { { C::execution_sel, 1 },
211 { C::execution_discard, 1 },
212 { C::execution_dying_context_id, 42 },
213 { C::execution_dying_context_id_inv, FF(42).invert() },
214 { C::execution_enqueued_call_end, 0 } },
215 // Last row gets propagated discard values. Propagation doesn't apply to next row because last=1.
216 { { C::execution_sel, 1 },
217 { C::execution_discard, 1 },
218 { C::execution_dying_context_id, 42 },
219 { C::execution_dying_context_id_inv, FF(42).invert() } },
220 { { C::execution_sel, 0 } },
221 });
222
223 check_relation<execution_discard>(
224 trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
225
226 // Negative test: doesn't propagate but it should.
227 trace.set(C::execution_discard, 2, 0);
228 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace,
229 execution_discard::SR_DISCARD_IFF_DYING_CONTEXT,
230 execution_discard::SR_DYING_CONTEXT_PROPAGATION),
231 "DISCARD_IFF_DYING_CONTEXT");
232
233 // Second try: adapt dying_context_id to make SR_DISCARD_IFF_DYING_CONTEXT valid.
234 trace.set(C::execution_dying_context_id, 2, 0);
235 trace.set(C::execution_dying_context_id_inv, 2, 0);
236 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace,
237 execution_discard::SR_DISCARD_IFF_DYING_CONTEXT,
238 execution_discard::SR_DYING_CONTEXT_PROPAGATION),
239 "DYING_CONTEXT_PROPAGATION");
240}
241
242TEST(ExecutionDiscardConstrainingTest, DiscardPropagationLiftedEndOfEnqueuedCall)
243{
244 // Test propagation lifted at end of enqueued call (exit_call && !has_parent)
245 TestTraceContainer trace({
246 { { C::precomputed_first_row, 1 } },
247 // Exiting top-level call - propagation lifted
248 { { C::execution_sel, 1 },
249 { C::execution_discard, 1 },
250 { C::execution_dying_context_id, 42 },
251 { C::execution_dying_context_id_inv, FF(42).invert() },
252 { C::execution_sel_exit_call, 1 },
253 { C::execution_has_parent_ctx, 0 },
254 { C::execution_enqueued_call_end, 1 } },
255 // Next row can have different discard values
256 { { C::execution_sel, 1 }, { C::execution_discard, 0 }, { C::execution_dying_context_id, 0 } },
257 { { C::execution_sel, 1 } },
258 { { C::execution_sel, 0 } },
259 });
260
261 check_relation<execution_discard>(
262 trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
263}
264
265TEST(ExecutionDiscardConstrainingTest, DiscardPropagationLiftedResolvesDyingContext)
266{
267 // Test propagation lifted when resolving dying context (sel_failure && is_dying_context)
268 TestTraceContainer trace({
269 { { C::precomputed_first_row, 1 } },
270 // Failure in dying context - propagation lifted
271 { { C::execution_sel, 1 },
272 { C::execution_context_id, 42 },
273 { C::execution_discard, 1 },
274 { C::execution_dying_context_id, 42 },
275 { C::execution_dying_context_id_inv, FF(42).invert() },
276 { C::execution_sel_failure, 1 },
277 { C::execution_is_dying_context, 1 },
278 { C::execution_dying_context_diff_inv, 0 },
279 { C::execution_enqueued_call_end, 0 } },
280 // Next row can have different discard values
281 { { C::execution_sel, 1 },
282 { C::execution_discard, 0 },
283 { C::execution_dying_context_id, 0 },
284 { C::execution_enqueued_call_end, 0 } },
285 { { C::execution_sel, 1 } },
286 { { C::execution_sel, 0 } },
287 });
288
289 check_relation<execution_discard>(
290 trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
291}
292
293TEST(ExecutionDiscardConstrainingTest, DiscardPropagationLiftedNestedCallFromUndiscarded)
294{
295 // Test propagation lifted when making nested call from undiscarded context
296 TestTraceContainer trace({
297 { { C::precomputed_first_row, 1 } },
298 // Making a call from undiscarded context - propagation lifted
299 { { C::execution_sel, 1 },
300 { C::execution_discard, 0 },
301 { C::execution_dying_context_id, 0 },
302 { C::execution_sel_enter_call, 1 },
303 { C::execution_enqueued_call_end, 0 } },
304 // Next row can raise discard (nested context will error)
305 { { C::execution_sel, 1 },
306 { C::execution_discard, 1 },
307 { C::execution_dying_context_id, 99 },
308 { C::execution_dying_context_id_inv, FF(99).invert() } },
309 // Last row keeps the values (propagation doesn't apply because last=1)
310 { { C::execution_sel, 1 },
311 { C::execution_discard, 1 },
312 { C::execution_dying_context_id, 99 },
313 { C::execution_dying_context_id_inv, FF(99).invert() } },
314 { { C::execution_sel, 0 } },
315 });
316
317 // This should pass because sel_enter_call=1 lifts the propagation constraint
318 check_relation<execution_discard>(
319 trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
320}
321
322TEST(ExecutionDiscardConstrainingTest, DiscardDyingContextMustError)
323{
324 // Test that dying context must exit with failure
325 TestTraceContainer trace({
326 { { C::precomputed_first_row, 1 } },
327 // Dying context exits with error - OK
328 { { C::execution_sel, 1 },
329 { C::execution_context_id, 42 },
330 { C::execution_discard, 1 },
331 { C::execution_dying_context_id, 42 },
332 { C::execution_is_dying_context, 1 },
333 { C::execution_sel_exit_call, 1 },
334 { C::execution_sel_error, 1 },
335 { C::execution_sel_execute_revert, 0 },
336 { C::execution_sel_failure, 1 },
337 { C::execution_dying_context_diff_inv, 0 } },
338 { { C::execution_sel, 1 } },
339 { { C::execution_sel, 0 } },
340 });
341
342 check_relation<execution_discard>(trace, execution_discard::SR_DYING_CONTEXT_MUST_FAIL);
343
344 // Negative test: dying context exits without error
345 trace.set(C::execution_sel_failure, 1, 0);
346 trace.set(C::execution_sel_error, 1, 0);
347 trace.set(C::execution_sel_execute_revert, 1, 0);
348
349 // As defined in context,pil, sel_exit_call = sel_failure + sel_execute_return; therefore
350 // we must set sel_execute_return to 1 to make the relation valid.
351 trace.set(C::execution_sel_execute_return, 1, 1);
352
353 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_DYING_CONTEXT_MUST_FAIL),
354 "DYING_CONTEXT_MUST_FAIL");
355}
356
357TEST(ExecutionDiscardConstrainingTest, DiscardComplexScenario)
358{
359 // Complex scenario: nested calls with errors
360 TestTraceContainer trace({
361 { { C::precomputed_first_row, 1 } },
362 // Row 1: Parent context, no discard
363 { { C::execution_sel, 1 },
364 { C::execution_context_id, 1 },
365 { C::execution_discard, 0 },
366 { C::execution_dying_context_id, 0 },
367 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
368 { C::execution_is_dying_context, 0 },
369 { C::execution_enqueued_call_end, 0 } },
370 // Row 2: Call to nested context (that will eventually error)
371 { { C::execution_sel, 1 },
372 { C::execution_context_id, 1 },
373 { C::execution_discard, 0 },
374 { C::execution_dying_context_id, 0 },
375 { C::execution_dying_context_id_inv, 0 },
376 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
377 { C::execution_sel_enter_call, 1 },
378 { C::execution_enqueued_call_end, 0 } },
379 // Row 3: Nested context, discard raised because this context will error
380 { { C::execution_sel, 1 },
381 { C::execution_context_id, 2 },
382 { C::execution_discard, 1 },
383 { C::execution_dying_context_id, 2 },
384 { C::execution_dying_context_id_inv, FF(2).invert() },
385 { C::execution_is_dying_context, 1 },
386 { C::execution_dying_context_diff_inv, 0 },
387 { C::execution_enqueued_call_end, 0 } },
388 // Row 4: Nested context errors
389 { { C::execution_sel, 1 },
390 { C::execution_context_id, 2 },
391 { C::execution_discard, 1 },
392 { C::execution_dying_context_id, 2 },
393 { C::execution_dying_context_id_inv, FF(2).invert() },
394 { C::execution_is_dying_context, 1 },
395 { C::execution_sel_exit_call, 1 },
396 { C::execution_sel_error, 1 },
397 { C::execution_sel_execute_revert, 0 },
398 { C::execution_sel_failure, 1 },
399 { C::execution_dying_context_diff_inv, 0 },
400 { C::execution_has_parent_ctx, 1 },
401 { C::execution_enqueued_call_end, 0 } },
402 // Row 5: Back to parent, discard cleared
403 { { C::execution_sel, 1 },
404 { C::execution_context_id, 1 },
405 { C::execution_discard, 0 },
406 { C::execution_dying_context_id, 0 },
407 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
408 { C::execution_is_dying_context, 0 },
409 { C::execution_enqueued_call_end, 0 } },
410 { { C::execution_sel, 0 } },
411 });
412
413 // Only check the most important relations for this scenario
414 check_relation<execution_discard>(trace,
415 execution_discard::SR_IS_DYING_CONTEXT_CHECK,
416 execution_discard::SR_DISCARD_IFF_DYING_CONTEXT,
417 execution_discard::SR_DYING_CONTEXT_PROPAGATION,
418 execution_discard::SR_DYING_CONTEXT_MUST_FAIL);
419}
420
421TEST(ExecutionDiscardConstrainingTest, DiscardWithLastRow)
422{
423 // Test discard behavior with last row
424 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } },
425 { { C::execution_sel, 1 },
426 { C::execution_discard, 1 },
427 { C::execution_dying_context_id, 42 },
428 { C::execution_dying_context_id_inv, FF(42).invert() },
429 { C::execution_enqueued_call_end, 0 } },
430 // Last row also has discard values (propagation doesn't apply because last=1)
431 { { C::execution_sel, 1 },
432 { C::execution_discard, 1 },
433 { C::execution_dying_context_id, 42 },
434 { C::execution_dying_context_id_inv, FF(42).invert() } },
435 { { C::execution_sel, 0 } } });
436
437 check_relation<execution_discard>(
438 trace, execution_discard::SR_DISCARD_IFF_DYING_CONTEXT, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
439}
440
441// ====== EXPLOIT TESTS - These test vulnerabilities found in early versions ======
442
443TEST(ExecutionDiscardConstrainingTest, ExploitRaiseDiscardWithWrongDyingContext)
444{
445 // EXPLOIT 1: A calls B calls C. C fails.
446 // Attacker raises discard when entering B and sets dying context to C.
447 // Then C clears the flag when it fails.
448 // Result on attack success: B's operations are discarded even though B didn't fail.
449 TestTraceContainer trace({
450 { { C::precomputed_first_row, 1 } },
451 // Row 1: Context A (id=1), no discard initially
452 { { C::execution_sel, 1 },
453 { C::execution_context_id, 1 },
454 { C::execution_discard, 0 },
455 { C::execution_dying_context_id, 0 },
456 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
457 { C::execution_is_dying_context, 0 },
458 { C::execution_enqueued_call_end, 0 } },
459 // Row 2: A calls B - ATTACK: raise discard and set dying_context to C (id=3)
460 { { C::execution_sel, 1 },
461 { C::execution_context_id, 1 },
462 { C::execution_discard, 0 },
463 { C::execution_dying_context_id, 0 },
464 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
465 { C::execution_sel_enter_call, 1 },
466 { C::execution_enqueued_call_end, 0 } },
467 // Row 3: Entering B (id=2) - ATTACK: discard raised to 1, dying_context set to 3 (C)
468 { { C::execution_sel, 1 },
469 { C::execution_context_id, 2 },
470 { C::execution_discard, 1 },
471 { C::execution_dying_context_id, 3 },
472 { C::execution_dying_context_id_inv, FF(3).invert() },
473 { C::execution_dying_context_diff_inv, FF(2 - 3).invert() },
474 { C::execution_is_dying_context, 0 },
475 { C::execution_enqueued_call_end, 0 } },
476 // Row 4: B calls C
477 { { C::execution_sel, 1 },
478 { C::execution_context_id, 2 },
479 { C::execution_discard, 1 },
480 { C::execution_dying_context_id, 3 },
481 { C::execution_dying_context_id_inv, FF(3).invert() },
482 { C::execution_dying_context_diff_inv, FF(2 - 3).invert() },
483 { C::execution_is_dying_context, 0 },
484 { C::execution_sel_enter_call, 1 },
485 { C::execution_enqueued_call_end, 0 } },
486 // Row 5: C (id=3) executes and fails - this is the dying context
487 { { C::execution_sel, 1 },
488 { C::execution_context_id, 3 },
489 { C::execution_discard, 1 },
490 { C::execution_dying_context_id, 3 },
491 { C::execution_dying_context_id_inv, FF(3).invert() },
492 { C::execution_dying_context_diff_inv, 0 },
493 { C::execution_is_dying_context, 1 },
494 { C::execution_sel_exit_call, 1 },
495 { C::execution_sel_error, 1 },
496 { C::execution_sel_failure, 1 },
497 { C::execution_has_parent_ctx, 1 },
498 { C::execution_enqueued_call_end, 0 } },
499 // Row 6: Back to B - discard cleared because dying context resolved
500 { { C::execution_sel, 1 },
501 { C::execution_context_id, 2 },
502 { C::execution_discard, 0 },
503 { C::execution_dying_context_id, 0 },
504 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
505 { C::execution_is_dying_context, 0 },
506 { C::execution_enqueued_call_end, 0 } },
507 // Row 7: B exits successfully (no failure)
508 { { C::execution_sel, 1 },
509 { C::execution_context_id, 2 },
510 { C::execution_discard, 0 },
511 { C::execution_dying_context_id, 0 },
512 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
513 { C::execution_sel_exit_call, 1 },
514 { C::execution_sel_error, 0 },
515 { C::execution_sel_failure, 0 },
516 { C::execution_has_parent_ctx, 1 },
517 { C::execution_enqueued_call_end, 0 } },
518 { { C::execution_sel, 1 } },
519 { { C::execution_sel, 0 } },
520 });
521
522 // If the exploit works, this check will pass.
523 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace), "ENTER_CALL_DISCARD_MUST_BE_DYING_CONTEXT");
524}
525
526TEST(ExecutionDiscardConstrainingTest, ExploitAvoidDiscardByDelayingRaise)
527{
528 // EXPLOIT 2: A calls B calls C. B and C both fail.
529 // Attacker doesn't raise discard until it enters C, but sets the dying context to B.
530 // Then discard will remain 1 until it is cleared at the end of B.
531 // Result on attack success: B's rows before calling C are not discarded despite B's eventual failure.
532 TestTraceContainer trace({
533 { { C::precomputed_first_row, 1 } },
534 // Row 1: Context A (id=1), no discard
535 { { C::execution_sel, 1 },
536 { C::execution_context_id, 1 },
537 { C::execution_discard, 0 },
538 { C::execution_dying_context_id, 0 },
539 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
540 { C::execution_enqueued_call_end, 0 } },
541 // Row 2: A calls B
542 { { C::execution_sel, 1 },
543 { C::execution_context_id, 1 },
544 { C::execution_discard, 0 },
545 { C::execution_dying_context_id, 0 },
546 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
547 { C::execution_sel_enter_call, 1 },
548 { C::execution_enqueued_call_end, 0 } },
549 // Row 3: B (id=2) executes - ATTACK: don't raise discard yet
550 { { C::execution_sel, 1 },
551 { C::execution_context_id, 2 },
552 { C::execution_discard, 0 },
553 { C::execution_dying_context_id, 0 },
554 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
555 { C::execution_is_dying_context, 0 },
556 { C::execution_enqueued_call_end, 0 } },
557 // Row 4: B calls C
558 { { C::execution_sel, 1 },
559 { C::execution_context_id, 2 },
560 { C::execution_discard, 0 },
561 { C::execution_dying_context_id, 0 },
562 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
563 { C::execution_sel_enter_call, 1 },
564 { C::execution_enqueued_call_end, 0 } },
565 // Row 5: Entering C (id=3) - ATTACK: NOW raise discard but set dying_context to B (id=2)
566 { { C::execution_sel, 1 },
567 { C::execution_context_id, 3 },
568 { C::execution_discard, 1 },
569 { C::execution_dying_context_id, 2 },
570 { C::execution_dying_context_id_inv, FF(2).invert() },
571 { C::execution_dying_context_diff_inv, FF(3 - 2).invert() },
572 { C::execution_is_dying_context, 0 },
573 { C::execution_enqueued_call_end, 0 } },
574 // Row 6: C fails, but it's not the dying context so discard propagates
575 { { C::execution_sel, 1 },
576 { C::execution_context_id, 3 },
577 { C::execution_discard, 1 },
578 { C::execution_dying_context_id, 2 },
579 { C::execution_dying_context_id_inv, FF(2).invert() },
580 { C::execution_dying_context_diff_inv, FF(3 - 2).invert() },
581 { C::execution_is_dying_context, 0 },
582 { C::execution_sel_exit_call, 1 },
583 { C::execution_sel_error, 1 },
584 { C::execution_sel_failure, 1 },
585 { C::execution_has_parent_ctx, 1 },
586 { C::execution_enqueued_call_end, 0 } },
587 // Row 7: Back to B, discard still 1
588 { { C::execution_sel, 1 },
589 { C::execution_context_id, 2 },
590 { C::execution_discard, 1 },
591 { C::execution_dying_context_id, 2 },
592 { C::execution_dying_context_id_inv, FF(2).invert() },
593 { C::execution_dying_context_diff_inv, 0 },
594 { C::execution_is_dying_context, 1 },
595 { C::execution_enqueued_call_end, 0 } },
596 // Row 8: B fails and is the dying context, so discard gets cleared
597 { { C::execution_sel, 1 },
598 { C::execution_context_id, 2 },
599 { C::execution_discard, 1 },
600 { C::execution_dying_context_id, 2 },
601 { C::execution_dying_context_id_inv, FF(2).invert() },
602 { C::execution_dying_context_diff_inv, 0 },
603 { C::execution_is_dying_context, 1 },
604 { C::execution_sel_exit_call, 1 },
605 { C::execution_sel_error, 1 },
606 { C::execution_sel_failure, 1 },
607 { C::execution_has_parent_ctx, 1 },
608 { C::execution_enqueued_call_end, 0 } },
609 { { C::execution_sel, 1 } },
610 { { C::execution_sel, 0 } },
611 });
612
613 // If the exploit works, this check will pass.
614 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace), "ENTER_CALL_DISCARD_MUST_BE_DYING_CONTEXT");
615}
616
617TEST(ExecutionDiscardConstrainingTest, ExploitChangesDyingContextAfterResolution)
618{
619 // EXPLOIT 3: A calls B calls C. B and C both fail.
620 // Attacker sets dying context to C initially. When C dies, attacker changes dying context to B
621 // instead of clearing discard, allowing them to avoid discarding B's early operations.
622 // Result on attack success: B's rows before calling C are not discarded despite B's eventual failure.
623 TestTraceContainer trace({
624 { { C::precomputed_first_row, 1 } },
625 // Row 1: Context A calls B
626 { { C::execution_sel, 1 },
627 { C::execution_context_id, 1 },
628 { C::execution_discard, 0 },
629 { C::execution_dying_context_id, 0 },
630 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
631 { C::execution_sel_enter_call, 1 },
632 { C::execution_enqueued_call_end, 0 } },
633 // Row 2: B (id=2) executes - not discarded yet
634 { { C::execution_sel, 1 },
635 { C::execution_context_id, 2 },
636 { C::execution_discard, 0 },
637 { C::execution_dying_context_id, 0 },
638 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
639 { C::execution_enqueued_call_end, 0 } },
640 // Row 3: B calls C
641 { { C::execution_sel, 1 },
642 { C::execution_context_id, 2 },
643 { C::execution_discard, 0 },
644 { C::execution_dying_context_id, 0 },
645 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
646 { C::execution_sel_enter_call, 1 },
647 { C::execution_enqueued_call_end, 0 } },
648 // Row 4: Entering C (id=3) - raise discard, set dying_context to C
649 { { C::execution_sel, 1 },
650 { C::execution_context_id, 3 },
651 { C::execution_discard, 1 },
652 { C::execution_dying_context_id, 3 },
653 { C::execution_dying_context_id_inv, FF(3).invert() },
654 { C::execution_dying_context_diff_inv, 0 },
655 { C::execution_is_dying_context, 1 },
656 { C::execution_enqueued_call_end, 0 } },
657 // Row 5: C fails (dying context resolves, propagation lifted)
658 { { C::execution_sel, 1 },
659 { C::execution_context_id, 3 },
660 { C::execution_discard, 1 },
661 { C::execution_dying_context_id, 3 },
662 { C::execution_dying_context_id_inv, FF(3).invert() },
663 { C::execution_dying_context_diff_inv, 0 },
664 { C::execution_is_dying_context, 1 },
665 { C::execution_sel_exit_call, 1 },
666 { C::execution_sel_error, 1 },
667 { C::execution_sel_failure, 1 },
668 { C::execution_has_parent_ctx, 1 },
669 { C::execution_enqueued_call_end, 0 } },
670 // Row 6: Back to B - ATTACK: keep discard=1 but change dying context to B
671 { { C::execution_sel, 1 },
672 { C::execution_context_id, 2 },
673 { C::execution_discard, 1 },
674 { C::execution_dying_context_id, 2 },
675 { C::execution_dying_context_id_inv, FF(2).invert() },
676 { C::execution_dying_context_diff_inv, 0 },
677 { C::execution_is_dying_context, 1 },
678 { C::execution_enqueued_call_end, 0 } },
679 // Row 7: B fails and resolves as dying context, clearing discard again.
680 { { C::execution_sel, 1 },
681 { C::execution_context_id, 2 },
682 { C::execution_discard, 1 },
683 { C::execution_dying_context_id, 2 },
684 { C::execution_dying_context_id_inv, FF(2).invert() },
685 { C::execution_dying_context_diff_inv, 0 },
686 { C::execution_is_dying_context, 1 },
687 { C::execution_sel_exit_call, 1 },
688 { C::execution_sel_error, 1 },
689 { C::execution_sel_failure, 1 },
690 { C::execution_has_parent_ctx, 1 },
691 { C::execution_enqueued_call_end, 0 } },
692 { { C::execution_sel, 1 } },
693 { { C::execution_sel, 0 } },
694 });
695
696 // If the exploit works, this check will pass.
697 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace), "DYING_CONTEXT_WITH_PARENT_MUST_CLEAR_DISCARD");
698}
699
700} // namespace
701} // namespace bb::avm2::constraining
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessageRegex)
Definition assert.hpp:192
check_relation.hpp
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:40
trace
TestTraceContainer trace
Definition data_copy.test.cpp:63
flavor_settings.hpp
lookup_builder.hpp
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:16
bb::avm2::testing::empty_trace
TestTraceContainer empty_trace()
Definition fixtures.cpp:153
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
test_trace_container.hpp