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/gadgets/field_gt.hpp"
17#include "barretenberg/vm2/simulation/gadgets/poseidon2.hpp"
18#include "barretenberg/vm2/simulation/gadgets/public_data_tree_check.hpp"
19#include "barretenberg/vm2/simulation/lib/merkle.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::DeduplicatingEventEmitter;
44using simulation::EventEmitter;
45using simulation::ExecutionIdManager;
46using simulation::FieldGreaterThan;
47using simulation::FieldGreaterThanEvent;
48using simulation::MerkleCheck;
49using simulation::MerkleCheckEvent;
50using simulation::MockGreaterThan;
51using simulation::Poseidon2;
52using simulation::Poseidon2HashEvent;
53using simulation::Poseidon2PermutationEvent;
54using simulation::Poseidon2PermutationMemoryEvent;
55using simulation::PublicDataTreeCheck;
56using simulation::PublicDataTreeCheckEvent;
57using simulation::PublicDataTreeLeafPreimage;
58using simulation::RangeCheck;
59using simulation::RangeCheckEvent;
60using simulation::unconstrained_compute_leaf_slot;
61using simulation::unconstrained_root_from_path;
62
63using tracegen::FieldGreaterThanTraceBuilder;
64using tracegen::MerkleCheckTraceBuilder;
65using tracegen::Poseidon2TraceBuilder;
66using tracegen::PrecomputedTraceBuilder;
67using tracegen::PublicDataTreeTraceBuilder;
68using tracegen::PublicInputsTraceBuilder;
69using tracegen::RangeCheckTraceBuilder;
70using tracegen::TestTraceContainer;
71
72using FF = AvmFlavorSettings::FF;
73using C = Column;
74using public_data_check = bb::avm2::public_data_check<FF>;
75using public_data_squash = bb::avm2::public_data_squash<FF>;
76using UnconstrainedPoseidon2 = crypto::Poseidon2<crypto::Poseidon2Bn254ScalarFieldParams>;
77
78AztecAddress contract_address = 1;
79
80class PublicDataTreeCheckConstrainingTest : public ::testing::Test {
81 protected:
82 PublicDataTreeCheckConstrainingTest()
83 : execution_id_manager(0) {};
84
85 EventEmitter<Poseidon2HashEvent> hash_event_emitter;
86 EventEmitter<Poseidon2PermutationEvent> perm_event_emitter;
87 EventEmitter<Poseidon2PermutationMemoryEvent> perm_mem_event_emitter;
88
89 ExecutionIdManager execution_id_manager;
90 NiceMock<MockGreaterThan> mock_gt;
91 Poseidon2 poseidon2 =
92 Poseidon2(execution_id_manager, mock_gt, hash_event_emitter, perm_event_emitter, perm_mem_event_emitter);
93};
94
95struct TestParams {
96 FF slot;
97 FF value;
98 PublicDataTreeLeafPreimage low_leaf;
99};
100
101std::vector<TestParams> positive_tests = {
102 // Exists = true, leaf pointers to infinity
103 TestParams{ .slot = 42,
104 .value = 27,
105 .low_leaf = PublicDataTreeLeafPreimage(
106 PublicDataLeafValue(unconstrained_compute_leaf_slot(contract_address, 42), 27), 0, 0) },
107 // Exists = true, leaf points to higher value
108 TestParams{
109 .slot = 42,
110 .value = 27,
111 .low_leaf = PublicDataTreeLeafPreimage(
112 PublicDataLeafValue(unconstrained_compute_leaf_slot(contract_address, 42), 27), 28, FF::neg_one()) },
113 // Exists = false, low leaf points to infinity
114 TestParams{ .slot = 42, .value = 0, .low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(10, 0), 0, 0) },
115 // Exists = false, low leaf points to higher value
116 TestParams{
117 .slot = 42, .value = 0, .low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(10, 0), 28, FF::neg_one()) }
118};
119
120class PublicDataReadPositiveTests : public PublicDataTreeCheckConstrainingTest,
121 public ::testing::WithParamInterface<TestParams> {};
122
123TEST_P(PublicDataReadPositiveTests, Positive)
124{
125 const auto& param = GetParam();
126
127 auto test_public_inputs = testing::PublicInputsBuilder().build();
128
129 EventEmitter<MerkleCheckEvent> merkle_event_emitter;
130 MerkleCheck merkle_check(poseidon2, merkle_event_emitter);
131
132 EventEmitter<RangeCheckEvent> range_check_emitter;
133 RangeCheck range_check(range_check_emitter);
134
135 DeduplicatingEventEmitter<FieldGreaterThanEvent> field_gt_event_emitter;
136 FieldGreaterThan field_gt(range_check, field_gt_event_emitter);
137
138 EventEmitter<PublicDataTreeCheckEvent> public_data_tree_check_event_emitter;
139 PublicDataTreeCheck public_data_tree_check_simulator(
140 poseidon2, merkle_check, field_gt, execution_id_manager, public_data_tree_check_event_emitter);
141
142 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } } });
143 RangeCheckTraceBuilder range_check_builder;
144 Poseidon2TraceBuilder poseidon2_builder;
145 MerkleCheckTraceBuilder merkle_check_builder;
146 FieldGreaterThanTraceBuilder field_gt_builder;
147 PrecomputedTraceBuilder precomputed_builder;
148 PublicInputsTraceBuilder public_inputs_builder;
149 PublicDataTreeTraceBuilder public_data_tree_read_builder;
150
151 FF low_leaf_hash = poseidon2.hash(param.low_leaf.get_hash_inputs());
152 uint64_t leaf_index = 30;
153 std::vector<FF> sibling_path;
154 sibling_path.reserve(PUBLIC_DATA_TREE_HEIGHT);
155 for (size_t i = 0; i < PUBLIC_DATA_TREE_HEIGHT; ++i) {
156 sibling_path.emplace_back(i);
157 }
158 FF root = unconstrained_root_from_path(low_leaf_hash, leaf_index, sibling_path);
159
160 public_data_tree_check_simulator.assert_read(param.slot,
161 contract_address,
162 param.value,
163 param.low_leaf,
164 leaf_index,
165 sibling_path,
166 AppendOnlyTreeSnapshot{
167 .root = root,
168 .nextAvailableLeafIndex = 128,
169 });
170
171 precomputed_builder.process_misc(trace, 1 << 16);
172 precomputed_builder.process_sel_range_16(trace);
173 public_inputs_builder.process_public_inputs(trace, test_public_inputs);
174 public_inputs_builder.process_public_inputs_aux_precomputed(trace);
175 range_check_builder.process(range_check_emitter.dump_events(), trace);
176 poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
177 merkle_check_builder.process(merkle_event_emitter.dump_events(), trace);
178 field_gt_builder.process(field_gt_event_emitter.dump_events(), trace);
179 public_data_tree_read_builder.process(public_data_tree_check_event_emitter.dump_events(), trace);
180
181 check_all_interactions<PublicDataTreeTraceBuilder>(trace);
182
183 check_relation<public_data_check>(trace);
184 check_relation<public_data_squash>(trace);
185}
186
187INSTANTIATE_TEST_SUITE_P(PublicDataTreeConstrainingTest,
188 PublicDataReadPositiveTests,
189 ::testing::ValuesIn(positive_tests));
190
191TEST(PublicDataTreeConstrainingTest, NegativeStartCondition)
192{
193 // Test constraint: sel' * (1 - sel) * (1 - precomputed.first_row) = 0
194 TestTraceContainer trace({ {
195 { C::public_data_check_sel, 0 },
196 { C::precomputed_first_row, 1 },
197 },
198 {
199 { C::public_data_check_sel, 1 },
200 },
201 {
202 { C::public_data_check_sel, 1 },
203 } });
204
205 check_relation<public_data_check>(trace, public_data_check::SR_START_CONDITION);
206
207 // Invalid: sel can't be activated if prev is not the first row
208 trace.set(C::precomputed_first_row, 0, 0);
209
210 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_START_CONDITION),
211 "START_CONDITION");
212}
213
214TEST(PublicDataTreeConstrainingTest, NegativeExistsFlagCheck)
215{
216 // Test constraint: sel * (LEAF_SLOT_LOW_LEAF_SLOT_DIFF * (LEAF_EXISTS * (1 - leaf_slot_low_leaf_slot_diff_inv) +
217 // leaf_slot_low_leaf_slot_diff_inv) - 1 + LEAF_EXISTS) = 0
218 TestTraceContainer trace({
219 { { C::public_data_check_sel, 1 },
220 { C::public_data_check_leaf_slot, 27 },
221 { C::public_data_check_low_leaf_slot, 27 },
222 { C::public_data_check_leaf_slot_low_leaf_slot_diff_inv, 0 },
223 { C::public_data_check_leaf_not_exists, 0 } },
224 { { C::public_data_check_sel, 1 },
225 { C::public_data_check_leaf_slot, 28 },
226 { C::public_data_check_low_leaf_slot, 27 },
227 { C::public_data_check_leaf_slot_low_leaf_slot_diff_inv, FF(1).invert() },
228 { C::public_data_check_leaf_not_exists, 1 } },
229 });
230
231 check_relation<public_data_check>(trace, public_data_check::SR_EXISTS_FLAG_CHECK);
232
233 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
234
235 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_EXISTS_FLAG_CHECK),
236 "EXISTS_FLAG_CHECK");
237
238 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
239 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
240
241 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_EXISTS_FLAG_CHECK),
242 "EXISTS_FLAG_CHECK");
243}
244
245TEST(PublicDataTreeConstrainingTest, NegativeNextSlotIsZero)
246{
247 // Test constraint: leaf_not_exists * (low_leaf_next_slot * (NEXT_SLOT_IS_ZERO * (1 - next_slot_inv) +
248 // next_slot_inv) - 1 + NEXT_SLOT_IS_ZERO) = 0
249 TestTraceContainer trace({
250 {
251 { C::public_data_check_leaf_not_exists, 1 },
252 { C::public_data_check_low_leaf_next_slot, 0 },
253 { C::public_data_check_next_slot_inv, 0 },
254 { C::public_data_check_next_slot_is_nonzero, 0 },
255 },
256 {
257 { C::public_data_check_leaf_not_exists, 1 },
258 { C::public_data_check_low_leaf_next_slot, 1 },
259 { C::public_data_check_next_slot_inv, FF(1).invert() },
260 { C::public_data_check_next_slot_is_nonzero, 1 },
261 },
262 });
263
264 check_relation<public_data_check>(trace, public_data_check::SR_NEXT_SLOT_IS_ZERO_CHECK);
265
266 trace.set(C::public_data_check_next_slot_is_nonzero, 0, 1);
267
268 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_NEXT_SLOT_IS_ZERO_CHECK),
269 "NEXT_SLOT_IS_ZERO_CHECK");
270
271 trace.set(C::public_data_check_next_slot_is_nonzero, 0, 0);
272 trace.set(C::public_data_check_next_slot_is_nonzero, 1, 0);
273
274 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_NEXT_SLOT_IS_ZERO_CHECK),
275 "NEXT_SLOT_IS_ZERO_CHECK");
276}
277
278TEST(PublicDataTreeConstrainingTest, NegativeValueIsCorrect)
279{
280 // Test constraint: leaf_not_exists * (low_leaf_next_slot * (NEXT_SLOT_IS_ZERO * (1 - next_slot_inv) +
281 // next_slot_inv) - 1 + NEXT_SLOT_IS_ZERO) = 0
282 TestTraceContainer trace({
283 {
284 { C::public_data_check_low_leaf_value, 27 },
285 { C::public_data_check_leaf_not_exists, 0 },
286 { C::public_data_check_value, 27 },
287 },
288 {
289 { C::public_data_check_low_leaf_value, 27 },
290 { C::public_data_check_leaf_not_exists, 1 },
291 { C::public_data_check_value, 0 },
292 },
293 });
294
295 check_relation<public_data_check>(trace, public_data_check::SR_VALUE_IS_CORRECT);
296
297 // Invalid, if leaf exists, the value should be the low leaf value
298 trace.set(C::public_data_check_value, 0, 0);
299
300 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_VALUE_IS_CORRECT),
301 "VALUE_IS_CORRECT");
302
303 trace.set(C::public_data_check_value, 0, 27);
304 // Invalid, if leaf does not exists, the value should be zero
305 trace.set(C::public_data_check_value, 1, 27);
306
307 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_VALUE_IS_CORRECT),
308 "VALUE_IS_CORRECT");
309}
310
311TEST_F(PublicDataTreeCheckConstrainingTest, PositiveWriteExists)
312{
313 FF slot = 40;
314 FF leaf_slot = unconstrained_compute_leaf_slot(contract_address, slot);
315 FF new_value = 27;
316 TestMemoryTree<Poseidon2HashPolicy> public_data_tree(8, PUBLIC_DATA_TREE_HEIGHT);
317
318 AvmAccumulatedData accumulated_data = {};
319 accumulated_data.publicDataWrites[0] = PublicDataWrite{
320 .leafSlot = leaf_slot,
321 .value = new_value,
322 };
323
324 auto test_public_inputs = testing::PublicInputsBuilder()
325 .set_accumulated_data(accumulated_data)
326 .set_accumulated_data_array_lengths({ .publicDataWrites = 1 })
327 .build();
328
329 EventEmitter<MerkleCheckEvent> merkle_event_emitter;
330 MerkleCheck merkle_check(poseidon2, merkle_event_emitter);
331
332 EventEmitter<RangeCheckEvent> range_check_emitter;
333 RangeCheck range_check(range_check_emitter);
334
335 DeduplicatingEventEmitter<FieldGreaterThanEvent> field_gt_event_emitter;
336 FieldGreaterThan field_gt(range_check, field_gt_event_emitter);
337
338 EventEmitter<PublicDataTreeCheckEvent> public_data_tree_check_event_emitter;
339 PublicDataTreeCheck public_data_tree_check_simulator(
340 poseidon2, merkle_check, field_gt, execution_id_manager, public_data_tree_check_event_emitter);
341
342 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } } });
343 RangeCheckTraceBuilder range_check_builder;
344 Poseidon2TraceBuilder poseidon2_builder;
345 MerkleCheckTraceBuilder merkle_check_builder;
346 FieldGreaterThanTraceBuilder field_gt_builder;
347 PrecomputedTraceBuilder precomputed_builder;
348 PublicInputsTraceBuilder public_inputs_builder;
349 PublicDataTreeTraceBuilder public_data_tree_builder;
350
351 PublicDataTreeLeafPreimage low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, 1), 0, 0);
352 FF low_leaf_hash = UnconstrainedPoseidon2::hash(low_leaf.get_hash_inputs());
353 uint64_t low_leaf_index = 30;
354 public_data_tree.update_element(low_leaf_index, low_leaf_hash);
355
356 AppendOnlyTreeSnapshot prev_snapshot =
357 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(), .nextAvailableLeafIndex = 128 };
358 std::vector<FF> low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
359
360 PublicDataTreeLeafPreimage updated_low_leaf = low_leaf;
361 updated_low_leaf.leaf.value = new_value;
362 FF updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
363 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
364
365 FF intermediate_root = public_data_tree.root();
366 std::vector<FF> insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
367
368 // No insertion happens
369 AppendOnlyTreeSnapshot next_snapshot =
370 AppendOnlyTreeSnapshot{ .root = intermediate_root,
371 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex };
372
373 AppendOnlyTreeSnapshot result_snapshot = public_data_tree_check_simulator.write(slot,
374 contract_address,
375 new_value,
376 low_leaf,
377 low_leaf_index,
378 low_leaf_sibling_path,
379 prev_snapshot,
380 insertion_sibling_path,
381 false);
382 EXPECT_EQ(next_snapshot, result_snapshot);
383
384 precomputed_builder.process_misc(trace, 1 << 16);
385 precomputed_builder.process_sel_range_16(trace);
386 public_inputs_builder.process_public_inputs(trace, test_public_inputs);
387 public_inputs_builder.process_public_inputs_aux_precomputed(trace);
388 range_check_builder.process(range_check_emitter.dump_events(), trace);
389 poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
390 merkle_check_builder.process(merkle_event_emitter.dump_events(), trace);
391 field_gt_builder.process(field_gt_event_emitter.dump_events(), trace);
392 public_data_tree_builder.process(public_data_tree_check_event_emitter.dump_events(), trace);
393
394 check_relation<public_data_check>(trace);
395 check_relation<public_data_squash>(trace);
396
397 check_all_interactions<PublicDataTreeTraceBuilder>(trace);
398}
399
400TEST_F(PublicDataTreeCheckConstrainingTest, PositiveSquashing)
401{
402 // This test will write
403 // 1. slot 42 with value 27
404 // 2. (dummy write to check ordering) slot 50 with value 0
405 // 3. slot 42 with value 28
406 // If squashing is correct, we should get (42, 28), (50, 0)
407 FF slot = 42;
408 FF leaf_slot = unconstrained_compute_leaf_slot(contract_address, slot);
409 FF new_value = 27; // Will get squashed
410 FF updated_value = 28;
411
412 FF dummy_slot = 50;
413 FF dummy_leaf_slot = unconstrained_compute_leaf_slot(contract_address, dummy_slot);
414 FF dummy_leaf_value = 0;
415
416 // The expected tree order is low_leaf_slot := 40 < leaf_slot < second_low_leaf_slot < dummy_leaf_slot
417 // We set second_low_leaf_slot == leaf_slot + 1. (We do not need to know the preimage for second_low_leaf_slot)
418 ASSERT_GT(dummy_leaf_slot, leaf_slot + 1);
419
420 FF low_leaf_slot = 40;
421 TestMemoryTree<Poseidon2HashPolicy> public_data_tree(8, PUBLIC_DATA_TREE_HEIGHT);
422
423 AvmAccumulatedData accumulated_data = {};
424 accumulated_data.publicDataWrites[0] = PublicDataWrite{
425 .leafSlot = leaf_slot,
426 .value = updated_value,
427 };
428
429 accumulated_data.publicDataWrites[1] = PublicDataWrite{
430 .leafSlot = dummy_leaf_slot,
431 .value = dummy_leaf_value,
432 };
433
434 auto test_public_inputs = testing::PublicInputsBuilder()
435 .set_accumulated_data(accumulated_data)
436 .set_accumulated_data_array_lengths({ .publicDataWrites = 2 })
437 .build();
438
439 EventEmitter<MerkleCheckEvent> merkle_event_emitter;
440 MerkleCheck merkle_check(poseidon2, merkle_event_emitter);
441
442 EventEmitter<RangeCheckEvent> range_check_emitter;
443 RangeCheck range_check(range_check_emitter);
444
445 DeduplicatingEventEmitter<FieldGreaterThanEvent> field_gt_event_emitter;
446 FieldGreaterThan field_gt(range_check, field_gt_event_emitter);
447
448 EventEmitter<PublicDataTreeCheckEvent> public_data_tree_check_event_emitter;
449 PublicDataTreeCheck public_data_tree_check_simulator(
450 poseidon2, merkle_check, field_gt, execution_id_manager, public_data_tree_check_event_emitter);
451
452 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } } });
453 RangeCheckTraceBuilder range_check_builder;
454 Poseidon2TraceBuilder poseidon2_builder;
455 MerkleCheckTraceBuilder merkle_check_builder;
456 FieldGreaterThanTraceBuilder field_gt_builder;
457 PrecomputedTraceBuilder precomputed_builder;
458 PublicInputsTraceBuilder public_inputs_builder;
459 PublicDataTreeTraceBuilder public_data_tree_read_builder;
460
461 // Insert leaves which are already present in the tree (test preparation)
462 PublicDataTreeLeafPreimage low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(low_leaf_slot, 1), 0, 0);
463 FF low_leaf_hash = UnconstrainedPoseidon2::hash(low_leaf.get_hash_inputs());
464 uint64_t low_leaf_index = 30;
465 public_data_tree.update_element(low_leaf_index, low_leaf_hash);
466
467 uint64_t second_low_leaf_index = 31;
468 FF second_low_leaf_slot = leaf_slot + 1;
469
470 PublicDataTreeLeafPreimage second_low_leaf =
471 PublicDataTreeLeafPreimage(PublicDataLeafValue(second_low_leaf_slot, 1), 0, 0);
472 FF second_low_leaf_hash = UnconstrainedPoseidon2::hash(second_low_leaf.get_hash_inputs());
473 public_data_tree.update_element(second_low_leaf_index, second_low_leaf_hash);
474
475 AppendOnlyTreeSnapshot prev_snapshot =
476 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(), .nextAvailableLeafIndex = 128 };
477 std::vector<FF> low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
478
479 // Insertion section
480 PublicDataTreeLeafPreimage updated_low_leaf = low_leaf;
481 updated_low_leaf.nextIndex = prev_snapshot.nextAvailableLeafIndex;
482 updated_low_leaf.nextKey = leaf_slot;
483 FF updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
484 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
485
486 std::vector<FF> insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
487
488 PublicDataTreeLeafPreimage new_leaf =
489 PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, new_value), low_leaf.nextIndex, low_leaf.nextKey);
490 FF new_leaf_hash = UnconstrainedPoseidon2::hash(new_leaf.get_hash_inputs());
491
492 uint64_t value_to_be_updated_leaf_index = prev_snapshot.nextAvailableLeafIndex;
493 public_data_tree.update_element(value_to_be_updated_leaf_index, new_leaf_hash);
494
495 AppendOnlyTreeSnapshot next_snapshot =
496 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
497 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex + 1 };
498
499 AppendOnlyTreeSnapshot snapshot_after_insertion = public_data_tree_check_simulator.write(slot,
500 contract_address,
501 new_value,
502 low_leaf,
503 low_leaf_index,
504 low_leaf_sibling_path,
505 prev_snapshot,
506 insertion_sibling_path,
507 false);
508 EXPECT_EQ(next_snapshot, snapshot_after_insertion);
509
510 // Dummy insertion section
511
512 prev_snapshot = snapshot_after_insertion;
513
514 low_leaf = second_low_leaf;
515 low_leaf_hash = second_low_leaf_hash;
516 low_leaf_index = second_low_leaf_index;
517 low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
518
519 updated_low_leaf = low_leaf;
520 updated_low_leaf.nextIndex = prev_snapshot.nextAvailableLeafIndex;
521 updated_low_leaf.nextKey = dummy_leaf_slot;
522 updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
523 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
524 insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
525
526 new_leaf = PublicDataTreeLeafPreimage(
527 PublicDataLeafValue(dummy_leaf_slot, dummy_leaf_value), low_leaf.nextIndex, low_leaf.nextKey);
528 new_leaf_hash = UnconstrainedPoseidon2::hash(new_leaf.get_hash_inputs());
529
530 uint64_t dummy_leaf_index = prev_snapshot.nextAvailableLeafIndex;
531 public_data_tree.update_element(dummy_leaf_index, new_leaf_hash);
532
533 next_snapshot = AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
534 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex + 1 };
535
536 AppendOnlyTreeSnapshot snapshot_after_dummy_insertion =
537 public_data_tree_check_simulator.write(dummy_slot,
538 contract_address,
539 dummy_leaf_value,
540 low_leaf,
541 low_leaf_index,
542 low_leaf_sibling_path,
543 prev_snapshot,
544 insertion_sibling_path,
545 false);
546 EXPECT_EQ(next_snapshot, snapshot_after_dummy_insertion);
547
548 // Update section
549
550 low_leaf_index = value_to_be_updated_leaf_index;
551 prev_snapshot = snapshot_after_dummy_insertion;
552
553 low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, new_value), 0, 0);
554 low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
555
556 updated_low_leaf = low_leaf;
557 updated_low_leaf.leaf.value = updated_value;
558 updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
559 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
560 insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.nextAvailableLeafIndex);
561
562 // No insertion happens
563 next_snapshot = AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
564 .nextAvailableLeafIndex = prev_snapshot.nextAvailableLeafIndex };
565 AppendOnlyTreeSnapshot snapshot_after_update = public_data_tree_check_simulator.write(slot,
566 contract_address,
567 updated_value,
568 low_leaf,
569 low_leaf_index,
570 low_leaf_sibling_path,
571 prev_snapshot,
572 insertion_sibling_path,
573 true);
574 EXPECT_EQ(next_snapshot, snapshot_after_update);
575
576 ASSERT_LE(test_public_inputs.accumulatedDataArrayLengths.publicDataWrites,
577 test_public_inputs.accumulatedData.publicDataWrites.size());
578
579 const auto* public_data_writes_start = test_public_inputs.accumulatedData.publicDataWrites.begin();
580 std::vector<PublicDataWrite> public_data_writes(
581 public_data_writes_start,
582 public_data_writes_start + test_public_inputs.accumulatedDataArrayLengths.publicDataWrites);
583
584 public_data_tree_check_simulator.generate_ff_gt_events_for_squashing(public_data_writes);
585
586 precomputed_builder.process_misc(trace, 1 << 16);
587 precomputed_builder.process_sel_range_16(trace);
588 public_inputs_builder.process_public_inputs(trace, test_public_inputs);
589 public_inputs_builder.process_public_inputs_aux_precomputed(trace);
590 range_check_builder.process(range_check_emitter.dump_events(), trace);
591 poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
592 merkle_check_builder.process(merkle_event_emitter.dump_events(), trace);
593 field_gt_builder.process(field_gt_event_emitter.dump_events(), trace);
594 public_data_tree_read_builder.process(public_data_tree_check_event_emitter.dump_events(), trace);
595
596 check_relation<public_data_check>(trace);
597 check_relation<public_data_squash>(trace);
598
599 check_all_interactions<PublicDataTreeTraceBuilder>(trace);
600}
601
602TEST(PublicDataTreeConstrainingTest, NegativeLowLeafValueUpdate)
603{
604 // Test constraint: write * ((low_leaf_value - value) * leaf_not_exists + value - updated_low_leaf_value) = 0
605 TestTraceContainer trace({
606 {
607 { C::public_data_check_write, 1 },
608 { C::public_data_check_leaf_not_exists, 0 },
609 { C::public_data_check_low_leaf_value, 27 },
610 { C::public_data_check_value, 28 },
611 { C::public_data_check_updated_low_leaf_value, 28 },
612 },
613 {
614 { C::public_data_check_write, 1 },
615 { C::public_data_check_leaf_not_exists, 1 },
616 { C::public_data_check_low_leaf_value, 27 },
617 { C::public_data_check_value, 28 },
618 { C::public_data_check_updated_low_leaf_value, 27 },
619 },
620 });
621
622 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE);
623
624 // Invalid, if leaf exists, updated_low_leaf_value should be the value to write
625 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
626
627 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE),
628 "LOW_LEAF_VALUE_UPDATE");
629
630 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
631 // Invalid, if leaf does not exist, updated_low_leaf_value should be the low leaf value
632 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
633
634 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE),
635 "LOW_LEAF_VALUE_UPDATE");
636}
637
638TEST(PublicDataTreeConstrainingTest, NegativeLowLeafNextIndexUpdate)
639{
640 // Test constraint: write * ((tree_size_before_write - low_leaf_next_index) * leaf_not_exists + low_leaf_next_index
641 // - updated_low_leaf_next_index) = 0
642 TestTraceContainer trace({
643 {
644 { C::public_data_check_write, 1 },
645 { C::public_data_check_leaf_not_exists, 0 },
646 { C::public_data_check_low_leaf_next_index, 27 },
647 { C::public_data_check_tree_size_before_write, 128 },
648 { C::public_data_check_updated_low_leaf_next_index, 27 },
649 },
650 {
651 { C::public_data_check_write, 1 },
652 { C::public_data_check_leaf_not_exists, 1 },
653 { C::public_data_check_low_leaf_next_index, 27 },
654 { C::public_data_check_tree_size_before_write, 128 },
655 { C::public_data_check_updated_low_leaf_next_index, 128 },
656 },
657 });
658
659 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE);
660
661 // Invalid, if leaf not exists, the updated_low_leaf_next_index should be the newly inserted leaf
662 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
663
664 EXPECT_THROW_WITH_MESSAGE(
665 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE),
666 "LOW_LEAF_NEXT_INDEX_UPDATE");
667
668 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
669 // Invalid, if leaf exists, the updated_low_leaf_next_index should be untouched
670 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
671
672 EXPECT_THROW_WITH_MESSAGE(
673 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE),
674 "LOW_LEAF_NEXT_INDEX_UPDATE");
675}
676
677TEST(PublicDataTreeConstrainingTest, NegativeLowLeafNextSlotUpdate)
678{
679 // Test constraint: write * ((leaf_slot - low_leaf_next_slot) * leaf_not_exists + low_leaf_next_slot -
680 // updated_low_leaf_next_slot) = 0
681 TestTraceContainer trace({
682 {
683 { C::public_data_check_write, 1 },
684 { C::public_data_check_leaf_not_exists, 0 },
685 { C::public_data_check_low_leaf_next_slot, 27 },
686 { C::public_data_check_leaf_slot, 28 },
687 { C::public_data_check_updated_low_leaf_next_slot, 27 },
688 },
689 {
690 { C::public_data_check_write, 1 },
691 { C::public_data_check_leaf_not_exists, 1 },
692 { C::public_data_check_low_leaf_next_slot, 27 },
693 { C::public_data_check_leaf_slot, 28 },
694 { C::public_data_check_updated_low_leaf_next_slot, 28 },
695 },
696 });
697
698 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE);
699
700 // Invalid, if leaf not exists, the updated_low_leaf_next_slot should be the newly inserted leaf slot
701 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
702
703 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE),
704 "LOW_LEAF_NEXT_SLOT_UPDATE");
705
706 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
707 // Invalid, if leaf exists, the updated_low_leaf_next_slot should be untouched
708 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
709
710 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE),
711 "LOW_LEAF_NEXT_SLOT_UPDATE");
712}
713
714TEST(PublicDataTreeConstrainingTest, NegativeUpdateRootValidation)
715{
716 // Test constraint: (1 - leaf_not_exists) * write * (write_root - intermediate_root) = 0
717 TestTraceContainer trace({
718 {
719 { C::public_data_check_write, 1 },
720 { C::public_data_check_leaf_not_exists, 0 },
721 { C::public_data_check_intermediate_root, 28 },
722 { C::public_data_check_write_root, 28 },
723 },
724 {
725 { C::public_data_check_write, 1 },
726 { C::public_data_check_leaf_not_exists, 1 },
727 { C::public_data_check_intermediate_root, 28 },
728 { C::public_data_check_write_root, 30 },
729 },
730 });
731
732 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE);
733
734 // Invalid, if leaf exists, the write root should be the intermediate root
735 trace.set(C::public_data_check_write_root, 0, 30);
736
737 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_UPDATE_ROOT_VALIDATION),
738 "UPDATE_ROOT_VALIDATION");
739}
740
741TEST(PublicDataTreeConstrainingTest, NegativeSetProtocolWrite)
742{
743 // Test constraint: protocol_write + non_protocol_write = write
744 TestTraceContainer trace({ {
745 { C::public_data_check_sel, 1 },
746 { C::public_data_check_write, 1 },
747 { C::public_data_check_protocol_write, 1 },
748 } });
749
750 check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK);
751
752 // Invalid, must set either protocol or non protocol write
753 trace.set(C::public_data_check_protocol_write, 0, 0);
754
755 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK),
756 "PROTOCOL_WRITE_CHECK");
757
758 trace.set(C::public_data_check_non_protocol_write, 0, 1);
759 check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK);
760
761 // Invalid, cannot both be a protocol and non protocol write
762 trace.set(C::public_data_check_protocol_write, 0, 1);
763 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK),
764 "PROTOCOL_WRITE_CHECK");
765}
766
767TEST(PublicDataTreeConstrainingTest, NegativeWriteIdxInitialValue)
768{
769 // Test constraint: (1 - sel) * sel' * (constants.AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX
770 // - write_idx') = 0
771 TestTraceContainer trace(
772 { {
773 { C::public_data_check_sel, 0 },
774 },
775 {
776 { C::public_data_check_sel, 1 },
777 { C::public_data_check_write_idx, AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX },
778 } });
779
780 check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INITIAL_VALUE);
781
782 // Invalid, if sel goes from 0 to 1, the write_idx should be the initial value
783 trace.set(C::public_data_check_write_idx, 1, 27);
784
785 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INITIAL_VALUE),
786 "WRITE_IDX_INITIAL_VALUE");
787}
788
789TEST(PublicDataTreeConstrainingTest, NegativeWriteIdxIncrement)
790{
791 // Test constraint: not_end * (write_idx + should_write_to_public_inputs - write_idx') = 0
792 TestTraceContainer trace({
793 {
794 { C::public_data_check_not_end, 1 },
795 { C::public_data_check_write_idx, 5 },
796 { C::public_data_check_should_write_to_public_inputs, 1 },
797 },
798 {
799 { C::public_data_check_not_end, 1 },
800 { C::public_data_check_write_idx, 6 },
801 { C::public_data_check_should_write_to_public_inputs, 0 },
802 },
803 {
804 { C::public_data_check_write_idx, 6 },
805 },
806 });
807
808 check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT);
809
810 // Invalid, if should_write_to_public_inputs is 0, the write_idx should not increment
811 trace.set(C::public_data_check_should_write_to_public_inputs, 0, 0);
812
813 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT),
814 "WRITE_IDX_INCREMENT");
815
816 // Invalid, if should_write_to_public_inputs is 1, the write_idx should increment
817 trace.set(C::public_data_check_should_write_to_public_inputs, 0, 1);
818 trace.set(C::public_data_check_should_write_to_public_inputs, 1, 1);
819
820 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT),
821 "WRITE_IDX_INCREMENT");
822}
823
824// Negative clock diff decompostion
825TEST(PublicDataTreeConstrainingTest, NegativeClockDiffDecomposition)
826{
827 // Test constraint: CLK_DIFF = clk_diff_lo + 2**16 * clk_diff_hi;
828 TestTraceContainer trace({
829 {
830 { C::public_data_check_not_end, 1 },
831 { C::public_data_check_clk, 12 << 28 },
832 { C::public_data_check_clk_diff_lo, 234 },
833 { C::public_data_check_clk_diff_hi, 1 << 12 },
834 },
835 {
836 { C::public_data_check_clk, (13 << 28) + 234 },
837 },
838 });
839
840 check_relation<public_data_check>(trace, public_data_check::SR_CLK_DIFF_DECOMP);
841
842 // Mutate wrongly clk_diff_lo
843 trace.set(C::public_data_check_clk_diff_lo, 0, trace.get(C::public_data_check_clk_diff_lo, 0) + 1);
844
845 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_CLK_DIFF_DECOMP),
846 "CLK_DIFF_DECOMP");
847
848 // Reset
849 trace.set(C::public_data_check_clk_diff_lo, 0, trace.get(C::public_data_check_clk_diff_lo, 0) - 1);
850
851 // Mutate wrongly clk_diff_hi
852 trace.set(C::public_data_check_clk_diff_hi, 0, trace.get(C::public_data_check_clk_diff_hi, 0) + 1);
853
854 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_CLK_DIFF_DECOMP),
855 "CLK_DIFF_DECOMP");
856}
857
858// Out of range clock diff
859TEST(PublicDataTreeConstrainingTest, NegativeOutOfRangeClockDiff)
860{
861 TestTraceContainer trace({
862 {
863 { C::public_data_check_not_end, 1 },
864 { C::public_data_check_clk_diff_lo, UINT16_MAX },
865 { C::public_data_check_clk_diff_hi, UINT16_MAX },
866 },
867 });
868
869 PrecomputedTraceBuilder precomputed_trace_builder;
870 precomputed_trace_builder.process_sel_range_16(trace);
871 precomputed_trace_builder.process_misc(trace, 1 << 16);
872
873 check_interaction<PublicDataTreeTraceBuilder,
874 lookup_public_data_check_clk_diff_range_lo_settings,
875 lookup_public_data_check_clk_diff_range_hi_settings>(trace);
876
877 // Mutate wrongly clk_diff_lo
878 trace.set(C::public_data_check_clk_diff_lo, 0, UINT16_MAX + 1);
879
880 EXPECT_THROW_WITH_MESSAGE(
881 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_check_clk_diff_range_lo_settings>(trace)),
882 "Failed.*LOOKUP_PUBLIC_DATA_CHECK_CLK_DIFF_RANGE_LO. Could not find tuple in destination.");
883
884 // Mutate wrongly clk_diff_hi
885 trace.set(C::public_data_check_clk_diff_hi, 0, UINT16_MAX + 1);
886
887 EXPECT_THROW_WITH_MESSAGE(
888 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_check_clk_diff_range_hi_settings>(trace)),
889 "Failed.*LOOKUP_PUBLIC_DATA_CHECK_CLK_DIFF_RANGE_HI. Could not find tuple in destination.");
890}
891
892// Squashing subtrace
893
894TEST(PublicDataTreeConstrainingTest, SquashingNegativeStartCondition)
895{
896 // Test constraint: sel' * (1 - sel) * (1 - precomputed.first_row) = 0
897 TestTraceContainer trace({ {
898 { C::public_data_squash_sel, 0 },
899 { C::precomputed_first_row, 1 },
900 },
901 {
902 { C::public_data_squash_sel, 1 },
903 },
904 {
905 { C::public_data_squash_sel, 1 },
906 } });
907
908 check_relation<public_data_squash>(trace, public_data_squash::SR_START_CONDITION);
909
910 // Invalid: sel can't be activated if prev is not the first row
911 trace.set(C::precomputed_first_row, 0, 0);
912
913 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_START_CONDITION),
914 "START_CONDITION");
915}
916
917TEST(PublicDataTreeConstrainingTest, SquashingNegativeCheckSameLeafSlot)
918{
919 // Test constraint: (sel * sel') * (1 - leaf_slot_increase) * (leaf_slot - leaf_slot') = 0
920 TestTraceContainer trace({ {
921 { C::public_data_squash_sel, 1 },
922 { C::public_data_squash_leaf_slot_increase, 1 },
923 { C::public_data_squash_leaf_slot, 27 },
924 },
925 {
926 { C::public_data_squash_sel, 1 },
927 { C::public_data_squash_leaf_slot_increase, 0 },
928 { C::public_data_squash_leaf_slot, 40 },
929 } });
930
931 check_relation<public_data_squash>(trace, public_data_squash::SR_CHECK_SAME_LEAF_SLOT);
932
933 // Invalid: if leaf_slot_increase is 0, the leaf_slot should not be different from the previous leaf_slot
934 trace.set(C::public_data_squash_leaf_slot_increase, 0, 0);
935
936 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_CHECK_SAME_LEAF_SLOT),
937 "CHECK_SAME_LEAF_SLOT");
938}
939
940TEST(PublicDataTreeConstrainingTest, SquashingNegativeFinalValuePropagation)
941{
942 // Test constraint: check_clock * (final_value - final_value') = 0;
943 TestTraceContainer trace({ {
944 { C::public_data_squash_sel, 1 },
945 { C::public_data_squash_check_clock, 1 },
946 { C::public_data_squash_final_value, 27 },
947 },
948 {
949 { C::public_data_squash_sel, 1 },
950 { C::public_data_squash_check_clock, 0 },
951 { C::public_data_squash_final_value, 27 },
952 } });
953
954 check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_PROPAGATION);
955
956 // Invalid: if final value changes, check_clk must be 0
957 trace.set(C::public_data_squash_final_value, 1, 28);
958
959 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_PROPAGATION),
960 "FINAL_VALUE_PROPAGATION");
961}
962
963TEST(PublicDataTreeConstrainingTest, SquashingNegativeFinalValueCheck)
964{
965 // Test constraint:
966 // LEAF_SLOT_END * (final_value - value) = 0;
967 TestTraceContainer trace({ {
968 { C::public_data_squash_sel, 1 },
969 { C::public_data_squash_final_value, 27 },
970 { C::public_data_squash_value, 99 },
971 },
972 {
973 { C::public_data_squash_sel, 1 },
974 { C::public_data_squash_final_value, 27 },
975 { C::public_data_squash_leaf_slot_increase, 1 },
976 { C::public_data_squash_value, 27 },
977 },
978 {
979 { C::public_data_squash_sel, 1 },
980 { C::public_data_squash_final_value, 42 },
981 { C::public_data_squash_value, 42 },
982 } });
983
984 check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK);
985
986 // Negative test: if END, value == final_value
987 trace.set(C::public_data_squash_value, 2, 99);
988
989 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK),
990 "FINAL_VALUE_CHECK");
991
992 trace.set(C::public_data_squash_value, 2, 42);
993
994 // Negative test: if leaf_slot_increase, value == final_value
995 trace.set(C::public_data_squash_value, 1, 99);
996
997 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK),
998 "FINAL_VALUE_CHECK");
999 trace.set(C::public_data_squash_value, 1, 27);
1000}
1001
1002TEST(PublicDataTreeConstrainingTest, SquashingNegativeLeafSlotIncrease)
1003{
1004 // Test constraint: leaf_slot_increase { leaf_slot', leaf_slot, sel } in ff_gt.sel_gt { ff_gt.a, ff_gt.b,
1005 // ff_gt.result }
1006 TestTraceContainer trace({ {
1007 { C::public_data_squash_leaf_slot_increase, 1 },
1008 { C::public_data_squash_leaf_slot, FF::modulus_minus_two },
1009 { C::public_data_squash_sel, 1 },
1010 },
1011 {
1012 { C::public_data_squash_leaf_slot_increase, 0 },
1013 { C::public_data_squash_leaf_slot, FF::modulus - 1 },
1014 { C::public_data_squash_sel, 1 },
1015 } });
1016
1017 // Corresponding ff_gt values. For this trace we keep the correct result.
1018 trace.set(0,
1019 { {
1020 { C::ff_gt_sel_gt, 1 },
1021 { C::ff_gt_a, FF::modulus - 1 },
1022 { C::ff_gt_b, FF::modulus_minus_two },
1023 { C::ff_gt_result, 1 },
1024 } });
1025
1026 trace.set(1,
1027 { {
1028 { C::ff_gt_sel_gt, 1 },
1029 { C::ff_gt_a, FF::modulus_minus_two },
1030 { C::ff_gt_b, FF::modulus_minus_two },
1031 { C::ff_gt_result, 0 },
1032 } });
1033
1034 trace.set(2,
1035 { {
1036 { C::ff_gt_sel_gt, 1 },
1037 { C::ff_gt_a, FF::modulus_minus_two },
1038 { C::ff_gt_b, FF::modulus - 3 },
1039 { C::ff_gt_result, 0 },
1040 } });
1041
1042 check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_leaf_slot_increase_ff_gt_settings>(trace);
1043
1044 // Mutate the second row to be equal to the first row
1045 trace.set(C::public_data_squash_leaf_slot, 1, FF::modulus_minus_two);
1046
1047 EXPECT_THROW_WITH_MESSAGE(
1048 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_leaf_slot_increase_ff_gt_settings>(
1049 trace)),
1050 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_LEAF_SLOT_INCREASE_FF_GT. Could not find tuple in destination.");
1051
1052 // Mutate the second row to be smaller than the first row
1053 trace.set(C::public_data_squash_leaf_slot, 1, FF::modulus - 3);
1054
1055 EXPECT_THROW_WITH_MESSAGE(
1056 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_leaf_slot_increase_ff_gt_settings>(
1057 trace)),
1058 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_LEAF_SLOT_INCREASE_FF_GT. Could not find tuple in destination.");
1059}
1060
1061TEST(PublicDataTreeConstrainingTest, SquashingNegativeClockDecomposition)
1062{
1063 // Test constraint: CLK_DIFF = clk_diff_lo + 2**16 * clk_diff_hi;
1064 TestTraceContainer trace({
1065 {
1066 { C::public_data_squash_sel, 1 },
1067 { C::public_data_squash_check_clock, 1 },
1068 { C::public_data_squash_clk, 1 << 25 },
1069 { C::public_data_squash_clk_diff_lo, 37 },
1070 { C::public_data_squash_clk_diff_hi, 12 },
1071 },
1072 {
1073 { C::public_data_squash_sel, 1 },
1074 { C::public_data_squash_clk, (1 << 25) + (12 << 16) + 37 },
1075 },
1076 });
1077
1078 check_relation<public_data_squash>(trace, public_data_squash::SR_CLK_DIFF_DECOMP);
1079
1080 // Mutate wrongly clk_diff_lo
1081 trace.set(C::public_data_squash_clk_diff_lo, 0, trace.get(C::public_data_squash_clk_diff_lo, 0) + 1);
1082
1083 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_CLK_DIFF_DECOMP),
1084 "CLK_DIFF_DECOMP");
1085
1086 // Reset
1087 trace.set(C::public_data_squash_clk_diff_lo, 0, trace.get(C::public_data_squash_clk_diff_lo, 0) - 1);
1088
1089 // Mutate wrongly clk_diff_hi
1090 trace.set(C::public_data_squash_clk_diff_hi, 0, trace.get(C::public_data_squash_clk_diff_hi, 0) + 1);
1091
1092 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_CLK_DIFF_DECOMP),
1093 "CLK_DIFF_DECOMP");
1094}
1095
1096// Out of range clk diff
1097TEST(PublicDataTreeConstrainingTest, SquashingNegativeOutOfRangeClockDiff)
1098{
1099 TestTraceContainer trace({
1100 {
1101 { C::public_data_squash_sel, 1 },
1102 { C::public_data_squash_check_clock, 1 },
1103 { C::public_data_squash_clk, 1 << 25 },
1104 { C::public_data_squash_clk_diff_lo, UINT16_MAX },
1105 { C::public_data_squash_clk_diff_hi, UINT16_MAX },
1106 },
1107 });
1108
1109 PrecomputedTraceBuilder precomputed_trace_builder;
1110 precomputed_trace_builder.process_sel_range_16(trace);
1111 precomputed_trace_builder.process_misc(trace, 1 << 16);
1112
1113 check_interaction<PublicDataTreeTraceBuilder,
1114 lookup_public_data_squash_clk_diff_range_lo_settings,
1115 lookup_public_data_squash_clk_diff_range_hi_settings>(trace);
1116
1117 // Mutate wrongly clk_diff_lo
1118 trace.set(C::public_data_squash_clk_diff_lo, 0, UINT16_MAX + 1);
1119
1120 EXPECT_THROW_WITH_MESSAGE(
1121 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_clk_diff_range_lo_settings>(trace)),
1122 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_CLK_DIFF_RANGE_LO. Could not find tuple in destination.");
1123
1124 // Mutate wrongly clk_diff_hi
1125 trace.set(C::public_data_squash_clk_diff_hi, 0, UINT16_MAX + 1);
1126
1127 EXPECT_THROW_WITH_MESSAGE(
1128 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_clk_diff_range_hi_settings>(trace)),
1129 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_CLK_DIFF_RANGE_HI. Could not find tuple in destination.");
1130}
1131
1132} // namespace
1133} // 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:108
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:167
PUBLIC_DATA_TREE_HEIGHT
#define PUBLIC_DATA_TREE_HEIGHT
Definition aztec_constants.hpp:6
mock_gt
StrictMock< MockGreaterThan > mock_gt
Definition bc_hashing.test.cpp:57
perm_mem_event_emitter
EventEmitter< Poseidon2PermutationMemoryEvent > perm_mem_event_emitter
Definition bc_hashing.test.cpp:55
perm_event_emitter
EventEmitter< Poseidon2PermutationEvent > perm_event_emitter
Definition bc_hashing.test.cpp:54
hash_event_emitter
EventEmitter< Poseidon2HashEvent > hash_event_emitter
Definition bc_hashing.test.cpp:53
poseidon2_builder
Poseidon2TraceBuilder poseidon2_builder
Definition bc_hashing.test.cpp:60
check_relation.hpp
bb::avm2::public_data_check
Definition public_data_check.hpp:35
bb::avm2::public_data_check::SR_CLK_DIFF_DECOMP
static constexpr size_t SR_CLK_DIFF_DECOMP
Definition public_data_check.hpp:42
bb::avm2::public_data_check::SR_START_CONDITION
static constexpr size_t SR_START_CONDITION
Definition public_data_check.hpp:40
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:46
bb::avm2::public_data_check::SR_VALUE_IS_CORRECT
static constexpr size_t SR_VALUE_IS_CORRECT
Definition public_data_check.hpp:48
bb::avm2::public_data_check::SR_EXISTS_FLAG_CHECK
static constexpr size_t SR_EXISTS_FLAG_CHECK
Definition public_data_check.hpp:43
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:44
bb::avm2::public_data_check::SR_LOW_LEAF_VALUE_UPDATE
static constexpr size_t SR_LOW_LEAF_VALUE_UPDATE
Definition public_data_check.hpp:45
bb::avm2::public_data_check::SR_PROTOCOL_WRITE_CHECK
static constexpr size_t SR_PROTOCOL_WRITE_CHECK
Definition public_data_check.hpp:41
bb::avm2::public_data_check::SR_WRITE_IDX_INITIAL_VALUE
static constexpr size_t SR_WRITE_IDX_INITIAL_VALUE
Definition public_data_check.hpp:50
bb::avm2::public_data_check::SR_UPDATE_ROOT_VALIDATION
static constexpr size_t SR_UPDATE_ROOT_VALIDATION
Definition public_data_check.hpp:49
bb::avm2::public_data_check::SR_WRITE_IDX_INCREMENT
static constexpr size_t SR_WRITE_IDX_INCREMENT
Definition public_data_check.hpp:51
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:47
bb::avm2::public_data_squash
Definition public_data_squash.hpp:33
bb::avm2::public_data_squash::SR_CLK_DIFF_DECOMP
static constexpr size_t SR_CLK_DIFF_DECOMP
Definition public_data_squash.hpp:40
bb::avm2::public_data_squash::SR_START_CONDITION
static constexpr size_t SR_START_CONDITION
Definition public_data_squash.hpp:38
bb::avm2::public_data_squash::SR_FINAL_VALUE_CHECK
static constexpr size_t SR_FINAL_VALUE_CHECK
Definition public_data_squash.hpp:42
bb::avm2::public_data_squash::SR_CHECK_SAME_LEAF_SLOT
static constexpr size_t SR_CHECK_SAME_LEAF_SLOT
Definition public_data_squash.hpp:39
bb::avm2::public_data_squash::SR_FINAL_VALUE_PROPAGATION
static constexpr size_t SR_FINAL_VALUE_PROPAGATION
Definition public_data_squash.hpp:41
bb::avm2::tracegen::FieldGreaterThanTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::FieldGreaterThanEvent >::Container &events, TraceContainer &trace)
Definition field_gt_trace.cpp:15
bb::avm2::tracegen::Poseidon2TraceBuilder::process_hash
void process_hash(const simulation::EventEmitterInterface< simulation::Poseidon2HashEvent >::Container &hash_events, TraceContainer &trace)
Definition poseidon2_trace.cpp:288
bb::avm2::tracegen::PrecomputedTraceBuilder::process_misc
void process_misc(TraceContainer &trace, const uint32_t num_rows=MAX_AVM_TRACE_SIZE)
Definition precomputed_trace.cpp:22
bb::avm2::tracegen::RangeCheckTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::RangeCheckEvent >::Container &events, TraceContainer &trace)
Definition range_check_trace.cpp:16
bb::avm2::tracegen::TraceContainer::get
const FF & get(Column col, uint32_t row) const
Definition trace_container.cpp:23
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:39
bb::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:50
range_check
RangeCheck range_check
Definition data_copy.test.cpp:52
trace
TestTraceContainer trace
Definition data_copy.test.cpp:62
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:97
event_emitter.hpp
field_gt_trace.hpp
flavor_settings.hpp
field_gt.hpp
public_data_tree_check.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:71
bb::avm2::constraining::check_interaction
void check_interaction(tracegen::TestTraceContainer &trace)
Definition check_relation.hpp:76
bb::avm2::constraining::TEST
TEST(TxExecutionConstrainingTest, WriteTreeValue)
Definition tx.test.cpp:402
bb::avm2::simulation::PublicDataTreeCheckEvent
std::variant< PublicDataTreeReadWriteEvent, CheckPointEventType > PublicDataTreeCheckEvent
Definition public_data_tree_check_event.hpp:41
bb::avm2::simulation::PublicDataTreeLeafPreimage
IndexedLeaf< PublicDataLeafValue > PublicDataTreeLeafPreimage
Definition update_check.test.cpp:30
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.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::avm2::lookup_public_data_check_clk_diff_range_lo_settings
lookup_settings< lookup_public_data_check_clk_diff_range_lo_settings_ > lookup_public_data_check_clk_diff_range_lo_settings
Definition lookups_public_data_check.hpp:31
bb::avm2::lookup_public_data_squash_clk_diff_range_lo_settings
lookup_settings< lookup_public_data_squash_clk_diff_range_lo_settings_ > lookup_public_data_squash_clk_diff_range_lo_settings
Definition lookups_public_data_squash.hpp:57
bb::avm2::lookup_public_data_squash_clk_diff_range_hi_settings
lookup_settings< lookup_public_data_squash_clk_diff_range_hi_settings_ > lookup_public_data_squash_clk_diff_range_hi_settings
Definition lookups_public_data_squash.hpp:79
bb::avm2::lookup_public_data_check_clk_diff_range_hi_settings
lookup_settings< lookup_public_data_check_clk_diff_range_hi_settings_ > lookup_public_data_check_clk_diff_range_hi_settings
Definition lookups_public_data_check.hpp:53
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:15
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:96
value
FF value
Definition public_data_tree.test.cpp:97
public_data_tree_check_event.hpp
public_data_tree_trace.hpp
public_inputs_builder.hpp
public_inputs_trace.hpp
range_check_trace.hpp
field_gt
FieldGreaterThan field_gt
Definition keccakf1600.test.cpp:45
field_gt_event_emitter
NoopEventEmitter< FieldGreaterThanEvent > field_gt_event_emitter
Definition keccakf1600.test.cpp:42
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
public_inputs_builder
tracegen::PublicInputsTraceBuilder public_inputs_builder
Definition tx.test.cpp:80