Struct mohan::merkle::MerkleTree

pub struct MerkleTree<T, A, K> where
    T: Element,
    A: Algorithm<T>,
    K: Store<T>,  { /* fields omitted */ }

Merkle Tree.

All leafs and nodes are stored in a linear array (vec).

A merkle tree is a tree in which every non-leaf node is the hash of its children nodes. A diagram depicting how it works:

        root = h1234 = h(h12 + h34)
       /                           \
 h12 = h(h1 + h2)            h34 = h(h3 + h4)
  /            \              /            \
h1 = h(tx1)  h2 = h(tx2)    h3 = h(tx3)  h4 = h(tx4)

In memory layout:

    [h1 h2 h3 h4 h12 h34 root]

Merkle root is always the last element in the array.

The number of inputs is not always a power of two which results in a balanced tree structure as above. In that case, parent nodes with no children are also zero and parent nodes with only a single left node are calculated by concatenating the left node with itself before hashing. Since this function uses nodes that are pointers to the hashes, empty nodes will be nil.

TODO: Ord

Methods

impl<T: Element, A: Algorithm<T>, K: Store<T>> MerkleTree<T, A, K>

pub fn new<I: IntoIterator<Item = T>>(data: I) -> MerkleTree<T, A, K>

Creates new merkle from a sequence of hashes.

pub fn from_data<O: Hashable<A>, I: IntoIterator<Item = O>>(
    data: I
) -> MerkleTree<T, A, K>

Creates new merkle tree from a list of hashable objects.

pub fn from_data_with_store<I: IntoIterator<Item = T>>(
    into: I,
    leaves: K,
    top_half: K
) -> MerkleTree<T, A, K>

Creates new merkle from an already allocated Store (used with DiskMmapStore::new_with_path to set its path before instantiating the MT, which would otherwise just call DiskMmapStore::new).

pub fn try_offload_store(&self) -> bool

pub fn gen_proof(&self, i: usize) -> Proof<T>

Generate merkle tree inclusion proof for leaf i

pub fn root(&self) -> T

Returns merkle root

pub fn len(&self) -> usize

Returns number of elements in the tree.

pub fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

pub fn height(&self) -> usize

Returns height of the tree

pub fn leafs(&self) -> usize

Returns original number of elements the tree was built upon.

pub fn read_at(&self, i: usize) -> T

Returns merkle root

pub fn read_range(&self, start: usize, end: usize) -> Vec<T>

pub fn read_into(&self, pos: usize, buf: &mut [u8])

Reads into a pre-allocated slice (for optimization purposes).

pub fn from_byte_slice(leafs: &[u8]) -> Self

Build the tree given a slice of all leafs, in bytes form.

Trait Implementations

impl<T: Clone, A: Clone, K: Clone> Clone for MerkleTree<T, A, K> where
    T: Element,
    A: Algorithm<T>,
    K: Store<T>, 

fn clone(&self) -> MerkleTree<T, A, K>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Eq, A: Eq, K: Eq> Eq for MerkleTree<T, A, K> where
    T: Element,
    A: Algorithm<T>,
    K: Store<T>, 

impl<T: PartialEq, A: PartialEq, K: PartialEq> PartialEq<MerkleTree<T, A, K>> for MerkleTree<T, A, K> where
    T: Element,
    A: Algorithm<T>,
    K: Store<T>, 

fn eq(&self, other: &MerkleTree<T, A, K>) -> bool

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

fn ne(&self, other: &MerkleTree<T, A, K>) -> bool

This method tests for !=.

impl<T: Debug, A: Debug, K: Debug> Debug for MerkleTree<T, A, K> where
    T: Element,
    A: Algorithm<T>,
    K: Store<T>, 

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

Formats the value using the given formatter.

impl<T: Element, A: Algorithm<T>, K: Store<T>> FromIterator<T> for MerkleTree<T, A, K>

fn from_iter<I: IntoIterator<Item = T>>(into: I) -> Self

Creates new merkle tree from an iterator over hashable objects.

impl<T: Element, A: Algorithm<T>, K: Store<T>> FromParallelIterator<T> for MerkleTree<T, A, K>

fn from_par_iter<I: IntoParallelIterator<Item = T>>(into: I) -> Self

Creates new merkle tree from an iterator over hashable objects.