Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
nullifier_memory_tree.test.cpp
Go to the documentation of this file.
1#include "nullifier_memory_tree.hpp"
2#include <gtest/gtest.h>
3
4using namespace bb;
5using namespace bb::crypto::merkle_tree;
6
7using HashPolicy = PedersenHashPolicy;
8using WrappedLeaf = WrappedNullifierLeaf<HashPolicy>;
9
10void print_tree(const size_t depth, std::vector<fr> hashes, std::string const& msg)
11{
12 info("\n", msg);
13 size_t offset = 0;
14 for (size_t i = 0; i < depth; i++) {
15 info("i = ", i);
16 size_t layer_size = (1UL << (depth - i));
17 for (size_t j = 0; j < layer_size; j++) {
18 info("j = ", j, ": ", hashes[offset + j]);
19 }
20 offset += layer_size;
21 }
22}
23
24bool check_hash_path(const fr& root,
25 const fr_hash_path& path,
26 const indexed_nullifier_leaf& leaf_value,
27 const size_t idx)
28{
29 auto current = WrappedLeaf(leaf_value).hash();
30 size_t depth_ = path.size();
31 size_t index = idx;
32 for (size_t i = 0; i < depth_; ++i) {
33 fr left = (index & 1) ? path[i].first : current;
34 fr right = (index & 1) ? current : path[i].second;
35 current = hash_pair_native(left, right);
36 index >>= 1;
37 }
38 return current == root;
39}
40
41TEST(crypto_nullifier_tree, test_nullifier_memory)
42{
43 // Create a depth-3 indexed merkle tree
44 constexpr size_t depth = 3;
45 NullifierMemoryTree<HashPolicy> tree(depth);
46
56 indexed_nullifier_leaf first_leaf = { 0, 1, 1 };
57 EXPECT_EQ(tree.get_leaves().size(), 2);
58 EXPECT_EQ(tree.get_leaves()[0].unwrap(), first_leaf);
59
69 tree.update_element(30);
70 EXPECT_EQ(tree.get_leaves().size(), 3);
71 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
72 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 2, 30 }).hash());
73 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
74
84 tree.update_element(10);
85 EXPECT_EQ(tree.get_leaves().size(), 4);
86 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
87 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
88 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
89 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 2, 30 }).hash());
90
100 tree.update_element(20);
101 EXPECT_EQ(tree.get_leaves().size(), 5);
102 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
103 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
104 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
105 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
106 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
107
108 // Adding the same value must not affect anything
109 tree.update_element(20);
110 EXPECT_EQ(tree.get_leaves().size(), 5);
111 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
112 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
113 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
114 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
115 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
116
126 tree.update_element(50);
127 EXPECT_EQ(tree.get_leaves().size(), 6);
128 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
129 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
130 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 5, 50 }).hash());
131 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
132 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
133 EXPECT_EQ(tree.get_leaves()[5].hash(), WrappedLeaf({ 50, 0, 0 }).hash());
134
135 // Manually compute the node values
136 auto e000 = tree.get_leaves()[0].hash();
137 auto e001 = tree.get_leaves()[1].hash();
138 auto e010 = tree.get_leaves()[2].hash();
139 auto e011 = tree.get_leaves()[3].hash();
140 auto e100 = tree.get_leaves()[4].hash();
141 auto e101 = tree.get_leaves()[5].hash();
142 auto e110 = fr::zero();
143 auto e111 = fr::zero();
144
145 auto e00 = HashPolicy::hash_pair(e000, e001);
146 auto e01 = HashPolicy::hash_pair(e010, e011);
147 auto e10 = HashPolicy::hash_pair(e100, e101);
148 auto e11 = HashPolicy::hash_pair(e110, e111);
149
150 auto e0 = HashPolicy::hash_pair(e00, e01);
151 auto e1 = HashPolicy::hash_pair(e10, e11);
152 auto root = HashPolicy::hash_pair(e0, e1);
153
154 // Check the hash path at index 2 and 3
155 // Note: This merkle proof would also serve as a non-membership proof of values in (10, 20) and (20, 30)
156 fr_hash_path expected = {
157 std::make_pair(e010, e011),
158 std::make_pair(e00, e01),
159 std::make_pair(e0, e1),
160 };
161 EXPECT_EQ(tree.get_hash_path(2), expected);
162 EXPECT_EQ(tree.get_hash_path(3), expected);
163 EXPECT_EQ(tree.root(), root);
164
165 // Check the hash path at index 6 and 7
166 expected = {
167 std::make_pair(e110, e111),
168 std::make_pair(e10, e11),
169 std::make_pair(e0, e1),
170 };
171 EXPECT_EQ(tree.get_hash_path(6), expected);
172 EXPECT_EQ(tree.get_hash_path(7), expected);
173}
174
175TEST(crypto_nullifier_tree, test_nullifier_memory_appending_zero)
176{
177 // Create a depth-3 indexed merkle tree
178 constexpr size_t depth = 3;
179 NullifierMemoryTree<HashPolicy> tree(depth);
180
190 WrappedLeaf first_leaf = WrappedLeaf({ 0, 1, 1 });
191 EXPECT_EQ(tree.get_leaves().size(), 2);
192 EXPECT_EQ(tree.get_leaves()[0], first_leaf);
193
203 tree.update_element(30);
204 EXPECT_EQ(tree.get_leaves().size(), 3);
205 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
206 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 2, 30 }).hash());
207 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
208
218 tree.update_element(10);
219 EXPECT_EQ(tree.get_leaves().size(), 4);
220 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
221 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
222 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
223 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 2, 30 }).hash());
224
234 tree.update_element(20);
235 EXPECT_EQ(tree.get_leaves().size(), 5);
236 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
237 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
238 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
239 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
240 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
241
242 // Adding the same value must not affect anything
243 tree.update_element(20);
244 EXPECT_EQ(tree.get_leaves().size(), 5);
245 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
246 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
247 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
248 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
249 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
250
260 tree.update_element(0);
261 EXPECT_EQ(tree.get_leaves().size(), 6);
262 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
263 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
264 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
265 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
266 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
267 EXPECT_EQ(tree.get_leaves()[5].hash(), WrappedLeaf::zero().hash());
268
269 /*
270 * Add new value 0:
271 *
272 * index 0 1 2 3 4 5 6 7
273 * ---------------------------------------------------------------------
274 * val 0 30 10 20 0 0 0 0
275 * nextIdx 2 0 3 1 0 0 0 0
276 * nextVal 10 0 20 30 0 0 0 0
277 */
278 tree.update_element(0);
279 EXPECT_EQ(tree.get_leaves().size(), 7);
280 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
281 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
282 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 0, 0 }).hash());
283 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
284 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
285 EXPECT_EQ(tree.get_leaves()[5].hash(), WrappedLeaf::zero().hash());
286 EXPECT_EQ(tree.get_leaves()[6].hash(), WrappedLeaf::zero().hash());
287
297 tree.update_element(50);
298 EXPECT_EQ(tree.get_leaves().size(), 8);
299 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf({ 0, 1, 1 }).hash());
300 EXPECT_EQ(tree.get_leaves()[1].hash(), WrappedLeaf({ 1, 3, 10 }).hash());
301 EXPECT_EQ(tree.get_leaves()[2].hash(), WrappedLeaf({ 30, 7, 50 }).hash());
302 EXPECT_EQ(tree.get_leaves()[3].hash(), WrappedLeaf({ 10, 4, 20 }).hash());
303 EXPECT_EQ(tree.get_leaves()[4].hash(), WrappedLeaf({ 20, 2, 30 }).hash());
304 EXPECT_EQ(tree.get_leaf(5).hash(), WrappedLeaf::zero().hash());
305 EXPECT_EQ(tree.get_leaf(6).hash(), WrappedLeaf::zero().hash());
306 EXPECT_EQ(tree.get_leaf(7).hash(), WrappedLeaf({ 50, 0, 0 }).hash());
307 // EXPECT_EQ(tree.get_leaf(7).hash(), first_leaf.hash());
308
309 // Manually compute the node values
310 auto e000 = tree.get_leaf(0).hash();
311 auto e001 = tree.get_leaf(1).hash();
312 auto e010 = tree.get_leaf(2).hash();
313 auto e011 = tree.get_leaf(3).hash();
314 auto e100 = tree.get_leaf(4).hash();
315 auto e101 = tree.get_leaf(5).hash();
316 auto e110 = tree.get_leaf(6).hash();
317 auto e111 = tree.get_leaf(7).hash();
318
319 auto e00 = HashPolicy::hash_pair(e000, e001);
320 auto e01 = HashPolicy::hash_pair(e010, e011);
321 auto e10 = HashPolicy::hash_pair(e100, e101);
322 auto e11 = HashPolicy::hash_pair(e110, e111);
323
324 auto e0 = HashPolicy::hash_pair(e00, e01);
325 auto e1 = HashPolicy::hash_pair(e10, e11);
326 auto root = HashPolicy::hash_pair(e0, e1);
327
328 fr_hash_path expected1 = {
329 std::make_pair(e000, e001),
330 std::make_pair(e00, e01),
331 std::make_pair(e0, e1),
332 };
333 EXPECT_EQ(tree.get_hash_path(0), expected1);
334 EXPECT_EQ(tree.get_hash_path(1), expected1);
335
336 // Check the hash path at index 2 and 3
337 // Note: This merkle proof would also serve as a non-membership proof of values in (10, 20) and (20, 30)
338 fr_hash_path expected = {
339 std::make_pair(e010, e011),
340 std::make_pair(e00, e01),
341 std::make_pair(e0, e1),
342 };
343 EXPECT_EQ(tree.get_hash_path(2), expected);
344 EXPECT_EQ(tree.get_hash_path(3), expected);
345 EXPECT_EQ(tree.root(), root);
346
347 // Check the hash path at index 6 and 7
348 expected = {
349 std::make_pair(e110, e111),
350 std::make_pair(e10, e11),
351 std::make_pair(e0, e1),
352 };
353 EXPECT_EQ(tree.get_hash_path(6), expected);
354 EXPECT_EQ(tree.get_hash_path(7), expected);
355}
356TEST(crypto_nullifier_tree, test_nullifier_tree)
357{
358 // Create a depth-8 indexed merkle tree
359 constexpr size_t depth = 8;
360 NullifierMemoryTree<HashPolicy> tree(depth);
361
362 EXPECT_EQ(tree.get_leaves().size(), 2); // prefill is 2
363 EXPECT_EQ(tree.get_leaves()[0].hash(), WrappedLeaf(indexed_nullifier_leaf{ 0, 1, 1 }).hash());
364
365 // Add 20 random values to the tree
366 for (size_t i = 0; i < 20; i++) {
367 auto value = fr::random_element();
368 tree.update_element(value);
369 }
370
371 auto abs_diff = [](uint256_t a, uint256_t b) {
372 if (a > b) {
373 return (a - b);
374 } else {
375 return (b - a);
376 }
377 };
378
379 // Check if a new random value is not a member of this tree.
380 fr new_member = fr::random_element();
381 const auto& leaves = tree.get_leaves();
382 std::vector<uint256_t> differences;
383 for (size_t i = 0; i < leaves.size(); i++) {
384 uint256_t diff_hi =
385 abs_diff(uint256_t(new_member), uint256_t(leaves[i].has_value() ? leaves[i].unwrap().value : 0));
386 uint256_t diff_lo =
387 abs_diff(uint256_t(new_member), uint256_t(leaves[i].has_value() ? leaves[i].unwrap().nextValue : 0));
388 differences.push_back(diff_hi + diff_lo);
389 }
390 auto it = std::min_element(differences.begin(), differences.end());
391 auto index = static_cast<size_t>(it - differences.begin());
392
393 // Merkle proof at `index` proves non-membership of `new_member`
394 auto hash_path = tree.get_hash_path(index);
395 EXPECT_TRUE(check_hash_path(tree.root(), hash_path, leaves[index].unwrap(), index));
396}
bb::crypto::merkle_tree::MemoryTree::get_hash_path
fr_hash_path get_hash_path(size_t index) const
Definition memory_tree.hpp:83
bb::crypto::merkle_tree::MemoryTree::root
fr root() const
Definition memory_tree.hpp:40
bb::crypto::merkle_tree::NullifierMemoryTree
Definition nullifier_memory_tree.hpp:74
bb::crypto::merkle_tree::NullifierMemoryTree::get_leaf
const WrappedNullifierLeaf< HashingPolicy > get_leaf(size_t index)
Definition nullifier_memory_tree.hpp:87
bb::crypto::merkle_tree::NullifierMemoryTree::get_leaves
const std::vector< WrappedNullifierLeaf< HashingPolicy > > & get_leaves()
Definition nullifier_memory_tree.hpp:92
bb::crypto::merkle_tree::NullifierMemoryTree::update_element
fr_sibling_path update_element(fr const &value)
Definition nullifier_memory_tree.hpp:138
bb::crypto::merkle_tree::WrappedNullifierLeaf
Wrapper for the Nullifier leaf class that allows for 0 values.
Definition nullifier_leaf.hpp:42
bb::crypto::merkle_tree::WrappedNullifierLeaf::zero
static WrappedNullifierLeaf< HashingPolicy > zero()
Generate a zero leaf (call the constructor with no arguments)
Definition nullifier_leaf.hpp:93
bb::numeric::uint256_t
Definition uint256.hpp:32
info
void info(Args... args)
Definition log.hpp:70
a
FF a
Definition field_gt.test.cpp:51
b
FF b
Definition field_gt.test.cpp:52
offset
ssize_t offset
Definition engine.cpp:36
hash
void hash(State &state) noexcept
Definition merkle_tree.bench.cpp:28
bb::crypto::merkle_tree
Definition content_addressed_append_only_tree.hpp:33
bb::crypto::merkle_tree::hash_path
std::vector< std::pair< bb::stdlib::field_t< Ctx >, bb::stdlib::field_t< Ctx > > > hash_path
Definition hash_path.hpp:17
bb::crypto::merkle_tree::print_tree
void print_tree(const uint32_t depth, std::vector< fr > hashes, std::string const &msg)
Definition fixtures.hpp:49
bb::crypto::merkle_tree::fr_hash_path
std::vector< std::pair< fr, fr > > fr_hash_path
Definition hash_path.hpp:15
bb::crypto::merkle_tree::hash_pair_native
bb::fr hash_pair_native(bb::fr const &lhs, bb::fr const &rhs)
Definition hash.hpp:40
bb
Entry point for Barretenberg command-line interface.
Definition acir_format_getters.cpp:6
bb::TEST
TEST(MegaCircuitBuilder, CopyConstructor)
Definition mega_circuit_builder.test.cpp:14
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
nullifier_memory_tree.hpp
check_hash_path
bool check_hash_path(const fr &root, const fr_hash_path &path, const indexed_nullifier_leaf &leaf_value, const size_t idx)
Definition nullifier_memory_tree.test.cpp:24
WrappedLeaf
WrappedNullifierLeaf< HashPolicy > WrappedLeaf
Definition nullifier_memory_tree.test.cpp:8
value
FF value
Definition public_data_tree.test.cpp:96
bb::crypto::merkle_tree::PedersenHashPolicy
Definition hash.hpp:21
bb::crypto::merkle_tree::PedersenHashPolicy::hash_pair
static fr hash_pair(const fr &lhs, const fr &rhs)
Definition hash.hpp:24
bb::crypto::merkle_tree::Poseidon2HashPolicy
Definition hash.hpp:29
bb::crypto::merkle_tree::indexed_nullifier_leaf
Definition nullifier_leaf.hpp:15
bb::field< Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:665
bb::field< Bn254FrParams >::zero
static constexpr field zero()
Definition field_declarations.hpp:240