Struct tree_hash::MerkleHasher

pub struct MerkleHasher { /* private fields */ }

Provides a Merkle-root hasher that allows for streaming bytes (i.e., providing any-length byte slices without need to separate into leaves). Efficiently handles cases where not all leaves have been provided by assuming all non-provided leaves are [0; 32] and pre-computing the zero-value hashes at all depths of the tree.

This algorithm aims to allocate as little memory as possible and it does this by “folding” up the tree as each leaf is provided. Consider this step-by-step functional diagram of hashing a tree with depth three:

Functional Diagram

Nodes that are - have not been defined and do not occupy memory. Nodes that are L are leaves that are provided but are not stored. Nodes that have integers (1, 2) are stored in our struct. Finally, nodes that are X were stored, but are now removed.

Start

          -
         / \
        -   -
       / \ / \
      -  - -  -

Provide first leaf

          -
         / \
        2   -
       / \ / \
      L  - -  -

Provide second leaf

          1
         / \
        X   -
       / \ / \
      L  L -  -

Provide third leaf

          1
         / \
        X   3
       / \ / \
      L  L L  -

Provide fourth and final leaf

          1
         / \
        X   X
       / \ / \
      L  L L  L

Implementations

impl MerkleHasher

pub fn with_leaves(num_leaves: usize) -> Self

Instantiate a hasher for a tree with a given number of leaves.

num_leaves will be rounded to the next power of two. E.g., if num_leaves == 6, then the tree will actually be able to accomodate 8 leaves and the resulting hasher is exactly the same as one that was instantiated with Self::with_leaves(8).

Notes

If num_leaves == 0, a tree of depth 1 will be created. If no leaves are provided it will return a root of [0; 32].

pub fn write(&mut self, bytes: &[u8]) -> Result<(), Error>

Write some bytes to the hasher.

Errors

Returns an error if the given bytes would create a leaf that would exceed the maximum permissible number of leaves defined by the initialization depth. E.g., a tree of depth == 2 can only accept 2 leaves. A tree of depth == 14 can only accept 8,192 leaves.

pub fn finish(self) -> Result<Hash256, Error>

Returns the root of the Merkle tree.

If not all leaves have been provided, the tree will be efficiently completed under the assumption that all not-yet-provided leaves are equal to [0; 32].

Errors

Returns an error if the bytes remaining in the buffer would create a leaf that would exceed the maximum permissible number of leaves defined by the initialization depth.