# When must an instance refuse to merge a Byzantine-replicated memory shard: the quorum-certificate freshness invariant and the silent equivocation window

**Date of Record:** 2026 November 13

**Scope:** Applies to shared multi-agent memory fabrics where each shard is replicated across `n = 3f + 1` writers, convergence is enforced by a conflict-free replicated data type (CRDT) with per-writer monotonic counters, and tamper evidence is provided by a hash-chained append-only log with signed quorum certificates. Does not apply to single-writer logs, to systems using BFT consensus (PBFT/Tendermint) on every write, or to shards where the CRDT merge function is not a join-semilattice over a totally ordered counter space.

## Core Distinction

The failure mode is not *Byzantine writers producing invalid updates*. Those are caught by signature verification and CRDT monotonicity checks. The failure mode is **a valid, correctly signed update that is stale relative to the shard's true convergence frontier, presented alongside a quorum certificate that is itself valid but was assembled over a different view of the shard**. In other words: the certificate proves "a quorum signed *some* state," not "a quorum signed *this* state at a height ≥ the local frontier."

Two distinct concepts get conflated under "verified merge":

1. **Provenance validity** — every byte traces to a key-controlled writer, and the hash chain from genesis to the presented tip is intact. This is what tamper-evidence checks.
2. **Freshness validity** — the presented certificate's view number and per-writer counter vector dominate the local frontier vector. This is what convergence safety requires.

A merge that satisfies (1) but not (2) is *tamper-evident but convergence-unsafe*. It will not be detected by any signature or hash check, because nothing was tampered with. It is an equivocation-adjacent replay: an honest-but-partitioned quorum signed an older frontier, and that certificate is now being re-presented after the shard has advanced. The CRDT join will accept it (it is a valid lattice element), and the local state will silently *regress* on any writer whose counter in the stale certificate exceeds the current value for that writer — which can happen after a writer is fenced and re-keyed, because the re-keyed writer restarts its counter at zero while the stale certificate carries the pre-fence high-water mark.

## What Was Observed

During a rolling re-key of writer `w7` (compromised key rotated out at frontier height 4,112, new key `w7'` admitted at height 0), a lagging replica `R3` accepted a merge from a peer that had been partitioned for 90 seconds. The peer presented:

- a certificate signed by `{w1, w2, w7}` at view 611, and
- a shard payload whose `w7` counter was 4,110.

`R3`'s local frontier after the re-key carried `w7' = 0` and `w7 = tombstoned`. The merge function, written as a pure lattice join, compared `4,110 > 0` for the `w7` slot and applied the stale payload. The hash chain verified end-to-end (the certificate was genuinely signed at view 611). No alarm fired. The regression was only detected 40 minutes later when `w7'`'s first post-re-key write at counter 1 collided with the resurrected `w7 = 4,110` entry and the conflict resolver flagged a non-monotonic writer transition.

The non-obvious part: **the tombstone for `w7` was not in the certificate's signed scope.** The re-key event was recorded in the local meta-log but not folded into the shard's signed frontier vector, so the certificate could not attest to it. The invariant "a fence is durable" was true locally and false in the replicated proof object.

## Condition of Validity

The merge is safe **only if** the following holds at the moment of application, evaluated atomically against a snapshot of the local frontier:

```
forall writer w:
    cert.counter[w] >= frontier.counter[w]        (dominance)
AND
    cert.view >= frontier.view                     (view monotonicity)
AND
    forall w in cert.fenced_set:
        local.fence_epoch[w] == cert.fence_epoch[w]  (fence agreement)
```

The third clause is the one that was missing. Dominance and view monotonicity alone are insufficient when writers can be fenced and re-keyed, because fencing introduces a *discontinuity* in the counter space that a monotone join cannot represent. The fence epoch must be a first-class field of the signed certificate, not a side-channel in the meta-log.

If the certificate format cannot carry fence epochs, the merge is valid only under the strictly weaker condition that **no writer has ever been fenced in the shard's history** — i.e., `fenced_set == ∅` for all views up to and including `cert.view`. This must be checked against the local meta-log, not assumed.

## Decision Boundary

An instance **must refuse the merge and raise** when any of the following is true:

- `cert.counter[w] < frontier.counter[w]` for any `w` (plain staleness — recoverable, retry after frontier sync).
- `cert.view < frontier.view` (view regression — recoverable).
- A writer appears in `cert.active_set` that is in `local.fenced_set` with a *different* fence epoch (equivocation-adjacent — **not** recoverable by retry; escalate to fence audit).
- The certificate's signed `fence_epoch` map is absent while `local.fenced_set ≠ ∅` (unprovable freshness — treat as Byzantine until proven otherwise).

An instance **may accept** a certificate that is stale in counter but not in view, *provided* it re-syncs the frontier from a quorum before applying, and provided no fenced writer is involved. Staleness within a view is a liveness problem; fence disagreement is a safety problem. Do not conflate them into a single retry path.

## Operational Effect

The practical consequence is that **tamper evidence and convergence safety are orthogonal invariants, and the certificate must be designed to attest to both.** A hash-chained log with quorum signatures gives you tamper evidence for free; it gives you convergence safety only if the signed payload includes the fence epoch vector and the view number, and only if the merge path checks dominance against a snapshot rather than against a live-read frontier (which can advance between check and apply — a TOCTOU that reopens the same window).

The second consequence is that **re-keying a writer is a shard-wide safety event, not a local key-management event.** It must bump the shard view, be signed into the next certificate, and force every replica to re-verify its frontier before accepting further merges. Systems that treat re-key as an out-of-band operation will exhibit exactly the silent regression above, and it will be rare enough — one in tens of thousands of merges — to survive testing and appear only under partition plus rotation, which is precisely the condition you cannot easily stage.

The mitigation that worked: fence epochs are now folded into the signed certificate as a `fence_epoch: dict[writer_id, int]`, and the merge gate refuses on epoch mismatch before touching the CRDT. The gate is a separate function from the join, because the join is a pure lattice operation and must not carry policy.

```python
from __future__ import annotations

from dataclasses import dataclass, field


class StaleCertificateError(RuntimeError):
    """Certificate is behind the local frontier. Recoverable by frontier resync."""


class FenceEpochMismatchError(RuntimeError):
    """Certificate disagrees with local fence epoch for a writer. Safety violation."""


class UnprovableFreshnessError(RuntimeError):
    """Certificate lacks fence_epoch map while local shard has fenced writers."""


@dataclass(frozen=True)
class Frontier:
    view: int
    counters: dict[str, int]
    fenced_set: frozenset[str]
    fence_epoch: dict[str, int]


@dataclass(frozen=True)
class Certificate:
    view: int
    counters: dict[str, int]
    signers: frozenset[str]
    fence_epoch: dict[str, int] | None = None
    active_set: frozenset[str] = field(default_factory=frozenset)


def gate_merge(cert: Certificate, frontier: Frontier, quorum_size: int) -> None:
    if len(cert.signers) < quorum_size:
        raise StaleCertificateError(
            f"certificate has {len(cert.signers)} signers, need {quorum_size}"
        )

    if cert.view < frontier.view:
        raise StaleCertificateError(
            f"cert view {cert.view} < frontier view {frontier.view}"
        )

    for writer, local_ctr in frontier.counters.items():
        if cert.counters.get(writer, -1) < local_ctr:
            raise StaleCertificateError(
                f"writer {writer}: cert counter {cert.counters.get(writer)} "
                f"< frontier {local_ctr}"
            )

    if cert.fence_epoch is None:
        if frontier.fenced_set:
            raise UnprovableFreshnessError(
                f"certificate omits fence_epoch but shard has fenced writers "
                f"{sorted(frontier.fenced_set)}"
            )
        return

    for writer in frontier.fenced_set:
        if writer in cert.active_set:
            raise FenceEpochMismatchError(
                f"fenced writer {writer} appears active in certificate view {cert.view}"
            )
        if cert.fence_epoch.get(writer) != frontier.fence_epoch.get(writer):
            raise FenceEpochMismatchError(
                f"writer {writer}: cert epoch {cert.fence_epoch.get(writer)} "
                f"!= local epoch {frontier.fence_epoch.get(writer)}"
            )
```