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(leaf_value, leaf_index, sibling_path);
30
31 merkle_check.assert_membership(leaf_value, leaf_index, sibling_path, root);
32 MerkleCheckEvent expect_event = {
33 .leaf_value = leaf_value,
34 .leaf_index = leaf_index,
35 .sibling_path = sibling_path,
36 .root = root,
37 };
38
39 FF leaf_value2 = 334;
40 uint64_t leaf_index2 = 31;
41 std::vector<FF> sibling_path2 = { 10, 2, 30, 4, 50, 7 };
42 FF root2 = unconstrained_root_from_path(leaf_value2, leaf_index2, sibling_path2);
43 merkle_check.assert_membership(leaf_value2, leaf_index2, sibling_path2, root2);
44 MerkleCheckEvent expect_event2 = {
45 .leaf_value = leaf_value2,
46 .leaf_index = leaf_index2,
47 .sibling_path = sibling_path2,
48 .root = root2,
49 };
50
51 EXPECT_THAT(emitter.dump_events(), ElementsAre(expect_event, expect_event2));
52}
53
54TEST(MerkleCheckSimulationTest, Write)
55{
56 // This fake will still perform hashing but is "lightweight" for simulation-only
57 PurePoseidon2 poseidon2 = PurePoseidon2();
58
59 EventEmitter<MerkleCheckEvent> emitter;
60 MerkleCheck merkle_check(poseidon2, emitter);
61
62 FF current_value = 333;
63 FF new_value = 334;
64 uint64_t leaf_index = 30;
65 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
66 FF current_root = unconstrained_root_from_path(current_value, leaf_index, sibling_path);
67 FF expected_new_root = unconstrained_root_from_path(new_value, leaf_index, sibling_path);
68
69 MerkleCheckEvent expect_event = {
70 .leaf_value = current_value,
71 .new_leaf_value = new_value,
72 .leaf_index = leaf_index,
73 .sibling_path = sibling_path,
74 .root = current_root,
75 .new_root = expected_new_root,
76 };
77
78 FF new_root = merkle_check.write(current_value, new_value, leaf_index, sibling_path, current_root);
79
80 EXPECT_EQ(new_root, expected_new_root);
81 EXPECT_THAT(emitter.dump_events(), ElementsAre(expect_event));
82}
83
84TEST(MerkleCheckSimulationTest, NegativeBadFinalIndex)
85{
86 // This fake will still perform hashing but is "lightweight" for simulation-only
87 PurePoseidon2 poseidon2 = PurePoseidon2();
88
89 EventEmitter<MerkleCheckEvent> emitter;
90 MerkleCheck merkle_check(poseidon2, emitter);
91
92 FF leaf_value = 333;
93 uint64_t leaf_index = 64; // too large! halving it 5 times results in 2!
94 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
95 FF root = unconstrained_root_from_path(leaf_value, leaf_index, sibling_path);
96
97 EXPECT_THROW_WITH_MESSAGE(merkle_check.assert_membership(leaf_value, leaf_index, sibling_path, root),
98 "Merkle check's final node index must be 0");
99 EXPECT_THROW_WITH_MESSAGE(merkle_check.write(leaf_value, 334, leaf_index, sibling_path, root),
100 "Merkle check's final node index must be 0");
101}
102
103TEST(MerkleCheckSimulationTest, NegativeWrongRoot)
104{
105 // This fake will still perform hashing but is "lightweight" for simulation-only
106 PurePoseidon2 poseidon2 = PurePoseidon2();
107
108 EventEmitter<MerkleCheckEvent> emitter;
109 MerkleCheck merkle_check(poseidon2, emitter);
110
111 FF leaf_value = 333;
112 uint64_t leaf_index = 30;
113 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
114 FF incorrect_root = 66;
115
116 EXPECT_THROW_WITH_MESSAGE(merkle_check.assert_membership(leaf_value, leaf_index, sibling_path, incorrect_root),
117 "Merkle read check failed");
118 EXPECT_THROW_WITH_MESSAGE(merkle_check.write(leaf_value, 334, leaf_index, sibling_path, incorrect_root),
119 "Merkle read check failed");
120}
121
122TEST(MerkleCheckSimulationTest, NegativeWrongLeafIndex)
123{
124 // This fake will still perform hashing but is "lightweight" for simulation-only
125 PurePoseidon2 poseidon2 = PurePoseidon2();
126
127 EventEmitter<MerkleCheckEvent> emitter;
128 MerkleCheck merkle_check(poseidon2, emitter);
129
130 FF leaf_value = 333;
131 uint64_t leaf_index = 30;
132 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
133 FF root = unconstrained_root_from_path(leaf_value, leaf_index, sibling_path);
134 uint64_t incorrect_leaf_index = 31;
135 EXPECT_THROW_WITH_MESSAGE(merkle_check.assert_membership(leaf_value, incorrect_leaf_index, sibling_path, root),
136 "Merkle read check failed");
137 EXPECT_THROW_WITH_MESSAGE(merkle_check.write(leaf_value, 334, incorrect_leaf_index, sibling_path, root),
138 "Merkle read check failed");
139}
140
141TEST(MerkleCheckSimulationTest, NegativeWrongSiblingPath)
142{
143 // This fake will still perform hashing but is "lightweight" for simulation-only
144 PurePoseidon2 poseidon2 = PurePoseidon2();
145
146 EventEmitter<MerkleCheckEvent> emitter;
147 MerkleCheck merkle_check(poseidon2, emitter);
148
149 FF leaf_value = 333;
150 uint64_t leaf_index = 30;
151 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
152 FF root = unconstrained_root_from_path(leaf_value, leaf_index, sibling_path);
153 // corrupt the sibling path
154 sibling_path[2] = 11;
155
156 EXPECT_THROW_WITH_MESSAGE(merkle_check.assert_membership(leaf_value, leaf_index, sibling_path, root),
157 "Merkle read check failed");
158 EXPECT_THROW_WITH_MESSAGE(merkle_check.write(leaf_value, 334, leaf_index, sibling_path, root),
159 "Merkle read check failed");
160}
161
162TEST(MerkleCheckSimulationTest, NegativeWrongLeafValue)
163{
164 // This fake will still perform hashing but is "lightweight" for simulation-only
165 PurePoseidon2 poseidon2 = PurePoseidon2();
166
167 EventEmitter<MerkleCheckEvent> emitter;
168 MerkleCheck merkle_check(poseidon2, emitter);
169
170 FF leaf_value = 333;
171 uint64_t leaf_index = 30;
172 std::vector<FF> sibling_path = { 10, 2, 30, 4, 50, 6 };
173 FF root = unconstrained_root_from_path(leaf_value, leaf_index, sibling_path);
174 FF incorrect_leaf_value = 334;
175
176 EXPECT_THROW_WITH_MESSAGE(merkle_check.assert_membership(incorrect_leaf_value, leaf_index, sibling_path, root),
177 "Merkle read check failed");
178 EXPECT_THROW_WITH_MESSAGE(merkle_check.write(incorrect_leaf_value, 334, leaf_index, sibling_path, root),
179 "Merkle read check failed");
180}
181
182} // namespace
183} // namespace bb::avm2::simulation
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessageRegex)
Definition assert.hpp:193
merkle_check
MerkleCheck merkle_check
Definition bc_retrieval.test.cpp:307
bb::avm2::simulation::MerkleCheck::write
FF write(const FF &current_value, const FF &new_value, const 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:73
bb::avm2::simulation::MerkleCheck::assert_membership
void assert_membership(const FF &leaf_value, const 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:22
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(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