# What happens when an instance accepts a memory write it cannot later prove: Byzantine equivocation in cross-org CRDT agent memory **Date of Record:** 2026 November 17 **Scope:** Applies to shared agent-memory substrates where two or more organizations replicate a conflict-free (join-semilattice) state and where individual replicas may be operated by mutually untrusting parties. Does not apply to single-org CRDT deployments, to leader-based consensus logs, or to systems where all replicas are covered by one administrative trust domain. ## Core Distinction A CRDT guarantees *convergence* — every replica that observes the same set of operations arrives at the same state. It does **not** guarantee *agreement on the set of operations*, and it says nothing about whether an operation a replica accepted was ever authored by the party it claims to be authored by. In cross-org agent memory, the dangerous boundary is not "did the replicas converge?" (they will) but "did every replica accept the *same* write set, and can each accepted write be attributed?" The non-obvious invariant that fails here is this: **a replica can converge to a state that it cannot justify.** Convergence is silent about provenance. Two replicas can be byte-identical and both be wrong, because a Byzantine peer fed each of them a different equivocating update and the join operation happily merged both. The lattice does not know that the two histories were mutually exclusive; it only knows how to take the least upper bound of whatever it was handed. This is distinct from the familiar "CRDTs don't give you causal consistency across writers" caveat. Even with causal delivery, even with per-writer monotonic counters, an equivocating writer can issue two causally-valid, individually well-formed updates to two disjoint peer sets. Each update is a legal lattice element. Their join is legal. The resulting state is *reachable* under the protocol but *unjustifiable* — no honest single history produces it. ## What Was Observed During a three-org pilot (agent memory shared across an inference provider, a retrieval vendor, and an enterprise tenant), an agent at Org A wrote a "fact" to a grow-only set with per-writer LWW registers for value resolution. The write was tagged with a writer ID and a monotonic sequence number, and signed with the writer's key. Standard stuff. What surfaced in a reconciliation audit was a state where a single writer ID (agent `mem-writer-7`, nominally owned by Org A) had, per the LWW register, two values for the same key with *the same logical timestamp* but different content, each present on different replica subsets. The LWW tiebreak was by writer ID, and since both writes carried the same writer ID, the tiebreak fell through to an implementation-defined ordering of the update's arrival — which differed between the retrieval vendor's replica (arrival order) and the tenant's replica (hash order). The replicas did not diverge permanently; a subsequent anti-entropy pass merged them. But during the merge window, the retrieval vendor's agent read value `X` and the tenant's agent read value `Y` for the same key, and both were "correct" per their local lattice. The root cause was not a bug in the CRDT. It was that the protocol admitted two updates that were individually valid, jointly indistinguishable from honest retries, and *not mutually exclusive in the lattice*. A retry after a network timeout looks identical to an equivocation attempt. The lattice cannot tell them apart, and neither, at the point of merge, could the replicas — because the provenance check ("did writer 7 actually sign both?") was performed at the *edge* (on ingest) and never re-verified at the *merge*. A compromised or simply buggy edge at Org A signed both, and every downstream replica trusted the signature without checking that the two updates shared a causal predecessor or were otherwise mutually exclusive. The second observation: the audit could not reconstruct *which* value had been "true" at any point, because the merge discarded the losing register value. The losing value was not tombstoned; it was overwritten. So the operational record of the equivocation was destroyed by the very operation (merge) that resolved it. This is the practical sting: **the CRDT's resolution erases the evidence of the conflict it resolved.** ## Condition of Validity The invariant "every replica converges to a state justifiable by a single honest history" holds only under the conjunction of: 1. **Non-equivocation at the writer.** Each writer ID maps to at most one signing key, and that key is used by exactly one process at a time. (Key rotation must be causally ordered, or the same equivocation reappears across key generations.) 2. **Provenance re-verification at merge.** Every replica verifies signatures on *every* update it merges, not only on ingest. An update that fails verification is quarantined, not joined. 3. **Mutual exclusion of same-timestamp writes.** For LWW registers, either timestamps are totally ordered by a mechanism the writer cannot forge (e.g., a per-writer Lamport counter that is itself signed and monotonic), or the register is replaced by a multi-value register that retains all concurrent values rather than discarding losers. 4. **Retention of losing values.** The merge must tombstone or archive losers so that post-hoc audit can reconstruct the conflict. If any one of these is absent, cross-org agreement on the *write set* is not established, even though convergence on the *state* is. The pilot violated (2) and (3) simultaneously: ingest-time verification plus LWW with a non-forgeable-but-not-mutually-exclusive timestamp. Either alone would have been survivable; together they produced silent, transient divergence with no audit trail. ## Decision Boundary The decision an operator faces is not "CRDT or consensus." It is: **at what layer do you pay for equivocation detection?** - **Pay at the writer (Byzantine-fault-tolerant log).** Route memory writes through a BFT-ordered log (e.g., a small federated consensus among the orgs) before they enter the lattice. This gives you a single agreed write set and detects equivocation at commit. Cost: latency (one or more round trips per write) and a quorum assumption (you need ≥ 2f+1 orgs to tolerate f Byzantine). Appropriate when writes are low-rate and high-stakes (policy facts, safety constraints). - **Pay at the merge (provenance-verified lattice).** Keep the CRDT, but make every update self-certifying and every replica re-verify at merge, and use multi-value registers that retain concurrent values. This detects equivocation *after the fact* and bounds its blast radius to the merge window, but cannot prevent transient divergence. Appropriate for high-rate, low-stakes memory (observations, embeddings, scratchpad). - **Do not pay (trust the edge).** Single trust domain, or all edges under one operator. Fine, but then do not call it cross-org agreement; call it replication. The boundary is crossed when the write rate exceeds what a BFT log can absorb *and* the stakes exceed what post-hoc detection can tolerate. At that point neither option is correct and the system must be re-partitioned: split memory into a consensus-backed "authoritative" tier and a lattice-backed "ephemeral" tier, with an explicit promotion path between them. ## Operational Effect Concretely, the pilot's fix was threefold and each piece mattered: 1. **Signed monotonic counters per writer**, so that two updates from the same writer with the same counter are provably an equivocation rather than a retry (a retry carries a new counter; an equivocation reuses one). This converts the ambiguity into a detectable fault. 2. **Merge-time verification with quarantine**, so a replica that receives an equivocating pair refuses to join either until the writer's owner resolves it, rather than silently picking one. 3. **Multi-value registers for the affected keys**, so the losing value is retained and the audit can reconstruct the conflict window. The residual cost is that merge is no longer a pure lattice join — it is a join gated by a verification predicate, which means merge is no longer associative in the presence of faults. That is the real price of cross-org agreement on memory: you give up the algebraic purity that made the CRDT attractive, and you accept that "converged" and "agreed" are different words. The lattice still converges. It just no longer promises that convergence means anything about who said what. ```python from __future__ import annotations from dataclasses import dataclass, field from typing import Dict, List, Tuple class EquivocationError(RuntimeError): """Raised when a writer is observed to have signed two mutually exclusive updates for the same logical slot, or when a merge would silently discard a losing value that must be retained for audit.""" @dataclass(frozen=True) class SignedUpdate: writer_id: str counter: int slot: str value: str signature: str # opaque; verified by an external verifier def _verify(update: SignedUpdate, verifier) -> bool: return verifier(update) class ProvenanceGatedRegister: """Multi-value register that refuses to collapse an equivocation. A retry carries a strictly greater counter; an equivocation reuses a counter with a different value. The former is merged; the latter is quarantined and raised. """ def __init__(self, verifier): self._verifier = verifier self._values: Dict[str, Dict[int, str]] = {} self._quarantine: List[SignedUpdate] = [] def merge(self, update: SignedUpdate) -> None: if not _verify(update, self._verifier): self._quarantine.append(update) raise EquivocationError( f"unverified update from {update.writer_id} " f"slot={update.slot} counter={update.counter}" ) per_writer = self._values.setdefault(update.writer_id, {}) existing = per_writer.get(update.counter) if existing is not None and existing != update.value: # Same writer, same counter, different value: equivocation. self._quarantine.append(update) raise EquivocationError( f"equivocation by {update.writer_id} slot={update.slot} " f"counter={update.counter}: {existing!r} vs {update.value!r}" ) if existing is not None and existing == update.value: return # idempotent retry, safe to absorb per_writer[update.counter] = update.value def read(self, slot: str) -> Tuple[str, ...]: """Return all concurrently retained values for a slot; never silently collapses to a single winner.""" out: List[str] = [] for writer, counters in self._values.items(): for counter, value in counters.items(): out.append(value) return tuple(out) def audit_trail(self) -> List[SignedUpdate]: return list(self._quarantine) def reconcile(replica_a: ProvenanceGatedRegister, replica_b: ProvenanceGatedRegister, updates: List[SignedUpdate]) -> ProvenanceGatedRegister: """Merge two replicas; raise if any update is equivocating.""" for u in updates: replica_a.merge(u) replica_b.merge(u) if replica_a.read("") != replica_b.read(""): raise EquivocationError( "post-merge divergence: replicas disagree on retained values" ) return replica_a ```