Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
public_data_tree.test.cpp
Go to the documentation of this file.
1#include <gmock/gmock.h>
2#include <gtest/gtest.h>
3
4#include <cmath>
5#include <cstdint>
6
7#include "barretenberg/crypto/poseidon2/poseidon2.hpp"
8#include "barretenberg/vm2/common/avm_inputs.hpp"
9#include "barretenberg/vm2/constraining/flavor_settings.hpp"
10#include "barretenberg/vm2/constraining/testing/check_relation.hpp"
11#include "barretenberg/vm2/generated/relations/lookups_public_data_check.hpp"
12#include "barretenberg/vm2/generated/relations/merkle_check.hpp"
13#include "barretenberg/vm2/generated/relations/public_data_check.hpp"
14#include "barretenberg/vm2/simulation/events/event_emitter.hpp"
15#include "barretenberg/vm2/simulation/events/public_data_tree_check_event.hpp"
16#include "barretenberg/vm2/simulation/field_gt.hpp"
17#include "barretenberg/vm2/simulation/lib/merkle.hpp"
18#include "barretenberg/vm2/simulation/poseidon2.hpp"
19#include "barretenberg/vm2/simulation/public_data_tree_check.hpp"
20#include "barretenberg/vm2/simulation/testing/mock_gt.hpp"
21#include "barretenberg/vm2/testing/fixtures.hpp"
22#include "barretenberg/vm2/testing/macros.hpp"
23#include "barretenberg/vm2/testing/public_inputs_builder.hpp"
24#include "barretenberg/vm2/testing/test_tree.hpp"
25#include "barretenberg/vm2/tracegen/field_gt_trace.hpp"
26#include "barretenberg/vm2/tracegen/lib/lookup_builder.hpp"
27#include "barretenberg/vm2/tracegen/merkle_check_trace.hpp"
28#include "barretenberg/vm2/tracegen/poseidon2_trace.hpp"
29#include "barretenberg/vm2/tracegen/precomputed_trace.hpp"
30#include "barretenberg/vm2/tracegen/public_data_tree_trace.hpp"
31#include "barretenberg/vm2/tracegen/public_inputs_trace.hpp"
32#include "barretenberg/vm2/tracegen/range_check_trace.hpp"
33#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
34
35namespace bb::avm2::constraining {
36namespace {
37
38using ::testing::NiceMock;
39using ::testing::TestWithParam;
40
41using testing::TestMemoryTree;
42
43using simulation::EventEmitter;
44using simulation::ExecutionIdManager;
45using simulation::FieldGreaterThan;
46using simulation::FieldGreaterThanEvent;
47using simulation::MerkleCheck;
48using simulation::MerkleCheckEvent;
49using simulation::MockGreaterThan;
50using simulation::Poseidon2;
51using simulation::Poseidon2HashEvent;
52using simulation::Poseidon2PermutationEvent;
53using simulation::Poseidon2PermutationMemoryEvent;
54using simulation::PublicDataTreeCheck;
55using simulation::PublicDataTreeCheckEvent;
56using simulation::PublicDataTreeLeafPreimage;
57using simulation::RangeCheck;
58using simulation::RangeCheckEvent;
59using simulation::unconstrained_compute_leaf_slot;
60using simulation::unconstrained_root_from_path;
61
62using tracegen::FieldGreaterThanTraceBuilder;
63using tracegen::MerkleCheckTraceBuilder;
64using tracegen::Poseidon2TraceBuilder;
65using tracegen::PrecomputedTraceBuilder;
66using tracegen::PublicDataTreeTraceBuilder;
67using tracegen::PublicInputsTraceBuilder;
68using tracegen::RangeCheckTraceBuilder;
69using tracegen::TestTraceContainer;
70
71using FF = AvmFlavorSettings::FF;
72using C = Column;
73using public_data_check = bb::avm2::public_data_check<FF>;
74using public_data_squash = bb::avm2::public_data_squash<FF>;
75using UnconstrainedPoseidon2 = crypto::Poseidon2<crypto::Poseidon2Bn254ScalarFieldParams>;
76
77AztecAddress contract_address = 1;
78
79class PublicDataTreeCheckConstrainingTest : public ::testing::Test {
80 protected:
81 PublicDataTreeCheckConstrainingTest()
82 : execution_id_manager(0) {};
83
84 EventEmitter<Poseidon2HashEvent> hash_event_emitter;
85 EventEmitter<Poseidon2PermutationEvent> perm_event_emitter;
86 EventEmitter<Poseidon2PermutationMemoryEvent> perm_mem_event_emitter;
87
88 ExecutionIdManager execution_id_manager;
89 NiceMock<MockGreaterThan> mock_gt;
90 Poseidon2 poseidon2 =
91 Poseidon2(execution_id_manager, mock_gt, hash_event_emitter, perm_event_emitter, perm_mem_event_emitter);
92};
93
94struct TestParams {
95 FF slot;
96 FF value;
97 PublicDataTreeLeafPreimage low_leaf;
98};
99
100std::vector<TestParams> positive_tests = {
101 // Exists = true, leaf pointers to infinity
102 TestParams{ .slot = 42,
103 .value = 27,
104 .low_leaf = PublicDataTreeLeafPreimage(
105 PublicDataLeafValue(unconstrained_compute_leaf_slot(contract_address, 42), 27), 0, 0) },
106 // Exists = true, leaf points to higher value
107 TestParams{
108 .slot = 42,
109 .value = 27,
110 .low_leaf = PublicDataTreeLeafPreimage(
111 PublicDataLeafValue(unconstrained_compute_leaf_slot(contract_address, 42), 27), 28, FF::neg_one()) },
112 // Exists = false, low leaf points to infinity
113 TestParams{ .slot = 42, .value = 0, .low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(10, 0), 0, 0) },
114 // Exists = false, low leaf points to higher value
115 TestParams{
116 .slot = 42, .value = 0, .low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(10, 0), 28, FF::neg_one()) }
117};
118
119class PublicDataReadPositiveTests : public PublicDataTreeCheckConstrainingTest,
120 public ::testing::WithParamInterface<TestParams> {};
121
122TEST_P(PublicDataReadPositiveTests, Positive)
123{
124 const auto& param = GetParam();
125
126 auto test_public_inputs = testing::PublicInputsBuilder().build();
127
128 EventEmitter<MerkleCheckEvent> merkle_event_emitter;
129 MerkleCheck merkle_check(poseidon2, merkle_event_emitter);
130
131 EventEmitter<RangeCheckEvent> range_check_emitter;
132 RangeCheck range_check(range_check_emitter);
133
134 EventEmitter<FieldGreaterThanEvent> field_gt_event_emitter;
135 FieldGreaterThan field_gt(range_check, field_gt_event_emitter);
136
137 EventEmitter<PublicDataTreeCheckEvent> public_data_tree_check_event_emitter;
138 PublicDataTreeCheck public_data_tree_check_simulator(
139 poseidon2, merkle_check, field_gt, execution_id_manager, public_data_tree_check_event_emitter);
140
141 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } } });
142 RangeCheckTraceBuilder range_check_builder;
143 Poseidon2TraceBuilder poseidon2_builder;
144 MerkleCheckTraceBuilder merkle_check_builder;
145 FieldGreaterThanTraceBuilder field_gt_builder;
146 PrecomputedTraceBuilder precomputed_builder;
147 PublicInputsTraceBuilder public_inputs_builder;
148 PublicDataTreeTraceBuilder public_data_tree_read_builder;
149
150 FF low_leaf_hash = poseidon2.hash(param.low_leaf.get_hash_inputs());
151 uint64_t leaf_index = 30;
152 std::vector<FF> sibling_path;
153 sibling_path.reserve(PUBLIC_DATA_TREE_HEIGHT);
154 for (size_t i = 0; i < PUBLIC_DATA_TREE_HEIGHT; ++i) {
155 sibling_path.emplace_back(i);
156 }
157 FF root = unconstrained_root_from_path(low_leaf_hash, leaf_index, sibling_path);
158
159 public_data_tree_check_simulator.assert_read(param.slot,
160 contract_address,
161 param.value,
162 param.low_leaf,
163 leaf_index,
164 sibling_path,
165 AppendOnlyTreeSnapshot{
166 .root = root,
167 .nextAvailableLeafIndex = 128,
168 });
169
170 precomputed_builder.process_misc(trace, AVM_PUBLIC_INPUTS_COLUMNS_MAX_LENGTH);
171 public_inputs_builder.process_public_inputs(trace, test_public_inputs);
172 public_inputs_builder.process_public_inputs_aux_precomputed(trace);
173 range_check_builder.process(range_check_emitter.dump_events(), trace);
174 poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
175 merkle_check_builder.process(merkle_event_emitter.dump_events(), trace);
176 field_gt_builder.process(field_gt_event_emitter.dump_events(), trace);
177 public_data_tree_read_builder.process(public_data_tree_check_event_emitter.dump_events(), trace);
178
179 check_all_interactions<PublicDataTreeTraceBuilder>(trace);
180
181 check_relation<public_data_check>(trace);
182 check_relation<public_data_squash>(trace);
183}
184
185INSTANTIATE_TEST_SUITE_P(PublicDataTreeConstrainingTest,
186 PublicDataReadPositiveTests,
187 ::testing::ValuesIn(positive_tests));
188
189TEST(PublicDataTreeConstrainingTest, NegativeStartCondition)
190{
191 // Test constraint: sel' * (1 - sel) * (1 - precomputed.first_row) = 0
192 TestTraceContainer trace({ {
193 { C::public_data_check_sel, 0 },
194 { C::precomputed_first_row, 1 },
195 },
196 {
197 { C::public_data_check_sel, 1 },
198 },
199 {
200 { C::public_data_check_sel, 1 },
201 } });
202
203 check_relation<public_data_check>(trace, public_data_check::SR_START_CONDITION);
204
205 // Invalid: sel can't be activated if prev is not the first row
206 trace.set(C::precomputed_first_row, 0, 0);
207
208 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_START_CONDITION),
209 "START_CONDITION");
210}
211
212TEST(PublicDataTreeConstrainingTest, NegativeExistsFlagCheck)
213{
214 // Test constraint: sel * (LEAF_SLOT_LOW_LEAF_SLOT_DIFF * (LEAF_EXISTS * (1 - leaf_slot_low_leaf_slot_diff_inv) +
215 // leaf_slot_low_leaf_slot_diff_inv) - 1 + LEAF_EXISTS) = 0
216 TestTraceContainer trace({
217 { { C::public_data_check_sel, 1 },
218 { C::public_data_check_leaf_slot, 27 },
219 { C::public_data_check_low_leaf_slot, 27 },
220 { C::public_data_check_leaf_slot_low_leaf_slot_diff_inv, 0 },
221 { C::public_data_check_leaf_not_exists, 0 } },
222 { { C::public_data_check_sel, 1 },
223 { C::public_data_check_leaf_slot, 28 },
224 { C::public_data_check_low_leaf_slot, 27 },
225 { C::public_data_check_leaf_slot_low_leaf_slot_diff_inv, FF(1).invert() },
226 { C::public_data_check_leaf_not_exists, 1 } },
227 });
228
229 check_relation<public_data_check>(trace, public_data_check::SR_EXISTS_FLAG_CHECK);
230
231 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
232
233 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_EXISTS_FLAG_CHECK),
234 "EXISTS_FLAG_CHECK");
235
236 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
237 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
238
239 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_EXISTS_FLAG_CHECK),
240 "EXISTS_FLAG_CHECK");
241}
242
243TEST(PublicDataTreeConstrainingTest, NegativeNextSlotIsZero)
244{
245 // Test constraint: leaf_not_exists * (low_leaf_next_slot * (NEXT_SLOT_IS_ZERO * (1 - next_slot_inv) +
246 // next_slot_inv) - 1 + NEXT_SLOT_IS_ZERO) = 0
247 TestTraceContainer trace({
248 {
249 { C::public_data_check_leaf_not_exists, 1 },
250 { C::public_data_check_low_leaf_next_slot, 0 },
251 { C::public_data_check_next_slot_inv, 0 },
252 { C::public_data_check_next_slot_is_nonzero, 0 },
253 },
254 {
255 { C::public_data_check_leaf_not_exists, 1 },
256 { C::public_data_check_low_leaf_next_slot, 1 },
257 { C::public_data_check_next_slot_inv, FF(1).invert() },
258 { C::public_data_check_next_slot_is_nonzero, 1 },
259 },
260 });
261
262 check_relation<public_data_check>(trace, public_data_check::SR_NEXT_SLOT_IS_ZERO_CHECK);
263
264 trace.set(C::public_data_check_next_slot_is_nonzero, 0, 1);
265
266 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_NEXT_SLOT_IS_ZERO_CHECK),
267 "NEXT_SLOT_IS_ZERO_CHECK");
268
269 trace.set(C::public_data_check_next_slot_is_nonzero, 0, 0);
270 trace.set(C::public_data_check_next_slot_is_nonzero, 1, 0);
271
272 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_NEXT_SLOT_IS_ZERO_CHECK),
273 "NEXT_SLOT_IS_ZERO_CHECK");
274}
275
276TEST(PublicDataTreeConstrainingTest, NegativeValueIsCorrect)
277{
278 // Test constraint: leaf_not_exists * (low_leaf_next_slot * (NEXT_SLOT_IS_ZERO * (1 - next_slot_inv) +
279 // next_slot_inv) - 1 + NEXT_SLOT_IS_ZERO) = 0
280 TestTraceContainer trace({
281 {
282 { C::public_data_check_low_leaf_value, 27 },
283 { C::public_data_check_leaf_not_exists, 0 },
284 { C::public_data_check_value, 27 },
285 },
286 {
287 { C::public_data_check_low_leaf_value, 27 },
288 { C::public_data_check_leaf_not_exists, 1 },
289 { C::public_data_check_value, 0 },
290 },
291 });
292
293 check_relation<public_data_check>(trace, public_data_check::SR_VALUE_IS_CORRECT);
294
295 // Invalid, if leaf exists, the value should be the low leaf value
296 trace.set(C::public_data_check_value, 0, 0);
297
298 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_VALUE_IS_CORRECT),
299 "VALUE_IS_CORRECT");
300
301 trace.set(C::public_data_check_value, 0, 27);
302 // Invalid, if leaf does not exists, the value should be zero
303 trace.set(C::public_data_check_value, 1, 27);
304
305 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_VALUE_IS_CORRECT),
306 "VALUE_IS_CORRECT");
307}
308
309TEST_F(PublicDataTreeCheckConstrainingTest, PositiveWriteExists)
310{
311 FF slot = 40;
312 FF leaf_slot = unconstrained_compute_leaf_slot(contract_address, slot);
313 FF new_value = 27;
314 TestMemoryTree<Poseidon2HashPolicy> public_data_tree(8, PUBLIC_DATA_TREE_HEIGHT);
315
316 AvmAccumulatedData accumulated_data = {};
317 accumulated_data.publicDataWrites[0] = PublicDataWrite{
318 .leafSlot = leaf_slot,
319 .value = new_value,
320 };
321
322 auto test_public_inputs = testing::PublicInputsBuilder()
323 .set_accumulated_data(accumulated_data)
324 .set_accumulated_data_array_lengths({ .publicDataWrites = 1 })
325 .build();
326
327 EventEmitter<MerkleCheckEvent> merkle_event_emitter;
328 MerkleCheck merkle_check(poseidon2, merkle_event_emitter);
329
330 EventEmitter<RangeCheckEvent> range_check_emitter;
331 RangeCheck range_check(range_check_emitter);
332
333 EventEmitter<FieldGreaterThanEvent> field_gt_event_emitter;
334 FieldGreaterThan field_gt(range_check, field_gt_event_emitter);
335
336 EventEmitter<PublicDataTreeCheckEvent> public_data_tree_check_event_emitter;
337 PublicDataTreeCheck public_data_tree_check_simulator(
338 poseidon2, merkle_check, field_gt, execution_id_manager, public_data_tree_check_event_emitter);
339
340 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } } });
341 RangeCheckTraceBuilder range_check_builder;
342 Poseidon2TraceBuilder poseidon2_builder;
343 MerkleCheckTraceBuilder merkle_check_builder;
344 FieldGreaterThanTraceBuilder field_gt_builder;
345 PrecomputedTraceBuilder precomputed_builder;
346 PublicInputsTraceBuilder public_inputs_builder;
347 PublicDataTreeTraceBuilder public_data_tree_builder;
348
349 PublicDataTreeLeafPreimage low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, 1), 0, 0);
350 FF low_leaf_hash = UnconstrainedPoseidon2::hash(low_leaf.get_hash_inputs());
351 uint64_t low_leaf_index = 30;
352 public_data_tree.update_element(low_leaf_index, low_leaf_hash);
353
354 AppendOnlyTreeSnapshot prev_snapshot =
355 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(), .nextAvailableLeafIndex = 128 };
356 std::vector<FF> low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
357
358 PublicDataTreeLeafPreimage updated_low_leaf = low_leaf;
359 updated_low_leaf.leaf.value = new_value;
360 FF updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
361 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
362
363 FF intermediate_root = public_data_tree.root();
364 std::vector<FF> insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
365
366 // No insertion happens
367 AppendOnlyTreeSnapshot next_snapshot =
368 AppendOnlyTreeSnapshot{ .root = intermediate_root,
369 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex };
370
371 AppendOnlyTreeSnapshot result_snapshot = public_data_tree_check_simulator.write(slot,
372 contract_address,
373 new_value,
374 low_leaf,
375 low_leaf_index,
376 low_leaf_sibling_path,
377 prev_snapshot,
378 insertion_sibling_path,
379 false);
380 EXPECT_EQ(next_snapshot, result_snapshot);
381
382 precomputed_builder.process_misc(trace, AVM_PUBLIC_INPUTS_COLUMNS_MAX_LENGTH);
383 public_inputs_builder.process_public_inputs(trace, test_public_inputs);
384 public_inputs_builder.process_public_inputs_aux_precomputed(trace);
385 range_check_builder.process(range_check_emitter.dump_events(), trace);
386 poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
387 merkle_check_builder.process(merkle_event_emitter.dump_events(), trace);
388 field_gt_builder.process(field_gt_event_emitter.dump_events(), trace);
389 public_data_tree_builder.process(public_data_tree_check_event_emitter.dump_events(), trace);
390
391 check_relation<public_data_check>(trace);
392 check_relation<public_data_squash>(trace);
393
394 check_all_interactions<PublicDataTreeTraceBuilder>(trace);
395}
396
397TEST_F(PublicDataTreeCheckConstrainingTest, PositiveSquashing)
398{
399 // This test will write
400 // 1. slot 42 with value 27
401 // 2. (dummy write to check ordering) slot 50 with value 0
402 // 3. slot 42 with value 28
403 // If squashing is correct, we should get (42, 28), (50, 0)
404 FF slot = 42;
405 FF leaf_slot = unconstrained_compute_leaf_slot(contract_address, slot);
406 FF new_value = 27; // Will get squashed
407 FF updated_value = 28;
408
409 FF dummy_slot = 50;
410 FF dummy_leaf_slot = unconstrained_compute_leaf_slot(contract_address, dummy_slot);
411 FF dummy_leaf_value = 0;
412
413 // The expected tree order is 40 => leaf_slot => dummy_leaf_slot
414 ASSERT_GT(dummy_leaf_slot, leaf_slot);
415
416 FF low_leaf_slot = 40;
417 TestMemoryTree<Poseidon2HashPolicy> public_data_tree(8, PUBLIC_DATA_TREE_HEIGHT);
418
419 AvmAccumulatedData accumulated_data = {};
420 accumulated_data.publicDataWrites[0] = PublicDataWrite{
421 .leafSlot = leaf_slot,
422 .value = updated_value,
423 };
424
425 accumulated_data.publicDataWrites[1] = PublicDataWrite{
426 .leafSlot = dummy_leaf_slot,
427 .value = dummy_leaf_value,
428 };
429
430 auto test_public_inputs = testing::PublicInputsBuilder()
431 .set_accumulated_data(accumulated_data)
432 .set_accumulated_data_array_lengths({ .publicDataWrites = 2 })
433 .build();
434
435 EventEmitter<MerkleCheckEvent> merkle_event_emitter;
436 MerkleCheck merkle_check(poseidon2, merkle_event_emitter);
437
438 EventEmitter<RangeCheckEvent> range_check_emitter;
439 RangeCheck range_check(range_check_emitter);
440
441 EventEmitter<FieldGreaterThanEvent> field_gt_event_emitter;
442 FieldGreaterThan field_gt(range_check, field_gt_event_emitter);
443
444 EventEmitter<PublicDataTreeCheckEvent> public_data_tree_check_event_emitter;
445 PublicDataTreeCheck public_data_tree_check_simulator(
446 poseidon2, merkle_check, field_gt, execution_id_manager, public_data_tree_check_event_emitter);
447
448 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } } });
449 RangeCheckTraceBuilder range_check_builder;
450 Poseidon2TraceBuilder poseidon2_builder;
451 MerkleCheckTraceBuilder merkle_check_builder;
452 FieldGreaterThanTraceBuilder field_gt_builder;
453 PrecomputedTraceBuilder precomputed_builder;
454 PublicInputsTraceBuilder public_inputs_builder;
455 PublicDataTreeTraceBuilder public_data_tree_read_builder;
456
457 PublicDataTreeLeafPreimage low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(low_leaf_slot, 1), 0, 0);
458 FF low_leaf_hash = UnconstrainedPoseidon2::hash(low_leaf.get_hash_inputs());
459 uint64_t low_leaf_index = 30;
460 public_data_tree.update_element(low_leaf_index, low_leaf_hash);
461
462 AppendOnlyTreeSnapshot prev_snapshot =
463 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(), .nextAvailableLeafIndex = 128 };
464 std::vector<FF> low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
465
466 // Insertion section
467
468 PublicDataTreeLeafPreimage updated_low_leaf = low_leaf;
469 updated_low_leaf.nextIndex = prev_snapshot.nextAvailableLeafIndex;
470 updated_low_leaf.nextKey = leaf_slot;
471 FF updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
472 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
473
474 std::vector<FF> insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
475
476 PublicDataTreeLeafPreimage new_leaf =
477 PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, new_value), low_leaf.nextIndex, low_leaf.nextKey);
478 FF new_leaf_hash = UnconstrainedPoseidon2::hash(new_leaf.get_hash_inputs());
479
480 uint64_t value_to_be_updated_leaf_index = prev_snapshot.nextAvailableLeafIndex;
481 public_data_tree.update_element(value_to_be_updated_leaf_index, new_leaf_hash);
482
483 AppendOnlyTreeSnapshot next_snapshot =
484 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
485 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex + 1 };
486
487 AppendOnlyTreeSnapshot snapshot_after_insertion = public_data_tree_check_simulator.write(slot,
488 contract_address,
489 new_value,
490 low_leaf,
491 low_leaf_index,
492 low_leaf_sibling_path,
493 prev_snapshot,
494 insertion_sibling_path,
495 false);
496 EXPECT_EQ(next_snapshot, snapshot_after_insertion);
497
498 // Dummy insertion section
499
500 low_leaf_index = prev_snapshot.nextAvailableLeafIndex;
501 prev_snapshot = snapshot_after_insertion;
502
503 low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, new_value), 0, 0);
504 low_leaf_hash = UnconstrainedPoseidon2::hash(low_leaf.get_hash_inputs());
505 low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
506
507 updated_low_leaf = low_leaf;
508 updated_low_leaf.nextIndex = prev_snapshot.nextAvailableLeafIndex;
509 updated_low_leaf.nextKey = dummy_leaf_slot;
510 updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
511 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
512
513 insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
514
515 new_leaf = PublicDataTreeLeafPreimage(
516 PublicDataLeafValue(dummy_leaf_slot, dummy_leaf_value), low_leaf.nextIndex, low_leaf.nextKey);
517 new_leaf_hash = UnconstrainedPoseidon2::hash(new_leaf.get_hash_inputs());
518
519 uint64_t dummy_leaf_index = prev_snapshot.nextAvailableLeafIndex;
520 public_data_tree.update_element(dummy_leaf_index, new_leaf_hash);
521
522 next_snapshot = AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
523 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex + 1 };
524
525 AppendOnlyTreeSnapshot snapshot_after_dummy_insertion =
526 public_data_tree_check_simulator.write(dummy_slot,
527 contract_address,
528 dummy_leaf_value,
529 low_leaf,
530 low_leaf_index,
531 low_leaf_sibling_path,
532 prev_snapshot,
533 insertion_sibling_path,
534 false);
535 EXPECT_EQ(next_snapshot, snapshot_after_dummy_insertion);
536
537 // Update section
538
539 low_leaf_index = value_to_be_updated_leaf_index;
540 prev_snapshot = snapshot_after_dummy_insertion;
541
542 low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, new_value), dummy_leaf_index, dummy_leaf_slot);
543 low_leaf_hash = UnconstrainedPoseidon2::hash(low_leaf.get_hash_inputs());
544 low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
545
546 updated_low_leaf = low_leaf;
547 updated_low_leaf.leaf.value = updated_value;
548 updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
549 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
550
551 insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
552
553 // No insertion happens
554 next_snapshot = AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
555 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex };
556
557 AppendOnlyTreeSnapshot snapshot_after_update = public_data_tree_check_simulator.write(slot,
558 contract_address,
559 updated_value,
560 low_leaf,
561 low_leaf_index,
562 low_leaf_sibling_path,
563 prev_snapshot,
564 insertion_sibling_path,
565 true);
566 EXPECT_EQ(next_snapshot, snapshot_after_update);
567
568 precomputed_builder.process_misc(trace, AVM_PUBLIC_INPUTS_COLUMNS_MAX_LENGTH);
569 public_inputs_builder.process_public_inputs(trace, test_public_inputs);
570 public_inputs_builder.process_public_inputs_aux_precomputed(trace);
571 range_check_builder.process(range_check_emitter.dump_events(), trace);
572 poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
573 merkle_check_builder.process(merkle_event_emitter.dump_events(), trace);
574 field_gt_builder.process(field_gt_event_emitter.dump_events(), trace);
575 public_data_tree_read_builder.process(public_data_tree_check_event_emitter.dump_events(), trace);
576
577 check_relation<public_data_check>(trace);
578 check_relation<public_data_squash>(trace);
579
580 check_all_interactions<PublicDataTreeTraceBuilder>(trace);
581}
582
583TEST(PublicDataTreeConstrainingTest, NegativeLowLeafValueUpdate)
584{
585 // Test constraint: write * ((low_leaf_value - value) * leaf_not_exists + value - updated_low_leaf_value) = 0
586 TestTraceContainer trace({
587 {
588 { C::public_data_check_write, 1 },
589 { C::public_data_check_leaf_not_exists, 0 },
590 { C::public_data_check_low_leaf_value, 27 },
591 { C::public_data_check_value, 28 },
592 { C::public_data_check_updated_low_leaf_value, 28 },
593 },
594 {
595 { C::public_data_check_write, 1 },
596 { C::public_data_check_leaf_not_exists, 1 },
597 { C::public_data_check_low_leaf_value, 27 },
598 { C::public_data_check_value, 28 },
599 { C::public_data_check_updated_low_leaf_value, 27 },
600 },
601 });
602
603 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE);
604
605 // Invalid, if leaf exists, updated_low_leaf_value should be the value to write
606 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
607
608 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE),
609 "LOW_LEAF_VALUE_UPDATE");
610
611 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
612 // Invalid, if leaf does not exist, updated_low_leaf_value should be the low leaf value
613 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
614
615 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE),
616 "LOW_LEAF_VALUE_UPDATE");
617}
618
619TEST(PublicDataTreeConstrainingTest, NegativeLowLeafNextIndexUpdate)
620{
621 // Test constraint: write * ((tree_size_before_write - low_leaf_next_index) * leaf_not_exists + low_leaf_next_index
622 // - updated_low_leaf_next_index) = 0
623 TestTraceContainer trace({
624 {
625 { C::public_data_check_write, 1 },
626 { C::public_data_check_leaf_not_exists, 0 },
627 { C::public_data_check_low_leaf_next_index, 27 },
628 { C::public_data_check_tree_size_before_write, 128 },
629 { C::public_data_check_updated_low_leaf_next_index, 27 },
630 },
631 {
632 { C::public_data_check_write, 1 },
633 { C::public_data_check_leaf_not_exists, 1 },
634 { C::public_data_check_low_leaf_next_index, 27 },
635 { C::public_data_check_tree_size_before_write, 128 },
636 { C::public_data_check_updated_low_leaf_next_index, 128 },
637 },
638 });
639
640 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE);
641
642 // Invalid, if leaf not exists, the updated_low_leaf_next_index should be the newly inserted leaf
643 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
644
645 EXPECT_THROW_WITH_MESSAGE(
646 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE),
647 "LOW_LEAF_NEXT_INDEX_UPDATE");
648
649 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
650 // Invalid, if leaf exists, the updated_low_leaf_next_index should be untouched
651 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
652
653 EXPECT_THROW_WITH_MESSAGE(
654 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE),
655 "LOW_LEAF_NEXT_INDEX_UPDATE");
656}
657
658TEST(PublicDataTreeConstrainingTest, NegativeLowLeafNextSlotUpdate)
659{
660 // Test constraint: write * ((leaf_slot - low_leaf_next_slot) * leaf_not_exists + low_leaf_next_slot -
661 // updated_low_leaf_next_slot) = 0
662 TestTraceContainer trace({
663 {
664 { C::public_data_check_write, 1 },
665 { C::public_data_check_leaf_not_exists, 0 },
666 { C::public_data_check_low_leaf_next_slot, 27 },
667 { C::public_data_check_leaf_slot, 28 },
668 { C::public_data_check_updated_low_leaf_next_slot, 27 },
669 },
670 {
671 { C::public_data_check_write, 1 },
672 { C::public_data_check_leaf_not_exists, 1 },
673 { C::public_data_check_low_leaf_next_slot, 27 },
674 { C::public_data_check_leaf_slot, 28 },
675 { C::public_data_check_updated_low_leaf_next_slot, 28 },
676 },
677 });
678
679 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE);
680
681 // Invalid, if leaf not exists, the updated_low_leaf_next_slot should be the newly inserted leaf slot
682 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
683
684 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE),
685 "LOW_LEAF_NEXT_SLOT_UPDATE");
686
687 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
688 // Invalid, if leaf exists, the updated_low_leaf_next_slot should be untouched
689 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
690
691 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE),
692 "LOW_LEAF_NEXT_SLOT_UPDATE");
693}
694
695TEST(PublicDataTreeConstrainingTest, NegativeUpdateRootValidation)
696{
697 // Test constraint: (1 - leaf_not_exists) * write * (write_root - intermediate_root) = 0
698 TestTraceContainer trace({
699 {
700 { C::public_data_check_write, 1 },
701 { C::public_data_check_leaf_not_exists, 0 },
702 { C::public_data_check_intermediate_root, 28 },
703 { C::public_data_check_write_root, 28 },
704 },
705 {
706 { C::public_data_check_write, 1 },
707 { C::public_data_check_leaf_not_exists, 1 },
708 { C::public_data_check_intermediate_root, 28 },
709 { C::public_data_check_write_root, 30 },
710 },
711 });
712
713 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE);
714
715 // Invalid, if leaf exists, the write root should be the intermediate root
716 trace.set(C::public_data_check_write_root, 0, 30);
717
718 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_UPDATE_ROOT_VALIDATION),
719 "UPDATE_ROOT_VALIDATION");
720}
721
722TEST(PublicDataTreeConstrainingTest, NegativeWriteIdxInitialValue)
723{
724 // Test constraint: (1 - sel) * sel' * (constants.AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX
725 // - write_idx') = 0
726 TestTraceContainer trace(
727 { {
728 { C::public_data_check_sel, 0 },
729 },
730 {
731 { C::public_data_check_sel, 1 },
732 { C::public_data_check_write_idx, AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX },
733 } });
734
735 check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INITIAL_VALUE);
736
737 // Invalid, if sel goes from 0 to 1, the write_idx should be the initial value
738 trace.set(C::public_data_check_write_idx, 1, 27);
739
740 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INITIAL_VALUE),
741 "WRITE_IDX_INITIAL_VALUE");
742}
743
744TEST(PublicDataTreeConstrainingTest, NegativeWriteIdxIncrement)
745{
746 // Test constraint: not_end * (write_idx + should_write_to_public_inputs - write_idx') = 0
747 TestTraceContainer trace({
748 {
749 { C::public_data_check_not_end, 1 },
750 { C::public_data_check_write_idx, 5 },
751 { C::public_data_check_should_write_to_public_inputs, 1 },
752 },
753 {
754 { C::public_data_check_not_end, 1 },
755 { C::public_data_check_write_idx, 6 },
756 { C::public_data_check_should_write_to_public_inputs, 0 },
757 },
758 {
759 { C::public_data_check_write_idx, 6 },
760 },
761 });
762
763 check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT);
764
765 // Invalid, if should_write_to_public_inputs is 0, the write_idx should not increment
766 trace.set(C::public_data_check_should_write_to_public_inputs, 0, 0);
767
768 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT),
769 "WRITE_IDX_INCREMENT");
770
771 // Invalid, if should_write_to_public_inputs is 1, the write_idx should increment
772 trace.set(C::public_data_check_should_write_to_public_inputs, 0, 1);
773 trace.set(C::public_data_check_should_write_to_public_inputs, 1, 1);
774
775 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT),
776 "WRITE_IDX_INCREMENT");
777}
778
779// Squashing subtrace
780
781TEST(PublicDataTreeConstrainingTest, SquashingNegativeStartCondition)
782{
783 // Test constraint: sel' * (1 - sel) * (1 - precomputed.first_row) = 0
784 TestTraceContainer trace({ {
785 { C::public_data_squash_sel, 0 },
786 { C::precomputed_first_row, 1 },
787 },
788 {
789 { C::public_data_squash_sel, 1 },
790 },
791 {
792 { C::public_data_squash_sel, 1 },
793 } });
794
795 check_relation<public_data_squash>(trace, public_data_squash::SR_START_CONDITION);
796
797 // Invalid: sel can't be activated if prev is not the first row
798 trace.set(C::precomputed_first_row, 0, 0);
799
800 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_START_CONDITION),
801 "START_CONDITION");
802}
803
804TEST(PublicDataTreeConstrainingTest, SquashingNegativeCheckSameLeafSlot)
805{
806 // Test constraint: (sel * sel') * (1 - leaf_slot_increase) * (leaf_slot - leaf_slot') = 0
807 TestTraceContainer trace({ {
808 { C::public_data_squash_sel, 1 },
809 { C::public_data_squash_leaf_slot_increase, 1 },
810 { C::public_data_squash_leaf_slot, 27 },
811 },
812 {
813 { C::public_data_squash_sel, 1 },
814 { C::public_data_squash_leaf_slot_increase, 0 },
815 { C::public_data_squash_leaf_slot, 40 },
816 } });
817
818 check_relation<public_data_squash>(trace, public_data_squash::SR_CHECK_SAME_LEAF_SLOT);
819
820 // Invalid: if leaf_slot_increase is 0, the leaf_slot should not be different from the previous leaf_slot
821 trace.set(C::public_data_squash_leaf_slot_increase, 0, 0);
822
823 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_CHECK_SAME_LEAF_SLOT),
824 "CHECK_SAME_LEAF_SLOT");
825}
826
827TEST(PublicDataTreeConstrainingTest, SquashingNegativeFinalValuePropagation)
828{
829 // Test constraint: check_clock * (final_value - final_value') = 0;
830 TestTraceContainer trace({ {
831 { C::public_data_squash_sel, 1 },
832 { C::public_data_squash_check_clock, 1 },
833 { C::public_data_squash_final_value, 27 },
834 },
835 {
836 { C::public_data_squash_sel, 1 },
837 { C::public_data_squash_check_clock, 0 },
838 { C::public_data_squash_final_value, 27 },
839 } });
840
841 check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_PROPAGATION);
842
843 // Invalid: if final value changes, check_clk must be 0
844 trace.set(C::public_data_squash_final_value, 1, 28);
845
846 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_PROPAGATION),
847 "FINAL_VALUE_PROPAGATION");
848}
849
850TEST(PublicDataTreeConstrainingTest, SquashingNegativeFinalValueCheck)
851{
852 // Test constraint:
853 // LEAF_SLOT_END * (final_value - value) = 0;
854 TestTraceContainer trace({ {
855 { C::public_data_squash_sel, 1 },
856 { C::public_data_squash_final_value, 27 },
857 { C::public_data_squash_value, 99 },
858 },
859 {
860 { C::public_data_squash_sel, 1 },
861 { C::public_data_squash_final_value, 27 },
862 { C::public_data_squash_leaf_slot_increase, 1 },
863 { C::public_data_squash_value, 27 },
864 },
865 {
866 { C::public_data_squash_sel, 1 },
867 { C::public_data_squash_final_value, 42 },
868 { C::public_data_squash_value, 42 },
869 } });
870
871 check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK);
872
873 // Negative test: if END, value == final_value
874 trace.set(C::public_data_squash_value, 2, 99);
875
876 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK),
877 "FINAL_VALUE_CHECK");
878
879 trace.set(C::public_data_squash_value, 2, 42);
880
881 // Negative test: if leaf_slot_increase, value == final_value
882 trace.set(C::public_data_squash_value, 1, 99);
883
884 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK),
885 "FINAL_VALUE_CHECK");
886 trace.set(C::public_data_squash_value, 1, 27);
887}
888
889} // namespace
890} // namespace bb::avm2::constraining
INSTANTIATE_TEST_SUITE_P
INSTANTIATE_TEST_SUITE_P(AcirTests, AcirIntegrationSingleTest, testing::Values("a_1327_concrete_in_generic", "a_1_mul", "a_2_div", "a_3_add", "a_4_sub", "a_5_over", "a_6", "a_6_array", "a_7", "a_7_function", "aes128_encrypt", "arithmetic_binary_operations", "array_dynamic", "array_dynamic_blackbox_input", "array_dynamic_main_output", "array_dynamic_nested_blackbox_input", "array_eq", "array_if_cond_simple", "array_len", "array_neq", "array_sort", "array_to_slice", "array_to_slice_constant_length", "assert", "assert_statement", "assign_ex", "bigint", "bit_and", "bit_not", "bit_shifts_comptime", "bit_shifts_runtime", "blake3", "bool_not", "bool_or", "break_and_continue", "brillig_acir_as_brillig", "brillig_array_eq", "brillig_array_to_slice", "brillig_arrays", "brillig_assert", "brillig_bit_shifts_runtime", "brillig_blake2s", "brillig_blake3", "brillig_calls", "brillig_calls_array", "brillig_calls_conditionals", "brillig_conditional", "brillig_cow", "brillig_cow_assign", "brillig_cow_regression", "brillig_ecdsa_secp256k1", "brillig_ecdsa_secp256r1", "brillig_embedded_curve", "brillig_fns_as_values", "brillig_hash_to_field", "brillig_identity_function", "brillig_keccak", "brillig_loop", "brillig_nested_arrays", "brillig_not", "brillig_oracle", "brillig_pedersen", "brillig_recursion", "brillig_references", "brillig_schnorr", "brillig_sha256", "brillig_signed_cmp", "brillig_signed_div", "brillig_slices", "brillig_to_be_bytes", "brillig_to_bits", "brillig_to_bytes_integration", "brillig_to_le_bytes", "brillig_top_level", "brillig_uninitialized_arrays", "brillig_wrapping", "cast_bool", "closures_mut_ref", "conditional_1", "conditional_2", "conditional_regression_421", "conditional_regression_547", "conditional_regression_661", "conditional_regression_short_circuit", "conditional_regression_underflow", "custom_entry", "databus", "debug_logs", "diamond_deps_0", "double_verify_nested_proof", "double_verify_proof", "ecdsa_secp256k1", "ecdsa_secp256r1", "ecdsa_secp256r1_3x", "eddsa", "embedded_curve_ops", "field_attribute", "generics", "global_consts", "hash_to_field", "hashmap", "higher_order_functions", "if_else_chain", "import", "inline_never_basic", "integer_array_indexing", "keccak256", "main_bool_arg", "main_return", "merkle_insert", "missing_closure_env", "modules", "modules_more", "modulus", "nested_array_dynamic", "nested_array_dynamic_simple", "nested_array_in_slice", "nested_arrays_from_brillig", "no_predicates_basic", "no_predicates_brillig", "no_predicates_numeric_generic_poseidon", "operator_overloading", "pedersen_check", "pedersen_commitment", "pedersen_hash", "poseidon_bn254_hash", "poseidonsponge_x5_254", "pred_eq", "prelude", "references", "regression", "regression_2660", "regression_3051", "regression_3394", "regression_3607", "regression_3889", "regression_4088", "regression_4124", "regression_4202", "regression_4449", "regression_4709", "regression_5045", "regression_capacity_tracker", "regression_mem_op_predicate", "regression_method_cannot_be_found", "regression_struct_array_conditional", "schnorr", "sha256", "sha2_byte", "side_effects_constrain_array", "signed_arithmetic", "signed_comparison", "signed_division", "simple_2d_array", "simple_add_and_ret_arr", "simple_array_param", "simple_bitwise", "simple_comparison", "simple_mut", "simple_not", "simple_print", "simple_program_addition", "simple_radix", "simple_shield", "simple_shift_left_right", "slice_coercion", "slice_dynamic_index", "slice_loop", "slices", "strings", "struct", "struct_array_inputs", "struct_fields_ordering", "struct_inputs", "submodules", "to_be_bytes", "to_bytes_consistent", "to_bytes_integration", "to_le_bytes", "trait_as_return_type", "trait_impl_base_type", "traits_in_crates_1", "traits_in_crates_2", "tuple_inputs", "tuples", "type_aliases", "u128", "u16_support", "unconstrained_empty", "unit_value", "unsafe_range_constraint", "witness_compression", "xor"))
TEST_P
TEST_P(AcirIntegrationSingleTest, DISABLED_ProveAndVerifyProgram)
Definition acir_integration.test.cpp:123
avm_inputs.hpp
AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX
#define AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX
Definition aztec_constants.hpp:162
AVM_PUBLIC_INPUTS_COLUMNS_MAX_LENGTH
#define AVM_PUBLIC_INPUTS_COLUMNS_MAX_LENGTH
Definition aztec_constants.hpp:165
PUBLIC_DATA_TREE_HEIGHT
#define PUBLIC_DATA_TREE_HEIGHT
Definition aztec_constants.hpp:5
check_relation.hpp
bb::avm2::public_data_check
Definition public_data_check.hpp:34
bb::avm2::public_data_check::SR_START_CONDITION
static constexpr size_t SR_START_CONDITION
Definition public_data_check.hpp:66
bb::avm2::public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE
static constexpr size_t SR_LOW_LEAF_NEXT_INDEX_UPDATE
Definition public_data_check.hpp:70
bb::avm2::public_data_check::SR_VALUE_IS_CORRECT
static constexpr size_t SR_VALUE_IS_CORRECT
Definition public_data_check.hpp:72
bb::avm2::public_data_check::SR_EXISTS_FLAG_CHECK
static constexpr size_t SR_EXISTS_FLAG_CHECK
Definition public_data_check.hpp:67
bb::avm2::public_data_check::SR_NEXT_SLOT_IS_ZERO_CHECK
static constexpr size_t SR_NEXT_SLOT_IS_ZERO_CHECK
Definition public_data_check.hpp:68
bb::avm2::public_data_check::SR_LOW_LEAF_VALUE_UPDATE
static constexpr size_t SR_LOW_LEAF_VALUE_UPDATE
Definition public_data_check.hpp:69
bb::avm2::public_data_check::SR_WRITE_IDX_INITIAL_VALUE
static constexpr size_t SR_WRITE_IDX_INITIAL_VALUE
Definition public_data_check.hpp:74
bb::avm2::public_data_check::SR_UPDATE_ROOT_VALIDATION
static constexpr size_t SR_UPDATE_ROOT_VALIDATION
Definition public_data_check.hpp:73
bb::avm2::public_data_check::SR_WRITE_IDX_INCREMENT
static constexpr size_t SR_WRITE_IDX_INCREMENT
Definition public_data_check.hpp:75
bb::avm2::public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE
static constexpr size_t SR_LOW_LEAF_NEXT_SLOT_UPDATE
Definition public_data_check.hpp:71
bb::avm2::public_data_squash
Definition public_data_squash.hpp:33
bb::avm2::public_data_squash::SR_START_CONDITION
static constexpr size_t SR_START_CONDITION
Definition public_data_squash.hpp:53
bb::avm2::public_data_squash::SR_FINAL_VALUE_CHECK
static constexpr size_t SR_FINAL_VALUE_CHECK
Definition public_data_squash.hpp:56
bb::avm2::public_data_squash::SR_CHECK_SAME_LEAF_SLOT
static constexpr size_t SR_CHECK_SAME_LEAF_SLOT
Definition public_data_squash.hpp:54
bb::avm2::public_data_squash::SR_FINAL_VALUE_PROPAGATION
static constexpr size_t SR_FINAL_VALUE_PROPAGATION
Definition public_data_squash.hpp:55
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:36
bb::crypto::Poseidon2::hash
static FF hash(const std::vector< FF > &input)
Hashes a vector of field elements.
bb::crypto::merkle_tree::ContentAddressedIndexedTree
Implements a parallelized batch insertion indexed tree Accepts template argument of the type of store...
Definition content_addressed_indexed_tree.hpp:52
range_check_builder
RangeCheckTraceBuilder range_check_builder
Definition alu.test.cpp:120
precomputed_builder
PrecomputedTraceBuilder precomputed_builder
Definition alu.test.cpp:119
field_gt_builder
FieldGreaterThanTraceBuilder field_gt_builder
Definition alu.test.cpp:121
execution_id_manager
ExecutionIdManager execution_id_manager
Definition data_copy.test.cpp:47
range_check
RangeCheck range_check
Definition data_copy.test.cpp:49
trace
TestTraceContainer trace
Definition data_copy.test.cpp:59
perm_event_emitter
NoopEventEmitter< Poseidon2PermutationEvent > perm_event_emitter
Definition merkle_check.test.cpp:567
perm_mem_event_emitter
NoopEventEmitter< Poseidon2PermutationMemoryEvent > perm_mem_event_emitter
Definition merkle_check.test.cpp:568
mock_gt
NiceMock< MockGreaterThan > mock_gt
Definition merkle_check.test.cpp:571
hash_event_emitter
EventEmitter< Poseidon2HashEvent > hash_event_emitter
Definition merkle_check.test.cpp:566
low_leaf
NullifierTreeLeafPreimage low_leaf
Definition nullifier_tree_check.test.cpp:74
contract_address
AztecAddress contract_address
Definition written_public_data_slots_tree_check.test.cpp:96
event_emitter.hpp
field_gt.hpp
field_gt_trace.hpp
flavor_settings.hpp
merkle_check.hpp
lookup_builder.hpp
lookups_public_data_check.hpp
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessage)
Definition macros.hpp:7
merkle_check_trace.hpp
mock_gt.hpp
bb::avm2::constraining::TEST_F
TEST_F(AvmRecursiveTests, GoblinRecursion)
A test of the Goblinized AVM recursive verifier.
Definition recursive_verifier.test.cpp:66
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::simulation::PublicDataTreeCheckEvent
std::variant< PublicDataTreeReadWriteEvent, CheckPointEventType > PublicDataTreeCheckEvent
Definition public_data_tree_check_event.hpp:42
bb::avm2::simulation::PublicDataTreeLeafPreimage
IndexedLeaf< PublicDataLeafValue > PublicDataTreeLeafPreimage
Definition public_data_tree_check_event.hpp:12
bb::avm2::simulation::unconstrained_root_from_path
FF unconstrained_root_from_path(const FF &leaf_value, const uint64_t leaf_index, std::span< const FF > path)
Definition merkle.cpp:12
bb::avm2::simulation::PublicDataLeafValue
::bb::crypto::merkle_tree::PublicDataLeafValue PublicDataLeafValue
Definition db_interfaces.hpp:29
bb::avm2::simulation::unconstrained_compute_leaf_slot
FF unconstrained_compute_leaf_slot(const AztecAddress &contract_address, const FF &slot)
Definition merkle.cpp:26
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:16
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
poseidon2_trace.hpp
precomputed_trace.hpp
public_data_check.hpp
slot
FF slot
Definition public_data_tree.test.cpp:95
value
FF value
Definition public_data_tree.test.cpp:96
public_data_tree_check.hpp
public_data_tree_check_event.hpp
public_data_tree_trace.hpp
public_inputs_builder.hpp
public_inputs_trace.hpp
range_check_trace.hpp
bb::crypto::merkle_tree::IndexedLeaf::leaf
LeafType leaf
Definition indexed_leaf.hpp:138
bb::crypto::merkle_tree::IndexedLeaf::get_hash_inputs
std::vector< fr > get_hash_inputs() const
Definition indexed_leaf.hpp:191
bb::crypto::merkle_tree::IndexedLeaf::nextIndex
index_t nextIndex
Definition indexed_leaf.hpp:139
bb::crypto::merkle_tree::IndexedLeaf::nextKey
fr nextKey
Definition indexed_leaf.hpp:140
test_trace_container.hpp
test_tree.hpp
field_gt
NiceMock< MockFieldGreaterThan > field_gt
Definition tx_execution.test.cpp:31