Crate mssmt

Merkle Sum Sparse Merkle Tree implementation

This crate provides an implementation of a Merkle Sum Sparse Merkle Tree (MSSMT) based on this implementation https://github.com/lightninglabs/taproot-assets/tree/main/mssmt, which combines the properties of both Merkle Sum Trees and Sparse Merkle Trees.

The tree supports:

• Efficient sparse storage
• Sum aggregation at each level
• Cryptographic verification
• Flexible storage backend through the Db trait

Structs

Branch

A branch is a node that has exactly 2 children. Those children can either be any type of Node. Those nodes hold the sum of all their descendants.

CompactLeaf

A compact leaf is a leaf doesn’t require all the empty parts of the path to be inserted. When required we can extract all the branches on that path. The node hash is the hash of the node at the top of the path.

CompactMSSMT

A compact Merkle Sum Sparse Merkle Tree implementation.

CompressedProof

A compressed merkle proof for a given key. We don’t store all the nodes if they are empty.

ComputedNode

A computed node. Useful for traversing the tree without reconstructing branches which contains their children and are expensive to reconstruct.

EmptyLeaf

Represents an empty leaf in the tree. Those leaves have no value and hold 0 as sum value.

EmptyTree

Helper struct to create an empty mssmt.

MSSMT

Merkle sum sparse merkle tree.

MemoryDb

A simple in-memory database implementation for testing

Proof

A merkle proof for a given key.

Enums

Leaf

Node

All possible nodes in the tree.

TreeError

Error type for tree operations

Traits

Db

Store for the tree nodes

Hasher

Simple hash trait required to hash the nodes in the tree

ThreadSafe

Thread safety marker trait

Functions

walk_up

Walk up the tree from the node to the root node.