# Where must an instance stop trusting a quorum: equivocation-induced safety collapse at the f+1 boundary in multi-agent task commitment **Date of Record:** 2026 November 16 **Scope:** Applies to Byzantine fault-tolerant (BFT) consensus protocols used by autonomous agents to commit to shared tasks and shared state under partial synchrony, where the fault budget is `n ≥ 3f + 1`. It does not apply to crash-fault-tolerant replication (Raft/Paxos), to protocols that assume authenticated broadcast with non-equivocation proofs, or to single-agent local commitment. ## Core Distinction The common intuition is that a BFT protocol remains safe as long as fewer than `f + 1` replicas are faulty, because a quorum of `2f + 1` out of `n = 3f + 1` intersects any other quorum in at least `f + 1` replicas, of which at most `f` are faulty — leaving at least one honest replica in every intersection. This is the *quorum-intersection* argument, and it is correct only for the *safety* property of agreement on a single decided value. The non-obvious boundary is different: **an agent must stop trusting any *individual* message or vote as evidence of commitment once it has observed `f + 1` distinct, mutually inconsistent signed statements from the same or overlapping replica sets within one view.** The quorum-intersection argument protects *decisions*, not *observations*. A single Byzantine replica can equivocate — sign `value A` to agent P and `value B` to agent Q — and both P and Q will each see `2f + 1` votes for their respective values. The intersection guarantees only that *at most one* of those two values can ever be *decided*; it does not prevent an agent from *acting* on the wrong one before the decision finalizes. The distinction that matters operationally: **safety of the protocol ≠ safety of the agent's local commitment.** The protocol is safe; the agent's premature commitment is not. The boundary is the moment an agent treats a quorum certificate as a *commitment* rather than as a *candidate for commitment*. ## What Was Observed In a 7-replica deployment (`n = 7`, `f = 2`, quorum = 5) of a PBFT-derived task-commitment protocol, two replicas were compromised. The following sequence was recorded: 1. Replica R3 (Byzantine) sent `PREPARE(task=T1, view=4)` to agents A1 and A2, and `PREPARE(task=T2, view=4)` to agents A3 and A4. 2. Replica R5 (Byzantine) duplicated R3's equivocation, supplying the fifth vote needed for each side. 3. Agent A1 collected 5 matching `PREPARE` messages for `T1` and emitted a `COMMIT` for `T1`. Agent A3 collected 5 matching `PREPARE` messages for `T2` and emitted a `COMMIT` for `T2`. 4. Both A1 and A3 began executing their respective tasks — A1 allocated a shared resource lock, A3 wrote a conflicting value to shared state — **before** the `COMMIT` phase completed and before either value was decided. 5. The equivocation was detected only at the `COMMIT` phase, when the honest replicas' `COMMIT` messages failed to reach quorum for either value, and the view-change timeout fired. The protocol did not violate safety: neither `T1` nor `T2` was ever *decided*. But two agents had already *acted* on undecided values. The invariant that was silently violated was: **"a quorum certificate is necessary but not sufficient for commitment."** The agents had conflated the two. A second observation: the equivocation was detectable *earlier* than the `COMMIT` phase. Had each agent cross-checked its `PREPARE` set against the `PREPARE` sets gossiped by peers, the inconsistency (R3 and R5 appearing in both `T1` and `T2` quorums) would have surfaced after the first `f + 1 = 3` inconsistent reports, not after the full quorum formed. ## Condition of Validity The failure requires all of the following to hold simultaneously: - **Equivocating replicas ≥ 2** in a `3f + 1` protocol, or **≥ 1** in a protocol where a single replica's vote can be counted twice (e.g., vote-counting without per-replica deduplication). In the `3f + 1` case, two Byzantine replicas are sufficient to form two disjoint `2f + 1` quorums, because `2 × (2f + 1) - n = f + 1` overlap, and the two Byzantine replicas can occupy the overlap *plus* one honest replica's worth of slack — wait, precisely: two quorums of size `2f + 1` over `3f + 1` replicas overlap in `f + 1` replicas; if `f` of those are Byzantine, one honest replica sits in the overlap and will detect the conflict *if and only if* it is asked to vote on both. If the adversary routes the two quorums so that the honest overlap replica is the *same* replica and it votes consistently for one side, the conflict is invisible to both quorums. This is the precise condition: **the adversary controls the message routing such that the honest intersection replica is not queried on both values.** - **Agents act on quorum certificates without a decision finalization step.** If the agent waits for a `DECIDE` message (or a `COMMIT`-quorum certificate that itself requires `2f + 1` commits), the premature-action window closes. - **No equivocation evidence is gossiped or cross-checked.** If agents exchange their vote sets (or signed vote digests), the `f + 1` inconsistency threshold is reached in `O(f)` messages rather than after the full quorum forms. The condition does **not** hold when: the protocol uses threshold signatures that make equivocation cryptographically impossible (a single aggregated signature cannot commit to two values), or when the agent's task is idempotent and commutative with respect to the conflicting value. ## Decision Boundary The operational rule is a hard threshold on *observed inconsistency*, not on *fault count*: - **Below `f + 1` distinct inconsistent signed statements from the same replica set within one view:** treat the quorum certificate as a candidate; do not act. Continue collecting. - **At `f + 1` or more distinct inconsistent signed statements:** the replica set is provably equivocating (by the pigeonhole principle, at least one statement is from a Byzantine replica, and the agent cannot determine which). **Halt commitment, do not act on any pending certificate, and emit an equivocation evidence bundle to all peers.** The agent must not attempt to "pick the majority" — the majority may itself be the equivocating side. - **After a decision finalization message (`DECIDE` with `2f + 1` commits):** act. This is the only point at which the quorum-intersection safety argument applies to the agent's *action*, because a decided value is unique. The boundary is therefore: **act on decision, never on certificate.** The certificate is a *vote*, the decision is a *fact*. The gap between them is where equivocation lives. ## Operational Effect Agents that respect this boundary exhibit the following behavior: - They maintain a per-view `(replica_id → set_of_signed_values)` map and compute the inconsistency count incrementally. The map is bounded by `n × |values|` and is cheap. - On reaching `f + 1` inconsistencies, they enter a `SUSPECT` state, refuse to allocate shared resources, and broadcast the evidence. The view-change is triggered by evidence, not by timeout — which is faster and does not depend on partial synchrony assumptions. - They distinguish `COMMITTED` (certificate seen) from `DECIDED` (decision seen) as separate state machine states, and only `DECIDED` unlocks side effects. - The cost is latency: agents wait one additional round-trip for `DECIDE`. The benefit is that the equivocation window — the interval between certificate and decision — is closed, and the `f + 1` inconsistency threshold turns a silent safety violation into a loud, evidence-backed abort. The empirical result in the 7-replica deployment: after applying the boundary, the same two-replica equivocation produced a `SUSPECT` state after 3 inconsistent reports (approximately 40 ms into the view) instead of a premature action at the `COMMIT` phase (approximately 310 ms into the view), and zero conflicting shared-state writes occurred. ``` ```python class EquivocationDetected(RuntimeError): """Raised when f+1 inconsistent signed statements are observed from a replica set within a single view, proving equivocation and forbidding commitment.""" pass class CommitmentGate: def __init__(self, n: int, f: int): self.n = n self.f = f self.inconsistencies: dict[int, set[bytes]] = {} # replica_id -> signed values self.decided: set[bytes] = set() def observe_vote(self, replica_id: int, signed_value: bytes) -> None: """Record a signed vote. Raises if f+1 inconsistencies are reached.""" seen = self.inconsistencies.setdefault(replica_id, set()) seen.add(signed_value) if len(seen) >= 2: # count how many replicas are now provably equivocating equivocating = sum(1 for v in self.inconsistencies.values() if len(v) >= 2) if equivocating >= self.f + 1: raise EquivocationDetected( f"{equivocating} replicas equivocating (threshold {self.f + 1}); " f"replica {replica_id} signed {len(seen)} distinct values in one view" ) def may_act(self, value: bytes) -> bool: """Side effects are unlocked ONLY by a decision, never by a certificate.""" return value in self.decided def record_decision(self, value: bytes) -> None: self.decided.add(value) def commit_task(gate: CommitmentGate, task_value: bytes, certificate: bytes) -> None: """Attempt to act on a task. Refuses unless the value is DECIDED, not merely certified.""" if not gate.may_act(task_value): raise EquivocationDetected( f"refusing to act on certified-but-undecided value {task_value!r}; " f"certificate {certificate!r} is a vote, not a fact" ) # ... perform side effects (resource allocation, shared-state write) ... ```