merkle-clock
Overview
merkle-clock is a cryptographic causal ordering primitive for distributed systems. Unlike Lamport timestamps (which can't detect concurrency) or vector clocks (which require O(n) metadata), Merkle Clocks produce a content-addressed DAG where every event's identity is its BLAKE3 hash of (payload, parent hashes). This makes the entire causal history tamper-evident by construction — any change in payload or parent links produces a different hash. It is the foundational data structure behind protocols like hashgraph and provides deterministic partial ordering without a central coordinator.
Architecture & Design
A pure Rust library with a single dependency (blake3). The DAG enforces acyclicity on insertion and supports delta-state CRDT merge — two replicas synchronise by exchanging only the minimal set of missing events via BFS-based delta computation. A memoized ReachabilityIndex provides O(1) causal-order lookups, updated incrementally on every insert. Serde support uses human-readable hex strings for JSON and raw bytes for binary formats like CBOR.
Technical Capabilities
- 01
Content-Addressed Identity: Every event is its BLAKE3 hash of (payload, parents) — tamper-evident by construction.
- 02
Causal Ordering: Determine Before/After/Concurrent/Equal for any two events via bidirectional ancestor BFS or O(1) index lookup.
- 03
Delta-State Synchronisation: Exchange only missing events between replicas; merge is commutative, idempotent, and associative (property-based tested).
- 04
Incremental Reachability Index: Precompute ancestor sets with memoized DFS; index stays valid on insert without full rebuild.
- 05
Cycle Detection: Acyclicity enforced on insertion even against Byzantine or corrupted parent references.