Inheritance diagram for zeth.core.merkle_tree.MerkleTree:

Public Member Functions
def	__init__ (self, MerkleTreeData tree_data, int depth, ITreeHash tree_hash)

int	get_num_entries (self)

bytes	get_leaf (self, int index)

List[bytes]	get_leaves (self)

bytes	get_node (self, int layer_idx, int node_idx)

Iterator[Tuple[bytes, List[bytes]]]	get_layers (self)

bytes	get_root (self)

None	insert (self, bytes value)

bytes	recompute_root (self)

Static Public Member Functions
MerkleTree	empty_with_depth (int depth, ITreeHash tree_hash)

MerkleTree	empty_with_size (int num_leaves, ITreeHash tree_hash)

Public Attributes
	max_num_leaves

	depth

	tree_data

	num_new_leaves

	tree_hash

Detailed Description

Merkle tree structure matching that used in the mixer contract. Simple
implementation where unpopulated values (zeroes) are also stored.

Definition at line 60 of file merkle_tree.py.

Constructor & Destructor Documentation

◆ init()

def zeth.core.merkle_tree.MerkleTree.__init__	(		self,
		MerkleTreeData	tree_data,
		int	depth,
		ITreeHash	tree_hash
	)

Definition at line 65 of file merkle_tree.py.

     def __init__(
             self,
             tree_data: MerkleTreeData,
             depth: int,
             tree_hash: ITreeHash):
         self.max_num_leaves = pow(2, depth)
         self.depth = tree_data.depth
         self.tree_data = tree_data
         self.num_new_leaves = 0
         self.tree_hash = tree_hash
  

Member Function Documentation

◆ empty_with_depth()

MerkleTree zeth.core.merkle_tree.MerkleTree.empty_with_depth	(	int	depth,
		ITreeHash	tree_hash
	)

static

Definition at line 94 of file merkle_tree.py.

     def empty_with_depth(depth: int, tree_hash: ITreeHash) -> MerkleTree:
         return MerkleTree(
             MerkleTree._empty_data_with_depth(depth, tree_hash), depth, tree_hash)
  

Here is the caller graph for this function:

◆ empty_with_size()

MerkleTree zeth.core.merkle_tree.MerkleTree.empty_with_size	(	int	num_leaves,
		ITreeHash	tree_hash
	)

static

Definition at line 99 of file merkle_tree.py.

     def empty_with_size(num_leaves: int, tree_hash: ITreeHash) -> MerkleTree:
         depth = int(math.log(num_leaves, 2))
         assert pow(2, depth) == num_leaves, f"Non-pow-2 size {num_leaves} given"
         return MerkleTree.empty_with_depth(depth, tree_hash)
  

◆ get_layers()

Iterator[Tuple[bytes, List[bytes]]] zeth.core.merkle_tree.MerkleTree.get_layers ( self )

Public layers iterator.

Definition at line 125 of file merkle_tree.py.

     def get_layers(self) -> Iterator[Tuple[bytes, List[bytes]]]:
         """
         Public layers iterator.
         """
         assert self.num_new_leaves == 0
         return self._get_layers()
  

Here is the call graph for this function:

◆ get_leaf()

bytes zeth.core.merkle_tree.MerkleTree.get_leaf	(		self,
		int	index
	)

Definition at line 107 of file merkle_tree.py.

     def get_leaf(self, index: int) -> bytes:
         leaves = self.tree_data.layers[self.depth]
         if index < len(leaves):
             return leaves[index]
         return ZERO_ENTRY
  

◆ get_leaves()

List[bytes] zeth.core.merkle_tree.MerkleTree.get_leaves ( self )

Definition at line 113 of file merkle_tree.py.

     def get_leaves(self) -> List[bytes]:
         return self.tree_data.layers[self.depth]
  

◆ get_node()

bytes zeth.core.merkle_tree.MerkleTree.get_node	(		self,
		int	layer_idx,
		int	node_idx
	)

Definition at line 116 of file merkle_tree.py.

     def get_node(self, layer_idx: int, node_idx: int) -> bytes:
         assert layer_idx <= self.depth
         assert self.num_new_leaves == 0
         layer_idx = self.depth - layer_idx
         layer = self.tree_data.layers[layer_idx]
         if node_idx < len(layer):
             return layer[node_idx]
         return self.tree_data.default_values[layer_idx]
  

◆ get_num_entries()

int zeth.core.merkle_tree.MerkleTree.get_num_entries ( self )

Definition at line 104 of file merkle_tree.py.

     def get_num_entries(self) -> int:
         return len(self.tree_data.layers[self.depth])
  

◆ get_root()

bytes zeth.core.merkle_tree.MerkleTree.get_root ( self )

Definition at line 132 of file merkle_tree.py.

     def get_root(self) -> bytes:
         assert self.num_new_leaves == 0
         return self.tree_data.layers[0][0]
  

Here is the caller graph for this function:

◆ insert()

None zeth.core.merkle_tree.MerkleTree.insert	(		self,
		bytes	value
	)

Definition at line 136 of file merkle_tree.py.

     def insert(self, value: bytes) -> None:
         leaves = self.tree_data.layers[self.depth]
         assert len(leaves) < self.max_num_leaves
         leaves.append(value)
         self.num_new_leaves = self.num_new_leaves + 1
  

◆ recompute_root()

bytes zeth.core.merkle_tree.MerkleTree.recompute_root ( self )

After some new leaves have been added, perform the minimal set of hashes
to recompute the tree, expanding each layer to accommodate new nodes.

Definition at line 142 of file merkle_tree.py.

     def recompute_root(self) -> bytes:
         """
         After some new leaves have been added, perform the minimal set of hashes
         to recompute the tree, expanding each layer to accommodate new nodes.
         """
         if self.num_new_leaves == 0:
             return self.get_root()
  
         layers_it = self._get_layers()
  
         layer_default, layer = next(layers_it)
         end_idx = len(layer)
         start_idx = end_idx - self.num_new_leaves
         layer_size = self.max_num_leaves
  
         for parent_default, parent_layer in layers_it:
             # Computation for each layer is performed in _recompute_layer, which
             # also computes the start and end indices for the next layer in the
             # tree.
             start_idx, end_idx = _recompute_layer(
                 layer,
                 start_idx,
                 end_idx,
                 layer_default,
                 parent_layer,
                 self.tree_hash)
             layer = parent_layer
             layer_default = parent_default
             layer_size = int(layer_size / 2)
  
         self.num_new_leaves = 0
         assert len(layer) == 1
         assert layer_size == 1
         return layer[0]
  

Here is the call graph for this function:

Member Data Documentation

◆ depth

zeth.core.merkle_tree.MerkleTree.depth

Definition at line 67 of file merkle_tree.py.

◆ max_num_leaves

zeth.core.merkle_tree.MerkleTree.max_num_leaves

Definition at line 66 of file merkle_tree.py.

◆ num_new_leaves

zeth.core.merkle_tree.MerkleTree.num_new_leaves

Definition at line 69 of file merkle_tree.py.

◆ tree_data

zeth.core.merkle_tree.MerkleTree.tree_data

Definition at line 68 of file merkle_tree.py.

◆ tree_hash

zeth.core.merkle_tree.MerkleTree.tree_hash

Definition at line 70 of file merkle_tree.py.

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

/home/runner/work/zeth/zeth/client/zeth/core/merkle_tree.py

Public Member Functions

Static Public Member Functions

Public Attributes