Struct fuel_merkle::common::Position
source · pub struct Position(_);Expand description
Position
A Position represents a node’s position in a binary tree by encapsulating
the node’s index data. Indices are calculated through in-order traversal of
the nodes, starting with the first leaf node. Indexing starts at 0.
Merkle Trees
In the context of Merkle trees, trees are constructed “upwards” from leaf nodes. Therefore, indexing is done from the bottom up, starting with the leaves, rather than top down, starting with the root, and we can guarantee a deterministic construction of index data.
07
/ \
/ \
/ \
/ \
/ \
/ \
03 11
/ \ / \
/ \ / \
01 05 09 13
/ \ / \ / \ / \
00 02 04 06 08 10 12 14
In-order indices can be considered internal to the Position struct and are
used to facilitate the calculation of positional attributes and the
construction of other nodes. Leaf nodes have both an in-order index as part
of the tree, and a leaf index determined by its position in the bottom row.
Because of the in-order traversal used to calculate the in-order indices,
leaf nodes have the property that their in-order index is always equal to
their leaf index multiplied by 2.
/ \ / \ / \ / \
Leaf indices: 00 01 02 03 04 05 06 07
In-order indices: 00 02 04 06 08 10 12 14
This allows us to construct a Position (and its in-order index) by
providing either an in-order index directly or, in the case of a leaf, a
leaf index. This functionality is captured by from_in_order_index() and
from_leaf_index() respectively.
Traversal of a Merkle Tree can be performed by the methods on a given
Position to retrieve its sibling, parent, or uncle Position.
Merkle Mountain Ranges
Because the Position indices are calculated from in-order traversal
starting with the leaves, the deterministic quality of the indices holds
true for imbalanced binary trees, including Merkle Mountain Ranges. Consider
the following binary tree construction composed of seven leaves (with leaf
indices 0 through 6):
03
/ \
/ \
01 05 09
/ \ / \ / \
00 02 04 06 08 10 12
Note the absence of internal nodes that would be present in a fully balanced tree: inner nodes with indices 7 and 11 are absent. This is owing to the fact that node indices are calculated deterministically through in-order traversal, not calculated as a sequence.
Traversal of a Merkle Mountain Range is still done in the same manner as a
balanced Merkle tree, using methods to retrieve a Position's sibling,
parent, or uncle Position. However, in such cases, the corresponding
sibling or uncle nodes are not guaranteed to exist in the tree.
Implementations§
source§impl Position
impl Position
pub fn in_order_index(self) -> u64
pub fn leaf_index(self) -> u64
sourcepub fn from_in_order_index(index: u64) -> Self
pub fn from_in_order_index(index: u64) -> Self
Construct a position from an in-order index.
sourcepub fn from_leaf_index(index: u64) -> Self
pub fn from_leaf_index(index: u64) -> Self
Construct a position from a leaf index. The in-order index corresponding to the leaf index will always equal the leaf index multiplied by 2.
sourcepub fn sibling(self) -> Self
pub fn sibling(self) -> Self
The sibling position. A position shares the same parent and height as its sibling.
sourcepub fn parent(self) -> Self
pub fn parent(self) -> Self
The parent position. The parent position has a height less 1 relative to this position.
sourcepub fn uncle(self) -> Self
pub fn uncle(self) -> Self
The uncle position. The uncle position is the sibling of the parent and has a height less 1 relative to this position.
sourcepub fn left_child(self) -> Self
pub fn left_child(self) -> Self
The left child position. See child.
sourcepub fn right_child(self) -> Self
pub fn right_child(self) -> Self
The right child position. See child.
sourcepub fn height(self) -> u32
pub fn height(self) -> u32
The height of the index in a binary tree. Leaf nodes represent height 0. A leaf’s parent represents height 1. Height values monotonically increase as you ascend the tree.
Height is deterministically calculated as the number of trailing zeros of the complement of the position’s index. The following table demonstrates the relationship between a position’s height and the trailing zeros.
| Index (Dec) | Index (Bin) | !Index (Bin) | Trailing 0s | Height |
|---|---|---|---|---|
| 0 | 0000 | 1111 | 0 | 0 |
| 2 | 0010 | 1101 | 0 | 0 |
| 4 | 0100 | 1011 | 0 | 0 |
| 1 | 0001 | 1110 | 1 | 1 |
| 5 | 0101 | 1010 | 1 | 1 |
| 9 | 1001 | 0110 | 1 | 1 |
| 3 | 0011 | 1100 | 2 | 2 |
| 11 | 1011 | 0100 | 2 | 2 |
sourcepub fn is_leaf(self) -> bool
pub fn is_leaf(self) -> bool
Whether or not this position represents a leaf node.
Returns true if the position is a leaf node.
Returns false if the position is an internal node.
A position is a leaf node if and only if its in-order index is even. A position is an internal node if and only if its in-order index is odd.
sourcepub fn is_node(self) -> bool
pub fn is_node(self) -> bool
Whether or not this position represents an internal node.
Returns false if the position is a leaf node.
Returns true if the position is an internal node.
When a position is an internal node, the position will have both a left and right child.
sourcepub fn path(self, leaf: &Self, leaves_count: u64) -> PositionPath
pub fn path(self, leaf: &Self, leaves_count: u64) -> PositionPath
Given a leaf position and the total count of leaves in a tree, get the
path from this position to the given leaf position. The shape of the
tree is defined by the leaves_count parameter and constrains the
path. See PositionPath.