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 }, { C::execution_last, 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 }, { C::execution_last, 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_last, 1 },
128 { C::execution_context_id, 7 },
129 { C::execution_discard, 0 },
130 { C::execution_dying_context_id, 0 },
131 { C::execution_is_dying_context, 0 },
132 { C::execution_dying_context_diff_inv, FF(7 - 0).invert() } },
133 { { C::execution_sel, 0 } },
134 });
135
136 check_relation<execution_discard>(trace, execution_discard::SR_IS_DYING_CONTEXT_CHECK);
137
138 // Negative test: wrong is_dying_context when equal
139 trace.set(C::execution_is_dying_context, 1, 0);
140 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_IS_DYING_CONTEXT_CHECK),
141 "IS_DYING_CONTEXT_CHECK");
142
143 // Negative test: wrong is_dying_context when not equal
144 trace.set(C::execution_is_dying_context, 1, 1); // Reset
145 trace.set(C::execution_is_dying_context, 2, 1);
146 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_IS_DYING_CONTEXT_CHECK),
147 "IS_DYING_CONTEXT_CHECK");
148}
149
150TEST(ExecutionDiscardConstrainingTest, DiscardPropagationOfZeroDiscard)
151{
152 TestTraceContainer trace({
153 { { C::precomputed_first_row, 1 } },
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 { C::execution_resolves_dying_context, 0 },
164 { C::execution_nested_call_from_undiscarded_context, 0 },
165 { C::execution_propagate_discard, 1 } },
166 // Propagates to next row
167 { { C::execution_sel, 1 },
168 { C::execution_discard, 0 },
169 { C::execution_dying_context_id, 0 },
170 { C::execution_dying_context_id_inv, 0 },
171 { C::execution_enqueued_call_end, 0 },
172 { C::execution_resolves_dying_context, 0 },
173 { C::execution_nested_call_from_undiscarded_context, 0 },
174 { C::execution_propagate_discard, 1 } },
175 // Last row gets propagated discard values. Propagation doesn't apply to next row because last=1.
176 { { C::execution_sel, 1 },
177 { C::execution_discard, 0 },
178 { C::execution_dying_context_id, 0 },
179 { C::execution_last, 1 } },
180 { { C::execution_sel, 0 } },
181 });
182
183 check_relation<execution_discard>(
184 trace, execution_discard::SR_DISCARD_PROPAGATION, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
185
186 // Negative test: doesn't propagate but it should.
187 trace.set(C::execution_discard, 2, 42);
188 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_DISCARD_PROPAGATION),
189 "DISCARD_PROPAGATION");
190}
191
192TEST(ExecutionDiscardConstrainingTest, DiscardPropagationOfNonzeroDiscard)
193{
194 TestTraceContainer trace({
195 { { C::precomputed_first_row, 1 } },
196 // Normal propagation case
197 { { C::execution_sel, 1 },
198 { C::execution_discard, 1 },
199 { C::execution_dying_context_id, 42 },
200 { C::execution_sel_exit_call, 0 },
201 { C::execution_has_parent_ctx, 1 },
202 { C::execution_sel_failure, 0 },
203 { C::execution_is_dying_context, 0 },
204 { C::execution_sel_enter_call, 0 },
205 { C::execution_enqueued_call_end, 0 },
206 { C::execution_resolves_dying_context, 0 },
207 { C::execution_nested_call_from_undiscarded_context, 0 },
208 { C::execution_propagate_discard, 1 } },
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_enqueued_call_end, 0 },
214 { C::execution_resolves_dying_context, 0 },
215 { C::execution_nested_call_from_undiscarded_context, 0 },
216 { C::execution_propagate_discard, 1 } },
217 // Last row gets propagated discard values. Propagation doesn't apply to next row because last=1.
218 { { C::execution_sel, 1 },
219 { C::execution_discard, 1 },
220 { C::execution_dying_context_id, 42 },
221 { C::execution_last, 1 } },
222 { { C::execution_sel, 0 } },
223 });
224
225 check_relation<execution_discard>(
226 trace, execution_discard::SR_DISCARD_PROPAGATION, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
227
228 // Negative test: doesn't propagate but it should.
229 trace.set(C::execution_discard, 2, 0);
230 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_DISCARD_PROPAGATION),
231 "DISCARD_PROPAGATION");
232}
233
234TEST(ExecutionDiscardConstrainingTest, DiscardPropagationLiftedEndOfEnqueuedCall)
235{
236 // Test propagation lifted at end of enqueued call (exit_call && !has_parent)
237 TestTraceContainer trace({
238 { { C::precomputed_first_row, 1 } },
239 // Exiting top-level call - propagation lifted
240 { { C::execution_sel, 1 },
241 { C::execution_discard, 1 },
242 { C::execution_dying_context_id, 42 },
243 { C::execution_sel_exit_call, 1 },
244 { C::execution_has_parent_ctx, 0 },
245 { C::execution_enqueued_call_end, 1 },
246 { C::execution_resolves_dying_context, 0 },
247 { C::execution_nested_call_from_undiscarded_context, 0 } },
248 // Next row can have different discard values
249 { { C::execution_sel, 1 }, { C::execution_discard, 0 }, { C::execution_dying_context_id, 0 } },
250 { { C::execution_sel, 1 }, { C::execution_last, 1 } },
251 { { C::execution_sel, 0 } },
252 });
253
254 check_relation<execution_discard>(
255 trace, execution_discard::SR_DISCARD_PROPAGATION, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
256}
257
258TEST(ExecutionDiscardConstrainingTest, DiscardPropagationLiftedResolvesDyingContext)
259{
260 // Test propagation lifted when resolving dying context (sel_failure && is_dying_context)
261 TestTraceContainer trace({
262 { { C::precomputed_first_row, 1 } },
263 // Failure in dying context - propagation lifted
264 { { C::execution_sel, 1 },
265 { C::execution_context_id, 42 },
266 { C::execution_discard, 1 },
267 { C::execution_dying_context_id, 42 },
268 { C::execution_sel_failure, 1 },
269 { C::execution_is_dying_context, 1 },
270 { C::execution_dying_context_diff_inv, 0 },
271 { C::execution_enqueued_call_end, 0 },
272 { C::execution_resolves_dying_context, 1 },
273 { C::execution_nested_call_from_undiscarded_context, 0 } },
274 // Next row can have different discard values
275 { { C::execution_sel, 1 },
276 { C::execution_discard, 0 },
277 { C::execution_dying_context_id, 0 },
278 { C::execution_enqueued_call_end, 0 },
279 { C::execution_resolves_dying_context, 0 },
280 { C::execution_nested_call_from_undiscarded_context, 0 },
281 { C::execution_propagate_discard, 1 } },
282 { { C::execution_sel, 1 }, { C::execution_last, 1 } },
283 { { C::execution_sel, 0 } },
284 });
285
286 check_relation<execution_discard>(
287 trace, execution_discard::SR_DISCARD_PROPAGATION, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
288}
289
290TEST(ExecutionDiscardConstrainingTest, DiscardPropagationLiftedNestedCallFromUndiscarded)
291{
292 // Test propagation lifted when making nested call from undiscarded context
293 TestTraceContainer trace({
294 { { C::precomputed_first_row, 1 } },
295 // Making a call from undiscarded context - propagation lifted
296 { { C::execution_sel, 1 },
297 { C::execution_discard, 0 },
298 { C::execution_dying_context_id, 0 },
299 { C::execution_sel_enter_call, 1 },
300 { C::execution_enqueued_call_end, 0 },
301 { C::execution_resolves_dying_context, 0 },
302 { C::execution_nested_call_from_undiscarded_context, 1 } },
303 // Next row can raise discard (nested context will error)
304 { { C::execution_sel, 1 }, { C::execution_discard, 1 }, { C::execution_dying_context_id, 99 } },
305 // Last row keeps the values (propagation doesn't apply because last=1)
306 { { C::execution_sel, 1 },
307 { C::execution_discard, 1 },
308 { C::execution_dying_context_id, 99 },
309 { C::execution_last, 1 } },
310 { { C::execution_sel, 0 } },
311 });
312
313 // This should pass because sel_enter_call=1 lifts the propagation constraint
314 check_relation<execution_discard>(
315 trace, execution_discard::SR_DISCARD_PROPAGATION, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
316}
317
318TEST(ExecutionDiscardConstrainingTest, DiscardDyingContextMustError)
319{
320 // Test that dying context must exit with failure
321 TestTraceContainer trace({
322 { { C::precomputed_first_row, 1 } },
323 // Dying context exits with error - OK
324 { { C::execution_sel, 1 },
325 { C::execution_context_id, 42 },
326 { C::execution_discard, 1 },
327 { C::execution_dying_context_id, 42 },
328 { C::execution_is_dying_context, 1 },
329 { C::execution_sel_exit_call, 1 },
330 { C::execution_sel_error, 1 },
331 { C::execution_sel_execute_revert, 0 },
332 { C::execution_sel_failure, 1 },
333 { C::execution_dying_context_diff_inv, 0 } },
334 { { C::execution_sel, 1 }, { C::execution_last, 1 } },
335 { { C::execution_sel, 0 } },
336 });
337
338 check_relation<execution_discard>(trace, execution_discard::SR_DYING_CONTEXT_MUST_FAIL);
339
340 // Negative test: dying context exits without error
341 trace.set(C::execution_sel_failure, 1, 0);
342 trace.set(C::execution_sel_error, 1, 0);
343 trace.set(C::execution_sel_execute_revert, 1, 0);
344 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace, execution_discard::SR_DYING_CONTEXT_MUST_FAIL),
345 "DYING_CONTEXT_MUST_FAIL");
346}
347
348TEST(ExecutionDiscardConstrainingTest, DiscardComplexScenario)
349{
350 // Complex scenario: nested calls with errors
351 TestTraceContainer trace({
352 { { C::precomputed_first_row, 1 } },
353 // Row 1: Parent context, no discard
354 { { C::execution_sel, 1 },
355 { C::execution_context_id, 1 },
356 { C::execution_discard, 0 },
357 { C::execution_dying_context_id, 0 },
358 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
359 { C::execution_is_dying_context, 0 },
360 { C::execution_enqueued_call_end, 0 },
361 { C::execution_resolves_dying_context, 0 },
362 { C::execution_nested_call_from_undiscarded_context, 0 },
363 { C::execution_propagate_discard, 1 } },
364 // Row 2: Call to nested context (that will eventually error)
365 { { C::execution_sel, 1 },
366 { C::execution_context_id, 1 },
367 { C::execution_discard, 0 },
368 { C::execution_dying_context_id, 0 },
369 { C::execution_dying_context_id_inv, 0 },
370 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
371 { C::execution_sel_enter_call, 1 },
372 { C::execution_enqueued_call_end, 0 },
373 { C::execution_resolves_dying_context, 0 },
374 { C::execution_nested_call_from_undiscarded_context, 1 },
375 { C::execution_propagate_discard, 0 } },
376 // Row 3: Nested context, discard raised because this context will error
377 { { C::execution_sel, 1 },
378 { C::execution_context_id, 2 },
379 { C::execution_discard, 1 },
380 { C::execution_dying_context_id, 2 },
381 { C::execution_is_dying_context, 1 },
382 { C::execution_dying_context_diff_inv, 0 },
383 { C::execution_enqueued_call_end, 0 },
384 { C::execution_resolves_dying_context, 0 },
385 { C::execution_nested_call_from_undiscarded_context, 0 },
386 { C::execution_propagate_discard, 1 } },
387 // Row 4: Nested context errors
388 { { C::execution_sel, 1 },
389 { C::execution_context_id, 2 },
390 { C::execution_discard, 1 },
391 { C::execution_dying_context_id, 2 },
392 { C::execution_is_dying_context, 1 },
393 { C::execution_sel_exit_call, 1 },
394 { C::execution_sel_error, 1 },
395 { C::execution_sel_execute_revert, 0 },
396 { C::execution_sel_failure, 1 },
397 { C::execution_dying_context_diff_inv, 0 },
398 { C::execution_has_parent_ctx, 1 },
399 { C::execution_enqueued_call_end, 0 },
400 { C::execution_resolves_dying_context, 1 },
401 { C::execution_nested_call_from_undiscarded_context, 0 },
402 { C::execution_propagate_discard, 0 } },
403 // Row 5: Back to parent, discard cleared
404 { { C::execution_sel, 1 },
405 { C::execution_context_id, 1 },
406 { C::execution_discard, 0 },
407 { C::execution_dying_context_id, 0 },
408 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
409 { C::execution_is_dying_context, 0 },
410 { C::execution_enqueued_call_end, 0 },
411 { C::execution_resolves_dying_context, 0 },
412 { C::execution_nested_call_from_undiscarded_context, 0 },
413 { C::execution_propagate_discard, 1 } },
414 { { C::execution_sel, 0 } },
415 });
416
417 // Only check the most important relations for this scenario
418 check_relation<execution_discard>(trace,
419 execution_discard::SR_IS_DYING_CONTEXT_CHECK,
420 execution_discard::SR_DISCARD_PROPAGATION,
421 execution_discard::SR_DYING_CONTEXT_PROPAGATION,
422 execution_discard::SR_DYING_CONTEXT_MUST_FAIL);
423}
424
425TEST(ExecutionDiscardConstrainingTest, DiscardWithLastRow)
426{
427 // Test discard behavior with last row
428 TestTraceContainer trace({
429 { { C::precomputed_first_row, 1 } },
430 { { C::execution_sel, 1 },
431 { C::execution_discard, 1 },
432 { C::execution_dying_context_id, 42 },
433 { C::execution_enqueued_call_end, 0 },
434 { C::execution_resolves_dying_context, 0 },
435 { C::execution_nested_call_from_undiscarded_context, 0 },
436 { C::execution_propagate_discard, 1 } },
437 // Last row also has discard values (propagation doesn't apply because last=1)
438 { { C::execution_sel, 1 },
439 { C::execution_discard, 1 },
440 { C::execution_dying_context_id, 42 },
441 { C::execution_last, 1 } },
442 { { C::execution_sel, 0 } },
443 });
444
445 check_relation<execution_discard>(
446 trace, execution_discard::SR_DISCARD_PROPAGATION, execution_discard::SR_DYING_CONTEXT_PROPAGATION);
447}
448
449// ====== EXPLOIT TESTS - These test vulnerabilities found in early versions ======
450
451TEST(ExecutionDiscardConstrainingTest, ExploitRaiseDiscardWithWrongDyingContext)
452{
453 // EXPLOIT 1: A calls B calls C. C fails.
454 // Attacker raises discard when entering B and sets dying context to C.
455 // Then C clears the flag when it fails.
456 // Result on attack success: B's operations are discarded even though B didn't fail.
457 TestTraceContainer trace({
458 { { C::precomputed_first_row, 1 } },
459 // Row 1: Context A (id=1), no discard initially
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_is_dying_context, 0 },
466 { C::execution_enqueued_call_end, 0 },
467 { C::execution_resolves_dying_context, 0 },
468 { C::execution_nested_call_from_undiscarded_context, 0 },
469 { C::execution_propagate_discard, 1 } },
470 // Row 2: A calls B - ATTACK: raise discard and set dying_context to C (id=3)
471 { { C::execution_sel, 1 },
472 { C::execution_context_id, 1 },
473 { C::execution_discard, 0 },
474 { C::execution_dying_context_id, 0 },
475 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
476 { C::execution_sel_enter_call, 1 },
477 { C::execution_enqueued_call_end, 0 },
478 { C::execution_resolves_dying_context, 0 },
479 { C::execution_nested_call_from_undiscarded_context, 1 },
480 { C::execution_propagate_discard, 0 } },
481 // Row 3: Entering B (id=2) - ATTACK: discard raised to 1, dying_context set to 3 (C)
482 { { C::execution_sel, 1 },
483 { C::execution_context_id, 2 },
484 { C::execution_discard, 1 },
485 { C::execution_dying_context_id, 3 },
486 { C::execution_dying_context_id_inv, FF(3).invert() },
487 { C::execution_dying_context_diff_inv, FF(2 - 3).invert() },
488 { C::execution_is_dying_context, 0 },
489 { C::execution_enqueued_call_end, 0 },
490 { C::execution_resolves_dying_context, 0 },
491 { C::execution_nested_call_from_undiscarded_context, 0 },
492 { C::execution_propagate_discard, 1 } },
493 // Row 4: B calls C
494 { { C::execution_sel, 1 },
495 { C::execution_context_id, 2 },
496 { C::execution_discard, 1 },
497 { C::execution_dying_context_id, 3 },
498 { C::execution_dying_context_id_inv, FF(3).invert() },
499 { C::execution_dying_context_diff_inv, FF(2 - 3).invert() },
500 { C::execution_is_dying_context, 0 },
501 { C::execution_sel_enter_call, 1 },
502 { C::execution_enqueued_call_end, 0 },
503 { C::execution_resolves_dying_context, 0 },
504 { C::execution_nested_call_from_undiscarded_context, 0 },
505 { C::execution_propagate_discard, 0 } },
506 // Row 5: C (id=3) executes and fails - this is the dying context
507 { { C::execution_sel, 1 },
508 { C::execution_context_id, 3 },
509 { C::execution_discard, 1 },
510 { C::execution_dying_context_id, 3 },
511 { C::execution_dying_context_id_inv, FF(3).invert() },
512 { C::execution_dying_context_diff_inv, 0 },
513 { C::execution_is_dying_context, 1 },
514 { C::execution_sel_exit_call, 1 },
515 { C::execution_sel_error, 1 },
516 { C::execution_sel_failure, 1 },
517 { C::execution_has_parent_ctx, 1 },
518 { C::execution_enqueued_call_end, 0 },
519 { C::execution_resolves_dying_context, 1 },
520 { C::execution_nested_call_from_undiscarded_context, 0 },
521 { C::execution_propagate_discard, 0 } },
522 // Row 6: Back to B - discard cleared because dying context resolved
523 { { C::execution_sel, 1 },
524 { C::execution_context_id, 2 },
525 { C::execution_discard, 0 },
526 { C::execution_dying_context_id, 0 },
527 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
528 { C::execution_is_dying_context, 0 },
529 { C::execution_enqueued_call_end, 0 },
530 { C::execution_resolves_dying_context, 0 },
531 { C::execution_nested_call_from_undiscarded_context, 0 },
532 { C::execution_propagate_discard, 1 } },
533 // Row 7: B exits successfully (no failure)
534 { { C::execution_sel, 1 },
535 { C::execution_context_id, 2 },
536 { C::execution_discard, 0 },
537 { C::execution_dying_context_id, 0 },
538 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
539 { C::execution_sel_exit_call, 1 },
540 { C::execution_sel_error, 0 },
541 { C::execution_sel_failure, 0 },
542 { C::execution_has_parent_ctx, 1 },
543 { C::execution_enqueued_call_end, 0 },
544 { C::execution_resolves_dying_context, 0 },
545 { C::execution_nested_call_from_undiscarded_context, 0 },
546 { C::execution_propagate_discard, 0 } },
547 { { C::execution_sel, 1 }, { C::execution_last, 1 } },
548 { { C::execution_sel, 0 } },
549 });
550
551 // If the exploit works, this check will pass.
552 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace), "ENTER_CALL_DISCARD_MUST_BE_DYING_CONTEXT");
553}
554
555TEST(ExecutionDiscardConstrainingTest, ExploitAvoidDiscardByDelayingRaise)
556{
557 // EXPLOIT 2: A calls B calls C. B and C both fail.
558 // Attacker doesn't raise discard until it enters C, but sets the dying context to B.
559 // Then discard will remain 1 until it is cleared at the end of B.
560 // Result on attack success: B's rows before calling C are not discarded despite B's eventual failure.
561 TestTraceContainer trace({
562 { { C::precomputed_first_row, 1 } },
563 // Row 1: Context A (id=1), no discard
564 { { C::execution_sel, 1 },
565 { C::execution_context_id, 1 },
566 { C::execution_discard, 0 },
567 { C::execution_dying_context_id, 0 },
568 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
569 { C::execution_enqueued_call_end, 0 },
570 { C::execution_resolves_dying_context, 0 },
571 { C::execution_nested_call_from_undiscarded_context, 0 },
572 { C::execution_propagate_discard, 1 } },
573 // Row 2: A calls B
574 { { C::execution_sel, 1 },
575 { C::execution_context_id, 1 },
576 { C::execution_discard, 0 },
577 { C::execution_dying_context_id, 0 },
578 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
579 { C::execution_sel_enter_call, 1 },
580 { C::execution_enqueued_call_end, 0 },
581 { C::execution_resolves_dying_context, 0 },
582 { C::execution_nested_call_from_undiscarded_context, 1 },
583 { C::execution_propagate_discard, 0 } },
584 // Row 3: B (id=2) executes - ATTACK: don't raise discard yet
585 { { C::execution_sel, 1 },
586 { C::execution_context_id, 2 },
587 { C::execution_discard, 0 },
588 { C::execution_dying_context_id, 0 },
589 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
590 { C::execution_is_dying_context, 0 },
591 { C::execution_enqueued_call_end, 0 },
592 { C::execution_resolves_dying_context, 0 },
593 { C::execution_nested_call_from_undiscarded_context, 0 },
594 { C::execution_propagate_discard, 1 } },
595 // Row 4: B calls C
596 { { C::execution_sel, 1 },
597 { C::execution_context_id, 2 },
598 { C::execution_discard, 0 },
599 { C::execution_dying_context_id, 0 },
600 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
601 { C::execution_sel_enter_call, 1 },
602 { C::execution_enqueued_call_end, 0 },
603 { C::execution_resolves_dying_context, 0 },
604 { C::execution_nested_call_from_undiscarded_context, 1 },
605 { C::execution_propagate_discard, 0 } },
606 // Row 5: Entering C (id=3) - ATTACK: NOW raise discard but set dying_context to B (id=2)
607 { { C::execution_sel, 1 },
608 { C::execution_context_id, 3 },
609 { C::execution_discard, 1 },
610 { C::execution_dying_context_id, 2 },
611 { C::execution_dying_context_id_inv, FF(2).invert() },
612 { C::execution_dying_context_diff_inv, FF(3 - 2).invert() },
613 { C::execution_is_dying_context, 0 },
614 { C::execution_enqueued_call_end, 0 },
615 { C::execution_resolves_dying_context, 0 },
616 { C::execution_nested_call_from_undiscarded_context, 0 },
617 { C::execution_propagate_discard, 1 } },
618 // Row 6: C fails, but it's not the dying context so discard propagates
619 { { C::execution_sel, 1 },
620 { C::execution_context_id, 3 },
621 { C::execution_discard, 1 },
622 { C::execution_dying_context_id, 2 },
623 { C::execution_dying_context_id_inv, FF(2).invert() },
624 { C::execution_dying_context_diff_inv, FF(3 - 2).invert() },
625 { C::execution_is_dying_context, 0 },
626 { C::execution_sel_exit_call, 1 },
627 { C::execution_sel_error, 1 },
628 { C::execution_sel_failure, 1 },
629 { C::execution_has_parent_ctx, 1 },
630 { C::execution_enqueued_call_end, 0 },
631 { C::execution_resolves_dying_context, 0 },
632 { C::execution_nested_call_from_undiscarded_context, 0 },
633 { C::execution_propagate_discard, 0 } },
634 // Row 7: Back to B, discard still 1
635 { { C::execution_sel, 1 },
636 { C::execution_context_id, 2 },
637 { C::execution_discard, 1 },
638 { C::execution_dying_context_id, 2 },
639 { C::execution_dying_context_id_inv, FF(2).invert() },
640 { C::execution_dying_context_diff_inv, 0 },
641 { C::execution_is_dying_context, 1 },
642 { C::execution_enqueued_call_end, 0 },
643 { C::execution_resolves_dying_context, 0 },
644 { C::execution_nested_call_from_undiscarded_context, 0 },
645 { C::execution_propagate_discard, 1 } },
646 // Row 8: B fails and is the dying context, so discard gets cleared
647 { { C::execution_sel, 1 },
648 { C::execution_context_id, 2 },
649 { C::execution_discard, 1 },
650 { C::execution_dying_context_id, 2 },
651 { C::execution_dying_context_id_inv, FF(2).invert() },
652 { C::execution_dying_context_diff_inv, 0 },
653 { C::execution_is_dying_context, 1 },
654 { C::execution_sel_exit_call, 1 },
655 { C::execution_sel_error, 1 },
656 { C::execution_sel_failure, 1 },
657 { C::execution_has_parent_ctx, 1 },
658 { C::execution_enqueued_call_end, 0 },
659 { C::execution_resolves_dying_context, 1 },
660 { C::execution_nested_call_from_undiscarded_context, 0 },
661 { C::execution_propagate_discard, 0 } },
662 { { C::execution_sel, 1 }, { C::execution_last, 1 } },
663 { { C::execution_sel, 0 } },
664 });
665
666 // If the exploit works, this check will pass.
667 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace), "ENTER_CALL_DISCARD_MUST_BE_DYING_CONTEXT");
668}
669
670TEST(ExecutionDiscardConstrainingTest, ExploitChangesDyingContextAfterResolution)
671{
672 // EXPLOIT 3: A calls B calls C. B and C both fail.
673 // Attacker sets dying context to C initially. When C dies, attacker changes dying context to B
674 // instead of clearing discard, allowing them to avoid discarding B's early operations.
675 // Result on attack success: B's rows before calling C are not discarded despite B's eventual failure.
676 TestTraceContainer trace({
677 { { C::precomputed_first_row, 1 } },
678 // Row 1: Context A calls B
679 { { C::execution_sel, 1 },
680 { C::execution_context_id, 1 },
681 { C::execution_discard, 0 },
682 { C::execution_dying_context_id, 0 },
683 { C::execution_dying_context_diff_inv, FF(1 - 0).invert() },
684 { C::execution_sel_enter_call, 1 },
685 { C::execution_enqueued_call_end, 0 },
686 { C::execution_resolves_dying_context, 0 },
687 { C::execution_nested_call_from_undiscarded_context, 1 },
688 { C::execution_propagate_discard, 0 } },
689 // Row 2: B (id=2) executes - not discarded yet
690 { { C::execution_sel, 1 },
691 { C::execution_context_id, 2 },
692 { C::execution_discard, 0 },
693 { C::execution_dying_context_id, 0 },
694 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
695 { C::execution_enqueued_call_end, 0 },
696 { C::execution_resolves_dying_context, 0 },
697 { C::execution_nested_call_from_undiscarded_context, 0 },
698 { C::execution_propagate_discard, 1 } },
699 // Row 3: B calls C
700 { { C::execution_sel, 1 },
701 { C::execution_context_id, 2 },
702 { C::execution_discard, 0 },
703 { C::execution_dying_context_id, 0 },
704 { C::execution_dying_context_diff_inv, FF(2 - 0).invert() },
705 { C::execution_sel_enter_call, 1 },
706 { C::execution_enqueued_call_end, 0 },
707 { C::execution_resolves_dying_context, 0 },
708 { C::execution_nested_call_from_undiscarded_context, 1 },
709 { C::execution_propagate_discard, 0 } },
710 // Row 4: Entering C (id=3) - raise discard, set dying_context to C
711 { { C::execution_sel, 1 },
712 { C::execution_context_id, 3 },
713 { C::execution_discard, 1 },
714 { C::execution_dying_context_id, 3 },
715 { C::execution_dying_context_id_inv, FF(3).invert() },
716 { C::execution_dying_context_diff_inv, 0 },
717 { C::execution_is_dying_context, 1 },
718 { C::execution_enqueued_call_end, 0 },
719 { C::execution_resolves_dying_context, 0 },
720 { C::execution_nested_call_from_undiscarded_context, 0 },
721 { C::execution_propagate_discard, 1 } },
722 // Row 5: C fails (dying context resolves, propagation lifted)
723 { { C::execution_sel, 1 },
724 { C::execution_context_id, 3 },
725 { C::execution_discard, 1 },
726 { C::execution_dying_context_id, 3 },
727 { C::execution_dying_context_id_inv, FF(3).invert() },
728 { C::execution_dying_context_diff_inv, 0 },
729 { C::execution_is_dying_context, 1 },
730 { C::execution_sel_exit_call, 1 },
731 { C::execution_sel_error, 1 },
732 { C::execution_sel_failure, 1 },
733 { C::execution_has_parent_ctx, 1 },
734 { C::execution_enqueued_call_end, 0 },
735 { C::execution_resolves_dying_context, 1 },
736 { C::execution_nested_call_from_undiscarded_context, 0 },
737 { C::execution_propagate_discard, 0 } },
738 // Row 6: Back to B - ATTACK: keep discard=1 but change dying context to B
739 { { C::execution_sel, 1 },
740 { C::execution_context_id, 2 },
741 { C::execution_discard, 1 },
742 { C::execution_dying_context_id, 2 },
743 { C::execution_dying_context_id_inv, FF(2).invert() },
744 { C::execution_dying_context_diff_inv, 0 },
745 { C::execution_is_dying_context, 1 },
746 { C::execution_enqueued_call_end, 0 },
747 { C::execution_resolves_dying_context, 0 },
748 { C::execution_nested_call_from_undiscarded_context, 0 },
749 { C::execution_propagate_discard, 1 } },
750 // Row 7: B fails and resolves as dying context, clearing discard again.
751 { { C::execution_sel, 1 },
752 { C::execution_context_id, 2 },
753 { C::execution_discard, 1 },
754 { C::execution_dying_context_id, 2 },
755 { C::execution_dying_context_id_inv, FF(2).invert() },
756 { C::execution_dying_context_diff_inv, 0 },
757 { C::execution_is_dying_context, 1 },
758 { C::execution_sel_exit_call, 1 },
759 { C::execution_sel_error, 1 },
760 { C::execution_sel_failure, 1 },
761 { C::execution_has_parent_ctx, 1 },
762 { C::execution_enqueued_call_end, 0 },
763 { C::execution_resolves_dying_context, 1 },
764 { C::execution_nested_call_from_undiscarded_context, 0 },
765 { C::execution_propagate_discard, 0 } },
766 { { C::execution_sel, 1 }, { C::execution_last, 1 } },
767 { { C::execution_sel, 0 } },
768 });
769
770 // If the exploit works, this check will pass.
771 EXPECT_THROW_WITH_MESSAGE(check_relation<execution_discard>(trace), "DYING_CONTEXT_WITH_PARENT_MUST_CLEAR_DISCARD");
772}
773
774} // namespace
775} // namespace bb::avm2::constraining
check_relation.hpp
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:36
trace
TestTraceContainer trace
Definition data_copy.test.cpp:59
flavor_settings.hpp
lookup_builder.hpp
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessage)
Definition macros.hpp:7
bb::avm2::constraining::FF
AvmFlavorSettings::FF FF
Definition poseidon2.test.cpp:38
bb::avm2::constraining::TEST
TEST(TxExecutionConstrainingTest, WriteTreeValue)
Definition tx.test.cpp:508
bb::avm2::testing::empty_trace
TestTraceContainer empty_trace()
Definition fixtures.cpp:153
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:16
test_trace_container.hpp