Struct Monotree

pub struct Monotree {
    db: MemoryDb,
}

A structure for monotree

Fields

db: MemoryDb

Implementations

impl Monotree

pub fn new() -> Self

fn hash_digest(bytes: &[u8]) -> Hash

pub fn get_headroot(&self) -> GenericResult<Option<Hash>>

Retrieves the latest state (root) from the database.

pub fn set_headroot(&mut self, headroot: Option<&Hash>)

Sets the latest state (root) to the database.

pub fn prepare(&mut self)

pub fn commit(&mut self)

pub fn insert( &mut self, root: Option<&Hash>, key: &Hash, leaf: &Hash, ) -> GenericResult<Option<Hash>>

Insert key-leaf entry into the tree. Returns a new root hash.

fn put_node(&mut self, node: Node<'_>) -> GenericResult<Option<Hash>>

fn put( &mut self, root: &[u8], bits: Bits<'_>, leaf: &[u8], ) -> GenericResult<Option<Hash>>

Recursively insert a bytes (in forms of Bits) and a leaf into the tree.

Optimisation in monotree is mainly to compress the path as much as possible while reducing the number of db accesses using the most intuitive model. As a result, compared to the standard Sparse Merkle Tree this reduces the number of DB accesses from N to log2(N) in both reads and writes.

Whenever invoked a put() call, at least, more than one put_node() called, which triggers a single hash digest + a single DB write. Compressing the path reduces the number of put() calls, which yields reducing the number of hash function calls as well as the number of DB writes.

There are four modes when putting the entries and each of them is processed in a recursive put() call. The number in parenthesis refers to the minimum of DB access and hash fn calls required.

• set-aside (1) Putting the leaf to the next node in the current depth.
• replacement (1) Replaces the existing node on the path with the new leaf.
• consume & pass-over (2+) Consuming the path on the way, then pass the rest of work to their child node.
• split-node (2) Immediately split node into two with the longest common prefix, then wind the recursive stack from there returning resulting hashes.

pub fn get( &mut self, root: Option<&Hash>, key: &Hash, ) -> GenericResult<Option<Hash>>

Get a leaf hash for the given root and key.

fn find_key( &mut self, root: &[u8], bits: Bits<'_>, ) -> GenericResult<Option<Hash>>

pub fn remove( &mut self, root: Option<&Hash>, key: &[u8], ) -> GenericResult<Option<Hash>>

Remove the given key and its corresponding leaf from the tree. Returns a new root hash.

fn delete_key( &mut self, root: &[u8], bits: Bits<'_>, ) -> GenericResult<Option<Hash>>

pub fn inserts( &mut self, root: Option<&Hash>, keys: &[Hash], leaves: &[Hash], ) -> GenericResult<Option<Hash>>

This method is indented to use the insert() method in batch mode. Note that inserts() forces the batch to commit.

pub fn gets( &mut self, root: Option<&Hash>, keys: &[Hash], ) -> GenericResult<Vec<Option<Hash>>>

This method is intended to use the get() method in batch mode.

pub fn removes( &mut self, root: Option<&Hash>, keys: &[Hash], ) -> GenericResult<Option<Hash>>

This method is intended to use the remove() method in batch mode. Note that removes() forces the batch to commit.

pub fn get_merkle_proof( &mut self, root: Option<&Hash>, key: &[u8], ) -> GenericResult<Option<Proof>>

Generate a Merkle proof for the given root and key.

fn gen_proof( &mut self, root: &[u8], bits: Bits<'_>, proof: &mut Proof, ) -> GenericResult<Option<Proof>>

fn encode_proof( &self, bytes: &[u8], right: bool, ) -> GenericResult<(bool, Vec<u8>)>

Trait Implementations

impl Clone for Monotree

fn clone(&self) -> Monotree

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Monotree

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

Formats the value using the given formatter.

impl Default for Monotree

fn default() -> Self

Returns the “default value” for a type.