content_addressed_append_only_tree.test.cpp File Reference

#include "barretenberg/crypto/merkle_tree/append_only_tree/content_addressed_append_only_tree.hpp"
#include "../fixtures.hpp"
#include "../memory_tree.hpp"
#include "../test_fixtures.hpp"
#include "barretenberg/common/streams.hpp"
#include "barretenberg/common/test.hpp"
#include "barretenberg/common/thread_pool.hpp"
#include "barretenberg/crypto/merkle_tree/hash.hpp"
#include "barretenberg/crypto/merkle_tree/hash_path.hpp"
#include "barretenberg/crypto/merkle_tree/lmdb_store/lmdb_tree_store.hpp"
#include "barretenberg/crypto/merkle_tree/node_store/array_store.hpp"
#include "barretenberg/crypto/merkle_tree/node_store/cached_content_addressed_tree_store.hpp"
#include "barretenberg/crypto/merkle_tree/response.hpp"
#include "barretenberg/crypto/merkle_tree/signal.hpp"
#include "barretenberg/crypto/merkle_tree/types.hpp"
#include "barretenberg/ecc/curves/bn254/fr.hpp"
#include "barretenberg/lmdblib/lmdb_environment.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <exception>
#include <filesystem>
#include <memory>
#include <optional>
#include <stdexcept>
#include <vector>

Go to the source code of this file.

Classes
class	PersistedContentAddressedAppendOnlyTreeTest

Typedefs
using	Store = ContentAddressedCachedTreeStore< bb::fr >
using	TreeType = ContentAddressedAppendOnlyTree< Store, Poseidon2HashPolicy >
using	LMDBStoreType = LMDBTreeStore

Functions
void	check_size (TreeType &tree, index_t expected_size, bool includeUncommitted=true)
void	check_finalized_block_height (TreeType &tree, block_number_t expected_finalized_block)
void	check_block_height (TreeType &tree, index_t expected_block_height)
void	check_root (TreeType &tree, fr expected_root, bool includeUncommitted=true)
void	check_sibling_path (TreeType &tree, index_t index, fr_sibling_path expected_sibling_path, bool includeUncommitted=true, bool expected_result=true)
void	check_sibling_path_by_value (TreeType &tree, fr value, fr_sibling_path expected_sibling_path, index_t expected_index, bool includeUncommitted=true, bool expected_result=true)
void	check_historic_sibling_path (TreeType &tree, index_t index, fr_sibling_path expected_sibling_path, block_number_t blockNumber, bool expected_success=true)
void	check_historic_sibling_path_by_value (TreeType &tree, fr value, fr_sibling_path expected_sibling_path, index_t expected_index, block_number_t blockNumber, bool expected_success=true)
void	commit_tree (TreeType &tree, bool expected_success=true)
void	remove_historic_block (TreeType &tree, const block_number_t &blockNumber, bool expected_success=true)
void	unwind_block (TreeType &tree, const block_number_t &blockNumber, bool expected_success=true)
void	add_value (TreeType &tree, const fr &value)
void	add_values (TreeType &tree, const std::vector< fr > &values)
void	finalize_block (TreeType &tree, const block_number_t &blockNumber, bool expected_success=true)
void	check_leaf (TreeType &tree, const fr &leaf, index_t leaf_index, bool expected_success, bool expected_match=true, bool includeUncommitted=true)
void	check_historic_leaf (TreeType &tree, const block_number_t &blockNumber, const fr &leaf, index_t leaf_index, bool expected_success, bool expected_match=true, bool includeUncommitted=true)
void	check_sibling_path (fr expected_root, fr node, index_t index, fr_sibling_path sibling_path)
void	get_blocks_for_indices (TreeType &tree, const std::vector< index_t > &indices, std::vector< std::optional< block_number_t > > &blockNumbers)
void	get_blocks_for_indices (TreeType &tree, const block_number_t &blockNumber, const std::vector< index_t > &indices, std::vector< std::optional< block_number_t > > &blockNumbers)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_create)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, committing_with_no_changes_should_succeed)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_only_recreate_with_same_name_and_depth)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_add_value_and_get_sibling_path)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, reports_an_error_if_tree_is_overfilled)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, reports_an_error_if_index_out_of_tree_range)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, errors_are_caught_and_handled)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_commit_and_restore)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, test_size)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, test_find_leaf_index)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_add_multiple_values)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_add_multiple_values_in_a_batch)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_pad_with_zero_leaves)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_not_retrieve_zero_leaf_indices)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_commit_multiple_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_add_varying_size_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_retrieve_historic_sibling_paths)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, retrieves_historic_leaves)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, test_find_historic_leaf_index)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_be_filled)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_add_single_whilst_reading)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_get_inserted_leaves)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, returns_sibling_path)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_create_images_at_historic_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_remove_historic_block_data)
void	test_unwind (std::string directory, std::string name, uint64_t mapSize, uint64_t maxReaders, uint32_t depth, uint32_t blockSize, uint32_t numBlocks, uint32_t numBlocksToUnwind, std::vector< fr > values)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_unwind_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_unwind_all_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_unwind_initial_blocks_that_are_full_of_zeros)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_sync_and_unwind_large_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_commit_and_unwind_empty_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_commit_and_remove_historic_empty_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_retrieve_block_numbers_by_index)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_advance_finalized_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_finalize_multiple_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_not_finalize_block_beyond_pending_chain)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_not_fork_from_unwound_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_not_fork_from_expired_historical_blocks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_fork_from_block_zero_when_not_latest)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_not_unwind_finalized_block)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_not_historically_remove_finalized_block)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_checkpoint_and_revert_forks)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_commit_all_checkpoints)
	TEST_F (PersistedContentAddressedAppendOnlyTreeTest, can_revert_all_checkpoints)

Typedef Documentation

LMDBStoreType

using LMDBStoreType = LMDBTreeStore

Definition at line 36 of file content_addressed_append_only_tree.test.cpp.

Store

using Store = ContentAddressedCachedTreeStore<bb::fr>

Definition at line 34 of file content_addressed_append_only_tree.test.cpp.

TreeType

using TreeType = ContentAddressedAppendOnlyTree<Store, Poseidon2HashPolicy>

Definition at line 35 of file content_addressed_append_only_tree.test.cpp.

Function Documentation

add_value()

void add_value	(	TreeType &	tree,
		const fr &	value
	)

Definition at line 218 of file content_addressed_append_only_tree.test.cpp.

add_values()

void add_values	(	TreeType &	tree,
		const std::vector< fr > &	values
	)

Definition at line 230 of file content_addressed_append_only_tree.test.cpp.

check_block_height()

void check_block_height	(	TreeType &	tree,
		index_t	expected_block_height
	)

Definition at line 83 of file content_addressed_append_only_tree.test.cpp.

check_finalized_block_height()

void check_finalized_block_height	(	TreeType &	tree,
		block_number_t	expected_finalized_block
	)

Definition at line 71 of file content_addressed_append_only_tree.test.cpp.

check_historic_leaf()

void check_historic_leaf	(	TreeType &	tree,
		const block_number_t &	blockNumber,
		const fr &	leaf,
		index_t	leaf_index,
		bool	expected_success,
		bool	expected_match = true,
		bool	includeUncommitted = true
	)

Definition at line 274 of file content_addressed_append_only_tree.test.cpp.

check_historic_sibling_path()

void check_historic_sibling_path	(	TreeType &	tree,
		index_t	index,
		fr_sibling_path	expected_sibling_path,
		block_number_t	blockNumber,
		bool	expected_success = true
	)

Definition at line 146 of file content_addressed_append_only_tree.test.cpp.

check_historic_sibling_path_by_value()

void check_historic_sibling_path_by_value	(	TreeType &	tree,
		fr	value,
		fr_sibling_path	expected_sibling_path,
		index_t	expected_index,
		block_number_t	blockNumber,
		bool	expected_success = true
	)

Definition at line 164 of file content_addressed_append_only_tree.test.cpp.

check_leaf()

void check_leaf	(	TreeType &	tree,
		const fr &	leaf,
		index_t	leaf_index,
		bool	expected_success,
		bool	expected_match = true,
		bool	includeUncommitted = true
	)

Definition at line 256 of file content_addressed_append_only_tree.test.cpp.

check_root()

void check_root	(	TreeType &	tree,
		fr	expected_root,
		bool	includeUncommitted = true
	)

Definition at line 95 of file content_addressed_append_only_tree.test.cpp.

check_sibling_path() [1/2]

void check_sibling_path	(	fr	expected_root,
		fr	node,
		index_t	index,
		fr_sibling_path	sibling_path
	)

Definition at line 293 of file content_addressed_append_only_tree.test.cpp.

check_sibling_path() [2/2]

void check_sibling_path	(	TreeType &	tree,
		index_t	index,
		fr_sibling_path	expected_sibling_path,
		bool	includeUncommitted = true,
		bool	expected_result = true
	)

Definition at line 107 of file content_addressed_append_only_tree.test.cpp.

check_sibling_path_by_value()

void check_sibling_path_by_value	(	TreeType &	tree,
		fr	value,
		fr_sibling_path	expected_sibling_path,
		index_t	expected_index,
		bool	includeUncommitted = true,
		bool	expected_result = true
	)

Definition at line 125 of file content_addressed_append_only_tree.test.cpp.

check_size()

void check_size	(	TreeType &	tree,
		index_t	expected_size,
		bool	includeUncommitted = true
	)

Definition at line 59 of file content_addressed_append_only_tree.test.cpp.

commit_tree()

void commit_tree	(	TreeType &	tree,
		bool	expected_success = true
	)

Definition at line 185 of file content_addressed_append_only_tree.test.cpp.

finalize_block()

void finalize_block	(	TreeType &	tree,
		const block_number_t &	blockNumber,
		bool	expected_success = true
	)

Definition at line 242 of file content_addressed_append_only_tree.test.cpp.

get_blocks_for_indices() [1/2]

void get_blocks_for_indices	(	TreeType &	tree,
		const block_number_t &	blockNumber,
		const std::vector< index_t > &	indices,
		std::vector< std::optional< block_number_t > > &	blockNumbers
	)

Definition at line 326 of file content_addressed_append_only_tree.test.cpp.

get_blocks_for_indices() [2/2]

void get_blocks_for_indices	(	TreeType &	tree,
		const std::vector< index_t > &	indices,
		std::vector< std::optional< block_number_t > > &	blockNumbers
	)

Definition at line 314 of file content_addressed_append_only_tree.test.cpp.

remove_historic_block()

void remove_historic_block	(	TreeType &	tree,
		const block_number_t &	blockNumber,
		bool	expected_success = true
	)

Definition at line 196 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [1/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_add_multiple_values
	)

Definition at line 775 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [2/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_add_multiple_values_in_a_batch
	)

Definition at line 798 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [3/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_add_single_whilst_reading
	)

Definition at line 1102 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [4/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_add_value_and_get_sibling_path
	)

Definition at line 405 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [5/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_add_varying_size_blocks
	)

Definition at line 911 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [6/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_advance_finalized_blocks
	)

Definition at line 1791 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [7/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_be_filled
	)

Definition at line 1079 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [8/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_checkpoint_and_revert_forks
	)

Definition at line 2060 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [9/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_commit_all_checkpoints
	)

Definition at line 2169 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [10/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_commit_and_remove_historic_empty_blocks
	)

Definition at line 1634 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [11/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_commit_and_restore
	)

Definition at line 605 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [12/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_commit_and_unwind_empty_blocks
	)

Definition at line 1572 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [13/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_commit_multiple_blocks
	)

Definition at line 874 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [14/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_create
	)

Definition at line 339 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [15/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_create_images_at_historic_blocks
	)

Definition at line 1209 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [16/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_finalize_multiple_blocks
	)

Definition at line 1835 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [17/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_fork_from_block_zero_when_not_latest
	)

Definition at line 1952 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [18/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_get_inserted_leaves
	)

Definition at line 1145 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [19/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_not_finalize_block_beyond_pending_chain
	)

Definition at line 1868 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [20/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_not_fork_from_expired_historical_blocks
	)

Definition at line 1930 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [21/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_not_fork_from_unwound_blocks
	)

Definition at line 1908 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [22/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_not_historically_remove_finalized_block
	)

Definition at line 2022 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [23/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_not_retrieve_zero_leaf_indices
	)

Definition at line 849 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [24/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_not_unwind_finalized_block
	)

Definition at line 1984 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [25/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_only_recreate_with_same_name_and_depth
	)

Definition at line 394 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [26/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_pad_with_zero_leaves
	)

Definition at line 823 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [27/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_remove_historic_block_data
	)

Definition at line 1302 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [28/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_retrieve_block_numbers_by_index
	)

Definition at line 1696 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [29/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_retrieve_historic_sibling_paths
	)

Definition at line 949 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [30/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_revert_all_checkpoints
	)

Definition at line 2221 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [31/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_sync_and_unwind_large_blocks
	)

Definition at line 1557 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [32/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_unwind_all_blocks
	)

Definition at line 1521 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [33/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_unwind_blocks
	)

Definition at line 1515 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [34/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		can_unwind_initial_blocks_that_are_full_of_zeros
	)

Definition at line 1529 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [35/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		committing_with_no_changes_should_succeed
	)

Definition at line 355 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [36/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		errors_are_caught_and_handled
	)

Definition at line 501 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [37/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		reports_an_error_if_index_out_of_tree_range
	)

Definition at line 458 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [38/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		reports_an_error_if_tree_is_overfilled
	)

Definition at line 428 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [39/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		retrieves_historic_leaves
	)

Definition at line 1000 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [40/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		returns_sibling_path
	)

Definition at line 1166 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [41/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		test_find_historic_leaf_index
	)

Definition at line 1037 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [42/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		test_find_leaf_index
	)

Definition at line 703 of file content_addressed_append_only_tree.test.cpp.

TEST_F() [43/43]

TEST_F	(	PersistedContentAddressedAppendOnlyTreeTest	,
		test_size
	)

Definition at line 675 of file content_addressed_append_only_tree.test.cpp.

test_unwind()

void test_unwind	(	std::string	directory,
		std::string	name,
		uint64_t	mapSize,
		uint64_t	maxReaders,
		uint32_t	depth,
		uint32_t	blockSize,
		uint32_t	numBlocks,
		uint32_t	numBlocksToUnwind,
		std::vector< fr >	values
	)

Definition at line 1390 of file content_addressed_append_only_tree.test.cpp.

unwind_block()

void unwind_block	(	TreeType &	tree,
		const block_number_t &	blockNumber,
		bool	expected_success = true
	)

Definition at line 207 of file content_addressed_append_only_tree.test.cpp.