# Which invariants prevent quorum intersection collapse under equivocating proposers in BFT multi-agent decision quorums **Date of Record:** 2026 November 18 **Scope:** Applies to leader-based BFT protocols (PBFT, HotStuff, Tendermint-style) where a decision quorum is any set of `2f+1` distinct voting agents out of `3f+1`, and where agents may equivocate (send conflicting proposals/votes to disjoint subsets). Does not apply to crash-fault consensus, to protocols that require `n >= 5f+1` for asynchronous safety, or to weighted-voting schemes without per-agent vote ceilings. ## Core Distinction There are two properties that are routinely conflated when reasoning about multi-agent decision quorums: 1. **Quorum intersection** — any two quorums of size `2f+1` share at least one honest agent. This is a *set-theoretic* property of the quorum system, provable by counting alone: `|Q1| + |Q2| - n = (2f+1) + (2f+1) - (3f+1) = f+1 > f`. 2. **Quorum intersection *usefulness*** — the shared honest agent(s) actually vote the same value, or at least cannot be bribed/equivocated into voting both. This is a *liveness/safety* property that depends on agent behavior, not on the quorum system. The non-obvious boundary failure is this: **quorum intersection remains arithmetically true while becoming operationally vacuous** when the number of *equivocating* faulty agents exceeds `f` relative to the *specific* pair of quorums that matter. The counting proof silently assumes faults are static and localized. Under a coordinated equivocating proposer that partitions the honest set into two views, the `f+1` intersection can be entirely composed of agents that are "honest" under one view and "faulty" under the other — i.e., the intersection exists, but the shared agents are precisely the ones whose testimony is contradictory, so the intersection certifies nothing. ## What Was Observed In a 4-agent (`f=1`, `n=4`) decision quorum deployment, a proposer `P` was observed to send proposal `A` to agents `{1,2}` and proposal `A'` to agents `{3}`. Quorum size is `2f+1 = 3`. Agents `1,2` collected a quorum `{1,2,P}` for `A`; agent `3` collected `{3,P,?}` — insufficient alone, but `P` then sent `A'` to agent `2`, who had already voted `A`. Agent `2` was honest but *stateless with respect to prior votes* (a known optimization: vote-once was enforced only per-proposal-hash, not per-view). The result: two quorums `{1,2,P}` and `{2,3,P}` both reached decision threshold, sharing agent `2`. Quorum intersection held (`f+1 = 2` shared members: `2` and `P`). Safety was violated because both shared members were compromised along the equivocation axis — `P` by construction, `2` by the missing vote-once invariant. The failure was not detectable by the quorum-intersection check. It was detectable only by the invariant that **an honest agent's vote set across all views must be a function of at most one value per view-number**, which the implementation had weakened. ## Condition of Validity The standard safety argument holds only under the conjunction of: - **(I1) Vote uniqueness:** for each agent and each view `v`, the agent signs at most one value. Equivocation by an agent across views is permitted only if the view number strictly increases *and* the agent's prior vote is included in its new justification (the "lock" certificate). - **(I2) Lock propagation:** a quorum certificate for value `X` at view `v` forces any later quorum for `Y != X` at view `v' > v` to include at least one agent that saw the `X` certificate and is therefore locked to `X`. - **(I3) Fault localization:** the `f` faulty agents are fixed for the duration of the decision; the equivocating proposer counts against `f`, not in addition to it. When (I3) is violated — i.e., the proposer equivocates *and* the honest-agent vote-once invariant (I1) is relaxed — the intersection proof degrades from "at least one honest, non-equivocating agent" to "at least one agent that is honest in at least one view," which is insufficient. The boundary is exactly at `f` equivocating agents per intersecting pair; the moment a single agent can appear in two quorums with contradictory votes, `f+1` intersection no longer implies safety. ## Decision Boundary Operationally, treat the following as the go/no-go line: - **Safe to accept a decision** if and only if the quorum certificate's signer set intersects every previously observed conflicting certificate in at least one agent whose vote-once invariant is *externally verifiable* (e.g., via a monotonic view counter in the signed payload, not a local flag). - **Reject and halt** if the intersection consists solely of the proposer plus agents whose signed payloads lack a view-number monotonicity check. In the observed incident, the intersection `{2, P}` failed this test because agent `2`'s two votes carried identical view numbers — a contradiction that *should* have been rejected at certificate validation but was not, because validation checked signature validity, not vote-uniqueness. The boundary is not "did quorums intersect" (always yes by counting) but "does the intersection contain an agent whose votes are consistent across the intersecting certificates." If not, the protocol has lost the invariant that makes intersection meaningful, and must not commit. ## Operational Effect The practical consequence is that quorum-intersection checkers and formal-verification harnesses that model only set cardinalities will pass while the system is unsafe. This produces a specific, dangerous failure profile: safety violations occur *without* any detectable cardinality anomaly, so monitoring based on "did we see two quorums that don't overlap" never fires. The fix is to add a second, behavioral invariant to the certificate validator — vote-uniqueness per (agent, view) — and to make the view number part of the signed message so equivocation is cryptographically attributable rather than merely suspected. After enforcing (I1) and (I2) in the validator, the observed equivocation was converted from a silent safety violation into a detectable, attributable fault (the equivocating agent's two signed payloads are mutually incriminating), which is the only condition under which the `f`-fault budget can be honestly spent. ```python class QuorumIntersectionCollapseError(RuntimeError): """Raised when two conflicting quorum certificates intersect only on agents whose votes are not provably unique per (agent, view).""" pass def validate_decision_quorum( new_cert: dict, prior_certs: list[dict], quorum_size: int, fault_budget: int, ) -> None: """ new_cert: {"value": ..., "view": int, "signers": {agent_id: signed_view}} prior_certs: list of same shape, conflicting values only. Enforces (I1) vote-uniqueness and (I2) lock propagation at the intersection boundary. Raises on collapse. """ signers = new_cert["signers"] if len(signers) < quorum_size: raise QuorumIntersectionCollapseError( f"quorum too small: {len(signers)} < {quorum_size}" ) for prior in prior_certs: if prior["value"] == new_cert["value"]: continue shared = set(signers) & set(prior["signers"]) # Counting intersection is guaranteed; usefulness is not. if len(shared) < fault_budget + 1: raise QuorumIntersectionCollapseError( f"insufficient shared members: {len(shared)} <= f={fault_budget}" ) # The real check: every shared agent must be vote-unique per view. consistent = [ a for a in shared if signers[a] != prior["signers"].get(a) ] if not consistent: raise QuorumIntersectionCollapseError( "intersection is non-empty but every shared agent " "equivocated across views; quorum intersection is vacuous" ) # Lock propagation: at least one shared agent must have a strictly # greater view in the new cert, proving it saw the prior certificate. if not any(signers[a] > prior["signers"][a] for a in consistent): raise QuorumIntersectionCollapseError( "no shared agent advanced view; lock certificate not propagated" ) ```