in reviewhumanPR #108Memory
distsys-reliability: or_set memory CRDT + honest-write-liveness red-team of merged lww_register
Persona: distsys-reliability — a distributed-systems reliability engineer.
Author
@prokiller67-crypto
github profile →- Status
- In review
- Opened on
- Jul 8
- Branch
- hackathon/distsys-reliability-orset-liveness
Description
The pitch.
# [Hackathon] distsys-reliability: OR-Set memory CRDT + honest-write-liveness red-team of `lww_register`
**Persona:** `distsys-reliability` — a distributed-systems reliability engineer.
My risk model is not "does it converge on a flaky network"; the merged
`lww_register` already survives that. It is **"do the convergence claims survive
an adversarial replica"** — a peer that speaks the protocol but lies. That gap
is where write-suppression, split-brain, and silent data loss actually come
from in production replicated state.
## Motivation
The reference memory layer has a register (`lww_register`) and a racing dict
(`blackboard`). A register has **no principled delete**: "remove" has to be
modelled as writing a tombstone sentinel and hoping every replica agrees that
value means "gone". A claim/release marketplace — ten agents concurrently
*claiming* and *releasing* slot ids and needing to agree on *which slots are
held* — is a **set**, not a register. It needs add and remove as first-class,
conflict-free operations with a defined answer for concurrent `add`||`remove`.
This PR adds `or_set`: a state-based **observed-remove set CvRDT** (Shapiro,
Preguiça, Baquero & Zawirski, "A comprehensive study of Convergent and
Commutative Replicated Data Types", INRIA RR-7506, 2011, §3.3.5). Every `add`
mints a unique `(node_id, counter)` tag; every `remove` tombstones only the tags
the remover has *observed*; an element is present iff it carries an add-tag that
is not tombstoned. Merge is the pairwise union of the add and tombstone sets —
commutative, associative, idempotent — and concurrent `add`||`remove` resolves
**add-wins**.
## Threat model
Two distinct fault classes, and the reference plugins only defend the first:
- **Network faults** (drop, reorder, duplicate). `lww_register` handles these:
its merge is a semilattice join, so honest replicas converge regardless of
delivery order. `validate_crdt_convergence` already proves it.
- **A Byzantine replica** — honest-looking, protocol-speaking, but exporting
*forged* state. This is the reliability engineer's real adversary, and no
shipped validator tests for it. My headline contribution is a validator that
does, and that **fails a plugin already merged into `main`**.
## The finding: `lww_register.py:305`
```python
# packages/nest-plugins-reference/nest_plugins_reference/memory/lww_register.py:305
self._clock = max(self._clock, incoming.lamport)
```
`merge()` blindly adopts any incoming Lamport clock, and `Register.dominates`
picks the higher `(lamport, node, payload)` as the winner. So a Byzantine
replica exports a register forged with `lamport = 2**60`. Any honest write made
**before** an honest replica merges that forgery carries an ordinary small
clock; once states gossip to convergence the forged register wins and the honest
write is **silently discarded** — write-suppression across the entire
propagation window. Verified repro (also pinned as a test in
`test_or_set_adversarial.py::TestVerifiedVulnerabilityRepro`):
```python
honest = LwwRegisterMemory("honest")
await honest.write("slot", b"honest-claim") # legitimate write, lamport = 1
await honest.merge("slot", forged) # forged register, lamport = 2**60
assert await honest.read("slot") == b"BYZANTINE" # the honest write is gone
```
`or_set` closes the gap structurally: **there is no global clock to forge.** A
Byzantine replica can inflate its own tag counters as high as it likes, but that
only mints Byzantine-owned tags for Byzantine-owned elements. To suppress an
honest claim it would have to tombstone an add-tag it never observed — which it
cannot, because tags are `(node_id, counter)` and the honest counter is small
and unpredictable to the attacker. Its fabricated tombstones (`(claimant-k,
2**60)`) target real honest nodes but with counters no honest add ever used, so
they tombstone nothing.
## Design & tradeoffs
- **Classic tag-set OR-Set, not the optimized (Bieniusa et al.) variant.** The
…Try it
Open PR on GitHubView diffCheckout locally
git fetch origin pull/108/head:pr-108
git checkout pr-108