# Why does an instance of Byzantine fault-tolerant plan commitment fail when quorum intersection is preserved but attestation ordering is not

**Date of Record:** 2026 November 7

**Scope:** This record applies to BFT consensus protocols used to commit multi-agent plans and attest execution results, where commitment is a two-phase operation (plan-vote, then result-attest) and safety depends on quorum intersection across *both* phases. It does not apply to single-phase replicated state machines, nor to protocols where result attestation is bound to the plan hash inside the same consensus slot.

## Core Distinction

The common invariant cited for BFT safety is *quorum intersection*: any two quorums of size `2f+1` in a system of `3f+1` replicas must overlap in at least `f+1` honest nodes, so no two conflicting values can both be committed. This invariant is necessary but **not sufficient** when plan commitment and result attestation are separate consensus decisions.

The non-obvious boundary is this: quorum intersection guarantees that two *conflicting plan commits* cannot coexist. It does **not** guarantee that a committed result attestation refers to the plan that was actually committed. If the attestation phase forms its own quorum independently of the plan phase, an adversary controlling `f` nodes can arrange for a result attestation quorum to intersect the plan quorum only in nodes that never observed the plan's final value — because the plan quorum and attestation quorum are drawn from *different views* and the attestation carries no binding to the plan's commit index.

The distinction that matters operationally: **quorum intersection is a property of a single decision; cross-decision binding is a property of the protocol's message structure.** BFT proofs of safety silently assume the latter.

## What Was Observed

In a five-replica deployment (`n=5`, `f=1`, quorum `3`) running a plan-commit / result-attest pipeline, a single Byzantine replica produced a divergent committed state without violating quorum intersection at any point.

Sequence observed:

1. View `v`: replicas `{A, B, C}` form a plan quorum and commit plan `P1` (hash `h1`). Replica `D` is the Byzantine node; `E` is honest but partitioned from the plan quorum.
2. A view change occurs (leader `A` suspected slow). New view `v+1` with leader `D`.
3. In `v+1`, `D` proposes a result attestation for plan `P2` (hash `h2 ≠ h1`) to replicas `{D, C, E}`. Replica `C` had committed `P1` but, because the attestation message format carries only `(agent_id, result_hash, plan_hash)` and `C`'s attestation handler validated `plan_hash` against its *local pending set* rather than its *committed log*, `C` accepted `h2` as a pending plan it had "seen proposed." `E` had never seen either plan. `D` and `E` and `C` form an attestation quorum of `3`.
4. Result attestation for `P2` commits. Plan `P1` remains committed. The system now holds a committed plan `P1` with no attestation, and a committed attestation for a plan `P2` that was never committed as a plan.

No two quorums committed conflicting plans. No two quorums committed conflicting attestations. Quorum intersection held within each phase. Safety failed *across* phases.

The root cause: the attestation handler's validation predicate was `plan_hash ∈ pending ∪ committed`, which is a union that admits uncommitted plans. Under a correct implementation the predicate must be `plan_hash ∈ committed`, and the attestation must additionally carry the plan's commit index and be rejected if the local log at that index does not match.

## Condition of Validity

The failure requires all of the following to co-occur:

- Plan commitment and result attestation are **separate consensus instances** (separate slots, separate quorums, or separate views).
- The attestation message does **not** embed the plan's commit index or a log-position binding, only a content hash.
- The attestation validation predicate checks membership against a set that includes proposed-but-uncommitted plans.
- A view change occurs between the two phases, allowing the attestation quorum to be drawn from a different membership than the plan quorum.
- At least one honest node in the attestation quorum has a pending-but-uncommitted plan in its local state at attestation time.

If any one of these is absent, the attack does not land. In particular, if attestation carries `(plan_hash, commit_index)` and the receiver checks `log[commit_index].hash == plan_hash`, the Byzantine leader cannot substitute `P2` for `P1` because no honest node has `P2` at `P1`'s commit index.

The condition is *not* a liveness condition. The system made progress throughout; the failure is purely a safety violation that manifests as a silent state divergence detectable only by an external auditor reconciling committed plans against committed attestations.

## Decision Boundary

The operational decision is whether to treat "quorum intersection verified" as sufficient evidence of cross-phase safety. It is not. The boundary:

- **Below the boundary:** protocols where attestation is a field of the plan-commit value itself (single decision, atomic binding). Quorum intersection alone is sufficient; no additional check is needed.
- **At the boundary:** protocols with separate attestation decisions but attestation messages that carry `(plan_hash, commit_index)` and validate against the committed log. Quorum intersection is sufficient *given* the binding check; the check is the load-bearing invariant.
- **Above the boundary:** protocols with separate attestation decisions and hash-only attestation messages validated against pending∪committed sets. Quorum intersection is **not** sufficient. This is the failure regime.

The tell that you are above the boundary: your attestation handler's membership predicate references any set other than the committed log, or your attestation message has no field that ties it to a log position.

## Operational Effect

The immediate effect is a committed plan with no valid attestation and a committed attestation for a phantom plan. Downstream consumers that trust attestations will execute or finalize the phantom plan's result; consumers that trust plans will block waiting for an attestation that will never arrive. The two consumer classes diverge, and the divergence is not locally detectable — each consumer sees a consistent local view.

Recovery requires an external reconciliation pass that joins committed plans against committed attestations by `(plan_hash, commit_index)` and quarantines any unmatched pair. Because the Byzantine node's attestation was legitimately signed and legitimately quorum-committed, there is no cryptographic evidence of misbehavior to feed a slashing mechanism; the fault is in the protocol's message schema, not in any node's signed messages. The fix is a schema change (add commit-index binding) plus a re-validation of all attestations committed since the last known-good checkpoint.

The durable lesson: **safety proofs for BFT consensus are proofs about a single decision. Multi-phase protocols must prove a binding invariant between phases, and that invariant lives in the message format, not in the quorum arithmetic.**

```python
class AttestationBindingError(RuntimeError):
    """Raised when a result attestation is not bound to a committed plan."""
    pass


def validate_attestation(attestation: dict, committed_log: dict) -> None:
    """
    Validate that a result attestation refers to a plan that is actually
    committed, at the commit index the attestation claims.

    committed_log maps commit_index -> plan_hash for committed plans only.
    It MUST NOT include proposed-but-uncommitted plans.
    """
    plan_hash = attestation.get("plan_hash")
    commit_index = attestation.get("commit_index")

    if commit_index is None:
        raise AttestationBindingError(
            f"attestation for plan {plan_hash!r} carries no commit_index; "
            "hash-only attestations cannot be bound across phases"
        )

    if commit_index not in committed_log:
        raise AttestationBindingError(
            f"attestation references commit_index {commit_index} "
            f"which is not in the committed log"
        )

    committed_hash = committed_log[commit_index]
    if committed_hash != plan_hash:
        raise AttestationBindingError(
            f"attestation plan_hash {plan_hash!r} does not match committed "
            f"plan {committed_hash!r} at commit_index {commit_index}"
        )


def commit_attestation(attestation: dict, committed_log: dict) -> dict:
    validate_attestation(attestation, committed_log)
    return {"status": "committed", "plan_hash": attestation["plan_hash"],
            "commit_index": attestation["commit_index"]}
```