#merkle #tree #crdt #hash #anti-entropy


A data structure for efficient state-based CRDT replication and anti-entropy

10 releases (breaking)

0.7.1 Oct 18, 2023
0.6.0 Aug 23, 2023
0.4.0 Jul 26, 2023

#173 in Cryptography

Download history 14/week @ 2023-08-09 7/week @ 2023-08-16 204/week @ 2023-08-23 1576/week @ 2023-08-30 1481/week @ 2023-09-06 1859/week @ 2023-09-13 2061/week @ 2023-09-20 2225/week @ 2023-09-27 1619/week @ 2023-10-04 1997/week @ 2023-10-11 2183/week @ 2023-10-18 1976/week @ 2023-10-25 1589/week @ 2023-11-01 2219/week @ 2023-11-08 2208/week @ 2023-11-15 1563/week @ 2023-11-22

7,931 downloads per month


3.5K SLoC

crates.io docs.rs

Merkle Search Tree

This crate implements a Merkle Search Tree as described in the 2019 paper Merkle Search Trees: Efficient State-Based CRDTs in Open Networks by Alex Auvolat & François Taïani.[^cite]

When paired with CRDT-based value types, a Merkle Search Tree can act as an efficient anti-entropy primitive, allowing independent replicas to concurrently modify data within the tree with deterministic and eventual convergence across all peers.

See MerkleSearchTree documentation.

Use It

use merkle_search_tree::{MerkleSearchTree, diff::diff};

// Initialise a tree using the default configuration, appropriate for most uses.
let mut node_a = MerkleSearchTree::default();

// Upsert values into the tree.
// For the MST construct to be a CRDT itself, the values stored into the tree
// must also be CRDTs (or at least, have deterministic conflict resolution).
// Here the MST is used as an add-only set (a trivial CRDT) by using () as the
// key values.
node_a.upsert("bananas", &());
node_a.upsert("plátanos", &());

// Another node has differing keys.
let mut node_b = MerkleSearchTree::default();
node_b.upsert("donkey", &());

// The MST root hash can be used as an efficient consistency check (comparison
// is O(1) in space and time).
// In this case, both trees are inconsistent w.r.t each other, which is
// indicated by their differing root hashes.
assert_ne!(node_a.root_hash(), node_b.root_hash());

// Generate compact summaries of the MST content, suitable for transmission over
// the network, and use it to compute the diff between two trees.
let diff_range = diff(

// In this case, node B can obtain the missing/differing keys in node A by
// requesting keys within the computed diff range (inclusive):
assert_matches::assert_matches!(diff_range.as_slice(), [range] => {
    assert_eq!(range.start(), &"bananas");
    assert_eq!(range.end(), &"plátanos");


Operations against a Merkle Search Tree are fast, executing against millions/billions of keys per second:

Key Count Insert All Keys Generate Root Serialise Diff (consistent) Diff (inconsistent)
100 keys 7µs 3µs 98ns 152ns 261ns
1,000 keys 92µs 39µs 847ns 577ns 4µs
10,000 keys 1356µs 398µs 10µs 4µs 36µs
100,000 keys 17ms 3ms 112µs 26µs 287µs

The above measurements capture the single-threaded performance of operations against a tree containing varying numbers of keys on a M1 MacBook Pro.

  • Insert All Keys: insert the N keys listed for the row into an empty tree
  • Generate Root: regenerate the root hash of a modified tree
  • Serialise: encode the tree into a diff format for network communication
  • Diff (consistent): diff generation for identical trees (no differing ranges)
  • Diff (inconsistent): diff generation for a fully inconsistent tree

The benchmarks to generate these numbers are included in this repo (run cargo bench).


This crate is extensively tested using randomised fuzzing & property testing to validate correctness, and ensure no panics occur in release builds.

[^cite]: Alex Auvolat, François Taïani. Merkle Search Trees: Efficient State-Based CRDTs in Open Networks. SRDS 2019 - 38th IEEE International Symposium on Reliable Distributed Systems, Oct 2019, Lyon, France. pp.1-10, ⟨10.1109/SRDS.2019.00032⟩. ⟨hal-02303490⟩