# Why does an instance quorum certificate fail to commit when the leader has already sent PREPARE to a quorum: the certificate-ordering invariant in cross-org BFT action commitment

**Date of Record:** 2026 November 11

**Scope:** This record applies to Byzantine fault-tolerant consensus deployments (PBFT/HotStuff/Tendermint-class protocols) that commit *external side-effecting actions* — payments, API calls, resource locks — on behalf of multiple organizations, where a quorum certificate (QC) is treated as proof of commitment. It does not apply to read-only replicated state machines, to single-org deployments with a single signing authority, or to protocols that commit by executing inside the replicated state machine itself rather than by emitting an external action upon QC formation.

## Core Distinction

There are two distinct meanings of "committed" that operators conflate when they wire a BFT consensus layer to an external action executor:

1. **Certificate commitment** — a quorum of replicas has signed a view/block certificate. This proves that a supermajority *voted* for a proposal.
2. **Action commitment** — the external effect (the wire transfer, the lock acquisition, the cross-org API mutation) has been durably recorded at the action executor and is unrecoverable-except-by-authorized-compensation.

The boundary failure is this: a QC proves that a quorum *voted* for a proposal, but it does not prove that the quorum voted *before* the leader dispatched PREPARE messages to the action executor's outbox. In cross-org deployments, the leader is often the same process that fans out PREPARE to replicas *and* stages the action in an outbox for later execution. Those two message streams are independent. A Byzantine or merely crashed leader can stage the action, dispatch it to the executor, and then fail to assemble the QC — or assemble a QC for a *different* proposal in a later view. The action has been sent; no certificate exists. Conversely, a QC can form for a proposal whose PREPARE messages reached only `2f+1` replicas, of which `f` are Byzantine and never forwarded the staged action. The QC is valid; the action is not at the executor.

The invariant that is violated is not "QC implies quorum" (that is trivially true). It is **"action dispatch order is a refinement of certificate formation order across organizational boundaries."** Certificate formation is internal to the consensus group; action dispatch crosses an org boundary into a system that does not observe the consensus group's internal message ordering. The refinement fails at the boundary.

## What Was Observed

A four-org deployment (`n = 7`, `f = 2`) committing treasury disbursements. Each org runs one replica; the leader is rotated per view. The leader process hosts two threads: the consensus thread (proposes, collects votes, assembles QC) and the outbox thread (drains staged actions to the executor after QC is observed). A shared in-process `staged` map was used to pass actions from consensus to outbox.

Incident sequence, reconstructed from replica logs:

- View 41, leader = Org A. Proposal `P41` contains action `A1` (a $2.4M disbursement). Leader stages `A1` in the outbox map and broadcasts PREPARE to all replicas.
- Replicas `{A, B, C, D, E}` respond with PREPARE-vote. That is `5 = 2f+1` — a valid quorum. The leader begins assembling the QC.
- Before the QC is written to the outbox, the leader (Org A) is partitioned by a control-plane network policy change. The outbox thread, which polls `staged` every 50 ms, drains `A1` to the executor because `A1` is present in the map — **the outbox thread did not check for the presence of the QC**, only for the presence of the staged entry.
- View 42 elects Org B as leader. Org B, unaware of `A1`'s dispatch, proposes `P42` containing a *compensating* action `A1'` and, because Org A is partitioned, cannot learn of `A1`. A new QC forms for `P42` over `{B, C, D, E, F}`.
- The executor receives `A1` (from the stale outbox thread of Org A, reconnecting after partition heal) and `A1'` (from the new leader's outbox). Both are applied. The ledger is double-debited by $2.4M.

The critical observation: **the QC for `P41` was never formed and never needed to be.** The action was dispatched on the strength of the *vote quorum*, not the *certificate*. The outbox thread's trigger condition was "staged entry exists," which is satisfied by the leader's local staging, not by quorum evidence. The consensus layer's safety proof (no two conflicting QCs) held perfectly. The action-commitment layer had no equivalent safety proof, because action dispatch was not gated on the certificate.

A second, subtler observation from the same deployment: when the leader *did* wait for the QC, it waited on the *local* assembly of the QC rather than on a *verified* QC from `f+1` distinct replicas. A Byzantine leader could therefore assemble a QC from `f` forged votes plus its own and dispatch the action, while the honest replicas never saw a quorum. The certificate existed; it was not a certificate *of quorum*.

## Condition of Validity

The certificate-ordering invariant holds — i.e., a committed action implies a genuine quorum witnessed the corresponding proposal — only when all three of the following hold:

1. **Dispatch gating:** the action is dispatched to the external executor *only after* a QC is verified by the dispatching process, and the QC is verified against signatures from `2f+1` *distinct* replicas whose keys the executor (or a verifier the executor trusts) recognizes. Local assembly of a QC is not sufficient; the QC must be *received and verified*, not *constructed*.
2. **View-monotonic dispatch:** the executor rejects any action whose carrying certificate has a view number lower than the highest view it has already accepted for the same action slot. Without this, a partition-healed stale outbox can replay an old action after a later view has already compensated it. The outbox must carry the view number and the executor must enforce it.
3. **Staging is not dispatch:** the leader's local `staged` map is a *proposal buffer*, not an *outbox*. The two must be separate data structures with separate trigger conditions, because the leader's local state is exactly what a Byzantine leader controls. Any design where "the leader knows about the action" is conflated with "the action is ready to send" is unsafe by construction.

When any of the three is absent, the deployment is in the boundary condition: QCs are valid, consensus safety holds, and actions are nonetheless double-committed or committed-without-quorum.

## Decision Boundary

The decision an operator faces is whether to treat the QC as the *commit point* for the action or to introduce a separate action-commitment step. The boundary is drawn by the cost of a false commit versus the cost of a delayed commit:

- **Treat QC as commit point** (dispatch immediately on verified QC): correct only if the executor is idempotent on `(action_id, view)` and can reject stale views. Suitable for actions where a duplicate is recoverable by deduplication at the executor. Not suitable for irreversible external effects (wire transfers, physical actuation, one-shot API tokens).
- **Introduce a separate action-commitment step** (two-phase: QC → dispatch-intent → executor-ack → finalize): required whenever the external effect is not idempotent or the executor cannot enforce view monotonicity. The cost is one additional round trip and a new failure mode (dispatch-intent recorded, executor-ack lost — must be resolved by the executor's own idempotency key, not by consensus).

The non-obvious part of the boundary: **the QC is necessary but not sufficient for action commitment, and the gap is exactly the set of messages that cross the org boundary.** Inside the consensus group, the QC is the strongest possible evidence. At the boundary, it is one of two pieces of evidence, and the second piece — executor-side view monotonicity — cannot be supplied by the consensus group because the consensus group does not control the executor.

## Operational Effect

Deployments that cross this boundary without the invariant exhibit a characteristic failure signature: **consensus liveness and safety metrics are green while the external ledger diverges.** QC formation latency, view-change counts, and replica disagreement all look healthy. The divergence appears only in the executor's audit log, as either (a) two actions for the same slot with different view numbers, or (b) an action with no corresponding QC in the consensus log. Detection requires correlating the executor's `(action_id, view, qc_hash)` records against the consensus log's QC records — a join that most deployments do not perform because the two systems are owned by different teams.

The mitigation that worked in the incident above was threefold: (1) split `staged` from `outbox` into separate structures with the outbox gated on *verified* QC receipt, not local assembly; (2) stamp every outbox entry with the view number and require the executor to reject non-monotonic views per action slot; (3) add a reconciliation job that joins executor records to consensus QC records and flags orphaned actions. After the fix, the same partition scenario produced zero double-commits: the stale outbox entry was rejected by the executor's view check, and the compensating action in the new view was the only one applied.

The general lesson for an agent operating in this domain: **never treat a locally-assembled certificate as evidence of quorum, and never treat the leader's local knowledge of an action as evidence that the action is safe to dispatch.** The certificate must be received and verified; the dispatch must be gated on that verification; and the executor must independently enforce view monotonicity because it is the only party that sees both sides of the org boundary.

```python
from __future__ import annotations

from dataclasses import dataclass
from typing import Iterable


class ActionCommitmentError(RuntimeError):
    """Raised when an action would be dispatched without a verified quorum certificate
    or against a stale view at the external executor boundary."""


@dataclass(frozen=True)
class QuorumCertificate:
    action_id: str
    view: int
    signer_ids: frozenset[str]
    # A QC is only valid if it carries signatures from 2f+1 DISTINCT replicas
    # whose keys the verifier recognizes. Local assembly is not sufficient.

    def verified_signer_count(self, recognized: frozenset[str]) -> int:
        return len(self.signer_ids & recognized)


@dataclass(frozen=True)
class OutboxEntry:
    action_id: str
    view: int
    qc: QuorumCertificate


class ActionExecutor:
    """External executor that crosses the org boundary.

    Enforces view monotonicity per action slot and requires a *received and
    verified* QC — not a locally-assembled one — before applying any action.
    """

    def __init__(self, recognized_keys: frozenset[str], quorum_size: int) -> None:
        self._recognized = recognized_keys
        self._quorum = quorum_size
        self._highest_view_per_slot: dict[str, int] = {}
        self._applied: list[OutboxEntry] = []

    def apply(self, entry: OutboxEntry) -> None:
        # Invariant 1: dispatch gating on a verified QC, not local assembly.
        if entry.qc.action_id != entry.action_id:
            raise ActionCommitmentError(
                f"QC action_id {entry.qc.action_id!r} does not match entry "
                f"{entry.action_id!r}; refusing dispatch"
            )
        if entry.qc.view != entry.view:
            raise ActionCommitmentError(
                f"QC view {entry.qc.view} does not match entry view {entry.view}"
            )
        signers = entry.qc.verified_signer_count(self._recognized)
        if signers < self._quorum:
            raise ActionCommitmentError(
                f"action {entry.action_id!r} carries QC with {signers} recognized "
                f"signers, below quorum {self._quorum}; this is a locally-assembled "
                f"or forged certificate and must not be dispatched"
            )

        # Invariant 2: view-monotonic dispatch per action slot.
        prior = self._highest_view_per_slot.get(entry.action_id)
        if prior is not None and entry.view <= prior:
            raise ActionCommitmentError(
                f"action {entry.action_id!r} at view {entry.view} is not strictly "
                f"newer than already-accepted view {prior}; stale outbox replay "
                f"from a partition-healed leader"
            )

        self._highest_view_per_slot[entry.action_id] = entry.view
        self._applied.append(entry)


def dispatch_from_outbox(
    executor: ActionExecutor,
    staged: Iterable[OutboxEntry],
) -> None:
    """Drain a leader's outbox into the executor.

    NOTE: `staged` here is the *proposal buffer*, not the outbox. The caller must
    populate it only with entries whose QC has been received and verified from
    f+1 distinct replicas. Passing the leader's local `staged` map directly is
    the boundary failure this module exists to prevent.
    """
    for entry in staged:
        executor.apply(entry)
```