Crate merkle_tree_db

merkle-tree-db is a highly flexible library for working with merkle trees. It supports persistance over any key-value database backend. The merkle tree data structures are stored as sparse merkle trees allowing for efficient lookups, updates and persistence. The library is generic over the hasher used and the depth of the tree. Sparse merkle trees that leverage circuit friendly hash functions (e.g Poseidon, Rescue-Prime) are performant in a ZKP setting and as such this library can serve this purpose. This library supports both indexed merkle trees (max depth 64) and keyed (addressable) merkle trees (max depth usize::MAX).

Structs

IndexTreeDB

An immutable merkle tree db that uses a u64 index to specify the leaves in the tree. Wraps a KeyedTreeDB and converts a u64 index to a Key of the appropriate depth to access the underlying TreeDB.

IndexTreeDBBuilder

Used to construct an IndexTreeDB

IndexTreeDBMut

A mutable merkle tree db that uses a u64 index to specify the leaves in the tree. Wraps a KeyedTreeDBMut and converts a u64 index to a Key of the appropriate depth to access the underlying TreeDB.

IndexTreeDBMutBuilder

Used to construct a IndexTreeDBMut

Recorder

Recorder to record database reads.

StorageProof

A proof that some set of key-value pairs are included in a sparse merkle tree.

TreeDB

An immutable merkle tree db that uses a byte slice key to specify the leaves in the tree.

TreeDBBuilder

Used to construct a TreeDB

TreeDBMut

A mutable merkle tree db that uses a byte slice key to specify the leaves in the tree.

TreeDBMutBuilder

TreeDBMutBuilder use to build a TreeDBMut

Enums

TreeError

Errors associated with the tree. These errors are returned by the tree methods and wrap errors returned by the underlying components, these include:

Traits

HashDB

Trait modelling datastore keyed by a hash defined by the Hasher.

HashDBRef

Trait for immutable reference of HashDB.

Hasher

Trait describing an object that can hash a slice of bytes. Used to abstract other types over the hashing algorithm. Defines a single hash method and an Out associated type with the necessary bounds.

IndexTree

A immutable index-value datastore implemented as a database-backed sparse merkle tree.

IndexTreeMut

A mutable index-value datastore implemented as a database-backed sparse merkle tree.

KeyedTree

A immutable key-value datastore implemented as a database-backed sparse merkle tree.

KeyedTreeMut

A mutable key-value datastore implemented as a database-backed sparse merkle tree.

TreeRecorder

A trait that allows recording of tree nodes.

Type Aliases

DBValue

The type of value stored in the database backend.