Expand description
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
Defines constants for the tree.
An implementation of the MerkleBIT
with a HashMap
backend database.
Contains the actual operations of inserting, getting, and removing items from a tree.
Contains the traits necessary for tree operations
Contains a collection of structs for representing locations within the tree.
Contains a collection of structs for implementing tree databases.
Contains a collection of structs for implementing hashing functions in the tree.
Contains a collection of useful structs and functions for tree operations.
Type Definitions
Alias for a fixed sized array