Module tari_mmr::common[][src]

Functions

The height of a node in a full binary tree from its index.

The number of leaves in a MMR of the provided size. Example: on input 5 returns (2 + 1 + 1) as mmr state before adding 5 was 2 /
0 1 3 4 None is returned if the number of leaves exceeds the maximum value of a usize

Calculates the positions of the (parent, sibling) of the node at the provided position. Returns an error if the pos provided would result in an underflow or overflow.

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.

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 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 the node at this pos the “left” sibling of its parent?

Returns the leaf index derived from the MMR node index.

Returns the MMR node index derived from the leaf index.

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)