Crate starling 

Merkle Binary Indexed Tree

Introduction

This module implements MerkleBIT with an attached storage module. The implemented HashTree and RocksTree structures allow use with persistence in memory and storage respectively. Write operations are batched together and committed at the end of each insert op. The MerkleBit API abstracts all actions related to maintaining and updating the storage tree. The public APIs are

• new
• from_db
• get
• insert
• remove
• generate_inclusion_proof
• get_one
• insert_one
• and the associated function verify_inclusion_proof.

After each call to either insert or insert_one, a new root hash will be created which can be later used to access the inserted items.

Internal Structure

Internally, the MerkleBit is composed of a collection of trait structs which implement the Branch, Leaf, and Data nodes of the tree.

A Branch node contains first a split_index which indicates which bit of a given hash should be used to traverse the tree. This is an optimisation that makes this a sparse merkle tree. It then contains pointers to either the one side of the tree or the zero side of the tree. Additionally, a branch contains a copy of the key used during creation to determine if a branch should be inserted before it, and a count of the nodes under that branch.

A Leaf node contains an associated key for comparison, and a pointer to a Data node for retrieving information regarding access to the data. This is separate from the Data node for the purpose of only accessing data information if data should be retrieved.

A Data node contains the actual information to be retrieved. Data nodes can be arbitrary in size and the only restriction is that the data must be serializable and deserializable.

To illustrate these concepts, please refer to the diagram below:

                                                ----------------------
                                branch  --->    | split_index: usize |
                                  |             | zero: [u8]         |
      ----------------           / \            | one:  [u8]         |
      | key: [u8]    |          /   \           | count: u64         |
      | data: [u8]   | <----  leaf   leaf       | key:   [u8]        |
      ----------------         |                ----------------------
                               |
                               V
                             data
                               |
                               V
                        ------------------
                        | value: Vec<u8> |
                        ------------------

The MerkleBIT can be extended to support a wide variety of backend storage solutions given that you make implementations for the Branch, Leaf, and Data traits.

Modules

constants

Defines constants for the tree.

hash_tree

An implementation of the MerkleBIT with a HashMap backend database.

merkle_bit

Contains the actual operations of inserting, getting, and removing items from a tree.

traits

Contains the traits necessary for tree operations

tree

Contains a collection of structs for representing locations within the tree.

tree_db

Contains a collection of structs for implementing tree databases.

tree_hasher

Contains a collection of structs for implementing hashing functions in the tree.

utils

Contains a collection of useful structs and functions for tree operations.

Type Aliases

Array

Alias for a fixed sized array