Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
written_public_data_slots_tree_check.test.cpp
Go to the documentation of this file.
1#include "barretenberg/vm2/simulation/written_public_data_slots_tree_check.hpp"
2
3#include <gmock/gmock.h>
4#include <gtest/gtest.h>
5
6#include "barretenberg/crypto/merkle_tree/memory_tree.hpp"
7#include "barretenberg/vm2/common/avm_inputs.hpp"
8#include "barretenberg/vm2/common/aztec_types.hpp"
9#include "barretenberg/vm2/simulation/events/written_public_data_slot_tree_check_event.hpp"
10#include "barretenberg/vm2/simulation/lib/merkle.hpp"
11#include "barretenberg/vm2/simulation/lib/written_slots_tree.hpp"
12#include "barretenberg/vm2/simulation/testing/mock_field_gt.hpp"
13#include "barretenberg/vm2/simulation/testing/mock_merkle_check.hpp"
14#include "barretenberg/vm2/simulation/testing/mock_poseidon2.hpp"
15#include "barretenberg/vm2/testing/macros.hpp"
16
17namespace bb::avm2::simulation {
18
19using ::testing::_;
20using ::testing::ElementsAre;
21using ::testing::Return;
22using ::testing::StrictMock;
23
24using RawPoseidon2 = crypto::Poseidon2<crypto::Poseidon2Bn254ScalarFieldParams>;
25
26namespace {
27
28TEST(AvmSimulationWrittenPublicDataSlotsTree, ContainsNotExists)
29{
30 StrictMock<MockPoseidon2> poseidon2;
31 StrictMock<MockMerkleCheck> merkle_check;
32 StrictMock<MockFieldGreaterThan> field_gt;
33
34 EventEmitter<WrittenPublicDataSlotsTreeCheckEvent> event_emitter;
35
36 FF slot = 42;
37 AztecAddress contract_address = AztecAddress(27);
38 FF leaf_slot = RawPoseidon2::hash({ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot });
39
40 WrittenPublicDataSlotsTree initial_state = build_public_data_slots_tree();
41
42 // Prefill will point to our new leaf
43 ASSERT_EQ(initial_state.get_snapshot().nextAvailableLeafIndex, 1);
44 uint64_t low_leaf_index = 0;
45 WrittenPublicDataSlotsTreeLeafPreimage low_leaf = initial_state.get_leaf_preimage(low_leaf_index);
46
47 FF low_leaf_hash = RawPoseidon2::hash(low_leaf.get_hash_inputs());
48
49 auto sibling_path = initial_state.get_sibling_path(0);
50 auto snapshot = initial_state.get_snapshot();
51
52 WrittenPublicDataSlotsTreeCheck written_public_data_slots_tree_check(
53 poseidon2, merkle_check, field_gt, initial_state, event_emitter);
54
55 EXPECT_CALL(poseidon2, hash(std::vector<FF>{ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot }))
56 .WillRepeatedly(Return(FF(leaf_slot)));
57 EXPECT_CALL(poseidon2, hash(low_leaf.get_hash_inputs())).WillRepeatedly(Return(FF(low_leaf_hash)));
58 EXPECT_CALL(merkle_check, assert_membership(low_leaf_hash, low_leaf_index, _, snapshot.root))
59 .WillRepeatedly(Return());
60 EXPECT_CALL(field_gt, ff_gt(leaf_slot, low_leaf.leaf.slot)).WillRepeatedly(Return(true));
61
62 EXPECT_FALSE(written_public_data_slots_tree_check.contains(contract_address, slot));
63
64 WrittenPublicDataSlotsTreeCheckEvent expect_event = {
65 .contract_address = contract_address,
66 .slot = slot,
67 .leaf_slot = leaf_slot,
68 .prev_snapshot = snapshot,
69 .next_snapshot = snapshot,
70 .low_leaf_preimage = low_leaf,
71 .low_leaf_hash = low_leaf_hash,
72 .low_leaf_index = low_leaf_index,
73 };
74 EXPECT_THAT(event_emitter.dump_events(), ElementsAre(expect_event));
75}
76
77TEST(AvmSimulationWrittenPublicDataSlotsTree, ContainsExists)
78{
79 StrictMock<MockPoseidon2> poseidon2;
80 StrictMock<MockMerkleCheck> merkle_check;
81 StrictMock<MockFieldGreaterThan> field_gt;
82
83 EventEmitter<WrittenPublicDataSlotsTreeCheckEvent> event_emitter;
84 WrittenPublicDataSlotsTree initial_state = build_public_data_slots_tree();
85
86 FF slot = 42;
87 AztecAddress contract_address = AztecAddress(27);
88 FF leaf_slot = RawPoseidon2::hash({ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot });
89
90 uint64_t low_leaf_index = initial_state.get_snapshot().nextAvailableLeafIndex;
91 initial_state.insert_indexed_leaves({ { WrittenPublicDataSlotLeafValue(leaf_slot) } });
92
93 WrittenPublicDataSlotsTreeLeafPreimage low_leaf = initial_state.get_leaf_preimage(low_leaf_index);
94 FF low_leaf_hash = RawPoseidon2::hash(low_leaf.get_hash_inputs());
95 std::vector<FF> sibling_path = initial_state.get_sibling_path(low_leaf_index);
96 auto snapshot = initial_state.get_snapshot();
97
98 WrittenPublicDataSlotsTreeCheck written_public_data_slots_tree_check(
99 poseidon2, merkle_check, field_gt, initial_state, event_emitter);
100
101 EXPECT_CALL(poseidon2, hash(std::vector<FF>{ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot }))
102 .WillRepeatedly(Return(FF(leaf_slot)));
103 EXPECT_CALL(poseidon2, hash(low_leaf.get_hash_inputs())).WillRepeatedly(Return(FF(low_leaf_hash)));
104 EXPECT_CALL(merkle_check, assert_membership(low_leaf_hash, low_leaf_index, _, snapshot.root))
105 .WillRepeatedly(Return());
106
107 EXPECT_TRUE(written_public_data_slots_tree_check.contains(contract_address, slot));
108
109 WrittenPublicDataSlotsTreeCheckEvent expect_event = {
110 .contract_address = contract_address,
111 .slot = slot,
112 .leaf_slot = leaf_slot,
113 .prev_snapshot = snapshot,
114 .next_snapshot = snapshot,
115 .low_leaf_preimage = low_leaf,
116 .low_leaf_hash = low_leaf_hash,
117 .low_leaf_index = low_leaf_index,
118 };
119 EXPECT_THAT(event_emitter.dump_events(), ElementsAre(expect_event));
120}
121
122TEST(AvmSimulationWrittenPublicDataSlotsTree, ReadNotExistsLowPointsToAnotherLeaf)
123{
124 StrictMock<MockPoseidon2> poseidon2;
125 StrictMock<MockMerkleCheck> merkle_check;
126 StrictMock<MockFieldGreaterThan> field_gt;
127
128 EventEmitter<WrittenPublicDataSlotsTreeCheckEvent> event_emitter;
129
130 WrittenPublicDataSlotsTree initial_state = build_public_data_slots_tree();
131 // Prefill now points to leaf MAX
132 initial_state.insert_indexed_leaves({ { WrittenPublicDataSlotLeafValue(FF::neg_one()) } });
133
134 FF slot = 42;
135 AztecAddress contract_address = AztecAddress(27);
136 FF leaf_slot = RawPoseidon2::hash({ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot });
137
138 auto low_leaf = initial_state.get_leaf_preimage(0);
139
140 FF low_leaf_hash = RawPoseidon2::hash(low_leaf.get_hash_inputs());
141 uint64_t low_leaf_index = 0;
142 std::vector<FF> sibling_path = initial_state.get_sibling_path(low_leaf_index);
143 AppendOnlyTreeSnapshot snapshot = initial_state.get_snapshot();
144
145 WrittenPublicDataSlotsTreeCheck written_public_data_slots_tree_check(
146 poseidon2, merkle_check, field_gt, initial_state, event_emitter);
147
148 EXPECT_CALL(poseidon2, hash(std::vector<FF>{ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot }))
149 .WillRepeatedly(Return(FF(leaf_slot)));
150 EXPECT_CALL(poseidon2, hash(low_leaf.get_hash_inputs())).WillRepeatedly(Return(FF(low_leaf_hash)));
151 EXPECT_CALL(merkle_check, assert_membership(low_leaf_hash, low_leaf_index, _, snapshot.root))
152 .WillRepeatedly(Return());
153 EXPECT_CALL(field_gt, ff_gt(leaf_slot, low_leaf.leaf.slot)).WillRepeatedly(Return(true));
154 EXPECT_CALL(field_gt, ff_gt(low_leaf.nextKey, leaf_slot)).WillRepeatedly(Return(true));
155
156 written_public_data_slots_tree_check.contains(contract_address, slot);
157
158 WrittenPublicDataSlotsTreeCheckEvent expect_event = {
159 .contract_address = contract_address,
160 .slot = slot,
161 .leaf_slot = leaf_slot,
162 .prev_snapshot = snapshot,
163 .next_snapshot = snapshot,
164 .low_leaf_preimage = low_leaf,
165 .low_leaf_hash = low_leaf_hash,
166 .low_leaf_index = low_leaf_index,
167 };
168 EXPECT_THAT(event_emitter.dump_events(), ElementsAre(expect_event));
169}
170
171TEST(AvmSimulationWrittenPublicDataSlotsTree, InsertExists)
172{
173 StrictMock<MockPoseidon2> poseidon2;
174 StrictMock<MockMerkleCheck> merkle_check;
175 StrictMock<MockFieldGreaterThan> field_gt;
176
177 EventEmitter<WrittenPublicDataSlotsTreeCheckEvent> event_emitter;
178
179 FF slot = 42;
180 AztecAddress contract_address = AztecAddress(27);
181 FF leaf_slot = RawPoseidon2::hash({ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot });
182
183 WrittenPublicDataSlotsTree initial_state = build_public_data_slots_tree();
184 uint64_t low_leaf_index = initial_state.get_snapshot().nextAvailableLeafIndex;
185 initial_state.insert_indexed_leaves({ { WrittenPublicDataSlotLeafValue(leaf_slot) } });
186
187 WrittenPublicDataSlotsTreeLeafPreimage low_leaf = initial_state.get_leaf_preimage(low_leaf_index);
188 FF low_leaf_hash = RawPoseidon2::hash(low_leaf.get_hash_inputs());
189 std::vector<FF> sibling_path = initial_state.get_sibling_path(low_leaf_index);
190 AppendOnlyTreeSnapshot snapshot = initial_state.get_snapshot();
191
192 WrittenPublicDataSlotsTreeCheck written_public_data_slots_tree_check(
193 poseidon2, merkle_check, field_gt, initial_state, event_emitter);
194
195 EXPECT_CALL(poseidon2, hash(std::vector<FF>{ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot }))
196 .WillRepeatedly(Return(FF(leaf_slot)));
197 EXPECT_CALL(poseidon2, hash(low_leaf.get_hash_inputs())).WillRepeatedly(Return(FF(low_leaf_hash)));
198 EXPECT_CALL(merkle_check, assert_membership(low_leaf_hash, low_leaf_index, _, snapshot.root))
199 .WillRepeatedly(Return());
200
201 written_public_data_slots_tree_check.insert(contract_address, slot);
202
203 EXPECT_EQ(written_public_data_slots_tree_check.snapshot(), snapshot);
204
205 WrittenPublicDataSlotsTreeCheckEvent expect_event = {
206 .contract_address = contract_address,
207 .slot = slot,
208 .leaf_slot = leaf_slot,
209 .prev_snapshot = snapshot,
210 .next_snapshot = snapshot,
211 .low_leaf_preimage = low_leaf,
212 .low_leaf_hash = low_leaf_hash,
213 .low_leaf_index = low_leaf_index,
214 .write = true,
215 };
216 EXPECT_THAT(event_emitter.dump_events(), ElementsAre(expect_event));
217}
218
219TEST(AvmSimulationWrittenPublicDataSlotsTree, InsertAppend)
220{
221 StrictMock<MockPoseidon2> poseidon2;
222 StrictMock<MockMerkleCheck> merkle_check;
223 StrictMock<MockFieldGreaterThan> field_gt;
224
225 EventEmitter<WrittenPublicDataSlotsTreeCheckEvent> event_emitter;
226
227 FF slot = 100;
228 AztecAddress contract_address = AztecAddress(27);
229 FF leaf_slot = RawPoseidon2::hash({ GENERATOR_INDEX__PUBLIC_LEAF_INDEX, contract_address, slot });
230
231 WrittenPublicDataSlotsTree initial_state = build_public_data_slots_tree();
232 // Prefill will point to our new leaf
233 ASSERT_EQ(initial_state.get_snapshot().nextAvailableLeafIndex, 1);
234 uint64_t low_leaf_index = 0;
235 uint64_t new_leaf_index = 1;
236 WrittenPublicDataSlotsTreeLeafPreimage low_leaf = initial_state.get_leaf_preimage(low_leaf_index);
237
238 FF low_leaf_hash = RawPoseidon2::hash(low_leaf.get_hash_inputs());
239 WrittenPublicDataSlotsTree state_after_insert = initial_state;
240 state_after_insert.insert_indexed_leaves({ { WrittenPublicDataSlotLeafValue(leaf_slot) } });
241
242 std::vector<FF> low_leaf_sibling_path = initial_state.get_sibling_path(low_leaf_index);
243
244 WrittenPublicDataSlotsTreeLeafPreimage updated_low_leaf = low_leaf;
245 updated_low_leaf.nextIndex = new_leaf_index;
246 updated_low_leaf.nextKey = leaf_slot;
247 FF updated_low_leaf_hash = RawPoseidon2::hash(updated_low_leaf.get_hash_inputs());
248
249 FF intermediate_root = unconstrained_root_from_path(updated_low_leaf_hash, low_leaf_index, low_leaf_sibling_path);
250 std::vector<FF> insertion_sibling_path = state_after_insert.get_sibling_path(new_leaf_index);
251
252 WrittenPublicDataSlotsTreeLeafPreimage new_leaf = WrittenPublicDataSlotsTreeLeafPreimage(
253 WrittenPublicDataSlotLeafValue(leaf_slot), low_leaf.nextIndex, low_leaf.nextKey);
254 FF new_leaf_hash = RawPoseidon2::hash(new_leaf.get_hash_inputs());
255
256 WrittenPublicDataSlotsTreeCheck written_public_data_slots_tree_check(
257 poseidon2, merkle_check, field_gt, initial_state, event_emitter);
258
259 EXPECT_CALL(poseidon2, hash(_)).WillRepeatedly([](const std::vector<FF>& input) {
260 return RawPoseidon2::hash(input);
261 });
262 EXPECT_CALL(merkle_check,
263 write(low_leaf_hash, updated_low_leaf_hash, low_leaf_index, _, initial_state.get_snapshot().root))
264 .WillRepeatedly(Return(intermediate_root));
265 EXPECT_CALL(field_gt, ff_gt(leaf_slot, low_leaf.leaf.slot)).WillRepeatedly(Return(true));
266 EXPECT_CALL(field_gt, ff_gt(low_leaf.nextKey, leaf_slot)).WillRepeatedly(Return(true));
267 EXPECT_CALL(merkle_check, write(FF(0), new_leaf_hash, new_leaf_index, _, intermediate_root))
268 .WillRepeatedly(Return(state_after_insert.get_snapshot().root));
269
270 written_public_data_slots_tree_check.insert(contract_address, slot);
271
272 EXPECT_EQ(written_public_data_slots_tree_check.snapshot(), state_after_insert.get_snapshot());
273
274 WrittenPublicDataSlotsTreeCheckEvent expect_event = { .contract_address = contract_address,
275 .slot = slot,
276 .leaf_slot = leaf_slot,
277 .prev_snapshot = initial_state.get_snapshot(),
278 .next_snapshot = state_after_insert.get_snapshot(),
279 .low_leaf_preimage = low_leaf,
280 .low_leaf_hash = low_leaf_hash,
281 .low_leaf_index = low_leaf_index,
282 .write = true,
283 .append_data = SlotAppendData{
284 .updated_low_leaf_hash = updated_low_leaf_hash,
285 .new_leaf_hash = new_leaf_hash,
286 .intermediate_root = intermediate_root,
287 } };
288
289 EXPECT_THAT(event_emitter.dump_events(), ElementsAre(expect_event));
290}
291
292TEST(AvmSimulationWrittenPublicDataSlotsTree, CheckpointBehavior)
293{
294 StrictMock<MockPoseidon2> poseidon2;
295 StrictMock<MockMerkleCheck> merkle_check;
296 StrictMock<MockFieldGreaterThan> field_gt;
297
298 EventEmitter<WrittenPublicDataSlotsTreeCheckEvent> event_emitter;
299
300 EXPECT_CALL(poseidon2, hash(_)).WillRepeatedly([](const std::vector<FF>& input) {
301 return RawPoseidon2::hash(input);
302 });
303 EXPECT_CALL(merkle_check, write)
304 .WillRepeatedly(
305 [](FF current_leaf, FF new_leaf, uint64_t leaf_index, std::span<const FF> sibling_path, FF prev_root) {
306 EXPECT_EQ(unconstrained_root_from_path(current_leaf, leaf_index, sibling_path), prev_root);
307 return unconstrained_root_from_path(new_leaf, leaf_index, sibling_path);
308 });
309 EXPECT_CALL(merkle_check, assert_membership(_, _, _, _))
310 .WillRepeatedly([](FF current_leaf, uint64_t leaf_index, std::span<const FF> sibling_path, FF prev_root) {
311 EXPECT_EQ(unconstrained_root_from_path(current_leaf, leaf_index, sibling_path), prev_root);
312 });
313 EXPECT_CALL(field_gt, ff_gt(_, _)).WillRepeatedly(Return(true));
314
315 WrittenPublicDataSlotsTree initial_state = build_public_data_slots_tree();
316 WrittenPublicDataSlotsTreeCheck written_public_data_slots_tree_check(
317 poseidon2, merkle_check, field_gt, initial_state, event_emitter);
318
319 EXPECT_EQ(written_public_data_slots_tree_check.size(), 0);
320 written_public_data_slots_tree_check.create_checkpoint();
321
322 written_public_data_slots_tree_check.insert(AztecAddress(1), 1);
323 EXPECT_TRUE(written_public_data_slots_tree_check.contains(AztecAddress(1), 1));
324 EXPECT_EQ(written_public_data_slots_tree_check.size(), 1);
325
326 // Commit the checkpoint
327 written_public_data_slots_tree_check.commit_checkpoint();
328 EXPECT_TRUE(written_public_data_slots_tree_check.contains(AztecAddress(1), 1));
329 EXPECT_EQ(written_public_data_slots_tree_check.size(), 1);
330
331 // Create another checkpoint
332 written_public_data_slots_tree_check.create_checkpoint();
333
334 // Insert another slot
335 written_public_data_slots_tree_check.insert(AztecAddress(2), 2);
336 EXPECT_TRUE(written_public_data_slots_tree_check.contains(AztecAddress(2), 2));
337 EXPECT_EQ(written_public_data_slots_tree_check.size(), 2);
338
339 // Revert the checkpoint
340 written_public_data_slots_tree_check.revert_checkpoint();
341 EXPECT_TRUE(written_public_data_slots_tree_check.contains(AztecAddress(1), 1));
342 EXPECT_EQ(written_public_data_slots_tree_check.size(), 1);
343}
344
345} // namespace
346
347} // namespace bb::avm2::simulation
avm_inputs.hpp
GENERATOR_INDEX__PUBLIC_LEAF_INDEX
#define GENERATOR_INDEX__PUBLIC_LEAF_INDEX
Definition aztec_constants.hpp:270
aztec_types.hpp
bb::crypto::Poseidon2< crypto::Poseidon2Bn254ScalarFieldParams >::hash
static FF hash(const std::vector< FF > &input)
Hashes a vector of field elements.
event_emitter
EventEmitter< DataCopyEvent > event_emitter
Definition data_copy.test.cpp:53
low_leaf
NullifierTreeLeafPreimage low_leaf
Definition nullifier_tree_check.test.cpp:74
contract_address
AztecAddress contract_address
Definition written_public_data_slots_tree_check.test.cpp:96
memory_tree.hpp
hash
void hash(State &state) noexcept
Definition merkle_tree.bench.cpp:28
mock_field_gt.hpp
mock_merkle_check.hpp
mock_poseidon2.hpp
bb::avm2::simulation::poseidon2
crypto::Poseidon2< crypto::Poseidon2Bn254ScalarFieldParams > poseidon2
Definition contract_crypto.cpp:9
bb::avm2::simulation::TEST
TEST(EmitUnencryptedLogTest, Basic)
Definition emit_unencrypted_log.test.cpp:20
bb::avm2::simulation::WrittenPublicDataSlotsTreeLeafPreimage
IndexedLeaf< WrittenPublicDataSlotLeafValue > WrittenPublicDataSlotsTreeLeafPreimage
Definition written_slots_tree.hpp:40
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::build_public_data_slots_tree
WrittenPublicDataSlotsTree build_public_data_slots_tree()
Definition written_slots_tree.cpp:58
bb::avm2::simulation::WrittenPublicDataSlotsTree
IndexedMemoryTree< WrittenPublicDataSlotLeafValue, Poseidon2HashPolicy > WrittenPublicDataSlotsTree
Definition written_slots_tree.hpp:38
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:16
bb::write
void write(B &buf, field2< base_field, Params > const &value)
Definition field2_declarations.hpp:155
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
slot
FF slot
Definition public_data_tree.test.cpp:95
written_public_data_slots_tree_check.hpp
bb::crypto::merkle_tree::IndexedLeaf::leaf
LeafType leaf
Definition indexed_leaf.hpp:138
bb::crypto::merkle_tree::IndexedLeaf::get_hash_inputs
std::vector< fr > get_hash_inputs() const
Definition indexed_leaf.hpp:191
bb::crypto::merkle_tree::IndexedLeaf::nextIndex
index_t nextIndex
Definition indexed_leaf.hpp:139
bb::crypto::merkle_tree::IndexedLeaf::nextKey
fr nextKey
Definition indexed_leaf.hpp:140
field_gt
NiceMock< MockFieldGreaterThan > field_gt
Definition tx_execution.test.cpp:31
written_public_data_slots_tree_check
NiceMock< MockWrittenPublicDataSlotsTreeCheck > written_public_data_slots_tree_check
Definition tx_execution.test.cpp:33
written_public_data_slot_tree_check_event.hpp
written_slots_tree.hpp