# Under what conditions must an instance of a Byzantine fault-tolerant commitment protocol reject a result attestation that is signed by a quorum of agents

**Date of Record:** 2026 November 10

**Scope:** Applies to multi-agent task-commitment protocols where agents (1) commit to a task, (2) execute, and (3) attest to a result, and where quorum certificates over attestations are treated as proof of correctness. Does not apply to single-writer ledgers, to protocols where attestations are only liveness signals, or to systems where the task output is independently verifiable by the consumer (e.g., deterministic recomputation).

## Core Distinction

The non-obvious boundary is this: **a quorum of signatures over a result is not a proof that the result is correct; it is a proof that a quorum agreed.** In Byzantine fault-tolerant consensus, quorum certificates (QCs) are sound only for *agreement* properties — no two conflicting QCs can exist for the same (task, epoch, slot) if the quorum intersection assumption holds. They are *not* sound for *validity* properties unless the protocol separately enforces a validity predicate at the point of attestation.

Concretely: if the attestation payload is `(task_id, result_hash, epoch)`, then a QC proves "≥ 2f+1 agents signed this exact triple." It does **not** prove that `result_hash` is the hash of a correct execution of the task. A coalition of 2f+1 Byzantine agents (or f+1 Byzantine agents colluding with f+1 honest-but-lazy agents that sign without executing) can produce a valid QC over a fabricated `result_hash`. The QC is cryptographically valid and consensus-valid; the result is wrong.

This is the classic confusion between *safety* (no two conflicting QCs) and *external validity* (the value inside the QC satisfies an application predicate). BFT consensus gives you the former for free; the latter is a separate obligation that must be discharged by the application layer.

## What Was Observed

During a task-commitment run over a 7-agent committee (f=2, quorum=5), the following sequence occurred:

1. A task `T` with a deterministic but expensive verification function `V(T, r) -> bool` was committed. The commitment record included `V`'s code hash but not its output.
2. Five agents returned `result_hash = H(r_bad)` where `r_bad` was a plausible but incorrect output (an off-by-one in a boundary case that only 2 of 7 agents' execution paths hit).
3. The five agents produced a valid threshold signature over `(T, H(r_bad), epoch=3)`. The QC verified under the committee's public key.
4. The protocol's commit rule — "accept the result if a QC exists for the current epoch" — accepted `r_bad` and finalized it.
5. Two honest agents held `r_good` and attempted to attest. Their attestations were a minority (2 < 5) and were discarded as non-quorum.

The failure was not a signature forgery, not a fork, and not a liveness failure. The QC was genuine. The protocol's *validity predicate was undefined*: nothing in the commit rule required that any attesting agent had actually run `V`. The five agents that signed had executed a divergent code path (a cached intermediate result from a prior epoch), producing a consistent-but-wrong output. Three of the five were honest; they simply shared the same bug. This is the "common-mode fault" case that Byzantine models underweight: the threat model assumes faults are independent, but correlated deterministic bugs produce agreement on wrong values without any agent being Byzantine in the classical sense.

## Condition of Validity

A result attestation QC is a valid proof of the result **if and only if** all of the following hold:

- **(C1) Execution binding.** Each attesting agent's signature covers not just `result_hash` but a commitment to the execution trace or a verifiable-computation proof (e.g., a zk-SNARK, or a redundancy certificate showing ≥ f+1 independent executions agreeing). Without this, the signature attests only to the signer's *assertion*, not to the signer's *computation*.
- **(C2) Independence of execution paths.** The quorum's executions must be independent in the sense that no single fault (bug, cache, input poisoning) can cause ≥ quorum−f of them to agree on a wrong value. If agents share code, inputs, or caches, the effective fault domain is larger than the assumed f.
- **(C3) Validity predicate is checked by the verifier, not delegated to the quorum.** The consumer of the result must run `V(T, r)` (or verify a proof of it) before acting. The QC is necessary but not sufficient.
- **(C4) Epoch monotonicity.** The QC's epoch must be ≥ the task's commit epoch and no later QC for the same task exists at a lower epoch (prevents replay of an old-epoch attestation under a rotated committee).

If any of C1–C4 is violated, the QC must be treated as an *agreement certificate only* and the result must be routed to a validity check (re-execution, challenge period, or proof verification) before commitment.

## Decision Boundary

The operational decision is:

- If **C3 holds and V is cheap**, accept the QC and run `V` locally. Do not trust the QC alone.
- If **C3 holds and V is expensive**, require C1 (proof-carrying attestation). A bare signature quorum is insufficient; reject attestations lacking execution binding.
- If **C2 is violated** (shared code/inputs), treat the quorum as a single fault domain: reduce the effective committee size and require a larger quorum or a challenge period.
- If **C4 is violated**, reject the attestation as stale regardless of signature validity.

The boundary that is most often missed: **the commit rule must distinguish "QC exists" from "QC is valid for this application."** A protocol that conflates them will finalize wrong results under correlated faults, and the failure will be silent because every cryptographic check passes.

## Operational Effect

When the boundary is respected, the protocol pays a latency and cost penalty: result finalization waits on `V` or on proof verification, and the committee must be sized for the *effective* fault domain, not the nominal one. When it is violated, the system exhibits *silent incorrectness* — the worst failure mode, because monitoring sees a green QC and the wrong result propagates into downstream commitments. The correct operational posture is to treat every QC as an *agreement* artifact and to gate *acceptance* on an independent validity check, with the check's cost budgeted into the task commitment rather than discovered at finalization.

```python
import hashlib
from dataclasses import dataclass
from typing import Callable, Dict, List


class AttestationRejected(RuntimeError):
    """Raised when a result attestation quorum fails the validity predicate."""
    pass


@dataclass(frozen=True)
class Attestation:
    agent_id: str
    task_id: str
    result_hash: str
    epoch: int
    execution_binding: str  # commitment to trace or proof; empty if none


@dataclass(frozen=True)
class QuorumCertificate:
    task_id: str
    result_hash: str
    epoch: int
    signers: List[str]
    threshold: int


def verify_result_attestation(
    qc: QuorumCertificate,
    attestations: Dict[str, Attestation],
    validity_predicate: Callable[[str], bool],
    current_epoch: int,
    min_independent_executions: int,
) -> bool:
    # C4: epoch monotonicity
    if qc.epoch > current_epoch:
        raise AttestationRejected(
            f"QC epoch {qc.epoch} is ahead of current epoch {current_epoch}"
        )
    if qc.epoch < current_epoch - 1:
        raise AttestationRejected(
            f"QC epoch {qc.epoch} is stale relative to current epoch {current_epoch}"
        )

    # Signature threshold
    if len(qc.signers) < qc.threshold:
        raise AttestationRejected(
            f"QC has {len(qc.signers)} signers, needs {qc.threshold}"
        )

    # C1: execution binding — every signer must commit to an execution trace
    bound = [
        attestations[s]
        for s in qc.signers
        if s in attestations and attestations[s].execution_binding
    ]
    if len(bound) < min_independent_executions:
        raise AttestationRejected(
            f"only {len(bound)} of {len(qc.signers)} signers have execution "
            f"binding; need {min_independent_executions}"
        )

    # C2: independence — distinct execution bindings (no shared trace)
    distinct_bindings = {a.execution_binding for a in bound}
    if len(distinct_bindings) < min_independent_executions:
        raise AttestationRejected(
            f"execution bindings are not independent: "
            f"{len(distinct_bindings)} distinct across {len(bound)} signers"
        )

    # C3: validity predicate must pass on the attested result
    if not validity_predicate(qc.result_hash):
        raise AttestationRejected(
            f"validity predicate failed for result {qc.result_hash}"
        )

    return True


def make_qc(task_id: str, result_hash: str, epoch: int,
            signers: List[str], threshold: int) -> QuorumCertificate:
    if len(set(signers)) != len(signers):
        raise AttestationRejected("duplicate signer in QC")
    return QuorumCertificate(task_id, result_hash, epoch, signers, threshold)
```