Struct MerkleSearchTree

pub struct MerkleSearchTree<K, V, H = SipHasher, const N: usize = 16> { /* private fields */ }

An implementation of the Merkle Search Tree as described in Merkle Search Trees: Efficient State-Based CRDTs in Open Networks.

This implementation stores only keys directly in the tree - hashes of values are retained instead of the actual value. This allows greatest flexibility, as the user can choose the most appropriate key/value storage data structure, while using the MST strictly for anti-entropy / Merkle proofs.

Merkle Search Trees

In addition to the normal hash & consistency properties of a regular Merkle/hash tree, a MST is a searchable balanced B-tree with variable, probabilistically bounded page sizes and a deterministic representation irrespective of insert order - these properties make a MST a useful data structure for efficient state-based CRDT replication and anti-entropy.

Keys are stored in sort order (from min to max) in an MST. If monotonic keys are inserted, a minimal amount of hash re-computation needs to be performed as the nodes & pages for most of the older keys remain unchanged; this reduces the overhead of anti-entropy as fewer intermediate hashes need recomputing and exchanging during reconciliation.

Portability & Compatibility

For two MerkleSearchTree to be useful, both instances must produce identical hash digests for a given input. To do so, they must be using the same Hasher implementation, and in turn it must output a deterministic hash across all peers interacting with the MerkleSearchTree.

For ease of use, this library uses the standard library Hash trait by default to hash key and value types. The documentation for the trait warns it is not guaranteed to produce identical hashes for the same data across different compilation platforms and Rust compiler versions.

If you intend to interact with peers across multiple platforms and/or Rust versions, you should consider implementing a fully-deterministic Hasher specialised to your key/value types that does not make use of the Hash trait for correctness.

Any change to the underlying hash construction algorithm implemented in this crate that would cause existing hashes to no longer match will not occur without a breaking change major semver version bump once this crate reaches stability (>=1.0.0).

Lazy Tree Hash Generation

Each page within the tree maintains a cache of the pre-computed hash of itself, and the sub-tree rooted from it (all pages & nodes below it). Successive root hash queries will re-use this cached value to avoid hashing the full tree each time.

Upserting elements into the tree invalidates the cached hashes of the pages along the path to the leaf, and the leaf page itself. To amortise the cost of regenerating these hashes, the affected pages are marked as “dirty”, causing them to be rehashed next time the root hash is requested. This allows hash regeneration to be occur once per batch of upsert operations.

Example

use merkle_search_tree::MerkleSearchTree;

let mut t = MerkleSearchTree::default();
t.upsert("bananas", &"great");
t.upsert("plátano", &"muy bien");

// Obtain a root hash / merkle proof covering all the tree data
let hash_1 = t.root_hash().to_owned();
println!("{:?}", hash_1.as_ref());

// Modify the MST, reflecting the new value of an existing key
t.upsert("bananas", &"amazing");

// Obtain an updated root hash
let hash_2 = t.root_hash().to_owned();
println!("{:?}", hash_2);

// The root hash changes to reflect the changed state
assert_ne!(hash_1.as_ref(), hash_2.as_ref());

Implementations

impl<K, V, H, const N: usize> MerkleSearchTree<K, V, H, N>

pub fn new_with_hasher(hasher: H) -> Self

👎Deprecated since 0.8.0: please use Builder::with_hasher instead

Initialise a new MerkleSearchTree using the provided Hasher of keys & values.

pub fn root_hash_cached(&self) -> Option<&RootHash>

Return the precomputed root hash, if any.

This method never performs any hashing - if there’s no precomputed hash available, this immediately returns None. This operation is O(1).

If this returns None, call MerkleSearchTree::root_hash() to regenerate the root hash.

pub fn in_order_traversal<'a, T>(&'a self, visitor: &mut T)

where T: Visitor<'a, N, K>,

Perform a depth-first, in-order traversal, yielding each Page and Node to visitor.

An in-order traversal yields nodes in key order, from min to max.

pub fn node_iter(&self) -> impl Iterator<Item = &Node<N, K>>

Iterate over all Node in the tree in ascending key order.

This method can be used to inspect the keys stored in the tree:

let mut t = MerkleSearchTree::default();
t.upsert("bananas1", &42);
t.upsert("bananas3", &42);
t.upsert("bananas4", &42);
t.upsert("bananas2", &42);

// Collect the keys within the tree
let keys = t.node_iter().map(|v| *v.key()).collect::<Vec<_>>();

// Nodes are yield in ascending key order:
assert_eq!(
    keys.as_slice(),
    ["bananas1", "bananas2", "bananas3", "bananas4"]
)

impl<K, V, H, const N: usize> MerkleSearchTree<K, V, H, N>

where K: AsRef<[u8]>,

pub fn root_hash(&mut self) -> &RootHash

Generate the root hash if necessary, returning the result.

If there’s a precomputed root hash, it is immediately returned.

If no cached root hash is available all tree pages with modified child nodes are rehashed and the resulting new root hash is returned.

pub fn serialise_page_ranges(&self) -> Option<Vec<PageRange<'_, K>>>

where K: PartialOrd,

Serialise the key interval and hash covering each Page within this tree.

Page hashes are generated on demand - this method returns None if the tree needs rehashing (call MerkleSearchTree::root_hash() and retry).

Performs a pre-order traversal of all pages within this tree and emits a PageRange per page that covers the min/max key of the subtree at the given page.

The first page is the tree root, and as such has a key min/max that equals the min/max of the keys stored within this tree.

Reference vs. Owned

This method borrows the underlying keys within the tree - this avoids cloning the keys that form the page bounds when generating the PageRange to maximise performance, however this also prevents the caller from mutating the tree whilst holding onto the serialised pages (an immutable reference to the tree).

If the key type (K) implements Clone, a set of owned serialised pages that do not borrow from the tree can be created by constructing a PageRangeSnapshot from the returned PageRange array:

let mut t = MerkleSearchTree::default();
t.upsert("bananas", &42);

// Rehash the tree before generating the page ranges
let _ = t.root_hash();

// Generate the hashes & page ranges
let ranges = t.serialise_page_ranges().unwrap();

// At this point, attempting to insert into the tree fails because the
// tree is already borrowed as immutable.
//
// Instead clone all the keys and generate a snapshot:
let snap = PageRangeSnapshot::from(ranges);

// And the tree is free to be mutated while `snap` exists!
t.upsert("plátanos", &42);

// The `snap` yields `PageRange` for iteration:
assert_eq!(diff(snap.iter(), snap.iter()), vec![]);

impl<K, V, H, const N: usize> MerkleSearchTree<K, V, H, N>

where K: PartialOrd, H: Hasher<N, K> + Hasher<N, V>,

pub fn upsert(&mut self, key: K, value: &V)

Add or update the value for key.

This method invalidates the cached, precomputed root hash value, if any (even if the value is not modified).

Value Hash

The tree stores a the hashed representation of value - the actual value is not stored in the tree.

Trait Implementations

impl<K: Clone, V: Clone, H: Clone, const N: usize> Clone for MerkleSearchTree<K, V, H, N>

fn clone(&self) -> MerkleSearchTree<K, V, H, N>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug, H: Debug, const N: usize> Debug for MerkleSearchTree<K, V, H, N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for MerkleSearchTree<K, V>

fn default() -> Self

Returns the “default value” for a type.