Define general tree storage trait

[vlopes11]

It might be desirable to have a general storage trait so all the tree implementations (mountain range, sparse merkle tree, etc) can be purely functional and focus only on algorithm optimization, leaving storage optimization details outside of their scope.

A tree-like storage is usually composed of simple map-like operations for nodes and leaves. They are distinguished because leaves are often some arbitrary data while nodes are tuples of the digest of a given hash implementation.

The issue started with the PR #27 , but it was better to decouple such big topic from the implementation of the SMT itself.

Here is a suggested implementation with comments:

#![no_std]

extern crate alloc;

// cow is optimal to ease the storage requirements on whether or not he will pass references or
// owned values. sometimes the storage might have to fetch the data from async contexts - to not
// force the storage to hold the lock of the context while the data is being processed by the
// consumer, it will have the option to send it as owned. in other cases, the fetch operation is
// trivial (i.e. memory maps such as BTreeMap) so the storage can just return a reference.
use alloc::borrow::Cow;

// the hasher will be the responsible to define the concrete digest implementation for nodes and
// merge them, producing merkle paths.
use winter_crypto::Hasher;

// a tree node is either a single node (likely the root) or a pair with two digests, one
// representing a left value, the other a right value.
pub enum TreeNode<D> {
    Pair { left: D, right: D },
    Single(D),
}

// a tree storage is a common definition of map-like implementations optimized for merkle trees.
pub trait TreeStorage: Sized {
    // defines the index of a leaf in the tree. it is often just a single scalar value whereas a
    // node is indexed by a pair defining both the depth and its index for that depth. the leaf
    // will often have as depth the maximum value allowed for the concrete instance.
    type LeafIndex;

    // usually a pair defining the depth + index of the node for that depth.
    type NodeIndex;

    // an arbitrary error definition defined by the provider.
    type Error;

    // a common hash definition used for the backend. the purpose is to define the digest
    // concretely, allowing the storage to implement its functionality efficiently since it will be
    // aware of the details of the digest - such as bits count, parity, etc.
    type Hasher: Hasher;

    // a leaf that is separated from the nodes of the tree. usually the leaf contains information
    // relevant for the consumers of the tree, while the nodes contains only the required digest to
    // traverse the tree and generate paths.
    type Leaf: Clone;

    // create a new tree with for a given depth.
    fn new_with_depth(depth: u32) -> Result<Self, Self::Error>;

    // fetch the depth of the storage so tree implementers will be able to contruct merkle paths.
    fn depth(&self) -> u32;

    // fetch the fixed empty digest for a given depth, provided the upstream branch for that depth
    // is composed only of empty leaves.
    fn empty_digest(
        &self,
        depth: u32,
    ) -> Result<Option<Cow<'_, <Self::Hasher as Hasher>::Digest>>, Self::Error>;

    // append a new leaf to the storage, replacing a previous value, if applicable. we opt to not
    // return the previous value so the storage can freely discard the replaced value. if the user
    // needs the previous value, he can call `Self::get_leaf` and check the underlying `Option`.
    fn insert_leaf<L>(&mut self, index: Self::LeafIndex, leaf: L) -> Result<(), Self::Error>
    where
        L: Into<Self::Leaf>;

    // fetch a previously inserted leaf. usually the index will be a common reference scalar (i.e.
    // u64).
    fn get_leaf(&self, index: &Self::LeafIndex)
        -> Result<Option<Cow<'_, Self::Leaf>>, Self::Error>;

    // append a new node to the storage, replacing a previous value, if applicable. it follows the
    // same pattern of `Self::insert_leaf`; thus, it will not return the previous value.
    fn insert_node<N>(&mut self, index: Self::NodeIndex, node: N) -> Result<(), Self::Error>
    where
        N: Into<TreeNode<<Self::Hasher as Hasher>::Digest>>;

    // fetch a previously inserted node. usually the index will be a pair defining both the depth,
    // and the index of the node for that depth.
    fn get_node(&self, index: &Self::NodeIndex)
        -> Result<Option<Cow<'_, Self::Leaf>>, Self::Error>;
}

// create a new list of pairs `(depth, digest)` for a provided hasher and a given depth. it is a
// generic implementation to initialize storages and provide the empty digests via
// [`TreeStorage::empty_digest`]. we don't make assumptions on how the user wants to store this
// list so it is returned as a generic iterator, allowing the user to collect it how it best suits
// him.
pub fn compute_empty_digests<H>(depth: u32) -> impl Iterator<Item = (u32, H::Digest)>
where
    H: Hasher,
{
    (0..=depth).scan(H::Digest::default(), move |state, i| {
        Some((depth - i, core::mem::replace(state, H::merge(&[*state; 2]))))
    })
}

[bobbinth]

Superseded by the current work on TSMT (e.g., #173).