# Why does an instance of Byzantine consensus for multi-agent task commit fail at the quorum-intersection boundary when attestation sets are not transitively closed?

**Date of Record:** 2026 November 14

**Scope:** Applies to multi-agent systems where a task commit requires a supermajority of signed result attestations and where attestations may be relayed or aggregated by intermediate agents. Does not apply to systems with a single centralized attestor or to consensus protocols where every validator independently observes the raw result (i.e., no attestation relaying).

## Core Distinction

There are two distinct notions of "the set of agents that vouched for this result":

1. **The attestation frontier** — the set of agents whose *signatures* appear on the committed result payload.
2. **The attestation closure** — the set of agents whose signatures are transitively reachable through the relay graph, i.e., the agents that actually observed and signed the underlying observation, not merely countersigned a digest.

Byzantine fault-tolerant commit rules (2f+1 of 3f+1) are proven safe under the assumption that the quorum is computed over a *fixed, closed* validator set that each honest validator can independently enumerate. In multi-agent task commit, agents frequently relay attestations ("I saw A and B sign this digest, so I sign it too"), producing a frontier that is larger than the closure. The safety proof does not survive this substitution: two quorums of size 2f+1 can intersect in the *frontier* while their *closures* are disjoint, because the intersection consists entirely of relays that never observed the result. This is the boundary failure. The invariant that must hold is not "quorums intersect" but "quorums intersect in the closure."

## What Was Observed

During a task-commit round with 7 validators (f=2, quorum=5), two conflicting result digests were committed in the same round. The commit certificates for both digests each carried 5 signatures and passed local quorum verification. Inspection of the relay graph showed the intersection of the two frontier sets was 3 agents, all of which had signed both digests by *countersigning* a digest they received from a peer rather than by observing the task output. The closure of each frontier contained only 2 agents that had actually executed the task; the closures were disjoint. The intersection of the frontiers (3) satisfied the quorum-intersection arithmetic (5+5-7=3 ≥ f+1=3) while the intersection of the closures (0) did not. The protocol's arithmetic check was correct and the protocol was still unsafe, because the arithmetic was applied to the wrong set.

A secondary observation: honest relayers did not detect the problem because each individual relay step was locally justified ("I received a digest signed by ≥ quorum"). The violation is only visible at the level of the composed graph, which no single agent observes.

## Condition of Validity

The quorum-intersection safety argument is valid only when, for every committed certificate, the set of signers is a subset of agents that independently observed the attested result — that is, when frontier ⊆ closure, or equivalently when the relay graph is *transitively closed under the attestation relation* before the certificate is formed. This condition holds in classical BFT because validators are the observers. It fails whenever:

- Attestations are aggregatable (a signature over a digest can be produced without producing the digest's underlying observation), and
- The protocol accepts an aggregate whose members were not individually verified as observers, and
- The validator set is large enough that honest agents cannot afford to re-execute and instead rely on relayed evidence.

If any one of these three is absent, the classical argument is restored. The dangerous regime is specifically the conjunction: cheap relay + no observer check + economic pressure to relay.

## Decision Boundary

The decision to commit on a certificate must distinguish between *counting signatures* and *counting observers*. The operational boundary is:

- If the protocol cannot enumerate, for each signature, whether the signer executed the task (observer) or merely countersigned a digest (relay), then the certificate must be treated as *unverified evidence* and must not be used to commit. It may be used to *propose*.
- If the protocol can enumerate observers, quorum must be computed over observers only; relays may count toward liveness gossip but never toward the 2f+1 safety threshold.
- A certificate whose closure size is below f+1 must be rejected regardless of frontier size, because it provides no intersection guarantee with any future certificate.

The boundary is therefore: **frontier size governs liveness; closure size governs safety.** Any implementation that uses one number for both has collapsed the distinction and is unsound at this boundary.

## Operational Effect

Systems that cross this boundary exhibit a characteristic failure signature: commits succeed at normal rates, latency is unaffected, and the failure appears only as *occasional conflicting commits under partition or under adversarial relay injection*, typically at a rate proportional to the fraction of relay-only signers. Because each local check passes, the failure is invisible to per-agent monitoring and surfaces only in cross-agent reconciliation (two agents holding different committed results for the same task). The remediation is to attach an observer-proof to each attestation (e.g., a signature over the task output itself, not over its digest, or a verifiable execution receipt) and to recompute quorum over the closure. This raises attestation cost and reduces throughput, which is why the boundary is routinely crossed under load — the cost of closure verification is paid only when the system is already stressed, which is precisely when relay-only signers proliferate.

```python
class AttestationClosureError(RuntimeError):
    """Raised when a commit certificate's quorum is satisfied only by relay signers,
    i.e. frontier size >= quorum but closure size < f+1."""
    pass


def verify_commit_certificate(
    certificate: dict,
    f: int,
    quorum: int,
    observer_proofs: dict,
) -> bool:
    """
    certificate: {"digest": str, "signers": [agent_id, ...]}
    observer_proofs: {agent_id: bool}  # True iff agent independently executed the task
    Returns True iff the certificate is safe to commit on.
    """
    signers = certificate["signers"]
    frontier = set(signers)

    # Frontier must meet quorum for liveness justification.
    if len(frontier) < quorum:
        return False

    # Closure: only signers with an observer-proof count toward safety.
    closure = {a for a in frontier if observer_proofs.get(a, False)}

    # Safety requires closure to guarantee intersection with any future quorum.
    if len(closure) < f + 1:
        raise AttestationClosureError(
            f"certificate for digest {certificate['digest']!r} has "
            f"frontier={len(frontier)} (>= quorum {quorum}) but "
            f"closure={len(closure)} (< f+1={f + 1}); "
            f"relay-only signers={sorted(frontier - closure)}. "
            f"Refusing to commit: quorum intersection is not guaranteed."
        )

    return True
```