Classes
struct	AddDataResponse

struct	AddIndexedDataResponse

struct	AddIndexedDataSequentiallyResponse

class	ArrayStore
	A very basic 2-d array for use as a backing store for merkle trees. Can store up to 'indices' nodes per row and 'levels' rows. More...

struct	BlockForIndexResponse

struct	BlockIndexPayload

struct	BlockPayload

struct	CommitResponse

class	ContentAddressedAppendOnlyTree
	Implements a simple append-only merkle tree All methods are asynchronous unless specified as otherwise Accepts template arguments of the type of store backing the tree and the hashing policy Accepts the store as an argument on construction as well as a thread pool instance Asynchronous methods are exeucted on the provided thread pool. More...

class	ContentAddressedCache

class	ContentAddressedCachedTreeStore
	Serves as a key-value node store for merkle trees. Caches all changes in memory before persisting them during a 'commit' operation. Manages the persisted store by seperating the key spaces as follows: 1 byte key of 0: Tree meta data 8 byte integers: The index of each leaf to the value of that leaf 16 byte integers: Nodes in the tree, key value = ((2 ^ level) + index - 1) 32 bytes integers: The value of the leaf (32 bytes) to the set of indices where the leaf exists in the tree. More...

class	ContentAddressedIndexedTree
	Implements a parallelized batch insertion indexed tree Accepts template argument of the type of store backing the tree, the type of store containing the leaves and the hashing policy All public methods are asynchronous unless marked otherwise. More...

struct	FindLeafIndexResponse

struct	FindLeafPathResponse

struct	GetIndexedLeafResponse

struct	GetLeafResponse

struct	GetLowIndexedLeafResponse

struct	GetSiblingPathResponse

struct	indexed_nullifier_leaf

struct	IndexedLeaf

struct	LeafUpdateWitnessData

class	LMDBTreeStore

class	MemoryStore

class	MemoryTree

class	MerkleTree

class	MockPersistedStore

class	MockTransaction

struct	NodePayload

struct	NullifierLeafValue

class	NullifierMemoryTree

class	NullifierTree

struct	PedersenHashPolicy

struct	Poseidon2HashPolicy

struct	PublicDataLeafValue

struct	RemoveHistoricResponse

struct	RequestContext

struct	Response

struct	SiblingPathAndIndex

class	Signal
	Used in parallel insertions in the the IndexedTree. Workers signal to other following workes as they move up the level of the tree. More...

struct	TreeDBStats

struct	TreeMeta

struct	TreeMetaResponse

struct	TypedResponse

struct	UnwindResponse

class	WrappedNullifierLeaf
	Wrapper for the Nullifier leaf class that allows for 0 values. More...

Typedefs
using	ThreadPoolPtr = std::shared_ptr< ThreadPool >

using	fr_hash_path = std::vector< std::pair< fr, fr > >

using	fr_sibling_path = std::vector< fr >

template<typename Ctx >
using	hash_path = std::vector< std::pair< bb::stdlib::field_t< Ctx >, bb::stdlib::field_t< Ctx > > >

using	IndexedNullifierLeafType = IndexedLeaf< NullifierLeafValue >

using	IndexedPublicDataLeafType = IndexedLeaf< PublicDataLeafValue >

using	index_t = uint64_t

using	block_number_t = uint32_t

using	LeafIndexKeyType = uint64_t

using	BlockMetaKeyType = uint64_t

using	FrKeyType = uint256_t

using	MetaKeyType = uint8_t

Functions
std::string	random_string ()

std::string	random_temp_directory ()

void	print_tree (const uint32_t depth, std::vector< fr > hashes, std::string const &msg)

ThreadPoolPtr	make_thread_pool (uint64_t numThreads)

void	print_store_data (LMDBTreeStore::SharedPtr db, std::ostream &os)

bb::fr	hash_pair_native (bb::fr const &lhs, bb::fr const &rhs)

bb::fr	hash_native (std::vector< bb::fr > const &inputs)

bb::fr	compute_tree_root_native (std::vector< bb::fr > const &input)

std::vector< bb::fr >	compute_tree_native (std::vector< bb::fr > const &input)

fr_hash_path	get_new_hash_path (fr_hash_path const &old_path, uint128_t index, fr const &value)

fr_hash_path	get_random_hash_path (size_t const &tree_depth)

template<typename Ctx >
hash_path< Ctx >	create_witness_hash_path (Ctx &ctx, fr_hash_path const &input)

fr	get_hash_path_root (fr_hash_path const &input)

fr	zero_hash_at_height (size_t height)

IndexedNullifierLeafType	create_indexed_nullifier_leaf (const fr &value, index_t nextIndex, const fr &nextValue)

IndexedPublicDataLeafType	create_indexed_public_data_leaf (const fr &slot, const fr &value, index_t nextIndex, const fr &nextValue)

int	fr_key_cmp (const MDB_val a, const MDB_val b)

int	block_key_cmp (const MDB_val a, const MDB_val b)

int	index_key_cmp (const MDB_val a, const MDB_val b)

std::ostream &	operator<< (std::ostream &os, const BlockPayload &block)

template<typename T >
bool	bit_set (T const &index, size_t i)

std::ostream &	operator<< (std::ostream &os, const TreeMeta &meta)

template<typename HashingPolicy >
std::pair< size_t, bool >	find_closest_leaf (std::vector< WrappedNullifierLeaf< HashingPolicy > > const &leaves_, fr const &new_value)

template<typename ResponseType >
void	execute_and_report (const std::function< void(TypedResponse< ResponseType > &)> &f, const std::function< void(TypedResponse< ResponseType > &)> &on_completion)

void	execute_and_report (const std::function< void()> &f, const std::function< void(Response &)> &on_completion)

void	check_block_and_root_data (LMDBTreeStore::SharedPtr db, block_number_t blockNumber, fr root, bool expectedSuccess)

void	check_block_and_root_data (LMDBTreeStore::SharedPtr db, block_number_t blockNumber, fr root, bool expectedSuccess, bool expectedRootSuccess)

void	check_block_and_size_data (LMDBTreeStore::SharedPtr db, block_number_t blockNumber, index_t expectedSize, bool expectedSuccess)

void	check_indices_data (LMDBTreeStore::SharedPtr db, fr leaf, index_t index, bool entryShouldBePresent, bool indexShouldBePresent)

void	call_operation (std::function< void(std::function< void(const Response &response)>)> operation, bool expected_success=true)

template<typename LeafType , typename Hash >
void	check_leaf_by_hash (LMDBTreeStore::SharedPtr db, IndexedLeaf< LeafType > leaf, bool shouldBePresent)

template<typename LeafValueType , typename TypeOfTree >
void	check_find_leaf_index (TypeOfTree &tree, const std::vector< LeafValueType > &leaves, const std::vector< std::optional< index_t > > &expected_indices, bool expected_success, bool includeUncommitted=true)

template<typename LeafValueType , typename TypeOfTree >
void	check_find_leaf_index_from (TypeOfTree &tree, const std::vector< LeafValueType > &leaves, index_t start_index, const std::vector< std::optional< index_t > > &expected_indices, bool expected_success, bool includeUncommitted=true)

template<typename LeafValueType , typename TypeOfTree >
void	check_historic_find_leaf_index (TypeOfTree &tree, const std::vector< LeafValueType > &leaves, block_number_t blockNumber, const std::vector< std::optional< index_t > > &expected_indices, bool expected_success, bool includeUncommitted=true)

template<typename LeafValueType , typename TypeOfTree >
void	check_historic_find_leaf_index_from (TypeOfTree &tree, const std::vector< LeafValueType > &leaves, block_number_t blockNumber, index_t start_index, const std::vector< std::optional< index_t > > &expected_indices, bool expected_success, bool includeUncommitted=true)

template<typename LeafValueType , typename TypeOfTree >
void	check_find_leaf_index (TypeOfTree &tree, const LeafValueType &leaf, index_t expected_index, bool expected_success, bool includeUncommitted=true)

template<typename LeafValueType , typename TypeOfTree >
void	check_find_leaf_index_from (TypeOfTree &tree, const LeafValueType &leaf, index_t start_index, index_t expected_index, bool expected_success, bool includeUncommitted=true)

template<typename LeafValueType , typename TypeOfTree >
void	check_historic_find_leaf_index (TypeOfTree &tree, const LeafValueType &leaf, block_number_t blockNumber, index_t expected_index, bool expected_success, bool includeUncommitted=true)

template<typename LeafValueType , typename TypeOfTree >
void	check_historic_find_leaf_index_from (TypeOfTree &tree, const LeafValueType &leaf, block_number_t blockNumber, index_t start_index, index_t expected_index, bool expected_success, bool includeUncommitted=true)

template<typename TypeOfTree >
fr_sibling_path	get_sibling_path (TypeOfTree &tree, index_t index, bool includeUncommitted=true, bool expected_success=true)

template<typename TreeType >
void	rollback_tree (TreeType &tree)

template<typename TreeType >
void	checkpoint_tree (TreeType &tree)

template<typename TreeType >
void	commit_checkpoint_tree (TreeType &tree, bool expected_success=true)

template<typename TreeType >
void	revert_checkpoint_tree (TreeType &tree, bool expected_success=true)

template<typename TreeType >
void	commit_all_tree_checkpoints (TreeType &tree, bool expected_success=true)

template<typename TreeType >
void	revert_all_tree_checkpoints (TreeType &tree, bool expected_success=true)

template<typename LeafType >
fr	preimage_to_key (const LeafType &leaf)

fr	preimage_to_key (const fr &leaf)

template<typename LeafType >
bool	is_empty (const LeafType &leaf)

bool	is_empty (const fr &leaf)

template<typename LeafType >
constexpr bool	requires_preimage_for_key ()

template<>
constexpr bool	requires_preimage_for_key< fr > ()

std::ostream &	operator<< (std::ostream &os, const TreeDBStats &stats)

Variables
const uint32_t	NUM_VALUES = 1024

auto &	engine = numeric::get_debug_randomness()

auto &	random_engine = numeric::get_randomness()

constexpr size_t	REGULAR_NODE_SIZE = 64

constexpr size_t	STUMP_NODE_SIZE = 65

const std::string	BLOCKS_DB = "blocks"

const std::string	NODES_DB = "nodes"

const std::string	LEAF_PREIMAGES_DB = "leaf preimages"

const std::string	LEAF_INDICES_DB = "leaf indices"

const std::string	BLOCK_INDICES_DB = "block indices"

Typedef Documentation

◆ block_number_t

using bb::crypto::merkle_tree::block_number_t = typedef uint32_t

Definition at line 19 of file types.hpp.

◆ BlockMetaKeyType

using bb::crypto::merkle_tree::BlockMetaKeyType = typedef uint64_t

Definition at line 21 of file types.hpp.

◆ fr_hash_path

using bb::crypto::merkle_tree::fr_hash_path = typedef std::vector<std::pair<fr, fr> >

Definition at line 15 of file hash_path.hpp.

◆ fr_sibling_path

using bb::crypto::merkle_tree::fr_sibling_path = typedef std::vector<fr>

Definition at line 16 of file hash_path.hpp.

◆ FrKeyType

using bb::crypto::merkle_tree::FrKeyType = typedef uint256_t

Definition at line 22 of file types.hpp.

◆ hash_path

template<typename Ctx >

using bb::crypto::merkle_tree::hash_path = typedef std::vector<std::pair<bb::stdlib::field_t<Ctx>, bb::stdlib::field_t<Ctx> >>

Definition at line 17 of file hash_path.hpp.

◆ index_t

using bb::crypto::merkle_tree::index_t = typedef uint64_t

Definition at line 18 of file types.hpp.

◆ IndexedNullifierLeafType

using bb::crypto::merkle_tree::IndexedNullifierLeafType = typedef IndexedLeaf<NullifierLeafValue>

Definition at line 13 of file fixtures.hpp.

◆ IndexedPublicDataLeafType

using bb::crypto::merkle_tree::IndexedPublicDataLeafType = typedef IndexedLeaf<PublicDataLeafValue>

Definition at line 14 of file fixtures.hpp.

◆ LeafIndexKeyType

using bb::crypto::merkle_tree::LeafIndexKeyType = typedef uint64_t

Definition at line 20 of file types.hpp.

◆ MetaKeyType

using bb::crypto::merkle_tree::MetaKeyType = typedef uint8_t

Definition at line 23 of file types.hpp.

◆ ThreadPoolPtr

using bb::crypto::merkle_tree::ThreadPoolPtr = typedef std::shared_ptr<ThreadPool>

Definition at line 63 of file fixtures.hpp.

Function Documentation

◆ bit_set()

template<typename T >

bool bb::crypto::merkle_tree::bit_set	(	T const &	index,
		size_t	i
	)

inline

Definition at line 114 of file merkle_tree.hpp.

◆ block_key_cmp()

int bb::crypto::merkle_tree::block_key_cmp	(	const MDB_val *	a,
		const MDB_val *	b
	)

Definition at line 41 of file lmdb_tree_store.cpp.

◆ call_operation()

void bb::crypto::merkle_tree::call_operation	(	std::function< void(std::function< void(const Response &response)>)>	operation,
		bool	expected_success = `true`
	)

inline

Definition at line 79 of file test_fixtures.hpp.

◆ check_block_and_root_data() [1/2]

void bb::crypto::merkle_tree::check_block_and_root_data	(	LMDBTreeStore::SharedPtr	db,
		block_number_t	blockNumber,
		fr	root,
		bool	expectedSuccess
	)

inline

Definition at line 21 of file test_fixtures.hpp.

◆ check_block_and_root_data() [2/2]

void bb::crypto::merkle_tree::check_block_and_root_data	(	LMDBTreeStore::SharedPtr	db,
		block_number_t	blockNumber,
		fr	root,
		bool	expectedSuccess,
		bool	expectedRootSuccess
	)

inline

Definition at line 38 of file test_fixtures.hpp.

◆ check_block_and_size_data()

void bb::crypto::merkle_tree::check_block_and_size_data	(	LMDBTreeStore::SharedPtr	db,
		block_number_t	blockNumber,
		index_t	expectedSize,
		bool	expectedSuccess
	)

inline

Definition at line 53 of file test_fixtures.hpp.