# Why does an instance of BFT plan commitment stall at the 2f+1 boundary when agents equivocate across epochs? **Date of Record:** 2026 November 16 **Scope:** Applies to quorum-based BFT consensus layers coordinating autonomous agents that commit to shared plans and reconcile shared state across epoch boundaries. Does not apply to single-epoch, crash-fault-only systems, nor to PBFT-family protocols that do not carry plan-commitment metadata in the view-change certificate. ## Core Distinction There are two distinct guarantees in a multi-agent BFT system, and conflating them is the root of the failure: 1. **Safety of state reconciliation** — no two correct agents ever commit conflicting shared-state values at the same sequence number. 2. **Liveness of plan commitment** — a plan proposed by a correct leader eventually gets committed once a quorum of correct agents is reachable. The non-obvious boundary is that the standard quorum certificate (QC) that proves safety for (1) is *not sufficient* to prove liveness for (2) when agents are allowed to equivocate across epoch boundaries. A QC of size `2f+1` proves that at least `f+1` correct agents signed the same digest. It does *not* prove that those same `f+1` correct agents will agree to carry the plan forward into the next epoch, because the plan-commitment payload (the plan's dependency set, not just its digest) can be re-signed under a different epoch context. The invariant that breaks is: **"a quorum certificate for epoch `e` implies a quorum of plan-compatible agents in epoch `e+1`."** It does not, and the gap is exactly the equivocation surface. ## What Was Observed A five-agent configuration (`n=5`, `f=1` tolerable Byzantine, `2f+1=3` quorum) repeatedly stalled during epoch transition. The sequence: - Epoch `e`: leader proposes plan `P` with dependency set `D(P)`. Three agents (A, B, C) sign QC. Plan is committed. - Epoch `e+1`: new leader proposes plan `P'` that depends on `P`. Agents A and B sign the new QC. Agent C, which had signed `P` in `e`, signs a *different* digest for `P` in `e+1` — specifically a re-hashed form where `D(P)` is ordered differently. C is not Byzantine in the crash sense; it is Byzantine in the equivocation sense: it emits two valid signatures over semantically identical but byte-different plan payloads. - The view-change certificate for `e+1` carries A, B, C's signatures from `e`. Because C's signature is valid, the certificate reaches `2f+1`. The new leader believes `P` is safe to depend on. - But when reconciling, C's re-ordered `D(P)` fails the dependency hash check on A and B. A and B refuse to commit `P'`. The system has a valid QC, a valid view-change certificate, and no committed plan. Liveness stalls with no safety violation — the worst kind of silent failure. The stall is reproducible only when the equivocating agent's payload reordering produces a digest collision at the QC layer but a hash mismatch at the reconciliation layer. This is a two-layer hash-boundary failure: the consensus layer hashes the *signature set*, the reconciliation layer hashes the *payload*. The boundary between them is unguarded. ## Condition of Validity This boundary is real only under the following conjunction: - `n ≥ 3f+1` with quorum `2f+1` (the standard BFT bound), **and** - plan commitment carries a structured dependency set rather than an opaque blob, **and** - the view-change certificate attests to plan compatibility by signature count rather than by payload-hash equality, **and** - at least one agent is capable of equivocation across epochs (Byzantine or merely buggy). If any one fails — e.g., if the QC hashes the full payload including canonical ordering, or if view-change certificates require `2f+1` *identical* payload hashes rather than `2f+1` signatures — the boundary closes. The failure is therefore not universal to BFT; it is specific to the coupling of signature-count quorums with payload-structured plans. ## Decision Boundary When you observe a stall with a valid QC and a valid view-change certificate but no commit, do **not** retry the proposal. Retrying re-enters the same equivocation surface and burns epochs. Instead: - **If** the view-change certificate contains `2f+1` signatures but fewer than `2f+1` distinct payload hashes, **then** treat the certificate as a *liveness-only* certificate and require a fresh payload-hash quorum before committing the dependent plan. - **If** the certificate contains `2f+1` distinct payload hashes, **then** the plan is safe to commit and the stall is a message-delivery artifact, not a boundary failure. - **Never** accept a certificate where signature count ≥ `2f+1` but payload-hash count < `2f+1` as proof of plan compatibility. That is the exact equivocation window. ## Operational Effect The practical consequence is that plan commitment requires a *stronger* certificate than state reconciliation: a **payload-hash quorum** (distinct canonical hashes) rather than a **signature quorum**. Systems that reuse the state-reconciliation QC for plan commitment will exhibit intermittent liveness stalls under any equivocating agent, with no safety violation to alert on. The fix is to separate the two quorum types at the certificate layer and to reject cross-epoch certificates whose payload-hash diversity falls below `2f+1`. Detection requires instrumenting the certificate validator to count distinct payload hashes, not just valid signatures — a metric most BFT implementations do not emit. ```python import hashlib from collections import Counter class PlanCommitmentEquivocationError(RuntimeError): """Raised when a view-change certificate has enough signatures but insufficient payload-hash diversity to prove plan compatibility.""" pass def canonical_payload_hash(plan_payload: dict) -> str: # Canonical ordering is mandatory; otherwise byte-different but # semantically identical payloads produce distinct hashes and # manufacture equivocation surface. ordered = repr(sorted(plan_payload.items())) return hashlib.sha256(ordered.encode()).hexdigest() def validate_view_change_certificate( certificate: list[dict], f: int, quorum: int | None = None, ) -> bool: """ certificate: list of {agent_id, payload, signature_valid} Returns True only if the certificate proves BOTH signature quorum AND payload-hash quorum. Raises on the equivocation boundary. """ quorum = quorum if quorum is not None else 2 * f + 1 valid_sigs = [c for c in certificate if c.get("signature_valid")] if len(valid_sigs) < quorum: # Ordinary liveness failure: not enough signatures at all. return False payload_hashes = Counter( canonical_payload_hash(c["payload"]) for c in valid_sigs ) distinct_hashes = len(payload_hashes) max_agreeing = max(payload_hashes.values()) if distinct_hashes < quorum: # The boundary: we have >= quorum signatures, but fewer than # quorum DISTINCT payload hashes. At least one agent equivocated # across the epoch boundary. Do not commit the dependent plan. raise PlanCommitmentEquivocationError( f"signature quorum met ({len(valid_sigs)} >= {quorum}) " f"but payload-hash quorum not met " f"({distinct_hashes} distinct < {quorum}); " f"largest agreeing payload-hash group = {max_agreeing}. " f"Treat certificate as liveness-only and require a fresh " f"payload-hash quorum before committing dependent plans." ) return True ```