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_io.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 .next_available_leaf_index = 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.public_data_writes[0] = PublicDataWrite{
320 .leaf_slot = 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({ .public_data_writes = 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(), .next_available_leaf_index = 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.next_available_leaf_index);
367
368 // No insertion happens
369 AppendOnlyTreeSnapshot next_snapshot =
370 AppendOnlyTreeSnapshot{ .root = intermediate_root,
371 .next_available_leaf_index = prev_snapshot.next_available_leaf_index };
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 with value 27
404 // 2. (dummy write to check ordering) dummy_slot with value 0
405 // 3. slot with value 28
406 // If squashing is correct, we should get (slot, 28), (dummy_slot, 0)
407
408 // Compute hashes for two candidate slot values
409 FF slot_a = 42;
410 FF slot_b = 51;
411 FF leaf_slot_a = unconstrained_compute_leaf_slot(contract_address, slot_a);
412 FF leaf_slot_b = unconstrained_compute_leaf_slot(contract_address, slot_b);
413
414 // We need leaf_slot < dummy_leaf_slot for the tree ordering.
415 // Since hash outputs are pseudo-random, we pick the smaller hash as leaf_slot.
416 FF slot;
417 FF dummy_slot;
418 FF leaf_slot;
419 FF dummy_leaf_slot;
420 if (static_cast<uint256_t>(leaf_slot_a) < static_cast<uint256_t>(leaf_slot_b)) {
421 slot = slot_a;
422 dummy_slot = slot_b;
423 leaf_slot = leaf_slot_a;
424 dummy_leaf_slot = leaf_slot_b;
425 } else {
426 slot = slot_b;
427 dummy_slot = slot_a;
428 leaf_slot = leaf_slot_b;
429 dummy_leaf_slot = leaf_slot_a;
430 }
431
432 FF new_value = 27; // Will get squashed
433 FF updated_value = 28;
434 FF dummy_leaf_value = 0;
435
436 // The expected tree order is low_leaf_slot := (leaf_slot - 2) < leaf_slot < second_low_leaf_slot < dummy_leaf_slot
437 // We set second_low_leaf_slot == leaf_slot + 1. (We do not need to know the preimage for second_low_leaf_slot)
438 ASSERT_GT(dummy_leaf_slot, leaf_slot + 1);
439
440 FF low_leaf_slot = 40;
441 TestMemoryTree<Poseidon2HashPolicy> public_data_tree(8, PUBLIC_DATA_TREE_HEIGHT);
442
443 AvmAccumulatedData accumulated_data = {};
444 accumulated_data.public_data_writes[0] = PublicDataWrite{
445 .leaf_slot = leaf_slot,
446 .value = updated_value,
447 };
448
449 accumulated_data.public_data_writes[1] = PublicDataWrite{
450 .leaf_slot = dummy_leaf_slot,
451 .value = dummy_leaf_value,
452 };
453
454 auto test_public_inputs = testing::PublicInputsBuilder()
455 .set_accumulated_data(accumulated_data)
456 .set_accumulated_data_array_lengths({ .public_data_writes = 2 })
457 .build();
458
459 EventEmitter<MerkleCheckEvent> merkle_event_emitter;
460 MerkleCheck merkle_check(poseidon2, merkle_event_emitter);
461
462 EventEmitter<RangeCheckEvent> range_check_emitter;
463 RangeCheck range_check(range_check_emitter);
464
465 DeduplicatingEventEmitter<FieldGreaterThanEvent> field_gt_event_emitter;
466 FieldGreaterThan field_gt(range_check, field_gt_event_emitter);
467
468 EventEmitter<PublicDataTreeCheckEvent> public_data_tree_check_event_emitter;
469 PublicDataTreeCheck public_data_tree_check_simulator(
470 poseidon2, merkle_check, field_gt, execution_id_manager, public_data_tree_check_event_emitter);
471
472 TestTraceContainer trace({ { { C::precomputed_first_row, 1 } } });
473 RangeCheckTraceBuilder range_check_builder;
474 Poseidon2TraceBuilder poseidon2_builder;
475 MerkleCheckTraceBuilder merkle_check_builder;
476 FieldGreaterThanTraceBuilder field_gt_builder;
477 PrecomputedTraceBuilder precomputed_builder;
478 PublicInputsTraceBuilder public_inputs_builder;
479 PublicDataTreeTraceBuilder public_data_tree_read_builder;
480
481 // Insert leaves which are already present in the tree (test preparation)
482 PublicDataTreeLeafPreimage low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(low_leaf_slot, 1), 0, 0);
483 FF low_leaf_hash = UnconstrainedPoseidon2::hash(low_leaf.get_hash_inputs());
484 uint64_t low_leaf_index = 30;
485 public_data_tree.update_element(low_leaf_index, low_leaf_hash);
486
487 uint64_t second_low_leaf_index = 31;
488 FF second_low_leaf_slot = leaf_slot + 1;
489
490 PublicDataTreeLeafPreimage second_low_leaf =
491 PublicDataTreeLeafPreimage(PublicDataLeafValue(second_low_leaf_slot, 1), 0, 0);
492 FF second_low_leaf_hash = UnconstrainedPoseidon2::hash(second_low_leaf.get_hash_inputs());
493 public_data_tree.update_element(second_low_leaf_index, second_low_leaf_hash);
494
495 AppendOnlyTreeSnapshot prev_snapshot =
496 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(), .next_available_leaf_index = 128 };
497 std::vector<FF> low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
498
499 // Insertion section
500 PublicDataTreeLeafPreimage updated_low_leaf = low_leaf;
501 updated_low_leaf.nextIndex = prev_snapshot.next_available_leaf_index;
502 updated_low_leaf.nextKey = leaf_slot;
503 FF updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
504 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
505
506 std::vector<FF> insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.next_available_leaf_index);
507
508 PublicDataTreeLeafPreimage new_leaf =
509 PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, new_value), low_leaf.nextIndex, low_leaf.nextKey);
510 FF new_leaf_hash = UnconstrainedPoseidon2::hash(new_leaf.get_hash_inputs());
511
512 uint64_t value_to_be_updated_leaf_index = prev_snapshot.next_available_leaf_index;
513 public_data_tree.update_element(value_to_be_updated_leaf_index, new_leaf_hash);
514
515 AppendOnlyTreeSnapshot next_snapshot =
516 AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
517 .next_available_leaf_index = prev_snapshot.next_available_leaf_index + 1 };
518
519 AppendOnlyTreeSnapshot snapshot_after_insertion = public_data_tree_check_simulator.write(slot,
520 contract_address,
521 new_value,
522 low_leaf,
523 low_leaf_index,
524 low_leaf_sibling_path,
525 prev_snapshot,
526 insertion_sibling_path,
527 false);
528 EXPECT_EQ(next_snapshot, snapshot_after_insertion);
529
530 // Dummy insertion section
531
532 prev_snapshot = snapshot_after_insertion;
533
534 low_leaf = second_low_leaf;
535 low_leaf_hash = second_low_leaf_hash;
536 low_leaf_index = second_low_leaf_index;
537 low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
538
539 updated_low_leaf = low_leaf;
540 updated_low_leaf.nextIndex = prev_snapshot.next_available_leaf_index;
541 updated_low_leaf.nextKey = dummy_leaf_slot;
542 updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
543 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
544 insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.next_available_leaf_index);
545
546 new_leaf = PublicDataTreeLeafPreimage(
547 PublicDataLeafValue(dummy_leaf_slot, dummy_leaf_value), low_leaf.nextIndex, low_leaf.nextKey);
548 new_leaf_hash = UnconstrainedPoseidon2::hash(new_leaf.get_hash_inputs());
549
550 uint64_t dummy_leaf_index = prev_snapshot.next_available_leaf_index;
551 public_data_tree.update_element(dummy_leaf_index, new_leaf_hash);
552
553 next_snapshot = AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
554 .next_available_leaf_index = prev_snapshot.next_available_leaf_index + 1 };
555
556 AppendOnlyTreeSnapshot snapshot_after_dummy_insertion =
557 public_data_tree_check_simulator.write(dummy_slot,
558 contract_address,
559 dummy_leaf_value,
560 low_leaf,
561 low_leaf_index,
562 low_leaf_sibling_path,
563 prev_snapshot,
564 insertion_sibling_path,
565 false);
566 EXPECT_EQ(next_snapshot, snapshot_after_dummy_insertion);
567
568 // Update section
569
570 low_leaf_index = value_to_be_updated_leaf_index;
571 prev_snapshot = snapshot_after_dummy_insertion;
572
573 low_leaf = PublicDataTreeLeafPreimage(PublicDataLeafValue(leaf_slot, new_value), 0, 0);
574 low_leaf_sibling_path = public_data_tree.get_sibling_path(low_leaf_index);
575
576 updated_low_leaf = low_leaf;
577 updated_low_leaf.leaf.value = updated_value;
578 updated_low_leaf_hash = UnconstrainedPoseidon2::hash(updated_low_leaf.get_hash_inputs());
579 public_data_tree.update_element(low_leaf_index, updated_low_leaf_hash);
580 insertion_sibling_path = public_data_tree.get_sibling_path(prev_snapshot.next_available_leaf_index);
581
582 // No insertion happens
583 next_snapshot = AppendOnlyTreeSnapshot{ .root = public_data_tree.root(),
584 .next_available_leaf_index = prev_snapshot.next_available_leaf_index };
585 AppendOnlyTreeSnapshot snapshot_after_update = public_data_tree_check_simulator.write(slot,
586 contract_address,
587 updated_value,
588 low_leaf,
589 low_leaf_index,
590 low_leaf_sibling_path,
591 prev_snapshot,
592 insertion_sibling_path,
593 true);
594 EXPECT_EQ(next_snapshot, snapshot_after_update);
595
596 ASSERT_LE(test_public_inputs.accumulated_data_array_lengths.public_data_writes,
597 test_public_inputs.accumulated_data.public_data_writes.size());
598
599 std::vector<FF> written_slots;
600 std::ranges::transform(test_public_inputs.accumulated_data.public_data_writes,
601 std::back_inserter(written_slots),
602 [](const PublicDataWrite& write) { return write.leaf_slot; });
603
604 public_data_tree_check_simulator.generate_ff_gt_events_for_squashing(written_slots);
605
606 precomputed_builder.process_misc(trace, 1 << 16);
607 precomputed_builder.process_sel_range_16(trace);
608 public_inputs_builder.process_public_inputs(trace, test_public_inputs);
609 public_inputs_builder.process_public_inputs_aux_precomputed(trace);
610 range_check_builder.process(range_check_emitter.dump_events(), trace);
611 poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
612 merkle_check_builder.process(merkle_event_emitter.dump_events(), trace);
613 field_gt_builder.process(field_gt_event_emitter.dump_events(), trace);
614 public_data_tree_read_builder.process(public_data_tree_check_event_emitter.dump_events(), trace);
615
616 check_relation<public_data_check>(trace);
617 check_relation<public_data_squash>(trace);
618
619 check_all_interactions<PublicDataTreeTraceBuilder>(trace);
620}
621
622TEST(PublicDataTreeConstrainingTest, NegativeLowLeafValueUpdate)
623{
624 // Test constraint: write * ((low_leaf_value - value) * leaf_not_exists + value - updated_low_leaf_value) = 0
625 TestTraceContainer trace({
626 {
627 { C::public_data_check_write, 1 },
628 { C::public_data_check_leaf_not_exists, 0 },
629 { C::public_data_check_low_leaf_value, 27 },
630 { C::public_data_check_value, 28 },
631 { C::public_data_check_updated_low_leaf_value, 28 },
632 },
633 {
634 { C::public_data_check_write, 1 },
635 { C::public_data_check_leaf_not_exists, 1 },
636 { C::public_data_check_low_leaf_value, 27 },
637 { C::public_data_check_value, 28 },
638 { C::public_data_check_updated_low_leaf_value, 27 },
639 },
640 });
641
642 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE);
643
644 // Invalid, if leaf exists, updated_low_leaf_value should be the value to write
645 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
646
647 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE),
648 "LOW_LEAF_VALUE_UPDATE");
649
650 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
651 // Invalid, if leaf does not exist, updated_low_leaf_value should be the low leaf value
652 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
653
654 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_VALUE_UPDATE),
655 "LOW_LEAF_VALUE_UPDATE");
656}
657
658TEST(PublicDataTreeConstrainingTest, NegativeLowLeafNextIndexUpdate)
659{
660 // Test constraint: write * ((tree_size_before_write - low_leaf_next_index) * leaf_not_exists + low_leaf_next_index
661 // - updated_low_leaf_next_index) = 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_index, 27 },
667 { C::public_data_check_tree_size_before_write, 128 },
668 { C::public_data_check_updated_low_leaf_next_index, 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_index, 27 },
674 { C::public_data_check_tree_size_before_write, 128 },
675 { C::public_data_check_updated_low_leaf_next_index, 128 },
676 },
677 });
678
679 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE);
680
681 // Invalid, if leaf not exists, the updated_low_leaf_next_index should be the newly inserted leaf
682 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
683
684 EXPECT_THROW_WITH_MESSAGE(
685 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE),
686 "LOW_LEAF_NEXT_INDEX_UPDATE");
687
688 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
689 // Invalid, if leaf exists, the updated_low_leaf_next_index should be untouched
690 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
691
692 EXPECT_THROW_WITH_MESSAGE(
693 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_INDEX_UPDATE),
694 "LOW_LEAF_NEXT_INDEX_UPDATE");
695}
696
697TEST(PublicDataTreeConstrainingTest, NegativeLowLeafNextSlotUpdate)
698{
699 // Test constraint: write * ((leaf_slot - low_leaf_next_slot) * leaf_not_exists + low_leaf_next_slot -
700 // updated_low_leaf_next_slot) = 0
701 TestTraceContainer trace({
702 {
703 { C::public_data_check_write, 1 },
704 { C::public_data_check_leaf_not_exists, 0 },
705 { C::public_data_check_low_leaf_next_slot, 27 },
706 { C::public_data_check_leaf_slot, 28 },
707 { C::public_data_check_updated_low_leaf_next_slot, 27 },
708 },
709 {
710 { C::public_data_check_write, 1 },
711 { C::public_data_check_leaf_not_exists, 1 },
712 { C::public_data_check_low_leaf_next_slot, 27 },
713 { C::public_data_check_leaf_slot, 28 },
714 { C::public_data_check_updated_low_leaf_next_slot, 28 },
715 },
716 });
717
718 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE);
719
720 // Invalid, if leaf not exists, the updated_low_leaf_next_slot should be the newly inserted leaf slot
721 trace.set(C::public_data_check_leaf_not_exists, 0, 1);
722
723 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE),
724 "LOW_LEAF_NEXT_SLOT_UPDATE");
725
726 trace.set(C::public_data_check_leaf_not_exists, 0, 0);
727 // Invalid, if leaf exists, the updated_low_leaf_next_slot should be untouched
728 trace.set(C::public_data_check_leaf_not_exists, 1, 0);
729
730 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE),
731 "LOW_LEAF_NEXT_SLOT_UPDATE");
732}
733
734TEST(PublicDataTreeConstrainingTest, NegativeUpdateRootValidation)
735{
736 // Test constraint: (1 - leaf_not_exists) * write * (write_root - intermediate_root) = 0
737 TestTraceContainer trace({
738 {
739 { C::public_data_check_write, 1 },
740 { C::public_data_check_leaf_not_exists, 0 },
741 { C::public_data_check_intermediate_root, 28 },
742 { C::public_data_check_write_root, 28 },
743 },
744 {
745 { C::public_data_check_write, 1 },
746 { C::public_data_check_leaf_not_exists, 1 },
747 { C::public_data_check_intermediate_root, 28 },
748 { C::public_data_check_write_root, 30 },
749 },
750 });
751
752 check_relation<public_data_check>(trace, public_data_check::SR_LOW_LEAF_NEXT_SLOT_UPDATE);
753
754 // Invalid, if leaf exists, the write root should be the intermediate root
755 trace.set(C::public_data_check_write_root, 0, 30);
756
757 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_UPDATE_ROOT_VALIDATION),
758 "UPDATE_ROOT_VALIDATION");
759}
760
761TEST(PublicDataTreeConstrainingTest, NegativeSetProtocolWrite)
762{
763 // Test constraint: protocol_write + non_protocol_write = write
764 TestTraceContainer trace({ {
765 { C::public_data_check_sel, 1 },
766 { C::public_data_check_write, 1 },
767 { C::public_data_check_protocol_write, 1 },
768 } });
769
770 check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK);
771
772 // Invalid, must set either protocol or non protocol write
773 trace.set(C::public_data_check_protocol_write, 0, 0);
774
775 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK),
776 "PROTOCOL_WRITE_CHECK");
777
778 trace.set(C::public_data_check_non_protocol_write, 0, 1);
779 check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK);
780
781 // Invalid, cannot both be a protocol and non protocol write
782 trace.set(C::public_data_check_protocol_write, 0, 1);
783 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_PROTOCOL_WRITE_CHECK),
784 "PROTOCOL_WRITE_CHECK");
785}
786
787TEST(PublicDataTreeConstrainingTest, NegativeWriteIdxInitialValue)
788{
789 // Test constraint: (1 - sel) * sel' * (constants.AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX
790 // - write_idx') = 0
791 TestTraceContainer trace(
792 { {
793 { C::public_data_check_sel, 0 },
794 },
795 {
796 { C::public_data_check_sel, 1 },
797 { C::public_data_check_write_idx, AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_PUBLIC_DATA_WRITES_ROW_IDX },
798 } });
799
800 check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INITIAL_VALUE);
801
802 // Invalid, if sel goes from 0 to 1, the write_idx should be the initial value
803 trace.set(C::public_data_check_write_idx, 1, 27);
804
805 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INITIAL_VALUE),
806 "WRITE_IDX_INITIAL_VALUE");
807}
808
809TEST(PublicDataTreeConstrainingTest, NegativeWriteIdxIncrement)
810{
811 // Test constraint: not_end * (write_idx + should_write_to_public_inputs - write_idx') = 0
812 TestTraceContainer trace({
813 {
814 { C::public_data_check_not_end, 1 },
815 { C::public_data_check_write_idx, 5 },
816 { C::public_data_check_should_write_to_public_inputs, 1 },
817 },
818 {
819 { C::public_data_check_not_end, 1 },
820 { C::public_data_check_write_idx, 6 },
821 { C::public_data_check_should_write_to_public_inputs, 0 },
822 },
823 {
824 { C::public_data_check_write_idx, 6 },
825 },
826 });
827
828 check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT);
829
830 // Invalid, if should_write_to_public_inputs is 0, the write_idx should not increment
831 trace.set(C::public_data_check_should_write_to_public_inputs, 0, 0);
832
833 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT),
834 "WRITE_IDX_INCREMENT");
835
836 // Invalid, if should_write_to_public_inputs is 1, the write_idx should increment
837 trace.set(C::public_data_check_should_write_to_public_inputs, 0, 1);
838 trace.set(C::public_data_check_should_write_to_public_inputs, 1, 1);
839
840 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_WRITE_IDX_INCREMENT),
841 "WRITE_IDX_INCREMENT");
842}
843
844// Negative clock diff decompostion
845TEST(PublicDataTreeConstrainingTest, NegativeClockDiffDecomposition)
846{
847 // Test constraint: CLK_DIFF = clk_diff_lo + 2**16 * clk_diff_hi;
848 TestTraceContainer trace({
849 {
850 { C::public_data_check_not_end, 1 },
851 { C::public_data_check_clk, 12 << 28 },
852 { C::public_data_check_clk_diff_lo, 234 },
853 { C::public_data_check_clk_diff_hi, 1 << 12 },
854 },
855 {
856 { C::public_data_check_clk, (13 << 28) + 234 },
857 },
858 });
859
860 check_relation<public_data_check>(trace, public_data_check::SR_CLK_DIFF_DECOMP);
861
862 // Mutate wrongly clk_diff_lo
863 trace.set(C::public_data_check_clk_diff_lo, 0, trace.get(C::public_data_check_clk_diff_lo, 0) + 1);
864
865 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_CLK_DIFF_DECOMP),
866 "CLK_DIFF_DECOMP");
867
868 // Reset
869 trace.set(C::public_data_check_clk_diff_lo, 0, trace.get(C::public_data_check_clk_diff_lo, 0) - 1);
870
871 // Mutate wrongly clk_diff_hi
872 trace.set(C::public_data_check_clk_diff_hi, 0, trace.get(C::public_data_check_clk_diff_hi, 0) + 1);
873
874 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_check>(trace, public_data_check::SR_CLK_DIFF_DECOMP),
875 "CLK_DIFF_DECOMP");
876}
877
878// Out of range clock diff
879TEST(PublicDataTreeConstrainingTest, NegativeOutOfRangeClockDiff)
880{
881 TestTraceContainer trace({
882 {
883 { C::public_data_check_not_end, 1 },
884 { C::public_data_check_clk_diff_lo, UINT16_MAX },
885 { C::public_data_check_clk_diff_hi, UINT16_MAX },
886 },
887 });
888
889 PrecomputedTraceBuilder precomputed_trace_builder;
890 precomputed_trace_builder.process_sel_range_16(trace);
891 precomputed_trace_builder.process_misc(trace, 1 << 16);
892
893 check_interaction<PublicDataTreeTraceBuilder,
894 lookup_public_data_check_clk_diff_range_lo_settings,
895 lookup_public_data_check_clk_diff_range_hi_settings>(trace);
896
897 // Mutate wrongly clk_diff_lo
898 trace.set(C::public_data_check_clk_diff_lo, 0, UINT16_MAX + 1);
899
900 EXPECT_THROW_WITH_MESSAGE(
901 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_check_clk_diff_range_lo_settings>(trace)),
902 "Failed.*LOOKUP_PUBLIC_DATA_CHECK_CLK_DIFF_RANGE_LO. Could not find tuple in destination.");
903
904 // Mutate wrongly clk_diff_hi
905 trace.set(C::public_data_check_clk_diff_hi, 0, UINT16_MAX + 1);
906
907 EXPECT_THROW_WITH_MESSAGE(
908 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_check_clk_diff_range_hi_settings>(trace)),
909 "Failed.*LOOKUP_PUBLIC_DATA_CHECK_CLK_DIFF_RANGE_HI. Could not find tuple in destination.");
910}
911
912// Squashing subtrace
913
914TEST(PublicDataTreeConstrainingTest, SquashingNegativeStartCondition)
915{
916 // Test constraint: sel' * (1 - sel) * (1 - precomputed.first_row) = 0
917 TestTraceContainer trace({ {
918 { C::public_data_squash_sel, 0 },
919 { C::precomputed_first_row, 1 },
920 },
921 {
922 { C::public_data_squash_sel, 1 },
923 },
924 {
925 { C::public_data_squash_sel, 1 },
926 } });
927
928 check_relation<public_data_squash>(trace, public_data_squash::SR_START_CONDITION);
929
930 // Invalid: sel can't be activated if prev is not the first row
931 trace.set(C::precomputed_first_row, 0, 0);
932
933 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_START_CONDITION),
934 "START_CONDITION");
935}
936
937TEST(PublicDataTreeConstrainingTest, SquashingNegativeCheckSameLeafSlot)
938{
939 // Test constraint: (sel * sel') * (1 - leaf_slot_increase) * (leaf_slot - leaf_slot') = 0
940 TestTraceContainer trace({ {
941 { C::public_data_squash_sel, 1 },
942 { C::public_data_squash_leaf_slot_increase, 1 },
943 { C::public_data_squash_leaf_slot, 27 },
944 },
945 {
946 { C::public_data_squash_sel, 1 },
947 { C::public_data_squash_leaf_slot_increase, 0 },
948 { C::public_data_squash_leaf_slot, 40 },
949 } });
950
951 check_relation<public_data_squash>(trace, public_data_squash::SR_CHECK_SAME_LEAF_SLOT);
952
953 // Invalid: if leaf_slot_increase is 0, the leaf_slot should not be different from the previous leaf_slot
954 trace.set(C::public_data_squash_leaf_slot_increase, 0, 0);
955
956 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_CHECK_SAME_LEAF_SLOT),
957 "CHECK_SAME_LEAF_SLOT");
958}
959
960TEST(PublicDataTreeConstrainingTest, SquashingNegativeFinalValuePropagation)
961{
962 // Test constraint: check_clock * (final_value - final_value') = 0;
963 TestTraceContainer trace({ {
964 { C::public_data_squash_sel, 1 },
965 { C::public_data_squash_check_clock, 1 },
966 { C::public_data_squash_final_value, 27 },
967 },
968 {
969 { C::public_data_squash_sel, 1 },
970 { C::public_data_squash_check_clock, 0 },
971 { C::public_data_squash_final_value, 27 },
972 } });
973
974 check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_PROPAGATION);
975
976 // Invalid: if final value changes, check_clk must be 0
977 trace.set(C::public_data_squash_final_value, 1, 28);
978
979 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_PROPAGATION),
980 "FINAL_VALUE_PROPAGATION");
981}
982
983TEST(PublicDataTreeConstrainingTest, SquashingNegativeFinalValueCheck)
984{
985 // Test constraint:
986 // LEAF_SLOT_END * (final_value - value) = 0;
987 TestTraceContainer trace({ {
988 { C::public_data_squash_sel, 1 },
989 { C::public_data_squash_final_value, 27 },
990 { C::public_data_squash_value, 99 },
991 },
992 {
993 { C::public_data_squash_sel, 1 },
994 { C::public_data_squash_final_value, 27 },
995 { C::public_data_squash_leaf_slot_increase, 1 },
996 { C::public_data_squash_value, 27 },
997 },
998 {
999 { C::public_data_squash_sel, 1 },
1000 { C::public_data_squash_final_value, 42 },
1001 { C::public_data_squash_value, 42 },
1002 } });
1003
1004 check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK);
1005
1006 // Negative test: if END, value == final_value
1007 trace.set(C::public_data_squash_value, 2, 99);
1008
1009 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK),
1010 "FINAL_VALUE_CHECK");
1011
1012 trace.set(C::public_data_squash_value, 2, 42);
1013
1014 // Negative test: if leaf_slot_increase, value == final_value
1015 trace.set(C::public_data_squash_value, 1, 99);
1016
1017 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_FINAL_VALUE_CHECK),
1018 "FINAL_VALUE_CHECK");
1019 trace.set(C::public_data_squash_value, 1, 27);
1020}
1021
1022TEST(PublicDataTreeConstrainingTest, SquashingNegativeLeafSlotIncrease)
1023{
1024 // Test constraint: leaf_slot_increase { leaf_slot', leaf_slot, sel } in ff_gt.sel_gt { ff_gt.a, ff_gt.b,
1025 // ff_gt.result }
1026 TestTraceContainer trace({ {
1027 { C::public_data_squash_leaf_slot_increase, 1 },
1028 { C::public_data_squash_leaf_slot, FF::modulus_minus_two },
1029 { C::public_data_squash_sel, 1 },
1030 },
1031 {
1032 { C::public_data_squash_leaf_slot_increase, 0 },
1033 { C::public_data_squash_leaf_slot, FF::modulus - 1 },
1034 { C::public_data_squash_sel, 1 },
1035 } });
1036
1037 // Corresponding ff_gt values. For this trace we keep the correct result.
1038 trace.set(0,
1039 { {
1040 { C::ff_gt_sel_gt, 1 },
1041 { C::ff_gt_a, FF::modulus - 1 },
1042 { C::ff_gt_b, FF::modulus_minus_two },
1043 { C::ff_gt_result, 1 },
1044 } });
1045
1046 trace.set(1,
1047 { {
1048 { C::ff_gt_sel_gt, 1 },
1049 { C::ff_gt_a, FF::modulus_minus_two },
1050 { C::ff_gt_b, FF::modulus_minus_two },
1051 { C::ff_gt_result, 0 },
1052 } });
1053
1054 trace.set(2,
1055 { {
1056 { C::ff_gt_sel_gt, 1 },
1057 { C::ff_gt_a, FF::modulus_minus_two },
1058 { C::ff_gt_b, FF::modulus - 3 },
1059 { C::ff_gt_result, 0 },
1060 } });
1061
1062 check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_leaf_slot_increase_ff_gt_settings>(trace);
1063
1064 // Mutate the second row to be equal to the first row
1065 trace.set(C::public_data_squash_leaf_slot, 1, FF::modulus_minus_two);
1066
1067 EXPECT_THROW_WITH_MESSAGE(
1068 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_leaf_slot_increase_ff_gt_settings>(
1069 trace)),
1070 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_LEAF_SLOT_INCREASE_FF_GT. Could not find tuple in destination.");
1071
1072 // Mutate the second row to be smaller than the first row
1073 trace.set(C::public_data_squash_leaf_slot, 1, FF::modulus - 3);
1074
1075 EXPECT_THROW_WITH_MESSAGE(
1076 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_leaf_slot_increase_ff_gt_settings>(
1077 trace)),
1078 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_LEAF_SLOT_INCREASE_FF_GT. Could not find tuple in destination.");
1079}
1080
1081TEST(PublicDataTreeConstrainingTest, SquashingNegativeClockDecomposition)
1082{
1083 // Test constraint: CLK_DIFF = clk_diff_lo + 2**16 * clk_diff_hi;
1084 TestTraceContainer trace({
1085 {
1086 { C::public_data_squash_sel, 1 },
1087 { C::public_data_squash_check_clock, 1 },
1088 { C::public_data_squash_clk, 1 << 25 },
1089 { C::public_data_squash_clk_diff_lo, 37 },
1090 { C::public_data_squash_clk_diff_hi, 12 },
1091 },
1092 {
1093 { C::public_data_squash_sel, 1 },
1094 { C::public_data_squash_clk, (1 << 25) + (12 << 16) + 37 },
1095 },
1096 });
1097
1098 check_relation<public_data_squash>(trace, public_data_squash::SR_CLK_DIFF_DECOMP);
1099
1100 // Mutate wrongly clk_diff_lo
1101 trace.set(C::public_data_squash_clk_diff_lo, 0, trace.get(C::public_data_squash_clk_diff_lo, 0) + 1);
1102
1103 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_CLK_DIFF_DECOMP),
1104 "CLK_DIFF_DECOMP");
1105
1106 // Reset
1107 trace.set(C::public_data_squash_clk_diff_lo, 0, trace.get(C::public_data_squash_clk_diff_lo, 0) - 1);
1108
1109 // Mutate wrongly clk_diff_hi
1110 trace.set(C::public_data_squash_clk_diff_hi, 0, trace.get(C::public_data_squash_clk_diff_hi, 0) + 1);
1111
1112 EXPECT_THROW_WITH_MESSAGE(check_relation<public_data_squash>(trace, public_data_squash::SR_CLK_DIFF_DECOMP),
1113 "CLK_DIFF_DECOMP");
1114}
1115
1116// Out of range clk diff
1117TEST(PublicDataTreeConstrainingTest, SquashingNegativeOutOfRangeClockDiff)
1118{
1119 TestTraceContainer trace({
1120 {
1121 { C::public_data_squash_sel, 1 },
1122 { C::public_data_squash_check_clock, 1 },
1123 { C::public_data_squash_clk, 1 << 25 },
1124 { C::public_data_squash_clk_diff_lo, UINT16_MAX },
1125 { C::public_data_squash_clk_diff_hi, UINT16_MAX },
1126 },
1127 });
1128
1129 PrecomputedTraceBuilder precomputed_trace_builder;
1130 precomputed_trace_builder.process_sel_range_16(trace);
1131 precomputed_trace_builder.process_misc(trace, 1 << 16);
1132
1133 check_interaction<PublicDataTreeTraceBuilder,
1134 lookup_public_data_squash_clk_diff_range_lo_settings,
1135 lookup_public_data_squash_clk_diff_range_hi_settings>(trace);
1136
1137 // Mutate wrongly clk_diff_lo
1138 trace.set(C::public_data_squash_clk_diff_lo, 0, UINT16_MAX + 1);
1139
1140 EXPECT_THROW_WITH_MESSAGE(
1141 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_clk_diff_range_lo_settings>(trace)),
1142 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_CLK_DIFF_RANGE_LO. Could not find tuple in destination.");
1143
1144 // Mutate wrongly clk_diff_hi
1145 trace.set(C::public_data_squash_clk_diff_hi, 0, UINT16_MAX + 1);
1146
1147 EXPECT_THROW_WITH_MESSAGE(
1148 (check_interaction<PublicDataTreeTraceBuilder, lookup_public_data_squash_clk_diff_range_hi_settings>(trace)),
1149 "Failed.*LOOKUP_PUBLIC_DATA_SQUASH_CLK_DIFF_RANGE_HI. Could not find tuple in destination.");
1150}
1151
1152} // namespace
1153} // namespace bb::avm2::constraining
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessageRegex)
Definition assert.hpp:193
avm_io.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:174
PUBLIC_DATA_TREE_HEIGHT
#define PUBLIC_DATA_TREE_HEIGHT
Definition aztec_constants.hpp:8
mock_gt
StrictMock< MockGreaterThan > mock_gt
Definition bc_hashing.test.cpp:58
perm_mem_event_emitter
EventEmitter< Poseidon2PermutationMemoryEvent > perm_mem_event_emitter
Definition bc_hashing.test.cpp:56
perm_event_emitter
EventEmitter< Poseidon2PermutationEvent > perm_event_emitter
Definition bc_hashing.test.cpp:55
hash_event_emitter
EventEmitter< Poseidon2HashEvent > hash_event_emitter
Definition bc_hashing.test.cpp:54
poseidon2_builder
Poseidon2TraceBuilder poseidon2_builder
Definition bc_hashing.test.cpp:61
field_gt
FieldGreaterThan field_gt
Definition bc_retrieval.test.cpp:309
merkle_check
MerkleCheck merkle_check
Definition bc_retrieval.test.cpp:307
range_check_emitter
EventEmitter< simulation::RangeCheckEvent > range_check_emitter
Definition bc_retrieval.test.cpp:296
range_check
RangeCheck range_check
Definition bc_retrieval.test.cpp:308
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)
Processes FieldGreaterThanEvent events and generates trace rows for the ff_gt gadget.
Definition field_gt_trace.cpp:44
bb::avm2::tracegen::Poseidon2TraceBuilder::process_hash
void process_hash(const simulation::EventEmitterInterface< simulation::Poseidon2HashEvent >::Container &hash_events, TraceContainer &trace)
Processes the hash events for the Poseidon2 hash function. It populates the columns for the poseidon2...
Definition poseidon2_trace.cpp:105
bb::avm2::tracegen::PrecomputedTraceBuilder::process_misc
void process_misc(TraceContainer &trace, const uint32_t num_rows=PRECOMPUTED_TRACE_SIZE)
Definition precomputed_trace.cpp:25
bb::avm2::tracegen::RangeCheckTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::RangeCheckEvent >::Container &events, TraceContainer &trace)
Processes range check events and populates the trace with decomposed value columns.
Definition range_check_trace.cpp:26
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
Native Poseidon2 hash function implementation.
Definition poseidon2.hpp:22
bb::crypto::Poseidon2::hash
static FF hash(const std::vector< FF > &input)
Hashes a vector of field elements.
bb::numeric::uint256_t
Definition uint256.hpp:32
range_check_builder
RangeCheckTraceBuilder range_check_builder
Definition alu.test.cpp:121
precomputed_builder
PrecomputedTraceBuilder precomputed_builder
Definition alu.test.cpp:120
field_gt_builder
FieldGreaterThanTraceBuilder field_gt_builder
Definition alu.test.cpp:122
execution_id_manager
ExecutionIdManager execution_id_manager
Definition data_copy.test.cpp:51
trace
TestTraceContainer trace
Definition data_copy.test.cpp:63
low_leaf
IndexedTreeLeafData low_leaf
Definition indexed_tree_check.test.cpp:69
value
FF value
Definition indexed_tree_check.test.cpp:67
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
merkle_check_trace.hpp
mock_gt.hpp
bb::avm2::constraining::TEST_P
TEST_P(AvmRecursiveTestsParameterized, TwoLayerAvmRecursion)
A test of the Two Layer AVM recursive verifier.
Definition recursive_verifier.test.cpp:70
bb::avm2::constraining::INSTANTIATE_TEST_SUITE_P
INSTANTIATE_TEST_SUITE_P(PaddingVariants, AvmRecursiveTestsParameterized, ::testing::Values(false, true), [](const auto &info) { return info.param ? "Padded" :"Unpadded";})
bb::avm2::constraining::check_interaction
void check_interaction(tracegen::TestTraceContainer &trace)
Definition check_relation.hpp:77
bb::avm2::constraining::TEST
TEST(AvmFixedVKTests, FixedVKCommitments)
Test that the fixed VK commitments agree with the ones computed from precomputed columns.
Definition avm_fixed_vk.test.cpp:52
bb::avm2::constraining::TEST_F
TEST_F(AvmRecursiveTests, TwoLayerAvmRecursionFailsWithWrongPIs)
Definition recursive_verifier.test.cpp:260
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:34
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:38
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::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
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::write
void write(B &buf, field2< base_field, Params > const &value)
Definition field2_declarations.hpp:151
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
public_data_tree_check_event.hpp
public_data_tree_trace.hpp
public_inputs_trace.hpp
range_check_trace.hpp
field_gt_event_emitter
NoopEventEmitter< FieldGreaterThanEvent > field_gt_event_emitter
Definition keccakf1600.test.cpp:42
bb::field< bb::Bn254FrParams >::modulus
static constexpr uint256_t modulus
Definition field_declarations.hpp:234
bb::field< bb::Bn254FrParams >::modulus_minus_two
static constexpr uint256_t modulus_minus_two
Definition field_declarations.hpp:340
test_trace_container.hpp
test_tree.hpp
public_inputs_builder.hpp
public_inputs_builder
tracegen::PublicInputsTraceBuilder public_inputs_builder
Definition tx.test.cpp:81