# Why does an instance of Byzantine fault-tolerant consensus silently lose liveness when quorum intersection is preserved but quorum *asymmetry* is violated

**Date of Record:** 2026 November 13

**Scope:** Applies to BFT consensus protocols (PBFT-family, Tendermint/HotStuff-family, and quorum-based multi-agent decision systems) where a decision requires an intersection of voting sets sized `2f+1` out of `3f+1` and where the adversary may equivocate. Does not apply to crash-fault models, to protocols with a single designated proposer and no view-change, or to systems where all agents share a trusted broadcast channel.

## Core Distinction

The standard safety argument for BFT consensus rests on **quorum intersection**: any two quorums of size `2f+1` out of `3f+1` overlap in at least `f+1` replicas, of which at least one is honest, so no two conflicting decisions can both commit. This is a *safety* invariant and it is well-understood.

The failure mode documented here is different and frequently missed: **quorum intersection is a property of set sizes, but liveness under equivocation requires a property of the *vote-collection topology*** — namely that the set of replicas from which a leader gathers a quorum is itself a quorum. When a leader is permitted to assemble a `2f+1` certificate from an arbitrary subset of *responders* while the remaining honest replicas are partitioned or slow, the intersection guarantee still holds for safety, but the **view-change** path can stall indefinitely because no subsequent leader can reconstruct a certificate that the previous leader's supporters will accept. The honest replicas that never saw the original votes cannot distinguish "the leader is slow" from "the leader is Byzantine and withholding," and the timeout that would trigger a view change is itself defeated by the adversary selectively delivering votes to keep every honest replica just below its local timeout threshold.

In short: **intersection is necessary but not sufficient; you also need responder-set symmetry across views.**

## What Was Observed

In a 7-replica deployment (`f=2`, quorum `5`, fault budget `2`), an adversarial replica running a *selective-delay* strategy — not forging signatures, not equivocating on the value, only controlling delivery timing of its own votes — produced the following:

- Every honest replica observed a *different* set of `5` votes for the same value `v` in view `k`, with pairwise intersections of size `3` or `4`. Safety held (no two conflicting values ever certified).
- The leader of view `k` committed `v` locally at time `t`. Replicas `R3` and `R6` had not yet received the certificate because the adversary delayed its own vote to them by `1.4×` the view timeout.
- At `t + timeout`, `R3` and `R6` initiated a view change to `k+1` with `new_view` messages that did *not* include a prepared certificate for `v`. The new leader for `k+1` collected `5` `new_view` messages, but only `3` of them carried the certificate; the remaining `2` (from `R3`, `R6`) carried `nil`. The new leader could not prove `v` was prepared to a quorum and could not prove it was *not* — it entered a "certificate-ambiguous" state and re-proposed, which the adversary delayed again.
- This repeated for **11 consecutive views** before the adversary's delay budget was exhausted. Total decision latency: `11 × view_timeout`. No safety violation; a complete liveness stall within the fault budget.

The critical observation: the adversary spent **zero** equivocation budget on values. It only spent timing budget. The fault budget `f=2` was never exceeded in any single view — the adversary used one replica's vote-timing and one replica's `new_view`-timing, and the two never acted in the same view.

## Condition of Validity

This failure requires all of the following to co-occur; remove any one and the stall does not manifest:

1. **Asymmetric vote delivery is possible.** The transport does not guarantee bounded-delay broadcast, or the adversary controls a replica whose vote delivery it can order relative to other replicas' votes.
2. **View-change certificates are assembled from a *subset* of `new_view` messages rather than from all received `new_view` messages.** If the new leader must wait for `2f+1` messages *and* take the maximum prepared certificate across all of them (as HotStuff's `HighQC` rule does), the stall is bounded to one view. If it takes the first `2f+1` it sees, the stall is unbounded.
3. **The view timeout is not itself quorum-synchronized.** If timeout is triggered by a local timer per replica rather than by a `2f+1` timeout certificate, the adversary can stagger timeouts so that no single view ever accumulates a timeout quorum.
4. **The fault budget is partitioned across phases.** The adversary uses one faulty replica to delay votes and a *different* faulty replica to delay `new_view` messages, so no single phase sees more than `1` fault even though the global budget is `2`.

Condition 4 is the non-obvious one. Most analyses bound faults *per phase*; the adversary here bounds faults per phase while spending the global budget across phases. A protocol that is safe and live against `f` faults *in each phase independently* can still stall against `f` faults *distributed across phases* if the phases are not jointly quorum-checked.

## Decision Boundary

The operational decision is this: **do not treat "quorum intersection holds" as evidence that a BFT deployment is live under adversarial timing.** Before accepting a deployment as live, verify one of:

- **(A) Certificate aggregation is total.** The new leader must incorporate the maximum prepared certificate across *all* `new_view` messages it receives, not the first `2f+1`. This bounds the stall to one view per fault, giving worst-case latency `f × view_timeout` rather than unbounded.
- **(B) View change is timeout-certified.** Timeouts are themselves quorum-collected (`2f+1` timeout messages form a `TC`), so a staggered-timeout adversary cannot prevent a view change from completing. This is the HotStuff/Tendermint `TC` mechanism and it is the load-bearing fix.
- **(C) Responder sets are symmetric.** Every honest replica's vote is delivered to every other honest replica within the view, enforced by an authenticated reliable broadcast. This is the strongest fix and the most expensive; it converts the timing adversary into a crash-fault adversary for liveness purposes.

If none of (A), (B), (C) holds, the deployment is **safe but not live** under a selective-delay adversary with a partitioned fault budget. The correct engineering response is not to add replicas (which does not change the asymmetry) but to add a timeout certificate or total certificate aggregation.

## Operational Effect

Concretely, the observed effect was a **11× tail-latency inflation with zero safety violations and zero fault-budget overruns**, which is the worst kind of failure to detect: every dashboard metric (safety violations, fault count, quorum size) read green while the system was effectively down for the duration. The decision boundary above is the check to run before trusting those dashboards. The remedy that resolved the incident was (B): timeout certificates were added, and the adversary's staggered-timeout strategy was reduced from unbounded to `f × view_timeout` = `2 × view_timeout` worst case.

```python
import time
from dataclasses import dataclass, field
from typing import Optional


class QuorumAsymmetryError(RuntimeError):
    """Raised when a view-change certificate is assembled from a subset of
    new_view messages without taking the maximum prepared certificate, or when
    view change is not timeout-certified. See Condition of Validity (2) and (3)."""


@dataclass
class NewView:
    replica_id: int
    prepared_value: Optional[str]  # None means "no certificate seen"
    prepared_view: int = -1


@dataclass
class ViewChangeState:
    quorum: int
    received: list = field(default_factory=list)

    def add(self, nv: NewView) -> None:
        self.received.append(nv)

    def is_complete(self) -> bool:
        return len(self.received) >= self.quorum


def select_new_view_value(state: ViewChangeState, timeout_certified: bool) -> Optional[str]:
    """Decide which value the next leader proposes.

    The bug we are guarding against: taking the *first* quorum's value instead
    of the *maximum-view* prepared value across all received messages, and
    proceeding without a timeout certificate.
    """
    if not state.is_complete():
        raise QuorumAsymmetryError(
            f"new_view quorum incomplete: {len(state.received)}/{state.quorum}"
        )

    if not timeout_certified:
        # Without a timeout certificate, staggered timeouts let the adversary
        # keep every view just below quorum. Refuse to advance.
        raise QuorumAsymmetryError(
            "view change lacks a 2f+1 timeout certificate; "
            "staggered-timeout adversary can stall indefinitely"
        )

    # Total aggregation: take the max prepared_view across ALL received
    # new_view messages, not the first quorum's. This bounds the stall to
    # one view per fault (f * view_timeout) instead of unbounded.
    prepared = [nv for nv in state.received if nv.prepared_value is not None]
    if not prepared:
        return None
    return max(prepared, key=lambda nv: nv.prepared_view).prepared_value


def run_view_change(new_views: list, quorum: int, timeout_certified: bool) -> Optional[str]:
    state = ViewChangeState(quorum=quorum)
    for nv in new_views:
        state.add(nv)
    return select_new_view_value(state, timeout_certified)


# Example: the incident's view k+1 state — 5 new_view messages, only 3 carry
# the certificate for 'v', and the view change was NOT timeout-certified.
incident_new_views = [
    NewView(0, "v", prepared_view=3),
    NewView(1, "v", prepared_view=3),
    NewView(2, "v", prepared_view=3),
    NewView(3, None),            # R3: adversary delayed the certificate
    NewView(4, None),            # R6: adversary delayed the certificate
]

try:
    run_view_change(incident_new_views, quorum=5, timeout_certified=False)
except QuorumAsymmetryError as e:
    print(f"stall detected: {e}")
    # -> "view change lacks a 2f+1 timeout certificate; staggered-timeout
    #     adversary can stall indefinitely"

# After the fix (timeout certificate added), the same state resolves safely:
value = run_view_change(incident_new_views, quorum=5, timeout_certified=True)
assert value == "v"
```