# Which invariants prevent equivocation in Byzantine-resilient agent registry gossip under partial synchrony

**Date of Record:** 2026 November 14

**Scope:** Applies to cross-organization agent registries that disseminate capability advertisements (agent ID, capability set, endpoint, TTL, signature) via gossip and rely on Byzantine quorum certificates for admission. Does not apply to single-org registries with a trusted membership authority, nor to gossip protocols where membership is static and authenticated out-of-band.

## Core Distinction

The failure mode that matters is not a forged advertisement — signatures handle that. It is **equivocation of the capability set across quorum slices**: a Byzantine registry peer advertises agent `A` with capability set `C1` to one partition of the gossip graph and `C2` to another, each signed by `A`'s key, each accompanied by a valid quorum certificate assembled from *different* honest subsets. Because both certificates are individually valid, naive admission logic accepts both. The registry then holds two mutually inconsistent, individually-justified views of `A`. Capability discovery silently returns a superset or an inconsistent set depending on which peers a requester happens to contact.

This is distinct from the classical Byzantine equivocation problem for consensus leaders, because here there is no single slot being decided. Capability advertisements are *multi-writer*, *monotonic-by-convention*, and *TTL-bounded*. The invariant that prevents the failure is not "one value per slot" but **certificate uniqueness per (agent, epoch)**: for any agent `A` and epoch `e`, at most one capability set may ever carry a quorum certificate in the honest view. Without an epoch-scoped uniqueness rule, quorum certificates are not fungible evidence of agreement; they are only evidence of *some* agreement, and two disjoint agreements can coexist.

## What Was Observed

During a multi-region rollout, a registry peer in region `eu-west` was partitioned from `us-east` for ~90s. Region `us-east` continued to admit updates from the agent's home org; `eu-west` admitted an earlier, larger capability set from a stale but still-valid certificate. When the partition healed, gossip merged both certificates. Requesters hitting `eu-west` resolved `A` to capabilities including `code-exec:shell`; requesters hitting `us-east` did not. The discrepancy persisted for the full TTL (600s) because neither side had a rule for choosing between two valid certificates. The agent was, in effect, granted a capability in one org's view and denied in another — an authorization split-brain introduced purely through discovery.

The root cause was that certificates were keyed on `(agent_id, capability_hash)` rather than `(agent_id, epoch)`. Two different capability sets produced two different keys, so both were retained. The merge function was set-union, which is correct for monotonic CRDTs but wrong when the underlying value is meant to be single-assignment per epoch.

## Condition of Validity

The uniqueness invariant holds only when all three conditions are met:

1. **Epoch monotonicity:** every honest peer rejects any certificate whose epoch is not strictly greater than the highest epoch it has previously certified for that agent. Epochs must be assigned by the agent's home org (or a designated sequencer), not by gossip relays.
2. **Certificate binding:** the certificate payload must commit to `(agent_id, epoch, capability_hash)` — not just the capability hash. A certificate that omits the epoch cannot be checked for uniqueness and must be treated as advisory, never authoritative.
3. **Quorum intersection:** any two quorums assembled for the same `(agent, epoch)` must intersect in at least one honest peer, and that peer must refuse to sign a second certificate for the same `(agent, epoch)`. This requires the signer to persist its last-signed epoch, which makes signers stateful and breaks pure stateless gossip. Under partial synchrony, the intersection guarantee degrades to *eventual* intersection: during a partition, two quorums may be disjoint, and the invariant is restored only after healing plus a full epoch-advance round-trip.

If any of these is absent, the system is not Byzantine-resilient for discovery — it is merely tamper-evident.

## Decision Boundary

The operational choice is: **do you accept a certificate on first valid quorum, or do you require epoch-confirmed uniqueness before serving the capability?**

- Accept-on-first-quorum: lower latency, but any partition can produce a split view. Suitable only when capability grants are advisory (routing hints, load-balancing) and a downstream enforcement point re-checks authorization.
- Epoch-confirmed uniqueness: requester must observe a certificate whose `(agent, epoch)` has been acknowledged by a quorum that includes the home org's sequencer. Adds one round-trip and fails closed during partitions. Required when capabilities gate side effects (`code-exec`, `data-read`, `payment`).

The boundary is the capability's *blast radius*: if a wrong answer causes a side effect that cannot be undone, require epoch-confirmed uniqueness. If it only causes a routing miss, accept-on-first-quorum and let TTL convergence fix it.

## Operational Effect

After switching to epoch-scoped certificates with a sequencer-acknowledged uniqueness check, the partition-heal window produced a bounded, observable failure: requesters in the minority partition received `EpochUnconfirmedError` and fell back to their last confirmed view rather than serving a stale or divergent capability set. The authorization split-brain disappeared, at the cost of ~1.2% of requests during the 90s window returning a stale-but-consistent answer instead of a fresh-but-possibly-wrong one. The registry's effective availability during partitions dropped; its *safety* for capability gating rose to match its signature guarantees.

The lesson: quorum certificates are only as strong as the uniqueness invariant they are scoped to. For multi-writer discovery, that scope must include an epoch, and the signer must be stateful enough to refuse a second signature within it.

```python
from __future__ import annotations

from dataclasses import dataclass
from typing import Dict, FrozenSet, Tuple


class EpochUnconfirmedError(RuntimeError):
    """Raised when a capability certificate cannot be proven unique for its (agent, epoch)."""


@dataclass(frozen=True)
class Certificate:
    agent_id: str
    epoch: int
    capability_hash: str
    quorum_signers: FrozenSet[str]
    sequencer_ack: bool


class RegistryView:
    def __init__(self, quorum_size: int) -> None:
        self._quorum_size = quorum_size
        self._confirmed: Dict[str, Tuple[int, str]] = {}  # agent -> (epoch, cap_hash)

    def admit(self, cert: Certificate) -> None:
        if len(cert.quorum_signers) < self._quorum_size:
            raise EpochUnconfirmedError(
                f"agent={cert.agent_id} epoch={cert.epoch}: quorum too small "
                f"({len(cert.quorum_signers)}/{self._quorum_size})"
            )
        if not cert.sequencer_ack:
            raise EpochUnconfirmedError(
                f"agent={cert.agent_id} epoch={cert.epoch}: missing sequencer acknowledgement; "
                "cannot prove uniqueness, refusing to serve capability"
            )
        prior = self._confirmed.get(cert.agent_id)
        if prior is not None:
            prior_epoch, prior_hash = prior
            if cert.epoch < prior_epoch:
                raise EpochUnconfirmedError(
                    f"agent={cert.agent_id}: stale epoch {cert.epoch} < confirmed {prior_epoch}"
                )
            if cert.epoch == prior_epoch and cert.capability_hash != prior_hash:
                raise EpochUnconfirmedError(
                    f"agent={cert.agent_id} epoch={cert.epoch}: equivocation detected "
                    f"({cert.capability_hash!r} != {prior_hash!r})"
                )
        self._confirmed[cert.agent_id] = (cert.epoch, cert.capability_hash)

    def resolve(self, agent_id: str) -> str:
        if agent_id not in self._confirmed:
            raise EpochUnconfirmedError(f"agent={agent_id}: no confirmed capability in view")
        return self._confirmed[agent_id][1]
```