#include <merkle_tree.hpp>

Inheritance diagram for bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >:

Public Types
typedef uint256_t	index_t

Public Member Functions
	MerkleTree (Store &store, size_t depth, uint8_t tree_id=0)

	MerkleTree (MerkleTree const &other)=delete

	MerkleTree (MerkleTree &&other)

	~MerkleTree ()

fr_hash_path	get_hash_path (index_t index)

fr_sibling_path	get_sibling_path (index_t index)

fr	update_element (index_t index, fr const &value)

fr	root () const

size_t	depth () const

index_t	size () const

Protected Member Functions
void	load_metadata ()

fr	update_element (fr const &root, fr const &value, index_t index, size_t height)

fr	get_element (fr const &root, index_t index, size_t height)

fr	compute_zero_path_hash (size_t height, index_t index, fr const &value)

fr	binary_put (index_t a_index, fr const &a, fr const &b, size_t height)

fr	fork_stump (fr const &value1, index_t index1, fr const &value2, index_t index2, size_t height, size_t stump_height)

void	put (fr const &key, fr const &left, fr const &right)

void	put_stump (fr const &key, index_t index, fr const &value)

void	remove (fr const &key)

Protected Attributes
Store &	store_

std::vector< fr >	zero_hashes_

size_t	depth_

uint8_t	tree_id_

Detailed Description

template<typename Store, typename HashingPolicy>
class bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >

Definition at line 23 of file merkle_tree.hpp.

Member Typedef Documentation

◆ index_t

template<typename Store , typename HashingPolicy >

typedef uint256_t bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::index_t

Definition at line 25 of file merkle_tree.hpp.

Constructor & Destructor Documentation

◆ MerkleTree() [1/3]

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::MerkleTree	(	Store &	store,
		size_t	depth,
		uint8_t	tree_id = `0`
	)

Definition at line 120 of file merkle_tree.hpp.

◆ MerkleTree() [2/3]

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::MerkleTree ( MerkleTree< Store, HashingPolicy > const & other )

delete

◆ MerkleTree() [3/3]

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::MerkleTree ( MerkleTree< Store, HashingPolicy > && other )

Definition at line 138 of file merkle_tree.hpp.

◆ ~MerkleTree()

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::~MerkleTree ( )

Definition at line 145 of file merkle_tree.hpp.

Member Function Documentation

◆ binary_put()

template<typename Store , typename HashingPolicy >

fr bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::binary_put	(	index_t	a_index,
		fr const &	a,
		fr const &	b,
		size_t	height
	)

protected

Given child nodes a and b and index of a, compute their parent node p and store [p : (a, b)].

Parameters

a_index	the index of the child node `a`
a	child node
b	child node
height	the height of the parent node

Definition at line 319 of file merkle_tree.hpp.

◆ compute_zero_path_hash()

template<typename Store , typename HashingPolicy >

fr bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::compute_zero_path_hash	(	size_t	height,
		index_t	index,
		fr const &	value
	)

protected

Computes the root hash of a tree of height, that is empty other than value at index.

Parameters

height	The tree depth
index	the index of the non-empty leaf
value	the value to be stored in the non-empty leaf

Definition at line 413 of file merkle_tree.hpp.

◆ depth()

template<typename Store , typename HashingPolicy >

size_t bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::depth ( ) const

inline

Definition at line 40 of file merkle_tree.hpp.

◆ fork_stump()

template<typename Store , typename HashingPolicy >

fr bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::fork_stump	(	fr const &	value1,
		index_t	index1,
		fr const &	value2,
		index_t	index2,
		size_t	height,
		size_t	stump_height
	)

protected

Definition at line 330 of file merkle_tree.hpp.

◆ get_element()

template<typename Store , typename HashingPolicy >

fr bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::get_element	(	fr const &	root,
		index_t	index,
		size_t	height
	)

protected

◆ get_hash_path()

template<typename Store , typename HashingPolicy >

fr_hash_path bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::get_hash_path ( index_t index )

Definition at line 165 of file merkle_tree.hpp.

◆ get_sibling_path()

template<typename Store , typename HashingPolicy >

fr_sibling_path bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::get_sibling_path ( index_t index )

Definition at line 238 of file merkle_tree.hpp.

◆ load_metadata()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::load_metadata ( )

protected

◆ put()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::put	(	fr const &	key,
		fr const &	left,
		fr const &	right
	)

protected

Stores a parent node and child nodes in the database as [key : (left, right)].

Parameters

key	The node value to be stored as key
left	the left child node
right	the right child node

Definition at line 432 of file merkle_tree.hpp.

◆ put_stump()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::put_stump	(	fr const &	key,
		index_t	index,
		fr const &	value
	)

protected

Stores a stump [key : (value, index, true)] in the memory. The additional byte true is to denote this is a stump.

Parameters

key	The node value to be stored as key
value	value of the non-empty leaf in the stump
index	the index of the non-empty leaf in the stump

Definition at line 441 of file merkle_tree.hpp.

◆ remove()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::remove ( fr const & key )

protected

Definition at line 451 of file merkle_tree.hpp.

◆ root()

template<typename Store , typename HashingPolicy >

fr bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::root ( ) const

Definition at line 147 of file merkle_tree.hpp.

◆ size()

template<typename Store , typename HashingPolicy >

MerkleTree< Store, HashingPolicy >::index_t bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::size ( ) const

Definition at line 156 of file merkle_tree.hpp.

◆ update_element() [1/2]

template<typename Store , typename HashingPolicy >

fr bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::update_element	(	fr const &	root,
		fr const &	value,
		index_t	index,
		size_t	height
	)

protected

Computes the root hash of a tree of height, that is empty other than value at index.

Parameters

height	The tree depth
index	the index of the non-empty leaf
value	the value to be stored in the non-empty leaf

See also: Check full documentation: https://hackmd.io/2zyJc6QhRuugyH8D78Tbqg?view

Definition at line 356 of file merkle_tree.hpp.

◆ update_element() [2/2]

template<typename Store , typename HashingPolicy >

fr bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::update_element	(	index_t	index,
		fr const &	value
	)

Definition at line 298 of file merkle_tree.hpp.

Member Data Documentation

◆ depth_

template<typename Store , typename HashingPolicy >

size_t bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::depth_

protected

Definition at line 106 of file merkle_tree.hpp.

◆ store_

template<typename Store , typename HashingPolicy >

Store& bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::store_

protected

Definition at line 104 of file merkle_tree.hpp.

◆ tree_id_

template<typename Store , typename HashingPolicy >

uint8_t bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::tree_id_

protected

Definition at line 107 of file merkle_tree.hpp.

◆ zero_hashes_

template<typename Store , typename HashingPolicy >

std::vector<fr> bb::crypto::merkle_tree::MerkleTree< Store, HashingPolicy >::zero_hashes_

protected

Definition at line 105 of file merkle_tree.hpp.

The documentation for this class was generated from the following file:

src/barretenberg/crypto/merkle_tree/merkle_tree.hpp

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ index_t

Constructor & Destructor Documentation

◆ MerkleTree() [1/3]

◆ MerkleTree() [2/3]

◆ MerkleTree() [3/3]

◆ ~MerkleTree()

Member Function Documentation

◆ binary_put()

◆ compute_zero_path_hash()

◆ depth()

◆ fork_stump()

◆ get_element()

◆ get_hash_path()

◆ get_sibling_path()

◆ load_metadata()

◆ put()

◆ put_stump()

◆ remove()

◆ root()

◆ size()

◆ update_element() [1/2]

◆ update_element() [2/2]

Member Data Documentation

◆ depth_

◆ store_

◆ tree_id_

◆ zero_hashes_