Struct fuel_merkle::binary::MerkleTree

pub struct MerkleTree<TableType, StorageType> { /* private fields */ }

Implementations

impl<TableType, StorageType> MerkleTree<TableType, StorageType>

pub const fn empty_root() -> &'static Bytes32

pub fn root(&self) -> Bytes32

pub fn leaves_count(&self) -> u64

impl<TableType, StorageType, StorageError> MerkleTree<TableType, StorageType>

where TableType: Mappable<Key = u64, Value = Primitive, OwnedValue = Primitive>, StorageType: StorageInspect<TableType, Error = StorageError>,

pub fn new(storage: StorageType) -> Self

pub fn load( storage: StorageType, leaves_count: u64, ) -> Result<Self, MerkleTreeError<StorageError>>

A binary Merkle tree can be built from a collection of Merkle Mountain Range (MMR) peaks. The MMR structure can be accurately defined by the number of leaves in the leaf row.

Consider a binary Merkle tree with seven leaves, producing the following MMR structure:

      03
     /  \
    /    \
  01      05      09
 /  \    /  \    /  \
00  02  04  06  08  10  12

We observe that the tree has three peaks at positions 03, 09, and 12. These peak positions are recorded in the order that they appear, reading left to right in the tree structure, and only descend in height. These peak positions communicate everything needed to determine the remaining internal nodes building upwards to the root position:

           07
          /  \
         /    \
        /      \
       /        \
      /          \
     /            \
   03              11
  /  \            /  \
...  ...         /    \
               09      \
              /  \      \
            ...  ...    12

No additional intermediate nodes or leaves are required to calculate the root position.

The positions of the MMR peaks can be deterministically calculated as a function of n + 1 where n is the number of leaves in the tree. By appending an additional leaf node to the tree, we generate a new tree structure with additional internal nodes (N.B.: this may also change the root position if the tree is already balanced).

In our example, we add an additional leaf at leaf index 7 (in-order index 14):

           07
          /  \
         /    \
        /      \
       /        \
      /          \
     /            \
   03              11
  /  \            /  \
...  ...         /    \
               09      13
              /  \    /  \
            ...  ... 12  14

We observe that the path from the root position to our new leaf position yields a set of side positions that includes our original peak positions (see Path Iterator):

Path position	Side position
07	07
11	03
13	09
14	12

By excluding the root position 07, we have established the set of side positions 03, 09, and 12, matching our set of MMR peaks.

pub fn prove( &self, proof_index: u64, ) -> Result<(Bytes32, ProofSet), MerkleTreeError<StorageError>>

pub fn reset(&mut self)

impl<TableType, StorageType, StorageError> MerkleTree<TableType, StorageType>

where TableType: Mappable<Key = u64, Value = Primitive, OwnedValue = Primitive>, StorageType: StorageMutate<TableType, Error = StorageError>,

pub fn push(&mut self, data: &[u8]) -> Result<(), MerkleTreeError<StorageError>>

Adds a new leaf node to the tree.

WARNING

This code might modify the storage, and then return an error. TODO: fix this issue

Trait Implementations

impl<TableType: Clone, StorageType: Clone> Clone for MerkleTree<TableType, StorageType>

fn clone(&self) -> MerkleTree<TableType, StorageType>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<TableType: Debug, StorageType: Debug> Debug for MerkleTree<TableType, StorageType>

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

Formats the value using the given formatter.