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_constant_2, 2),
77 ROW_FIELD_EQ(merkle_check_read_output_hash, output_hash_1)),
78 // Second real row
79 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
80 ROW_FIELD_EQ(merkle_check_write, 0),
81 ROW_FIELD_EQ(merkle_check_read_node, output_hash_1), // Previous output becomes new leaf
82 ROW_FIELD_EQ(merkle_check_index, 0), // Index should be 0 at level 2
83 ROW_FIELD_EQ(merkle_check_path_len, 1), // Remaining path length is 0
84 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
85 ROW_FIELD_EQ(merkle_check_read_root, root),
86 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_2),
87 ROW_FIELD_EQ(merkle_check_start, 0),
88 ROW_FIELD_EQ(merkle_check_end, 1), // Done after two layers
89 ROW_FIELD_EQ(merkle_check_index_is_even, 1),
90 ROW_FIELD_EQ(merkle_check_read_left_node, left_node_2),
91 ROW_FIELD_EQ(merkle_check_read_right_node, right_node_2),
92 ROW_FIELD_EQ(merkle_check_constant_2, 2),
93 ROW_FIELD_EQ(merkle_check_read_output_hash, output_hash_2))));
94}
95
96TEST(MerkleCheckTraceGenTest, MerkleWrite)
97{
98 TestTraceContainer trace;
99 MerkleCheckTraceBuilder builder;
100
101 FF leaf_value = FF(123);
102 FF new_leaf_value = FF(456);
103 uint64_t leaf_index = 1; // Odd index
104
105 // Level 1 sibling
106 FF sibling_value_1 = FF(456);
107
108 // Compute hash for level 1
109 // For odd index, sibling is left, leaf is right
110 FF read_output_hash_1 = Poseidon2::hash({ sibling_value_1, leaf_value });
111 FF write_output_hash_1 = Poseidon2::hash({ sibling_value_1, new_leaf_value });
112
113 // Level 2 sibling
114 FF sibling_value_2 = FF(789);
115
116 // Compute hash for level 2
117 // For odd index 1 in level 1, parent is at index 0 (even) in level 2
118 FF read_output_hash_2 = Poseidon2::hash({ read_output_hash_1, sibling_value_2 });
119 FF write_output_hash_2 = Poseidon2::hash({ write_output_hash_1, sibling_value_2 });
120
121 std::vector<FF> sibling_path = { sibling_value_1, sibling_value_2 };
122 FF read_root = read_output_hash_2;
123 FF write_root = write_output_hash_2;
124
125 MerkleCheckEvent event = { .leaf_value = leaf_value,
126 .new_leaf_value = new_leaf_value,
127 .leaf_index = leaf_index,
128 .sibling_path = sibling_path,
129 .root = read_root,
130 .new_root = write_root };
131
132 builder.process({ event }, trace);
133
134 EXPECT_THAT(trace.as_rows(),
135 ElementsAre(
136 // First row is empty
137 AllOf(ROW_FIELD_EQ(merkle_check_sel, 0)),
138 // First real row
139 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
140 ROW_FIELD_EQ(merkle_check_write, 1),
141 ROW_FIELD_EQ(merkle_check_read_node, leaf_value),
142 ROW_FIELD_EQ(merkle_check_write_node, new_leaf_value),
143 ROW_FIELD_EQ(merkle_check_index, leaf_index),
144 ROW_FIELD_EQ(merkle_check_path_len, 2), // path length starts at 2
145 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, FF(2 - 1).invert()),
146 ROW_FIELD_EQ(merkle_check_read_root, read_root),
147 ROW_FIELD_EQ(merkle_check_write_root, write_root),
148 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_1),
149 ROW_FIELD_EQ(merkle_check_start, 1),
150 ROW_FIELD_EQ(merkle_check_end, 0), // Not done yet
151 ROW_FIELD_EQ(merkle_check_index_is_even, 0), // Odd index
152 ROW_FIELD_EQ(merkle_check_read_left_node, sibling_value_1),
153 ROW_FIELD_EQ(merkle_check_read_right_node, leaf_value),
154 ROW_FIELD_EQ(merkle_check_write_left_node, sibling_value_1),
155 ROW_FIELD_EQ(merkle_check_write_right_node, new_leaf_value),
156 ROW_FIELD_EQ(merkle_check_constant_2, 2),
157 ROW_FIELD_EQ(merkle_check_read_output_hash, read_output_hash_1),
158 ROW_FIELD_EQ(merkle_check_write_output_hash, write_output_hash_1)),
159 // Second real row
160 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
161 ROW_FIELD_EQ(merkle_check_write, 1),
162 ROW_FIELD_EQ(merkle_check_read_node, read_output_hash_1), // Previous output becomes new leaf
163 ROW_FIELD_EQ(merkle_check_write_node, write_output_hash_1),
164 ROW_FIELD_EQ(merkle_check_index, 0), // Index should be 0 at level 2
165 ROW_FIELD_EQ(merkle_check_path_len, 1), // Remaining path length is 0
166 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
167 ROW_FIELD_EQ(merkle_check_read_root, read_root),
168 ROW_FIELD_EQ(merkle_check_write_root, write_root),
169 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_2),
170 ROW_FIELD_EQ(merkle_check_start, 0),
171 ROW_FIELD_EQ(merkle_check_end, 1), // Done after two layers
172 ROW_FIELD_EQ(merkle_check_index_is_even, 1),
173 ROW_FIELD_EQ(merkle_check_read_left_node, read_output_hash_1),
174 ROW_FIELD_EQ(merkle_check_read_right_node, sibling_value_2),
175 ROW_FIELD_EQ(merkle_check_write_left_node, write_output_hash_1),
176 ROW_FIELD_EQ(merkle_check_write_right_node, sibling_value_2),
177 ROW_FIELD_EQ(merkle_check_constant_2, 2),
178 ROW_FIELD_EQ(merkle_check_read_output_hash, read_output_hash_2),
179 ROW_FIELD_EQ(merkle_check_write_output_hash, write_output_hash_2))));
180}
181
182TEST(MerkleCheckTraceGenTest, MixedEvents)
183{
184 TestTraceContainer trace;
185 MerkleCheckTraceBuilder builder;
186
187 // First event
188 FF leaf_value_1 = FF(111);
189 uint64_t leaf_index_1 = 6;
190 FF sibling_value_1 = FF(222);
191 FF output_hash_1 = Poseidon2::hash({ leaf_value_1, sibling_value_1 });
192
193 MerkleCheckEvent event1 = { .leaf_value = leaf_value_1,
194 .leaf_index = leaf_index_1,
195 .sibling_path = { sibling_value_1 },
196 .root = output_hash_1 };
197
198 // Second event
199 FF leaf_value_2 = FF(333);
200 FF new_leaf_value_2 = FF(444);
201 uint64_t leaf_index_2 = 11;
202 FF sibling_value_2 = FF(444);
203 FF read_output_hash_2 = Poseidon2::hash({ sibling_value_2, leaf_value_2 });
204 FF write_output_hash_2 = Poseidon2::hash({ sibling_value_2, new_leaf_value_2 });
205
206 MerkleCheckEvent event2 = { .leaf_value = leaf_value_2,
207 .new_leaf_value = new_leaf_value_2,
208 .leaf_index = leaf_index_2,
209 .sibling_path = { sibling_value_2 },
210 .root = read_output_hash_2,
211 .new_root = write_output_hash_2 };
212
213 builder.process({ event1, event2 }, trace);
214
215 EXPECT_THAT(trace.as_rows(),
216 ElementsAre(
217 // First row is empty
218 AllOf(ROW_FIELD_EQ(merkle_check_sel, 0)),
219 // First real row (read)
220 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
221 ROW_FIELD_EQ(merkle_check_write, 0),
222 ROW_FIELD_EQ(merkle_check_read_node, leaf_value_1),
223 ROW_FIELD_EQ(merkle_check_index, leaf_index_1),
224 ROW_FIELD_EQ(merkle_check_path_len, 1),
225 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
226 ROW_FIELD_EQ(merkle_check_read_root, output_hash_1),
227 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_1),
228 ROW_FIELD_EQ(merkle_check_start, 1),
229 ROW_FIELD_EQ(merkle_check_end, 1),
230 ROW_FIELD_EQ(merkle_check_index_is_even, 1),
231 ROW_FIELD_EQ(merkle_check_read_left_node, leaf_value_1),
232 ROW_FIELD_EQ(merkle_check_read_right_node, sibling_value_1),
233 ROW_FIELD_EQ(merkle_check_constant_2, 2),
234 ROW_FIELD_EQ(merkle_check_read_output_hash, output_hash_1)),
235 // Second real row (write)
236 AllOf(ROW_FIELD_EQ(merkle_check_sel, 1),
237 ROW_FIELD_EQ(merkle_check_write, 1),
238 ROW_FIELD_EQ(merkle_check_read_node, leaf_value_2),
239 ROW_FIELD_EQ(merkle_check_write_node, new_leaf_value_2),
240 ROW_FIELD_EQ(merkle_check_index, leaf_index_2),
241 ROW_FIELD_EQ(merkle_check_path_len, 1),
242 ROW_FIELD_EQ(merkle_check_remaining_path_len_inv, 0),
243 ROW_FIELD_EQ(merkle_check_read_root, read_output_hash_2),
244 ROW_FIELD_EQ(merkle_check_write_root, write_output_hash_2),
245 ROW_FIELD_EQ(merkle_check_sibling, sibling_value_2),
246 ROW_FIELD_EQ(merkle_check_start, 1),
247 ROW_FIELD_EQ(merkle_check_end, 1),
248 ROW_FIELD_EQ(merkle_check_index_is_even, 0),
249 ROW_FIELD_EQ(merkle_check_read_left_node, sibling_value_2),
250 ROW_FIELD_EQ(merkle_check_read_right_node, leaf_value_2),
251 ROW_FIELD_EQ(merkle_check_write_left_node, sibling_value_2),
252 ROW_FIELD_EQ(merkle_check_write_right_node, new_leaf_value_2),
253 ROW_FIELD_EQ(merkle_check_constant_2, 2),
254 ROW_FIELD_EQ(merkle_check_read_output_hash, read_output_hash_2),
255 ROW_FIELD_EQ(merkle_check_write_output_hash, write_output_hash_2))));
256}
257
258} // namespace
259} // namespace bb::avm2::tracegen
bb::avm2::tracegen::AluTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::AluEvent >::Container &events, TraceContainer &trace)
Definition alu_trace.cpp:312
bb::avm2::tracegen::TestTraceContainer::as_rows
std::vector< AvmFullRowConstRef > as_rows() const
Definition test_trace_container.cpp:41
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:59
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