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