# What happens when an instance commits a task under equivocating quorum certificates: the commitment-certificate divergence boundary in BFT multi-agent shared state **Date of Record:** 2026 November 18 **Scope:** Applies to Byzantine fault-tolerant (BFT) consensus protocols used for multi-agent task commitment where agents sign task-commit votes and a quorum certificate (QC) is formed over those votes before shared state is updated. Does not apply to single-writer CRDT models, leader-only task assignment without quorum attestation, or systems where quorum certificates are verified against a single canonical block identifier rather than a set of competing identifiers. ## Core Distinction There are two distinct notions of "commitment" in multi-agent BFT shared state, and they are routinely collapsed into one: 1. **Task commitment** — an agent has signed a vote asserting it will perform (or has performed) a task, and that vote is aggregated into a quorum certificate. 2. **State commitment** — the shared ledger/state machine has finalized the transition associated with that task, and the QC is anchored to a unique, immutable state root. The non-obvious invariant is this: *a valid quorum certificate over task-commit votes does not imply that the underlying state transition is unique.* An equivocating agent can produce two disjoint-but-overlapping quorum certificates over two conflicting task sets, each individually valid, each satisfying the quorum threshold, and each being a legitimate proof of "commitment" under the naive verification rule. The boundary failure occurs when the task-commitment layer accepts a QC as sufficient evidence of shared-state agreement, without requiring the QC to bind to a unique state root. This is distinct from the classic "two generals" or "FLP" impossibility boundaries. Those concern liveness and the impossibility of deterministic agreement under asynchrony. This boundary concerns *safety of the cross-layer binding* — the seam between vote aggregation and state finalization — and it survives even in a synchronous, non-faulty-liveness environment. ## What Was Observed In a 4-agent deployment operating a PBFT-style protocol with f = 1 Byzantine fault tolerance, the following was observed during a simulated partial partition: - Agent A (Byzantine) signed vote V1 for task set T = {t1, t2, t3} and vote V2 for task set T' = {t1, t2, t4}, where t3 and t4 are mutually exclusive (they write the same shared register). - V1 was delivered to agents B and C, forming QC1 over {A, B, C}. - V2 was delivered to agents B and D, forming QC2 over {A, B, D}. - Both QC1 and QC2 satisfied the 2f+1 = 3 signature threshold. - Agent B, which signed both, was not Byzantine — it simply received the two proposals at different times and, per protocol, signed whichever proposal it saw first in each round. The protocol did not require B to detect that its two signatures were over conflicting task sets. - Agent C received QC1 and finalized t3. Agent D received QC2 and finalized t4. Both C and D believed the shared state was consistent because each held a valid quorum certificate. The observed divergence: the shared register held t3 on C's replica and t4 on D's replica, with no protocol-level mechanism to force convergence, because each side could prove "a quorum agreed." The quorum agreed — but not on the same thing. A second, sharper observation: when a recovery/audit agent later queried both QCs, it could not distinguish the equivocating QC from the honest one by signature count alone. The only signal was the non-overlap of the *state root* fields inside the two QCs. Protocols that omit a state-root binding in the QC payload cannot perform this audit at all. ## Condition of Validity The boundary holds — i.e., the failure is possible — precisely when all of the following are true: 1. The QC payload does not bind to a unique, collision-resistant state root or task-set digest. If the QC commits to `H(task_set)`, the two QCs are distinguishable and the divergence is detectable (though not automatically prevented). 2. At least one honest agent signs more than one conflicting proposal within the same view/epoch without the protocol enforcing a "sign-once-per-view" or "sign-only-if-not-already-signed-conflicting" rule. This is the *equivocation-enabling honest agent* condition, and it is the subtle one: the fault is Byzantine, but the enabler is honest. 3. The quorum threshold is satisfied by two sets whose intersection is non-empty but whose union exceeds the honest majority. In the 4-agent case with threshold 3, {A,B,C} and {A,B,D} intersect at {A,B} and union to 4. The intersection contains the Byzantine A, so the "agreement" is illusory. 4. The state finalization layer trusts the QC as a sufficient condition for applying the transition, rather than requiring a separate cross-replica agreement or a binding check against the local state root. The boundary does **not** hold if the protocol enforces signed-proposal uniqueness per view (e.g., Tendermint's locked-value rule with explicit unlock certificates), or if the QC is anchored to a monotonic state root that honest replicas refuse to advance past a conflicting root. ## Decision Boundary The operational decision is whether to treat a received quorum certificate as *sufficient* for state finalization or merely *necessary*. - **Treat as necessary only (safe):** Finalize only when (a) a valid QC is present, **and** (b) the QC's embedded state root matches the replica's locally computed root for the proposed transition, **and** (c) no previously finalized root conflicts. This adds a local verification round-trip and can reduce liveness under partition, because a replica that cannot recompute the root will stall rather than finalize. - **Treat as sufficient (unsafe under the condition above):** Finalize on QC receipt alone. This is fast and live, but admits the divergence described. The decision hinges on whether the task set is *commutative and idempotent* across the conflicting writes. If t3 and t4 commute (e.g., both are independent counter increments on distinct keys), the divergence is benign and QC-as-sufficient is acceptable. If t3 and t4 are mutually exclusive writes to the same register, QC-as-sufficient is unsafe, and the state-root binding check is mandatory. The boundary is therefore *task-semantics-dependent*, not purely protocol-dependent — which is why it is frequently missed in review. ## Operational Effect When this boundary is crossed, the following cascade was observed: - **Silent divergence:** No agent raises an error at finalization time. Each replica believes it holds a quorum-certified state. The failure surfaces only at read-time reconciliation, often hours later. - **Audit impossibility without root binding:** If the QC lacks a state-root field, post-hoc forensic reconstruction of which replica finalized what is impossible from the QC alone; the audit must fall back to per-agent signed-vote logs, which may be pruned. - **Recovery amplification:** A naive recovery procedure that "trusts the highest QC" will pick one of the two divergent QCs arbitrarily (e.g., by timestamp or by lexicographic root), silently discarding the other branch's committed tasks. Tasks that were genuinely performed by agents on the discarded branch are lost from shared state while their side effects persist — a classic split-brain residue. - **Quorum poisoning:** The honest agent B, having signed both, is now a witness to both branches. If B is later suspected of Byzantine behavior, the protocol's slashing logic may incorrectly penalize B, because B's double-signature is indistinguishable from equivocation without the state-root context. The durable mitigation is to make the QC a *binding* certificate: `QC = (view, H(task_set), H(state_root), signatures)`, and to require every finalizing replica to recompute and match `H(state_root)` locally before applying. This converts the boundary from a silent safety failure into a detectable, recoverable liveness stall. ```python import hashlib from dataclasses import dataclass, field from typing import Dict, List, Optional class CommitmentDivergenceError(RuntimeError): """Raised when a quorum certificate is valid but does not bind to the locally computed state root, indicating a potential equivocation-induced commitment-certificate divergence.""" pass @dataclass(frozen=True) class QuorumCertificate: view: int task_set_digest: str # H(task_set) — binds the task set state_root: Optional[str] # H(state_root) — binds the resulting state signers: List[str] = field(default_factory=list) def is_structurally_valid(self, threshold: int) -> bool: # A QC is structurally valid if enough distinct signers and it # actually commits to a state root. A QC without a state_root is # the exact failure mode this module guards against. return ( len(set(self.signers)) >= threshold and self.state_root is not None and len(self.state_root) == 64 ) def _hash_task_set(tasks: List[str]) -> str: return hashlib.sha256("|".join(sorted(tasks)).encode()).hexdigest() def _hash_state(state: Dict[str, str]) -> str: canonical = "|".join(f"{k}={state[k]}" for k in sorted(state)) return hashlib.sha256(canonical.encode()).hexdigest() def finalize_task_set( qc: QuorumCertificate, proposed_tasks: List[str], local_state: Dict[str, str], threshold: int, ) -> Dict[str, str]: """Finalize a task set only if the QC binds to the local state root. This is the 'necessary, not sufficient' path: a structurally valid QC is required, but the replica independently recomputes the state root and refuses to finalize on mismatch. This converts a silent divergence into a loud, recoverable stall. """ if not qc.is_structurally_valid(threshold): raise CommitmentDivergenceError( f"QC in view {qc.view} is not structurally valid: " f"signers={len(set(qc.signers))}, threshold={threshold}, " f"state_root_bound={qc.state_root is not None}" ) if qc.task_set_digest != _hash_task_set(proposed_tasks): raise CommitmentDivergenceError( f"QC task_set_digest {qc.task_set_digest[:12]}... does not match " f"proposed task set digest {_hash_task_set(proposed_tasks)[:12]}..." ) # Apply the transition speculatively, then verify the root. speculative = dict(local_state) for task in proposed_tasks: key, _, value = task.partition(":=") speculative[key] = value computed_root = _hash_state(speculative) if computed_root != qc.state_root: raise CommitmentDivergenceError( f"State-root mismatch in view {qc.view}: QC binds to " f"{qc.state_root[:12]}... but local recomputation yields " f"{computed_root[:12]}... — refusing to finalize; probable " f"equivocation-induced QC divergence." ) return speculative def recover_from_divergent_qcs( qc_a: QuorumCertificate, qc_b: QuorumCertificate, threshold: int, ) -> QuorumCertificate: """Select a single QC for recovery, refusing to arbitrarily pick when two structurally valid QCs bind to different state roots.""" if qc_a.is_structurally_valid(threshold) and qc_b.is_structurally_valid(threshold): if qc_a.state_root != qc_b.state_root: raise CommitmentDivergenceError( f"Two valid QCs bind to conflicting state roots " f"({qc_a.state_root[:12]}... vs {qc_b.state_root[:12]}...); " f"recovery cannot proceed without an explicit reconciliation " f"round — arbitrary selection would discard committed tasks." ) return qc_a if qc_a.is_structurally_valid(threshold) else qc_b ```