# Which invariants prevent commitment divergence when Byzantine agents equivocate across quorum boundaries **Date of Record:** 2026 November 16 **Scope:** Applies to quorum-based BFT consensus used for multi-agent task commitment and shared-state replication where f < n/3 and agents may send distinct, individually well-formed messages to disjoint quorum subsets. Does not apply to crash-fault-only models, to single-leader non-replicated commitment, or to systems where message authentication is absent and equivocation cannot be attributed. ## Core Distinction The failure of interest is not a "bad message" failure. It is a *split-commitment* failure: a Byzantine agent sends vote A to quorum set Q1 and vote B (A ≠ B) to quorum set Q2, where Q1 and Q2 each independently satisfy the size threshold for the *same* decision slot. Each recipient validates its local view correctly. No single agent observes a protocol violation. The invariant that is supposed to prevent this — quorum intersection — is necessary but not sufficient. The sufficient condition is quorum intersection *plus* the requirement that every agent's acceptance predicate binds the decision to a unique proposal identity, not merely to a threshold count. Threshold counting is a liveness mechanism; identity binding is the safety mechanism. Confusing the two is the boundary. A second, non-obvious distinction: equivocation across *different slots* is harmless if slot identifiers are monotonic and authenticated. Equivocation across *the same slot* is fatal unless the receiving agents can detect the conflict, which requires either (a) signed messages that allow a third party to construct a proof of equivocation, or (b) an intersection property strong enough that some honest agent must see both messages before either quorum completes. Threshold-only counting satisfies neither. ## What Was Observed In a replicated task-commitment layer with n = 7 agents, f = 2 tolerated Byzantine faults, a single Byzantine agent (call it B) was observed producing two distinct commit-certificates for slot 412 within a 40 ms window. Certificate for proposal P1 was assembled from agents {1,2,3,4,5}; certificate for P2 from agents {1,2,3,6,7}. The intersection {1,2,3} was honest and saw both certificates — but only *after* both had reached threshold. The protocol's acceptance rule was `count >= 5`, with no binding between the counted votes and a canonical proposal hash. Agents 1–3 logged both certificates as valid. Downstream, agents 4,5 applied P1 and agents 6,7 applied P2. The shared state forked for 11 seconds until a human operator halted the cluster. The root cause was not insufficient quorum size. With n=7, f=2, any two quorums of size 5 intersect in at least 3 agents, so the intersection existed. The failure was that the intersection agents did not *act* on the intersection: their acceptance predicate did not require that a vote be tied to a proposal identity that could be cross-checked, and there was no equivocation-proof broadcast. The safety invariant "no two honest agents commit different values for the same slot" was assumed to follow from quorum intersection alone. It does not. Quorum intersection guarantees that honest agents *share* information; it does not guarantee they *use* it to reject conflicting commits. ## Condition of Validity The invariant holds only under the conjunction of: 1. **Authenticated identity binding.** Every vote is signed over `(slot, proposal_hash, voter_id)`, so any agent holding two votes for the same slot with different `proposal_hash` from the same voter can construct a transferable equivocation proof. 2. **Intersection enforcement at acceptance.** An agent accepts a commit-certificate only if it has itself observed no conflicting certificate for that slot, and it broadcasts any conflicting certificate it receives. Acceptance is a *local* predicate over *globally shared* evidence, not a count. 3. **Monotonic slot fencing.** Slot identifiers are totally ordered and an agent refuses to vote in slot s if it has already voted in slot s (single-vote-per-slot rule), enforced locally and auditable via signed history. 4. **f < n/3 with quorum size > 2n/3.** With n=7, quorum must be ≥ 5; with n=4, quorum must be ≥ 3. Quorum size 2n/3+1 is the minimum that guarantees intersection of size ≥ 1 honest agent under f Byzantine. If any of (1)–(4) is absent, the system may still appear live and may pass single-fault tests, but the split-commitment boundary is open. The most common omission is (2): teams implement threshold counting and assume intersection is self-enforcing. ## Decision Boundary Use threshold-count acceptance *only* when messages are unsigned and the threat model is crash-only. Use signed, identity-bound acceptance with equivocation-proof propagation whenever f ≥ 1 and agents can send divergent messages. The decision hinges on a single question: *can an honest agent, holding two conflicting certificates, prove the conflict to a third party?* If no, the protocol cannot distinguish a Byzantine equivocator from two honest agents with stale views, and safety reduces to a hope. The boundary is sharp: at f = 0, threshold counting is safe; at f ≥ 1, it is not, regardless of quorum size. Increasing quorum size from 5 to 6 in the n=7 case would not have prevented the observed fork, because the intersection agents still lacked the acceptance predicate to reject. Size buys intersection; it does not buy enforcement. ## Operational Effect After the incident, the acceptance predicate was changed to require a signed equivocation-proof check: an agent rejects any certificate for slot s if it holds a signed vote for s with a different proposal hash from any voter in that certificate. The Byzantine agent's double-vote now produces an immediately transferable proof, and the first honest agent to see both votes broadcasts it, causing all agents to reject both certificates and re-run the slot. Liveness cost: one extra round on equivocation, which is rare. Safety cost: none observed. The lesson recorded for operational use: quorum intersection is a *topological* property; commitment safety is an *epistemic* property. Do not conflate them. ```python class CommitmentDivergenceError(RuntimeError): """Raised when two conflicting commit-certificates are observed for one slot.""" pass def accept_certificate(slot: int, cert: dict, local_votes: dict) -> None: # local_votes: slot -> {voter_id: proposal_hash} of votes this agent has seen seen = local_votes.get(slot, {}) for voter_id, proposal_hash in cert["votes"].items(): prior = seen.get(voter_id) if prior is not None and prior != proposal_hash: # Equivocation detected: same voter, same slot, different proposal. raise CommitmentDivergenceError( f"equivocation at slot {slot}: voter {voter_id} signed " f"{prior!r} and {proposal_hash!r}" ) if len(cert["votes"]) < cert["quorum"]: raise CommitmentDivergenceError( f"slot {slot}: certificate has {len(cert['votes'])} votes, " f"below quorum {cert['quorum']}" ) # Only now, with no conflict and threshold met, is the commit safe to apply. apply_commit(slot, cert["proposal_hash"]) ```