Struct fuel_merkle::common::Position

pub struct Position(_);

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

impl Position

pub fn in_order_index(self) -> u64

pub fn leaf_index(self) -> u64

pub fn from_in_order_index(index: u64) -> Self

Construct a position from an in-order index.

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.

pub fn sibling(self) -> Self

The sibling position. A position shares the same parent and height as its sibling.

pub fn parent(self) -> Self

The parent position. The parent position has a height less 1 relative to this position.

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.

pub fn left_child(self) -> Self

The left child position. See child.

pub fn right_child(self) -> Self

The right child position. See child.

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

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.

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.

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.

Trait Implementations

impl Clone for Position

fn clone(&self) -> Position

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Position

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq<Position> for Position

fn eq(&self, other: &Position) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Copy for Position

impl Eq for Position

impl StructuralEq for Position

impl StructuralPartialEq for Position