Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
merkle_check_trace.test.cpp
Go to the documentation of this file.
1#include <gmock/gmock.h>
2#include <gtest/gtest.h>
3
4#include <cstdint>
5#include <vector>
6
7#include "barretenberg/crypto/poseidon2/poseidon2.hpp"
8#include "barretenberg/vm2/common/field.hpp"
9#include "barretenberg/vm2/constraining/flavor_settings.hpp"
10#include "barretenberg/vm2/constraining/full_row.hpp"
11#include "barretenberg/vm2/testing/macros.hpp"
12#include "barretenberg/vm2/tracegen/merkle_check_trace.hpp"
13#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
14
15namespace bb::avm2::tracegen {
16namespace {
17
18using testing::ElementsAre;
19using testing::Field;
20
21using R = TestTraceContainer::Row;
22using Poseidon2 = crypto::Poseidon2<crypto::Poseidon2Bn254ScalarFieldParams>;
23using simulation::MerkleCheckEvent;
24
25TEST(MerkleCheckTraceGenTest, MerkleRead)
26{
27 TestTraceContainer trace;
28 MerkleCheckTraceBuilder builder;
29
30 FF leaf_value = FF(123);
31 uint64_t leaf_index = 1; // Odd index
32
33 // Level 1 sibling
34 FF sibling_value_1 = FF(456);
35
36 // Compute hash for level 1
37 FF left_node_1 = sibling_value_1; // For odd index, sibling is left
38 FF right_node_1 = leaf_value; // For odd index, leaf is right
39 FF output_hash_1 = Poseidon2::hash({ left_node_1, right_node_1 });
40
41 // Level 2 sibling
42 FF sibling_value_2 = FF(789);
43
44 // Compute hash for level 2
45 FF left_node_2 = output_hash_1; // For odd index 1 in level 1, parent is at index 0 (even) in level 2
46 FF right_node_2 = sibling_value_2;
47 FF output_hash_2 = Poseidon2::hash({ left_node_2, right_node_2 });
48
49 std::vector<FF> sibling_path = { sibling_value_1, sibling_value_2 };
50 FF root = output_hash_2; // Root is the final output hash
51
52 MerkleCheckEvent event = {
53 .leaf_value = leaf_value, .leaf_index = leaf_index, .sibling_path = sibling_path, .root = root
54 };
55
56 builder.process({ event }, trace);
57
58 EXPECT_THAT(trace.as_rows(),
59 ElementsAre(
60 // First row is empty
61 AllOf(ROW_FIELD_EQ(merkle_check_sel, 0)),
62 // First real row
63 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
64 ROW_FIELD_EQ(merkle_check_write, 0),
65 ROW_FIELD_EQ(merkle_check_read_node, leaf_value),
66 ROW_FIELD_EQ(merkle_check_index, leaf_index),
67 ROW_FIELD_EQ(merkle_check_path_len, 2), // path length starts at 2
68 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, FF(2 - 1).invert()),
69 ROW_FIELD_EQ(merkle_check_read_root, root),
70 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_1),
71 ROW_FIELD_EQ(merkle_check_start, 1),
72 ROW_FIELD_EQ(merkle_check_end, 0), // Not done yet
73 ROW_FIELD_EQ(merkle_check_index_is_even, 0), // Odd index
74 ROW_FIELD_EQ(merkle_check_read_left_node, left_node_1),
75 ROW_FIELD_EQ(merkle_check_read_right_node, right_node_1),
76 ROW_FIELD_EQ(merkle_check_read_output_hash, output_hash_1)),
77 // Second real row
78 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
79 ROW_FIELD_EQ(merkle_check_write, 0),
80 ROW_FIELD_EQ(merkle_check_read_node, output_hash_1), // Previous output becomes new leaf
81 ROW_FIELD_EQ(merkle_check_index, 0), // Index should be 0 at level 2
82 ROW_FIELD_EQ(merkle_check_path_len, 1), // Remaining path length is 0
83 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
84 ROW_FIELD_EQ(merkle_check_read_root, root),
85 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_2),
86 ROW_FIELD_EQ(merkle_check_start, 0),
87 ROW_FIELD_EQ(merkle_check_end, 1), // Done after two layers
88 ROW_FIELD_EQ(merkle_check_index_is_even, 1),
89 ROW_FIELD_EQ(merkle_check_read_left_node, left_node_2),
90 ROW_FIELD_EQ(merkle_check_read_right_node, right_node_2),
91 ROW_FIELD_EQ(merkle_check_read_output_hash, output_hash_2))));
92}
93
94TEST(MerkleCheckTraceGenTest, MerkleWrite)
95{
96 TestTraceContainer trace;
97 MerkleCheckTraceBuilder builder;
98
99 FF leaf_value = FF(123);
100 FF new_leaf_value = FF(456);
101 uint64_t leaf_index = 1; // Odd index
102
103 // Level 1 sibling
104 FF sibling_value_1 = FF(456);
105
106 // Compute hash for level 1
107 // For odd index, sibling is left, leaf is right
108 FF read_output_hash_1 = Poseidon2::hash({ sibling_value_1, leaf_value });
109 FF write_output_hash_1 = Poseidon2::hash({ sibling_value_1, new_leaf_value });
110
111 // Level 2 sibling
112 FF sibling_value_2 = FF(789);
113
114 // Compute hash for level 2
115 // For odd index 1 in level 1, parent is at index 0 (even) in level 2
116 FF read_output_hash_2 = Poseidon2::hash({ read_output_hash_1, sibling_value_2 });
117 FF write_output_hash_2 = Poseidon2::hash({ write_output_hash_1, sibling_value_2 });
118
119 std::vector<FF> sibling_path = { sibling_value_1, sibling_value_2 };
120 FF read_root = read_output_hash_2;
121 FF write_root = write_output_hash_2;
122
123 MerkleCheckEvent event = { .leaf_value = leaf_value,
124 .new_leaf_value = new_leaf_value,
125 .leaf_index = leaf_index,
126 .sibling_path = sibling_path,
127 .root = read_root,
128 .new_root = write_root };
129
130 builder.process({ event }, trace);
131
132 EXPECT_THAT(trace.as_rows(),
133 ElementsAre(
134 // First row is empty
135 AllOf(ROW_FIELD_EQ(merkle_check_sel, 0)),
136 // First real row
137 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
138 ROW_FIELD_EQ(merkle_check_write, 1),
139 ROW_FIELD_EQ(merkle_check_read_node, leaf_value),
140 ROW_FIELD_EQ(merkle_check_write_node, new_leaf_value),
141 ROW_FIELD_EQ(merkle_check_index, leaf_index),
142 ROW_FIELD_EQ(merkle_check_path_len, 2), // path length starts at 2
143 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, FF(2 - 1).invert()),
144 ROW_FIELD_EQ(merkle_check_read_root, read_root),
145 ROW_FIELD_EQ(merkle_check_write_root, write_root),
146 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_1),
147 ROW_FIELD_EQ(merkle_check_start, 1),
148 ROW_FIELD_EQ(merkle_check_end, 0), // Not done yet
149 ROW_FIELD_EQ(merkle_check_index_is_even, 0), // Odd index
150 ROW_FIELD_EQ(merkle_check_read_left_node, sibling_value_1),
151 ROW_FIELD_EQ(merkle_check_read_right_node, leaf_value),
152 ROW_FIELD_EQ(merkle_check_write_left_node, sibling_value_1),
153 ROW_FIELD_EQ(merkle_check_write_right_node, new_leaf_value),
154 ROW_FIELD_EQ(merkle_check_read_output_hash, read_output_hash_1),
155 ROW_FIELD_EQ(merkle_check_write_output_hash, write_output_hash_1)),
156 // Second real row
157 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
158 ROW_FIELD_EQ(merkle_check_write, 1),
159 ROW_FIELD_EQ(merkle_check_read_node, read_output_hash_1), // Previous output becomes new leaf
160 ROW_FIELD_EQ(merkle_check_write_node, write_output_hash_1),
161 ROW_FIELD_EQ(merkle_check_index, 0), // Index should be 0 at level 2
162 ROW_FIELD_EQ(merkle_check_path_len, 1), // Remaining path length is 0
163 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
164 ROW_FIELD_EQ(merkle_check_read_root, read_root),
165 ROW_FIELD_EQ(merkle_check_write_root, write_root),
166 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_2),
167 ROW_FIELD_EQ(merkle_check_start, 0),
168 ROW_FIELD_EQ(merkle_check_end, 1), // Done after two layers
169 ROW_FIELD_EQ(merkle_check_index_is_even, 1),
170 ROW_FIELD_EQ(merkle_check_read_left_node, read_output_hash_1),
171 ROW_FIELD_EQ(merkle_check_read_right_node, sibling_value_2),
172 ROW_FIELD_EQ(merkle_check_write_left_node, write_output_hash_1),
173 ROW_FIELD_EQ(merkle_check_write_right_node, sibling_value_2),
174 ROW_FIELD_EQ(merkle_check_read_output_hash, read_output_hash_2),
175 ROW_FIELD_EQ(merkle_check_write_output_hash, write_output_hash_2))));
176}
177
178TEST(MerkleCheckTraceGenTest, MixedEvents)
179{
180 TestTraceContainer trace;
181 MerkleCheckTraceBuilder builder;
182
183 // First event
184 FF leaf_value_1 = FF(111);
185 uint64_t leaf_index_1 = 6;
186 FF sibling_value_1 = FF(222);
187 FF output_hash_1 = Poseidon2::hash({ leaf_value_1, sibling_value_1 });
188
189 MerkleCheckEvent event1 = { .leaf_value = leaf_value_1,
190 .leaf_index = leaf_index_1,
191 .sibling_path = { sibling_value_1 },
192 .root = output_hash_1 };
193
194 // Second event
195 FF leaf_value_2 = FF(333);
196 FF new_leaf_value_2 = FF(444);
197 uint64_t leaf_index_2 = 11;
198 FF sibling_value_2 = FF(444);
199 FF read_output_hash_2 = Poseidon2::hash({ sibling_value_2, leaf_value_2 });
200 FF write_output_hash_2 = Poseidon2::hash({ sibling_value_2, new_leaf_value_2 });
201
202 MerkleCheckEvent event2 = { .leaf_value = leaf_value_2,
203 .new_leaf_value = new_leaf_value_2,
204 .leaf_index = leaf_index_2,
205 .sibling_path = { sibling_value_2 },
206 .root = read_output_hash_2,
207 .new_root = write_output_hash_2 };
208
209 builder.process({ event1, event2 }, trace);
210
211 EXPECT_THAT(trace.as_rows(),
212 ElementsAre(
213 // First row is empty
214 AllOf(ROW_FIELD_EQ(merkle_check_sel, 0)),
215 // First real row (read)
216 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
217 ROW_FIELD_EQ(merkle_check_write, 0),
218 ROW_FIELD_EQ(merkle_check_read_node, leaf_value_1),
219 ROW_FIELD_EQ(merkle_check_index, leaf_index_1),
220 ROW_FIELD_EQ(merkle_check_path_len, 1),
221 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
222 ROW_FIELD_EQ(merkle_check_read_root, output_hash_1),
223 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_1),
224 ROW_FIELD_EQ(merkle_check_start, 1),
225 ROW_FIELD_EQ(merkle_check_end, 1),
226 ROW_FIELD_EQ(merkle_check_index_is_even, 1),
227 ROW_FIELD_EQ(merkle_check_read_left_node, leaf_value_1),
228 ROW_FIELD_EQ(merkle_check_read_right_node, sibling_value_1),
229 ROW_FIELD_EQ(merkle_check_read_output_hash, output_hash_1)),
230 // Second real row (write)
231 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
232 ROW_FIELD_EQ(merkle_check_write, 1),
233 ROW_FIELD_EQ(merkle_check_read_node, leaf_value_2),
234 ROW_FIELD_EQ(merkle_check_write_node, new_leaf_value_2),
235 ROW_FIELD_EQ(merkle_check_index, leaf_index_2),
236 ROW_FIELD_EQ(merkle_check_path_len, 1),
237 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
238 ROW_FIELD_EQ(merkle_check_read_root, read_output_hash_2),
239 ROW_FIELD_EQ(merkle_check_write_root, write_output_hash_2),
240 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_2),
241 ROW_FIELD_EQ(merkle_check_start, 1),
242 ROW_FIELD_EQ(merkle_check_end, 1),
243 ROW_FIELD_EQ(merkle_check_index_is_even, 0),
244 ROW_FIELD_EQ(merkle_check_read_left_node, sibling_value_2),
245 ROW_FIELD_EQ(merkle_check_read_right_node, leaf_value_2),
246 ROW_FIELD_EQ(merkle_check_write_left_node, sibling_value_2),
247 ROW_FIELD_EQ(merkle_check_write_right_node, new_leaf_value_2),
248 ROW_FIELD_EQ(merkle_check_read_output_hash, read_output_hash_2),
249 ROW_FIELD_EQ(merkle_check_write_output_hash, write_output_hash_2))));
250}
251
252} // namespace
253} // namespace bb::avm2::tracegen
bb::avm2::tracegen::AluTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::AluEvent >::Container &events, TraceContainer &trace)
Definition alu_trace.cpp:308
bb::avm2::tracegen::TestTraceContainer::as_rows
std::vector< AvmFullRowConstRef > as_rows() const
Definition test_trace_container.cpp:28
bb::crypto::Poseidon2< crypto::Poseidon2Bn254ScalarFieldParams >::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
builder
AluTraceBuilder builder
Definition alu.test.cpp:123
trace
TestTraceContainer trace
Definition data_copy.test.cpp:62
flavor_settings.hpp
full_row.hpp
ROW_FIELD_EQ
#define ROW_FIELD_EQ(field_name, expression)
Definition macros.hpp:15
merkle_check_trace.hpp
bb::avm2::simulation::TEST
TEST(EmitUnencryptedLogTest, Basic)
Definition emit_unencrypted_log.test.cpp:20
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
test_trace_container.hpp