Module geen::algos

Hiker Common Algorithms to climb the Mountain

Functions

bintree_height	The height of a node in a full binary tree from its index.
family	Calculates the positions of the parent and sibling of the node at the provided position.
family_branch	For a given starting position calculate the parent and sibling positions for the branch/path from that position to the peak of the tree. We will use the sibling positions to generate the "path" of a Merkle proof.
find_peaks	Gets the postorder traversal index of all peaks in a MMR given its size. Starts with the top peak, which is always on the left side of the range, and navigates toward lower siblings toward the right of the range.
is_leaf	Is this position a leaf in the MMR? We know the positions of all leaves based on the postorder height of an MMR of any size (somewhat unintuitively but this is how the PMMR is "append only").
is_left_sibling	Is the node at this pos the "left" sibling of its parent?
leaf_index	Returns the MMR index of the nth leaf node
n_leaves	The number of leaves in a MMR of the provided size.
peak_map_height	return (peak_map, pos_height) of given 0-based node pos prior to its addition Example: on input 4 returns (0b11, 0) as mmr state before adding 4 was 2 / 0 1 3 with 0b11 indicating presence of peaks of height 0 and 1. NOTE: the peak map also encodes the path taken from the root to the added node since the path turns left (resp. right) if-and-only-if a peak at that height is absent (resp. present)
peak_sizes_height	sizes of peaks and height of next node in mmr of given size Example: on input 5 returns ([3,1], 1) as mmr state before adding 5 was 2 / 0 1 3 4