Module grin_core::core::pmmr

source ·
Expand description

Persistent and prunable Merkle Mountain Range implementation. For a high level description of MMRs, see:

https://github. com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range. md

This implementation is built in two major parts:

  1. A set of low-level functions that allow navigation within an arbitrary sized binary tree traversed in postorder. To realize why this us useful, we start with the standard height sequence in a MMR: 0010012001… This is in fact identical to the postorder traversal (left-right-top) of a binary tree. In addition postorder traversal is independent of the height of the tree. This allows us, with a few primitive, to get the height of any node in the MMR from its position in the sequence, as well as calculate the position of siblings, parents, etc. As all those functions only rely on binary operations, they’re extremely fast.
  2. The implementation of a prunable MMR tree using the above. Each leaf is required to be Writeable (which implements Hashed). Tree roots can be trivially and efficiently calculated without materializing the full tree. The underlying Hashes are stored in a Backend implementation that can either be a simple Vec or a database.

Modules§

Structs§

  • PMMR
    Prunable Merkle Mountain Range implementation. All positions within the tree start at 0 just like array indices.
  • ReadonlyPMMR
    Readonly view of a PMMR.
  • RewindablePMMR
    Rewindable (but still readonly) view of a PMMR.
  • VecBackend
    Simple/minimal/naive MMR backend implementation backed by Vec and Vec. Removed pos are maintained in a HashSet.

Traits§

  • Backend
    Storage backend for the MMR, just needs to be indexed by order of insertion. The PMMR itself does not need the Backend to be accurate on the existence of an element (i.e. remove could be a no-op) but layers above can depend on an accurate Backend to check existence.
  • ReadablePMMR
    Trait with common methods for reading from a PMMR

Functions§

  • bintree_leaf_pos_iter
    Iterator over all leaf pos beneath the provided subtree root (including the root itself).
  • bintree_leftmost
    Gets the position of the leftmost node (i.e. leaf) beneath the provided subtree root.
  • bintree_pos_iter
    Iterator over all pos beneath the provided subtree root (including the root itself).
  • bintree_postorder_height
    The height of a node in a full binary tree from its postorder traversal index.
  • bintree_range
    All pos in the subtree beneath the provided root, including root itself.
  • bintree_rightmost
    Gets the position of the rightmost node (i.e. leaf) beneath the provided subtree root.
  • 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.
  • insertion_to_pmmr_index
    Returns the 0-based pmmr index of 0-based leaf index n
  • 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?
  • n_leaves
    The number of leaves in a MMR of the provided size.
  • peak_map_height
    peak bitmap and height of next node in mmr of given size Example: on size 4 returns (0b11, 0) as mmr tree of size 4 is 2 /
    0 1 3 with 0b11 indicating the presence of peaks of height 0 and 1, and 0 the height of the next node 4, which is a leaf 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 similar to peak_map_height but replacing bitmap by vector of sizes Example: on input 5 returns ([3,1], 1) as mmr state before adding 5 was 2 /
    0 1 3 4
  • peaks
    Gets the postorder traversal 0-based 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. For some odd reason, return empty when next node is not a leaf
  • pmmr_leaf_to_insertion_index
    Returns the insertion index of the given leaf index
  • round_up_to_leaf_pos
    returns least position >= pos0 with height 0