🎒 Monad Nomad

Subduction

Created 5 min read

CAUTION

Early release preview. Unstable API. Not for production use.

Motivation

Local-first applications need to sync CRDT data between peers without relying on a central server. This is already tricky — but it gets harder when the data is encrypted and you can’t inspect plaintext during sync. Subduction solves this by reconciling state using metadata (content hashes and fingerprints) rather than requiring decryption.

The protocol is also CRDT-agnostic. It was originally built for Automerge, but the core sync layer doesn’t assume anything about the CRDT it’s carrying.

Key Design Points

  • Encryption-friendly — sync never touches plaintext
  • Transport-agnostic — WebSocket, HTTP long-poll, and Iroh (QUIC) out of the box
  • Capability-based auth — separate connection policy (can this peer connect?) and storage policy (can this peer access this document?), with Keyhive integration
  • Mutual authentication — Ed25519 signed challenge/response handshake with nonce-based replay protection
  • no_std compatible — protocol logic works in Wasm and embedded environments
  • Idempotent — receiving the same data twice is always safe
  • Multi-platform — native Rust, browser and Node.js via Wasm, CLI for server/client/relay modes

Sedimentree

The core data structure is the Sedimentree — essentially an LSM tree adapted for CRDT graph data. Like a traditional LSM tree, it compacts small writes into progressively larger, more compressed layers. The twist is that compaction has to be deterministic across replicas — two peers that have never communicated need to arrive at the same fragment boundaries. Sedimentree achieves this by using the number of leading zero bytes in each item’s BLAKE3 content hash as the depth metric. Since the hash is a property of the content itself, any peer with the same data will partition it the same way.

Depth 0: ██ █ ███ █ ██ █ █ ███ ██  (many small fragments)
         ↓ compaction
Depth 1: ██████ ██ ████████ ████   (fewer, larger fragments)
         ↓ compaction
Depth 2: ███████████████████████   (fewest, most compressed)

Peers compare compact fingerprint summaries (SipHash-2-4, 8 bytes per item) at coarse layers first, then drill down to find what’s missing. This makes the initial diff ~75% smaller than sending full 32-byte digests. After the batch reconciliation, peers subscribe for real-time incremental forwarding of new commits.

Handshake

Before syncing, peers mutually authenticate via a two-message Ed25519 handshake. Either side can initiate — the protocol is symmetric.

sequenceDiagram
    participant I as Initiator
    participant R as Responder

    I->>R: Signed‹Challenge› { audience, timestamp, nonce }
    Note right of R: Verify signature
    Note right of R: Validate audience & timestamp
    Note right of R: Check nonce (replay protection)

    R->>I: Signed‹Response› { challenge_digest, timestamp }
    Note left of I: Verify signature
    Note left of I: Validate challenge_digest

    Note over I,R: Connection Established

Both sides learn each other’s peer ID from the signature’s verifying key. The nonce and timestamp prevent replay attacks; a nonce cache with lazy GC (4 buckets x 3 min = 12 min window) handles nonce tracking without a background task.

The handshake only establishes identity (“who is connecting?”). Whether the peer is allowed to connect is decided separately by the connection policy.

1.5 RTT Batch Reconciliation

Batch sync reconciles the complete state of a sedimentree between two peers in 1.5 round trips. Instead of exchanging full 32-byte digests, the requester computes compact 8-byte SipHash-2-4 fingerprints with a random per-request seed. Both sides fingerprint their items with the same seed and diff on u64 values.

sequenceDiagram
    participant A as Requester
    participant B as Responder

    A->>B: BatchSyncRequest { id, fingerprint_summary, subscribe }
    Note right of B: Recompute fingerprints with same seed
    Note right of B: Set diff (both directions)

    B->>A: BatchSyncResponse { data you're missing, fingerprints I need back }
    Note left of A: Store received commits, fragments, blobs

    A-->>B: Fire-and-forget: requested commits & fragments
    Note right of B: Store received data

    Note over A,B: Both sides synchronised (1.5 RT)

The third leg is fire-and-forget — storage is idempotent, and any missed data is caught on the next sync cycle. Confirmation is just another sync: if the diff comes back empty, the previous round succeeded.

Subscriptions

After the initial batch sync, peers can opt into real-time incremental updates by subscribing as part of the batch sync request. This bundles subscription with sync so the peer has current state before receiving live updates.

When a new commit or fragment arrives, the server:

  1. Looks up subscribers for that sedimentree
  2. Filters by authorisation
  3. Forwards to each authorised subscriber’s connections

Subscriptions are tracked per-peer (not per-connection), so multiple tabs/windows see the same updates. When a peer’s last connection closes, they’re automatically removed from all subscription sets.

Revocation is handled out-of-band: the peer learns about access changes via Keyhive, and Subduction simply stops forwarding when the auth check fails. No explicit revocation message needed.

See Also

  • Keyhive — the auth layer Subduction integrates with
  • Automerge — the primary target CRDT
  • Notes on Writing Wasm — patterns I developed while writing the Wasm bindings
  • wasm_refgen — a macro crate extracted from the Subduction Wasm work

Graph View

Backlinks