[−][src]Module grin_core::core::pmmr
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:
- 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.
- 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.
Structs
PMMR | Prunable Merkle Mountain Range implementation. All positions within the tree start at 1 as they're postorder tree traversal positions rather than 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 |
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. |
Functions
bintree_leftmost | Gets the position of the rightmost node (i.e. leaf) beneath the provided subtree root. |
bintree_postorder_height | The height of a node in a full binary tree from its postorder traversal index. This function is the base on which all others, as well as the MMR, are built. |
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 pmmr index of the nth inserted element |
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. |
path | Returns the path from the specified position up to its corresponding peak in the MMR. The size (and therefore the set of peaks) of the MMR is defined by last_pos. |
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
/ |
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
/ |
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. |