Skip to content
Crypto.world

Research

did:crdt: Coordination-Free Decentralised Identifiers via Signed CRDTs

Every production DID method faces a trade-off: to let a DID document change over time it coordinates through consensus (blockchains, with fees and latency), or to avoid consensus it freezes the…

did:crdt: Coordination-Free Decentralised Identifiers via Signed CRDTs
arXiv
2606.16223
Published
2026-06-15
Authors
Hugo O'Connor, Claire Barnes

AI summary

Overview

Research area: Decentralised identity (W3C Decentralised Identifiers), distributed systems (Conflict-Free Replicated Data Types, the CALM Theorem), and applied cryptography.

Technical level: Advanced. The paper assumes familiarity with join-semililattices, CRDT primitives, causal consistency and signature schemes, though the prose explains the reasoning behind each choice.

Scope (one sentence): The paper specifies and evaluates did:crdt, a W3C DID Core-aligned method in which each DID document field is a signed CRDT, so multi-device identity updates converge without a ledger, sequencer or any global total order.

What This Paper Is About

Every production DID method faces a trade-off: to let a DID document change over time it coordinates through consensus (blockchains, with fees and latency), or to avoid consensus it freezes the document (did:key, did:peer). The authors argue that no existing method simultaneously achieves no-consensus operation, offline mutation, cryptographic authorisation and W3C DID Core alignment. did:crdt targets all four by modelling each document field as a CRDT whose merge is commutative, associative and idempotent, so that replicas which have seen the same signed deltas reach the same document in any arrival order, while application-layer signatures separate authorisation from ordering.

Key Contributions

  1. A seven-field CRDT composition for the W3C DID document data model, mapping each field to a CRDT type (2P-Set for verification methods, OR-Set/ORSWOT for services, LWW-Map for metadata, Max-Register for key rotation, G-Set for credential revocations, boolean latch for deactivation) such that the product satisfies commutativity, associativity and idempotence.
  2. The did:crdt method specification: content-addressed identifier derivation via BLAKE3-256 over the genesis tuple, an eight-operation typed delta vocabulary, and deterministic concurrent-merge semantics.
  3. A system and threat model plus security analysis covering genesis attacks, delta replay, rotation races, state-size DoS, creation-flood sybil resistance, discovery-layer availability and the limits of key-compromise recovery, with Byzantine fault tolerance established for the signed-delta and verified-bundle replay paths and explicitly not claimed for the unauthenticated state-merge optimisation.
  4. A Rust reference implementation (no unsafe, WASM-compatible, ~3,700 non-blank lines in the pure core) with property-based convergence tests over randomised delta sequences and microsecond-scale merge latency measurements.

Main Findings

  • Coordination is removed rather than hidden: each DID document state is the product of seven independent CRDT fields, so by the CALM Theorem the state-merge path is confluent; the signed-delta path requires only causal delivery, which the authors stress is strictly weaker than the consensus-equivalent total-order broadcast ledgers need.
  • Identifiers are content-addressed and offline-creatable: the DID is the lowercase hex encoding of BLAKE3-256 over the tuple (τ₀, op₀, signer_key), hashed before the DID exists, so creation needs no network, registry or synchronisation and a given genesis delta deterministically yields the same DID.
  • Order-sensitivity is confined to admission, not merge: validating a delta is a five-step gate returning a three-valued result (Unknown/Valid/Invalid); a delta whose parents are missing is held pending rather than rejected, so any delivery order converges. Authorisation is checked against the delta's causal past, not current state.
  • Metadata timestamps are the weakest integrity surface: LWW-Map orders by the HLC physical-millisecond component (the node_id derived from the public key secures only the tiebreaker), so a Byzantine but authorised signer can inflate its timestamp to dominate a metadata key within the HLC skew bound; the paper recommends the OR-Set field where tamper-evident concurrency is needed.
  • Key compromise yields containment, not recovery: authorisation is flat, so any non-revoked key can sign any operation; revocation halts future misuse but cannot undo authorised writes, because grow-only sets retain attacker keys and the deactivation latch is irreversible. The authors state this is no worse than single-controller ledger methods like did:ethr but weaker than Sidetree/did:ion, which separate update and recovery keys.
  • Byzantine fault tolerance is path-dependent: it holds for live gossip ingest (signature-verified at the trust boundary) and for merge_verified_bundle (replay of a content-addressed bundle through full checks), but the unauthenticated merge_state API is a trusted-domain optimisation that voids Byzantine safety if used with an untrusted source.
  • Cost and latency contrast sharply with ledgers: the paper cites did:ethr at $0.066 per operation and 12.9 s, did:hedera at $0.00015 and 4.2 s (from Satybaldy et al.), and XRPL at $0.000026/op, against zero fees and <90 μs local merge for did:crdt, with hosting of $4–8/month versus $30–100.
  • Merge is fast and state is small: median merge latencies (Criterion 0.5, release + LTO, Apple M2 3.49 GHz) are 5–8 μs for small documents (1 key/1 service), 11–14 μs medium (10/10) and 70–88 μs large (100/100), including Merkle-DAG admission but not signature verification; every small-document operation exceeds 140 K ops/s. Measured state RAM is 1.0 KiB, 4.4 KiB and 37.9 KiB respectively, so a 1 GiB node holds roughly 1.0 M small DIDs' state.
  • Test coverage is property-based as well as functional: 262 functional tests (276 with service, 314 with sync), proptest runs of 256 cases each checking CRDT laws, convergence tests over 50/30 concurrent deltas, all 24 permutations of four deltas producing byte-identical state, and roughly 4 M-iteration fuzzing of deserialisation with no panics.
  • Fleet-scale economics favour the method: at roughly 1,440 deltas/day per unit, a 10,000-sensor fleet on XRPL would cost $137 K/year with per-mutation connectivity, whereas did:crdt runs it offline fee-free, at the cost of retained history of roughly 3–7 GB/day pending compaction.
  • Two limits are stated openly: there is no global "latest" (the monotone versionId orders states by delta inclusion but absolute recency needs a freshness response from a well-connected peer), and sybil resistance is designed but unimplemented (a 20-bit genesis proof-of-work at roughly 0.5 s per DID and roughly 10⁶× batch-flood cost, per-IP creation limits, optional invitation codes).

Methodology in Plain English

The authors start from a theoretical result, the CALM Theorem, which says that if a computation only ever adds information and never retracts it, replicas can run it independently and still agree once they have seen the same inputs. They take the W3C DID document and break it into parts that behave this way: a set of keys that can only be added, a set of revocations that can only be added, services that behave as add-wins, metadata as last-writer-wins with a clock and a key-derived tiebreaker, a rotation counter that keeps the highest value, and a deactivation flag that behaves like a latch. Because the merge rules for these parts are commutative, associative and idempotent, merging them in any order gives the same result.

Ordering is handled separately from authorisation. Every change is a small signed record carrying its author's timestamp, the hashes of the changes it builds on, an operation type and a signature. Because each record names its parents by hash, the history forms a Merkle DAG, so a receiver can reconstruct the required order itself: changes that arrive too early are held rather than rejected. The authors then work through the attack surface, run a Rust implementation through property-based and convergence tests (including simulated partitions and a live two-endpoint gossip test), and benchmark merge latency and memory footprint on small, medium and large documents.

Why This Matters

Impact on research: The paper is a worked demonstration that the CALM/CRDT argument extends to the DID document itself, not just to identity-adjacent data, and it draws a careful line between lattice monotonicity (which convergence needs) and observable monotonicity (which several of its fields deliberately break). It also names the exact price of dropping consensus — no canonical state, so a compromised key's writes merge rather than being adjudicated away — which is a useful framing for subsequent work on threshold-authorised identity.

Real-world applications:

  • Disaster response: the motivating scenario is an organisational DID co-managed by several authorised devices at incident command, evolving offline across split sites (registering radios, rotating a lost key, enrolling a replacement) and converging when a channel reappears, in contrast to centrally issued credentials such as PIV-I/FRAC and FEMA's central revocation update with an 18-hour window.
  • IoT and sensor fleets: key-rotating devices producing roughly 1,440 deltas/day per unit can update offline at zero marginal cost, avoiding per-mutation connectivity and ledger fees.
  • Multi-device identity wallets: a subject controlling several intermittently connected devices gets persistent identities with a full key lifecycle, which static methods like did:key and did:peer cannot provide.
  • Air-gapped and constrained environments: deltas are 200–500 bytes and the core is storage-agnostic and WASM-compatible, so transfers can go over QR, NFC, Bluetooth or USB, and the core can be embedded via FFI on mobile.

Industry relevance: the work targets W3C DID Core alignment and a DID Method Registry submission, and speaks directly to deployments weighing ledger fees and latency against offline operation. The authors note decentralised identity is identified as critical 6G infrastructure (citing Garzón et al.), and are explicit that the method is a poor fit where an operation's legal effect depends on a single authoritative order (e.g. eIDAS, where signature validity turns on revocation timing) or where an identifier must be publicly discoverable with no prior relationship.

Future Directions

  • Stronger authorisation: M-of-N threshold signing for sensitive operations, or a recovery-key policy, to bound single-key compromise — the gap the paper identifies as fundamental to its flat authorisation model.
  • Compact state: Merkle-inclusion proofs plus checkpoint compaction to bound cumulative log growth, which is currently unbounded (200–500 bytes per update, roughly 3–7 GB/day in the sensor-fleet example).
  • Completing the networking stack: durable persistence (a SQLite layer is specified but unbuilt), the sybil-resistance layers of the security section, hardened discovery against record erasure, and wide-area convergence measurement — the paper notes its latency figures exclude the not-yet-measured availability layer.
  • Formal and standards work: formal verification of the merge laws, plus the W3C DID conformance suite and DID Method Registry submission, since the paper claims alignment with DID Core rather than certified compliance.

Target Audience

Researchers and engineers working on self-sovereign identity and DID methods, distributed-systems practitioners interested in coordination-free designs and CALM/CRDT reasoning, and implementers who need a concrete, testable architecture for multi-device, offline-capable identity with signed deltas and Merkle-DAG history. Security reviewers evaluating the threat model will find the explicit statement of what Byzantine fault tolerance does and does not cover particularly useful; readers new to CRDTs or DID Core will find the framing accessible but should expect to consult the cited background material for the underlying theory.

Authors’ abstract

Existing Decentralised Identifier (DID) methods require coordination, an agreed global order of operations, to update a DID document: blockchain-anchored methods incur fees and latency; lightweight peer methods (did:key, did:peer) offer no update mechanism; and Sidetree methods still require blockchain ordering for finality. We present did:crdt, a DID method that targets W3C DID Core and removes the need for coordination entirely: there is no ledger, no sequencer, and no…

The full abstract on arXiv
Read the original paper