bm

Binary merkle tree implementation with support of merkleization, de-merkliezation and in-place tree modification.

SimpleSerialize (ssz) compliant.
Garbage collection support.

Concepts

We distingish Intermediate values and End values so that implementations can better handle preimage attacks.

Intermediate: a node that has two direct children left and right.
End: a node without any child.

Backend

The library bm provides two basic backends:

InMemoryBackend: a backend that stores all merkle nodes in-memory.
NoopBackend: dummy backend that discards any set operation, and return error on any get operation. This is useful if you're interested in the merkle root but does not actually need the merkle tree.

In-place Tree Modification

You can use bm library for in-place tree modification. To use the ssz compliant variant, choose new_with_inherited_empty when creating the backend and set List, PackedList's maximum length to an approriate value.

Raw: Raw binary merkle tree that allows directly operating on generalized merkle index.
List: Variable-sized vector list.
Vector: Fixed-sized tuple list.
PackedList: Packed variable-sized vector list.
PackedVector: Packed fixed-sized tuple list.

Merkleization

You can use bm-le library for merkleization. It is ssz compatibile and with some extensions to make it work better in certain environments. If you're only interested in the merkle root, use tree_root function. Otherwise, use IntoTree trait.

In order to merkleize vectors and lists, use FixedVec and VariableVec wrapper type. To merkleize bitvectors and bitlists, use FixedVec<bool> and VariableVec<bool>.

Demerkleization

Because some information are not available on type (like vector's length, and vector and list's maximum length), we use three traits for demerkleization support -- FromTree, FromListTree and FromVectorTree.

Basic Usage

See tests/ssz.rs for basic usage examples.