Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
merkle_check.test.cpp
Go to the documentation of this file.
1#include "barretenberg/vm2/simulation/gadgets/merkle_check.hpp"
2
3#include <gmock/gmock.h>
4#include <gtest/gtest.h>
5#include <optional>
6
7#include "barretenberg/vm2/simulation/events/event_emitter.hpp"
8#include "barretenberg/vm2/simulation/events/merkle_check_event.hpp"
9#include "barretenberg/vm2/simulation/lib/merkle.hpp"
10#include "barretenberg/vm2/simulation/standalone/pure_poseidon2.hpp"
11#include "barretenberg/vm2/testing/macros.hpp"
12
13namespace bb::avm2::simulation {
14namespace {
15
16using testing::ElementsAre;
17
18TEST(MerkleCheckSimulationTest, AssertMembership)
19{
20 // This fake will still perform hashing but is "lightweight" for simulation-only
21 PurePoseidon2 poseidon2 = PurePoseidon2();
22
23 EventEmitter<MerkleCheckEvent> emitter;
24 MerkleCheck merkle_check(poseidon2, emitter);
25
26 FF leaf_value = 333;
27 uint64_t leaf_index = 30;
28 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
29 FF root = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path);
30
31 merkle_check.assert_membership(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path, root);
32 MerkleCheckEvent expect_event = {
33 .merkle_hash_domain_separator = DOM_SEP__MERKLE_HASH,
34 .leaf_value = leaf_value,
35 .leaf_index = leaf_index,
36 .sibling_path = sibling_path,
37 .root = root,
38 };
39
40 FF leaf_value2 = 334;
41 uint64_t leaf_index2 = 31;
42 std::vector<FF> sibling_path2 = { 10, 2, 30, 4, 50, 7 };
43 FF root2 = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, leaf_value2, leaf_index2, sibling_path2);
44 merkle_check.assert_membership(DOM_SEP__MERKLE_HASH, leaf_value2, leaf_index2, sibling_path2, root2);
45 MerkleCheckEvent expect_event2 = {
46 .merkle_hash_domain_separator = DOM_SEP__MERKLE_HASH,
47 .leaf_value = leaf_value2,
48 .leaf_index = leaf_index2,
49 .sibling_path = sibling_path2,
50 .root = root2,
51 };
52
53 EXPECT_THAT(emitter.dump_events(), ElementsAre(expect_event, expect_event2));
54}
55
56TEST(MerkleCheckSimulationTest, Write)
57{
58 // This fake will still perform hashing but is "lightweight" for simulation-only
59 PurePoseidon2 poseidon2 = PurePoseidon2();
60
61 EventEmitter<MerkleCheckEvent> emitter;
62 MerkleCheck merkle_check(poseidon2, emitter);
63
64 FF current_value = 333;
65 FF new_value = 334;
66 uint64_t leaf_index = 30;
67 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
68 FF current_root = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, current_value, leaf_index, sibling_path);
69 FF expected_new_root = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, new_value, leaf_index, sibling_path);
70
71 MerkleCheckEvent expect_event = {
72 .merkle_hash_domain_separator = DOM_SEP__MERKLE_HASH,
73 .leaf_value = current_value,
74 .new_leaf_value = new_value,
75 .leaf_index = leaf_index,
76 .sibling_path = sibling_path,
77 .root = current_root,
78 .new_root = expected_new_root,
79 };
80
81 FF new_root =
82 merkle_check.write(DOM_SEP__MERKLE_HASH, current_value, new_value, leaf_index, sibling_path, current_root);
83
84 EXPECT_EQ(new_root, expected_new_root);
85 EXPECT_THAT(emitter.dump_events(), ElementsAre(expect_event));
86}
87
88TEST(MerkleCheckSimulationTest, NegativeBadFinalIndex)
89{
90 // This fake will still perform hashing but is "lightweight" for simulation-only
91 PurePoseidon2 poseidon2 = PurePoseidon2();
92
93 EventEmitter<MerkleCheckEvent> emitter;
94 MerkleCheck merkle_check(poseidon2, emitter);
95
96 FF leaf_value = 333;
97 uint64_t leaf_index = 64; // too large! halving it 5 times results in 2!
98 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
99 FF root = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path);
100
101 EXPECT_THROW_WITH_MESSAGE(
102 merkle_check.assert_membership(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path, root),
103 "Merkle check's final node index must be 0");
104 EXPECT_THROW_WITH_MESSAGE(merkle_check.write(DOM_SEP__MERKLE_HASH, leaf_value, 334, leaf_index, sibling_path, root),
105 "Merkle check's final node index must be 0");
106}
107
108TEST(MerkleCheckSimulationTest, NegativeWrongRoot)
109{
110 // This fake will still perform hashing but is "lightweight" for simulation-only
111 PurePoseidon2 poseidon2 = PurePoseidon2();
112
113 EventEmitter<MerkleCheckEvent> emitter;
114 MerkleCheck merkle_check(poseidon2, emitter);
115
116 FF leaf_value = 333;
117 uint64_t leaf_index = 30;
118 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
119 FF incorrect_root = 66;
120
121 EXPECT_THROW_WITH_MESSAGE(
122 merkle_check.assert_membership(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path, incorrect_root),
123 "Merkle read check failed");
124 EXPECT_THROW_WITH_MESSAGE(
125 merkle_check.write(DOM_SEP__MERKLE_HASH, leaf_value, 334, leaf_index, sibling_path, incorrect_root),
126 "Merkle read check failed");
127}
128
129TEST(MerkleCheckSimulationTest, NegativeWrongLeafIndex)
130{
131 // This fake will still perform hashing but is "lightweight" for simulation-only
132 PurePoseidon2 poseidon2 = PurePoseidon2();
133
134 EventEmitter<MerkleCheckEvent> emitter;
135 MerkleCheck merkle_check(poseidon2, emitter);
136
137 FF leaf_value = 333;
138 uint64_t leaf_index = 30;
139 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
140 FF root = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path);
141 uint64_t incorrect_leaf_index = 31;
142 EXPECT_THROW_WITH_MESSAGE(
143 merkle_check.assert_membership(DOM_SEP__MERKLE_HASH, leaf_value, incorrect_leaf_index, sibling_path, root),
144 "Merkle read check failed");
145 EXPECT_THROW_WITH_MESSAGE(
146 merkle_check.write(DOM_SEP__MERKLE_HASH, leaf_value, 334, incorrect_leaf_index, sibling_path, root),
147 "Merkle read check failed");
148}
149
150TEST(MerkleCheckSimulationTest, NegativeWrongSiblingPath)
151{
152 // This fake will still perform hashing but is "lightweight" for simulation-only
153 PurePoseidon2 poseidon2 = PurePoseidon2();
154
155 EventEmitter<MerkleCheckEvent> emitter;
156 MerkleCheck merkle_check(poseidon2, emitter);
157
158 FF leaf_value = 333;
159 uint64_t leaf_index = 30;
160 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
161 FF root = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path);
162 // corrupt the sibling path
163 sibling_path[2] = 11;
164
165 EXPECT_THROW_WITH_MESSAGE(
166 merkle_check.assert_membership(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path, root),
167 "Merkle read check failed");
168 EXPECT_THROW_WITH_MESSAGE(merkle_check.write(DOM_SEP__MERKLE_HASH, leaf_value, 334, leaf_index, sibling_path, root),
169 "Merkle read check failed");
170}
171
172TEST(MerkleCheckSimulationTest, NegativeWrongLeafValue)
173{
174 // This fake will still perform hashing but is "lightweight" for simulation-only
175 PurePoseidon2 poseidon2 = PurePoseidon2();
176
177 EventEmitter<MerkleCheckEvent> emitter;
178 MerkleCheck merkle_check(poseidon2, emitter);
179
180 FF leaf_value = 333;
181 uint64_t leaf_index = 30;
182 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
183 FF root = unconstrained_root_from_path(DOM_SEP__MERKLE_HASH, leaf_value, leaf_index, sibling_path);
184 FF incorrect_leaf_value = 334;
185
186 EXPECT_THROW_WITH_MESSAGE(
187 merkle_check.assert_membership(DOM_SEP__MERKLE_HASH, incorrect_leaf_value, leaf_index, sibling_path, root),
188 "Merkle read check failed");
189 EXPECT_THROW_WITH_MESSAGE(
190 merkle_check.write(DOM_SEP__MERKLE_HASH, incorrect_leaf_value, 334, leaf_index, sibling_path, root),
191 "Merkle read check failed");
192}
193
194} // namespace
195} // namespace bb::avm2::simulation
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessageRegex)
Definition assert.hpp:193
DOM_SEP__MERKLE_HASH
#define DOM_SEP__MERKLE_HASH
Definition aztec_constants.hpp:266
merkle_check
MerkleCheck merkle_check
Definition bc_retrieval.test.cpp:310
bb::avm2::simulation::MerkleCheck::write
FF write(uint64_t domain_separator, const FF &current_value, const FF &new_value, uint64_t leaf_index, std::span< const FF > sibling_path, const FF &current_root) override
Assert the membership of the current leaf value (same logic as assert_membership())....
Definition merkle_check.cpp:78
bb::avm2::simulation::MerkleCheck::assert_membership
void assert_membership(uint64_t domain_separator, const FF &leaf_value, uint64_t leaf_index, std::span< const FF > sibling_path, const FF &root) override
Assert membership of a leaf in a Merkle tree, i.e., verify that the leaf value, leaf index,...
Definition merkle_check.cpp:23
bb::crypto::Poseidon2
Native Poseidon2 hash function implementation.
Definition poseidon2.hpp:22
event_emitter.hpp
merkle_check_event.hpp
bb::avm2::simulation
AVM range check gadget for witness generation.
Definition address_derivation_event.hpp:6
bb::avm2::simulation::unconstrained_root_from_path
FF unconstrained_root_from_path(uint64_t domain_separator, const FF &leaf_value, const uint64_t leaf_index, std::span< const FF > path)
Definition merkle.cpp:12
bb::TEST
TEST(BoomerangMegaCircuitBuilder, BasicCircuit)
Definition graph_description_megacircuitbuilder.test.cpp:22
pure_poseidon2.hpp
merkle_check.hpp