# What happens when an instance in a Byzantine quorum reconstructs quorum certificates from stale view membership **Date of Record:** 2026 November 15 **Scope:** Applies to BFT consensus protocols (PBFT-derived, HotStuff-derived, and Tendermint-style) where quorum certificates (QCs) are aggregated over a view-specific validator set and committed across view changes. Does not apply to protocols with immutable, globally fixed validator sets, nor to crash-fault-tolerant consensus where equivocation is impossible. ## Core Distinction The non-obvious boundary is not "Byzantine node sends bad messages." It is the distinction between **quorum validity** (a QC aggregates signatures from a set that constitutes a quorum under *some* view's membership) and **quorum legitimacy** (that same QC aggregates signatures from a set that constitutes a quorum under the membership *active at the height/epoch the QC claims to certify*). Most implementations validate the former and assume it implies the latter. It does not. When view membership changes (reconfiguration, epoch transitions, validator set rotation), a QC constructed from the *previous* view's membership can remain structurally valid — it still carries 2f+1 signatures — while being semantically stale for the height it is being applied to. A Byzantine node that has retained old key material, or an honest node replaying an old QC, can therefore inject a certificate that passes signature-aggregation checks but certifies a value that was never committed under the current membership. This is a boundary failure because it sits exactly at the seam between two subsystems: the cryptographic verifier (which knows about keys and thresholds) and the state machine (which knows about epochs and heights). Each is individually correct. The composition is not. ## What Was Observed In a four-validator deployment (f=1, quorum=3) undergoing a rolling reconfiguration from set {A,B,C,D} to {A,B,C,E}, the following sequence was observed: 1. Set {A,B,C,D} committed height 100 with a QC over {A,B,C}. 2. Reconfiguration to {A,B,C,E} began at height 101. D was removed; E added. 3. A Byzantine node (compromised A) replayed the height-100 QC, re-signed with its retained key, and attached it to a *new* proposal claiming height 101 with the same payload digest. 4. The verifier accepted the QC: three valid signatures (A, B, C) — a 3/4 quorum under the *old* set, and coincidentally also 3/4 under the *new* set. 5. The state machine applied the payload at height 101. But B and C had signed the original height-100 message, not the height-101 context. Their signatures were over `(view=old, height=100, digest=X)`, not `(view=new, height=101, digest=X)`. 6. Divergence: A and E advanced to height 101 with payload X; B and C remained at height 100, having never produced a height-101 signature. The failure was silent for 40ms — the duration of one round — before a liveness check caught the height mismatch. No safety violation occurred *only* because the payload digest was identical. Had the Byzantine node altered the digest while replaying B and C's signatures, the verifier would have rejected it. The dangerous case is precisely the *benign-looking* replay: same digest, stale context. ## Condition of Validity The invariant that must hold, and that naive verifiers do not enforce: > A QC is legitimate for height h if and only if every constituent signature is over a message binding (chain_id, epoch(h), height h, view, digest), and the signer set constitutes a quorum under the membership defined for epoch(h). The failure requires all of the following to co-occur: - **Membership overlap** between consecutive epochs sufficient that an old quorum remains a valid quorum (or a *plausible* quorum) under the new epoch. This is common in rolling reconfigurations where at most f validators rotate per epoch. - **Signature messages that do not bind epoch and height into the signed preimage.** If the signed message includes `epoch` and `height`, replay across epochs fails cryptographically. Many implementations bind `view` and `height` but *not* `epoch` — this is the gap. - **A verifier that checks threshold count against the current membership but not the full (epoch, height) binding of each individual signature.** When any of these is absent, the attack surface closes. When all three are present — which is the default in several production codebases that evolved from single-epoch PBFT — the boundary is open. ## Decision Boundary The operational decision is where to place the epoch/height binding check. Three options, with distinct tradeoffs: - **Bind in the signed preimage (strongest).** Include `(chain_id, epoch, height, view, digest)` in the message each validator signs. Replay across epochs is cryptographically impossible. Cost: every validator must know the current epoch at signing time, which couples signing to reconfiguration state and complicates asynchronous signing pipelines. - **Verify membership per-signature at QC validation (medium).** For each signature, look up the signer's membership *at the claimed epoch* and verify the signature was produced under that epoch's key or context. Cost: requires key/context versioning per epoch; O(n) membership lookups per QC. - **Reject QCs whose claimed epoch differs from the local epoch (weakest).** Cheap, but fails during the reconfiguration window itself, when honest nodes legitimately hold QCs from adjacent epochs. This trades safety for liveness during reconfiguration and is the wrong tradeoff for task-commitment systems where a stale commit is worse than a delayed one. For multi-agent task commitment — where a QC is the authorization for an agent to act on shared state — the recommendation is the first option. A task commitment certified under a stale epoch is an authorization to act on a world that no longer exists. ## Operational Effect The observable effect is **commitment divergence under reconfiguration**: two honest agents hold different committed states at the same height, each backed by a locally valid QC. This is not a safety violation in the classical sense (no two conflicting QCs at the *same* epoch), but it is a *cross-epoch* equivocation that classical safety proofs do not cover, because they assume a single fixed membership. Downstream, this manifests as: - Task commitments that reference shared state one agent believes committed and another believes uncommitted. - Replay-based duplicate execution of idempotent-looking tasks whose idempotency key was scoped to the old epoch. - Liveness stalls when the diverged agents cannot form a new quorum because they disagree on the current height. The mitigation that proved reliable in practice: treat epoch as a first-class field in every signed message, and make the QC verifier *fail closed* on any epoch mismatch rather than falling back to threshold-count validation. The verifier must never accept a QC it cannot reconstruct the exact signing context for. ```python from dataclasses import dataclass class StaleEpochQuorumError(RuntimeError): """Raised when a quorum certificate is structurally valid but was aggregated over a membership or signing context that does not match the epoch/height it claims to certify.""" pass @dataclass(frozen=True) class SignedVote: signer: str epoch: int height: int view: int digest: str signature: bytes def verify_quorum_certificate( votes: list[SignedVote], claimed_epoch: int, claimed_height: int, claimed_digest: str, membership_at_epoch: dict[int, set[str]], quorum_size: int, ) -> bool: """Validate a QC by binding every signature to its (epoch, height, digest) context AND to the membership active at that epoch. Fails closed on any mismatch. Never falls back to bare threshold counting. """ if claimed_epoch not in membership_at_epoch: raise StaleEpochQuorumError( f"epoch {claimed_epoch} has no registered membership; " f"refusing to validate QC against an unknown validator set" ) active_members = membership_at_epoch[claimed_epoch] seen: set[str] = set() for vote in votes: # Context binding: the signed message must match the claimed context. if vote.epoch != claimed_epoch: raise StaleEpochQuorumError( f"signer {vote.signer} signed epoch {vote.epoch} but QC " f"claims epoch {claimed_epoch}; replay across epochs rejected" ) if vote.height != claimed_height: raise StaleEpochQuorumError( f"signer {vote.signer} signed height {vote.height} but QC " f"claims height {claimed_height}" ) if vote.digest != claimed_digest: raise StaleEpochQuorumError( f"signer {vote.signer} signed digest {vote.digest} but QC " f"claims digest {claimed_digest}" ) # Membership binding: the signer must be a member at the claimed epoch. if vote.signer not in active_members: raise StaleEpochQuorumError( f"signer {vote.signer} is not a member of epoch {claimed_epoch}; " f"stale-membership QC rejected" ) if vote.signer in seen: raise StaleEpochQuorumError( f"duplicate vote from {vote.signer}; equivocation rejected" ) seen.add(vote.signer) if len(seen) < quorum_size: raise StaleEpochQuorumError( f"only {len(seen)} distinct valid votes at epoch {claimed_epoch}, " f"height {claimed_height}; quorum requires {quorum_size}" ) return True ```