Vigil: Accountable Liveness against Selective Silence Jiawei Cheng1
Huiping Sun1
Rui Zhou1
Jinjue Zhou1
Zhong Chen2,3
1 School of Software & Microelectronics, Peking University, Beijing, China 2 School of Computer Science, Peking University, Beijing, China
arXiv:2609.18778v1 [cs.DC] 16 Sep 2026
3 School of AI and Liberal Art, Beijing Normal-Hong Kong Baptist University, Zhuhai, China
[email protected] [email protected] [email protected] [email protected] [email protected]
Abstract
H1 s vote
BFT accountability is well understood for safety violations, and recent work attributes global liveness violations; recipientselective silence remains unresolved. A selectively silent adversary withholds messages from some honest nodes while behaving correctly toward others. It can stall consensus yet evade every existing mechanism. We initiate a systematic study of accountability against selective silence. Negatively, a lone attacker silent toward at most f honest nodes is indistinguishable from an honest node, yielding a universal lower bound KSI ≥ f +1 on the silence identification threshold; moreover, any feedback-free repair after a silence-induced violation costs Θ(n3 ). Positively, V IGIL, a Tendermint variant, matches these bounds with attack-adaptive forwarding, via bitmap cross-attestation, core-based membership, and challenge–response auditing. It pays O(n) authenticators per node when no selective silence occurs (plus Θ(n2 ) bitmap metadata bits per node), relays in proportion to the attack’s width (sub-threshold silence can force up to n3 /27 relays per view, a cost we price exactly), and majority-accuses any node silent toward more than a tunable resilience τA of honest peers (KSI = τA +1, optimal at τA = f ). We also price the residual sub-threshold griefing surface exactly and extend identification to x-partial synchrony. Real-network experiments on a three-region WAN, together with a simulator held to exact equality with every closed form, confirm each threshold and cost: at 2% loss, an f +1 accusation bar falsely accuses 91.2% of honest nodes, while our majority bar accuses 0.002%.
1
B (Byz.)
votes
×
silen ce
H2 (stalls)
Figure 1: Selective silence: coalition B behaves correctly toward H1 but withholds all messages from H2 , which misses quorum and stalls; to H1 , every member of B appears honest. can be slashed [2–4]. For safety violations this is well understood, since conflicting signed votes are self-contained proof of equivocation [2–4]. Liveness violations are different. A liveness attacker need not say anything incriminating; it only needs to not say things. Silence leaves no signatures, and under partial synchrony it is provably indistinguishable from delay. Only recently has Accountable Liveness [1] achieved liveness accountability under predominantly synchronous conditions. It forces honest nodes to broadcast signed transcripts continuously, so an adversary can stall consensus only by going completely silent, which everyone can then accuse. The problem: selective silence. Existing livenessaccountability mechanisms leave a loophole. A selectively silent adversary (Figure 1) withholds all messages from a targeted subset of honest nodes while interacting correctly with everyone else: it deprives the targets of a quorum, yet to the non-targeted majority it looks exactly honest. Forwardingbased mechanisms [1] mitigate the effect, since forwarded votes fill the gaps, but they fail on two counts. (i) The attacker can evade identification. Forwarding repairs vote sets, but the silent nodes keep full standing and can retry forever. In a framework whose premise is deterrence, rational adversaries [41] simply operate below the punishment threshold. (ii) Everyone pays for an attack that mostly is not happening. To close gaps silence might create, honest nodes forward all votes in every view. This inflates common-case communi-
Introduction
Byzantine fault-tolerant (BFT) state machine replication (SMR) now underpins proof-of-stake blockchains and permissioned ledgers securing hundreds of billions of dollars [19,43]. At this scale, tolerating misbehavior is not enough. Systems demand accountability: when a guarantee is violated, honest nodes should produce irrefutable, transferable evidence identifying a substantial fraction of the misbehavers, so they 1
cation from O(n) to O(n2 ) (authenticators), with worst-case repair traffic of Θ(n3 ): a permanent tax in defense against an occasional attack. This raises our question:
below does not need); accountability requires τA < n/2 and synchrony or x-partial synchrony (x < 1 for online identification, x < 1/2 for transferable certificates, matching [1]’s frontier); KSI ≥ f +1; and one-shot, feedbackfree repair costs Θ(n3 ), even with threshold signatures (Sec. 3–4; multi-round adaptive repair is not covered by this bound, Sec. 9).
Can honest nodes identify, and hold accountable, selectively silent adversaries, while paying the unavoidable forwarding cost only when, and in proportion to how widely, selective silence actually occurs?
2. Vigil. Matches the bounds: KSI = τA +1, no false accusations, and O(n) authenticator overhead in the absence of selective silence (Θ(n2 ) metadata bits, Sec. 6.3); relay cost grows with the attack’s width, up to n3 /27 per view under sub-threshold silence. It also prices the residual sub-threshold griefing surface exactly (Sec. 5–6, 9).
A third goal is implicit and, by our lower bounds, unavoidable: silence too narrow to accuse must still be repaired, so its residual cost should at least be priced and attributed (Sec. 6). Why this is hard. An honest p that never hears from q cannot tell silence from loss, and cannot verify third-party claims that q was silent toward them: an execution in which q maliciously ignores an honest set S is, to every outsider, indistinguishable from one in which S maliciously ignores q and falsely accuses it. Not sending and pretending not to receive are information-theoretically equivalent, echoing muteness failure detectors [10] and PeerReview [11]. Any protocol accusing on unverifiable silence claims risks convicting an honest node. Vigil. We present Vigil, a synchronous-view Tendermint variant [7] that matches the bounds below with attack-adaptive forwarding. After each voting round, every node broadcasts a signed bitmap of the votes it received; nodes assemble the bitmaps into a graph of mutual attestations, extract a deterministic membership core provably containing all honest nodes, audit claimed receipts via challenge–response, and forward only the votes specific core members are missing. With no silence nothing is forwarded; cost grows in proportion to actual attacks, with a closed-form worst case that an adversary confining its silence below the accusation threshold can sustain indefinitely (Sec. 6). Any node silent toward more than τA honest nodes is majority-accused even if no violation materializes; here τA is a tunable accountability resilience ( f ≤ τA < n/2; optimal at τA = f ). To our knowledge, Vigil is the first to attain the information-theoretic f +1 identification threshold for recipient-selective silence under link nonobservability (at the optimal setting τA = f ; larger τA trades this threshold for the excessive-fault coverage of Theorem 7), punishing it during normal operation; the conservative majority bar (> n/2) rules out false accusations under framing and jitter (Sec. 6). Because membership is fixed before forwarding, a vote withheld in the voting phase and injected during forwarding gains nothing, closing the quorum-splitting gap in prior forwarding designs (Sec. 5). Table 1 positions Vigil against prior mechanisms. Contributions. 1. Limits. Under link non-observability, a lone attacker’s silence toward ≤ f honest nodes is indistinguishable from honesty in any network model (for a coalition of t the certified width is f −t+1 per node, which the universal bound
3. Extensions. A violation in an honest-leader synchronous view certifies t ≥ ⌈n/3⌉ > f , and Vigil names ≥ ⌈n/3⌉ culprits, matching the cap exactly; cross-view aggregation convicts for x < 1/2 (Sec. 6–7). 4. Evaluation. Real-network experiments on a three-region WAN under >5% cross-region loss, plus a simulator held to exact equality with every closed form, confirm each threshold and cost; four white-box adaptive strategies gain nothing (Sec. 8).
2
Background and Related Work
BFT SMR and liveness. In BFT state machine replication [6, 8, 29], n nodes, up to f Byzantine, agree on a transaction sequence. Eventual liveness cannot ground accountability, since its violation is never established at finite time. Following [1], we use a timely notion (Definition 2). Accountability for safety. Casper FFG [2], Polygraph [3] and its optimal-cost successor [42], and BFT forensics [4] all exploit one fact, that equivocation is self-incriminating, which silence does not provide; the availability-accountability dilemma [5, 45] sharpened the asymmetry. Recent work pushes correctness past the classical bounds [21, 24]; Theorem 7 pushes accountability past them too, keeping silence evidence sound for every t ≤ τA , even at t ≥ ⌈n/3⌉. Accountability for liveness. Accountable Liveness [1], the only prior work with provable liveness accountability, establishes impossibility under partial synchrony, introduces the ∆′ partially-synchronous model, and forces attackers into complete, observable silence via unconditional transcript broadcasting (Θ(n2 ) every view, left unoptimized). It never identifies the selective silencer, which merely fails, keeps standing, and retries; it treats omission as global, not per-recipient. The separation in one sentence: [1] asks who caused an eventual liveness violation; we ask how much recipient-specific silence can be attributed even before a violation materializes. Two recent directions bracket us. Scalable accountable agreement [22] compresses the common-case cost of accountable consensus, as does GALUPA [28] via gossiped aggregated 2
Tendermint [7] Forensics [4] Acc. Liveness [1] V IGIL
Common case
Attack case
IDs sel. silence?
Evidence pre-violation?
3
O(n) O(n) Θ(n2 ) O(n)
O(n) O(n2 ) Θ(n3 ) Θ(n3 )†
no no (safety) no yes
no no no yes
3.1
Model and Definitions System and Network Model
We consider n nodes with identifiers {0, . . . , n − 1}, connected by authenticated point-to-point channels [44], with three fault parameters: the actual corruption count t of an execution; the consensus resilience f with n > 3 f (every guarantee assumes t ≤ f unless stated); and the accountability resilience τA with f ≤ τA < n/2 (Proposition 1, Sec. 4, bounds this range); τA governs accountability only and does not extend consensus guarantees beyond t ≤ f . Separating t from f matters for Theorem 7, which handles super-threshold executions t ≥ ⌈n/3⌉ > f , extending the excessive-fault treatment of safety [21] to silence evidence. We assume a PKI with existentially unforgeable signatures; invalid messages are discarded. The underlying Tendermint safety and liveness are inherited unchanged: the attestation layer only reads votes and adds bookkeeping messages (Sec. 5). Synchrony. Sec. 5–6 assume synchronous views: delay bounded by a known ∆, ∆-spaced steps, fixed-length views. Views have fixed length L = 16∆ (Figure 3). Sec. 7 relaxes this to the ∆′ -partially-synchronous model of [1] (full asynchrony precludes deterministic consensus [30]): in every window of g(∆′ ) consecutive periods, at least a (1 − x) fraction are synchronous. Link non-observability. Each node observes only its own incident channels. It sees no communication between other pairs except as reported in protocol messages. This assumption is load-bearing for the lower bounds; trusted monitors escape it (Sec. 9). Randomness. The impossibility results extend to randomized protocols: Theorem 1’s coupling fixes all private tapes identically in both executions, reducing to the deterministic case tape by tape. Complexity measure. Communication counts authenticators (signed votes, blocks, forwards) per view [8]; unsigned metadata (bitmaps) is accounted separately in bits. Lower bounds (Theorem 4, Corollary 2) and the upper bound (Theorem 9) share this currency.
Table 1: Comparison (authenticator complexity per view). † Vigil’s relay is one-shot and feedback-free, the class to which the Θ(n3 ) lower bound of Corollary 2 applies; its worstcase constant is n3 /27 under the canonical parameterization n = 3 f +1, τA = f , over all silence/denial patterns (Thm. 9, Lemma 6); its attestation layer additionally costs O(n2 ) metadata bits per node (Sec. 6.3), a currency AL’s transcript broadcasting also pays. locking and output proofs; both aggregate signed evidence, which silence never produces, so identifying silence remains an orthogonal, cubic-worst-case expense (Sec. 4). Weak multishot accountability [23] relaxes identification to eventual detection across repeated instances; we ask for full identification within one window, which repetition cannot replace under rotating targets (W4). Detecting silent misbehavior. Muteness failure detectors [10] (extending [32, 39]) suspect silent nodes but cannot be implemented accurately; PeerReview [11] classifies omission faults as suspectable, never provable; the fault-detection problem [38] delimits detectable fault classes. Our indistinguishability theorem quantifies these classics: silence toward ≤ f honest nodes is invisible; everything above is punishable. Basilic [16] and Pod [17] detect only globally observable silence. The omission/mixed-fault line [12–15, 40] asks whether agreement is solvable under fine-grained faults; we ask whether fine-grained silence can be identified and priced. The distinction is technical. Zombies-and-ghosts detection [14] and the overlapping-fault treatment [15] classify nodes whose omissions disrupt their own participation, so the protocol can route around them; a selective silencer participates fully toward a quorum-sized majority and matches no such classifier. Their omission faults are also non-strategic; Theorem 1 makes false denial the exact dual of silence, forcing the audit of Sec. 5.4. Asymmetric Byzantine links [25] address feasibility under static trust structures, not accountability; censorship resistance [18] targets leaders excluding transactions, not nodes withholding protocol messages. Communication-efficient BFT. Threshold and aggregate signatures [8, 9, 35] cannot sidestep our forwarding lower bound: it stems from who must talk to whom, not message size; the bitmap layer adds only O(n2 ) bits per view (Sec. 3 keeps both currencies explicit). DARE [26] and subsystem specialization [27] pursue adaptivity on the protocol side; Vigil mirrors it on the evidence side. Attestation operates on signed receipts, not the consensus payload, so it is in principle portable to DAG-based BFT [36, 37] (Sec. 9).
3.2 Adversary and the Selective-Silence Attack The adversary A statically corrupts up to f nodes and may deliver, delay (within the synchrony bound), or drop their messages arbitrarily and adaptively, including per-recipient: sending to one honest node while withholding from another. Corruption is static: "adaptive" throughout (S4’s white-box strategies included) means a fixed coalition’s strategy adapts to protocol internals, never mid-execution corruption of membership. Definition 1 (Selectively silent node). A node q is selectively silent toward a set S of honest nodes in a view if q sends no protocol messages to any member of S during that view 3
while sending the protocol-prescribed messages to at least one honest node outside S. If S includes all honest nodes, q is completely silent (a special case). We write s(q) = |S| for q’s silence count in the view. Selective silence strictly generalizes classical mute/omission faults: its power and evasion come from keeping s(q) small while still depriving targets of a quorum. A may also lie about receipts, falsely denying messages duly delivered, which renders naive silence-reporting unsound (Sec. 4).
3.3
Liveness and Accountability Definitions
Definition 2 (Timely liveness). A protocol satisfies timely liveness with straggler slack τlive and deadline T if, for every transaction tx input to all honest nodes by the start of view v, all but at most τlive honest nodes commit tx within T rounds, whenever the actual corruption count satisfies t ≤ f ; a violation occurs when strictly more than τlive honest nodes have not. Vigil is analyzed at τlive = 0 and T = L (one view): every honest node must commit within the view. This makes liveness finite-time-checkable while tolerating bounded stragglers; both are needed for accountability to be well-posed [1]. Definition 3 (Accountable liveness). A protocol provides accountable liveness with strength k if, in synchronous views: (i) no false accusations: no honest node is ever majorityaccused; (ii) identification: whenever a timely liveness violation occurs under an honest leader, at least k Byzantine nodes are majority-accused (accused by more than n/2 nodes), forming a transferable certificate. Terminology: a node accuses q via its signed accusation bitmap; q is majority-accused (per view) at > n/2 accusers, and convicted when a window-level certificate names it (Sec. 7). We require the majority bar: any bar ≤ f lets the coalition alone convict an honest node, a bar slightly above f is inducible by jitter, and the majority bar requires co-opting > n/2 − f honest nodes, which never happens. Definition 4 (Potential liveness violation). A view exhibits a potential violation if the silent nodes’ behavior, extended to all honest nodes, would cause a timely violation. Every actual violation is potential; identifying attackers at potential violations punishes reconnaissance. The definition is interpretive: Vigil’s operational trigger is s(q) > τA (Theorem 5), and every such trigger is a potential violation in this sense. Definition 5 (Silence identification threshold KSI ). KSI (Π) is the least integer such that every Byzantine node silent toward at least KSI honest nodes is majority-accused, while no honest node ever is. Smaller is stronger: the adversary must confine each node’s silence to KSI − 1 targets to preserve impunity. KSI is the paper’s central quantitative object: Sec. 4 shows KSI ≥ f +1 universally; Sec. 5 shows Vigil achieves τA +1, matching at τA = f . The setting τA = f is admissible everywhere in the paper, Sec. 7 included; it is only Theorem 7’s
Symbol
Meaning
n f, t τA Q ∆ L ∆′ x, x̂ m H s(q), Sq KSI Kp AccK k
number of nodes consensus bound (n > 3 f ); actual corruptions accountability resilience ( f ≤ τA < n/2) voting quorum ⌊2n/3⌋ + 1 synchronous message-delay bound view length, L = 16∆ (Fig. 3) partial-synchrony period length [1] async. view fraction; conviction bar (Sec. 7) window size in views, m = g(∆′ ) (Sec. 7) honest set, |H| = n − t silence count of q; its silenced set silence identification threshold (Def. 5) membership set of observer p (core) window opening threshold (≤ τA ) protocol-step index (Sec. 4.2)
Table 2: Notation. excessive-fault regime f < t ≤ τA that it empties (Sec. 9). A worked instance: at n=31, f =8, τA =10, a coalition may silence up to 10 honest peers each with impunity; an 11th gets it majority-accused. Table 2 collects notation.
4 4.1
Impossibility and Lower Bounds The Feasibility Region
Proposition 1 (Resilience boundary). In any network, no protocol provides selective-silence accountability with resilience τA ≥ ⌊n/2⌋ + 1. Proof. Resilience τA requires the no-falseaccusation guarantee to hold in executions with actual corruption count t = τA ; the t/ f separation of Sec. 3.1 makes such executions admissible. A coalition of t ≥ ⌊n/2⌋ + 1 > n/2 nodes alone signs more than n/2 accusations and forges a majority-accusation certificate against any honest node, regardless of the protocol. (At even n, τA = n/2 leaves the coalition one signature short; we exclude it conservatively.) ■ Proposition 2 (Synchrony boundary). Under standard partial synchrony (unknown GST [31]), selective-silence accountability is impossible for any f ≥ 1. Proof. When an expected message from p fails to arrive at honest h by time θ, both "p is selectively silent" and "θ < GST" are consistent with h’s view; accusing at any finite time risks accusing an honest p, and never accusing forfeits identification. ■ Hence throughout we require τA < n/2 and a network that is synchronous or x-partially-synchronous with x < 1. Two layers of the feasibility region must be kept apart. Online per-view identification (each honest node accusing locally, in whichever synchronous views the schedule provides) is feasible for any x < 1, strictly beyond liveness accountability’s x < 1/2 [1]: identifying ongoing selective silence is possible where attributing a full violation is not. Transferable certificates that convince a third party still require x < 1/2 (Sec. 7): our results widen the online layer, not the certificate frontier 4
of [1].
E: q Byzantine q
4.2
× S
drop
q
S
Executions, Views, and Coupling observers C
An execution E is determined by the Byzantine set and strategy, the delivery schedule, and the random tapes (r p ). The view viewEp (k) at protocol step k is the messages p received up to k plus its initial state and consumed tape prefix; honest behavior is a deterministic function of the view. E, E ′ are ′ indistinguishable to p (E ≈ p E ′ ) if viewEp (k) = viewEp (k) for all k. (Throughout, k indexes protocol steps; t is reserved for the actual corruption count of Sec. 3.1.) Definition 3(i) then gives the workhorse of all lower bounds: Proposition 3 (Safe accusation). If a protocol never accuses honest nodes, then an honest node p may accuse q only if q is Byzantine in every execution E ′ with E ′ ≈ p E and with at most f Byzantine nodes. ■
4.3
E ′ : S Byzantine
observers C ′
∀p ∈ C: viewEp (k) = viewEp (k) for all k
Figure 2: Twin executions of Theorem 1 (|S| ≤ f ): withholding sends (E) and discarding receipts (E ′ ) are indistinguishable to every observer outside S ∪ {q} under link nonobservability. "maliciously not sending" and "maliciously pretending not to receive." Corollary 1 (Who can accuse). If q is silent toward S within the swap budget of Theorem 1 (e.g. |S| ≤ f with q the only corrupted node), no honest node outside S may accuse q: its view cannot refute q’s honesty (Theorem 1, Proposition 3), and any signed non-receipt claims it holds have at most |S| ≤ f distinct genuine signers, a set that could consist entirely of liars. Conversely, once q is silent toward f +1 honest nodes in a synchronous view (where an honest non-receipt claim is necessarily genuine), the f +1 claims refute q’s honesty in every consistent world: identification above this threshold is not information-theoretically precluded. ■
Local Indistinguishability
Theorem 1 (Local indistinguishability of bounded silence). Let Π be any SMR protocol under link non-observability, in any network model, with any communication budget. Let E be an execution with Byzantine set BE in which node q ∈ BE is selectively silent toward a set S of honest nodes, and assume the swap budget |S| + |BE \ {q}| ≤ f (in particular |S| ≤ f whenever q is the only corrupted node of E). Then there exists an execution E ′ in which q is honest, the nodes of S ∪ (BE \ {q}) are Byzantine, and E ≈ p E ′ for every node p ∈ / S ∪ {q}. Consequently, no node outside S ∪ {q} can determine whether q or the members of S misbehaved. Proof. Construct E ′ in three moves: (i) couple the random tapes; (ii) refine E first: instruct the Byzantine q to also discard, unprocessed, all messages from S, making q’s processed input "the view as if S never spoke"; (iii) in E ′ , corrupt S (legal under the budget above), have each u ∈ S run the honest protocol toward everyone except q, discarding q’s traffic; q is honest. Induction on protocol steps (Appendix A) gives ′ viewEp (k) = viewEp (k) for every p ∈ / S ∪ {q}: the executions differ only in who suppresses the q–S traffic, q’s outgoing traffic outside S coincides by (ii), and link non-observability hides the suppressed half (Figure 2). ■ Remark (scope). The swap budget is the theorem’s exact boundary. A single silencer (|BE | = 1) may hide a full width- f silence; a coalition of t simultaneous silencers can invoke the theorem node-by-node only up to width f − t + 1 each, since E ′ must keep the other t − 1 attackers Byzantine and corrupt S. Consequently joint patterns can be refutable even when each is individually plausible, the structure Vigil’s counting exploits (Lemma 4); the lower bound of Theorem 2 deliberately uses the single-silencer instance, which needs no such slack. The theorem holds in every network model, including perfect synchrony, formalizing the equivalence of
4.4
The Universal Lower Bound on KSI
Theorem 2 (KSI lower bound). For every SMR protocol Π under link non-observability, in synchronous or x-partiallysynchronous (x < 1) networks with τA < n/2: KSI (Π) ≥ f +1. Proof. It suffices to exhibit, for K = f , an execution in which a Byzantine node silent toward K honest nodes escapes majority accusation. Take E with BE = {q} (actual corruption count t = 1) and q selectively silent toward a set Sq of |Sq | = f honest nodes; the swap budget of Theorem 1 is met, since |Sq | + |BE \ {q}| = f . Who is guaranteed to accuse q? Honest nodes outside Sq cannot (Corollary 1), and no Byzantine node other than q exists. The guaranteed accuser set is therefore contained in Sq and has size at most f < n/2, so q is never majority-accused: KSI ≥ f +1. Using the singlesilencer instance keeps the bound unconditional — it costs the adversary one corruption and needs no budget slack (Remark, Sec. 4.3). Degraded network conditions only enlarge the innocent explanations, so the bound holds a fortiori under x-partial synchrony. ■ The bound is tight in principle (Corollary 1’s converse); the gap between "refutable" and "majority-accused by an actual protocol at low cost" is what Sec. 5 closes: Vigil achieves KSI = τA +1, matching at τA = f . Theorem 3 (Identification cap under liveness violations). Let the voting quorum be Q = ⌊2n/3⌋+1. In any synchronous view, no SMR protocol can guarantee, upon a timely liveness 5
violation, the majority accusation of more than n − Q + 1 = ⌈n/3⌉ Byzantine nodes. Proof sketch. The adversary silences exactly n − Q + 1 nodes; its remaining corrupted nodes follow the protocol to the letter and are unaccusable by Proposition 3. Full proof in Appendix C. ■ Theorem 7 (Sec. 6) matches this cap exactly: any violation in an honest-leader synchronous view is super-threshold (t ≥ ⌈n/3⌉ > f ), and Vigil majority-accuses at least ⌈n/3⌉ nodes for every t ≤ τA .
repair remains cubic against an adversary that aligns its corruptions with the relay schedule, whereas randomized multiround repair can reduce the sub-threshold cost to O(n2 ) in expectation (Sec. 9).
5
Vigil: Protocol Design
Vigil is a Tendermint variant [7]: publicly known random leaders, ∆-spaced steps, a proposal with echo-relay for equivocation detection [33] (per Theorem 4), and two voting rounds with quorum Q = ⌊2n/3⌋ + 1. Vigil adds a cross-attestation layer after each voting round, boundary slack, and an accusation broadcast at the view’s end. Pseudocode and the evidencepipeline schematic (Figure 8) are in Appendix D; Figure 3 shows one view’s timeline.
4.5 Forwarding Necessity and the Θ(n3 ) Communication Bound Once selective silence does cause a violation, holding anyone accountable forces relaying, and for feedback-free repair, in the worst case, Θ(n3 ) authenticators. Theorem 4 (Forwarding necessity). In synchronous or x-partially-synchronous (x < 1) networks with τA < n/2, if honest nodes relay neither the proposer’s block nor other nodes’ votes, then after a liveness violation caused by selective silence, no selectively silent node can be majorityaccused without accusing honest nodes. (The constructions use an actual corruption count ⌈n/3⌉ ≤ t ≤ τA . This is not an artifact: by Theorem 7 a violation under an honest leader implies t ≥ ⌈n/3⌉, so the premise is satisfiable only in the super-threshold regime.) Proof sketch. (Blocks.) A Byzantine leader partitions the honest nodes into equal halves A, B, proposes only to A, and stays silent toward B: each half’s accusation set falls short of a majority and contains honest nodes. (Votes.) In an A/B/C partition with |A| = |C| = t and C Byzantine and silent toward A, only A’s t < n/2 members can accuse C (Theorem 1), never a majority. Aggregation does not rescue the regime: the adversary can leave every honest node just below quorum with each Byzantine node silent toward fewer than half of the honest nodes, so no honest node holds a QC to aggregate. Full proofs in Appendix C. ■ Corollary 2 (Θ(n3 ) worst case, feedback-free repair). Under the assumptions of Theorem 4, consider protocols whose repair of missing votes, after such a violation, consists of relay messages determined by pre-violation local views alone (i.e., non-adaptive: no feedback from what other relayers forwarded). Any such protocol that guarantees majority accusation of at least one selectively silent node incurs Θ(n3 ) authenticator communication in the worst case. Proof sketch. Any designated-relay set of size ≤ f is plantable: the planted relay defaults to silence toward fewer than f nodes, indistinguishable by Theorem 1, so guaranteed repair needs all Θ(n) of B’s members each relaying Θ(n) votes. Full proof in Appendix C. ■ The corollary covers one-shot, feedback-free repair only. Multi-round repair driven by per-round receipt feedback is outside its scope: we conjecture that deterministic multi-round
5.1
Overview
Sec. 4 fixes the strategic situation: silence within Theorem 1’s swap budget is undetectable directly, so accusation must assemble more than f mutually corroborating, audited claims. What honest nodes can do is force everyone on the record: each node commits, via a signed bitmap, to which votes it claims to have received. Each claim is cross-checkable (a receipt by challenge; a non-receipt by the counterparty’s mirror bit). Assembling audited claims into an undirected graph turns silence into structure: honest nodes form a clique of size ≥ n − f , so any node outside every sufficiently dense substructure has demonstrably failed to communicate with too many peers, and is accusable by everyone without testimony about unobservable links. The design problem: extract from each local graph a membership set K that (P1) provably contains all honest nodes, (P2) contains only nodes with provably small silence count, and (P3) is deterministic polynomial time. Maximal cliques fail (P3): extraction is NP-hard, and greedy extraction drops honest nodes on adversarial graphs. Our key observation: cliques are overkill; degeneracy is the right notion.
5.2
Cross-Attestation Layer
After round r ∈ {1, 2} of view v, every node p broadcasts a signed bitmap bm p ∈ {0, 1}n with bm p [q] = 1 iff p received q’s round-r vote. Upon collecting bitmaps, p normalizes them: • Validity filter. Discard bitmaps of wrong length; discard node q entirely (mark for accusation) if q’s bitmap, vote, or bmq [p] = 1 attestation of p’s own vote is missing; an honest q in a synchronous view always provides all three. • Symmetrization. For every pair (u, w): if bmu [w] = 1 but bmw [u] = 0, reset bmu [w] ← 0. An edge survives only by mutual attestation. 6
slack ∆ propose 0∆
echo
vote1
bitmap1
chal1
reply1
vote2
relay1
4∆
8∆
bitmap2
chal2
reply2
relay2 12∆
accuse
slack 2∆ 16∆
Tendermint voting core (propose, echo, vote1 , vote2 )
Figure 3: Timeline of one V IGIL view (16∆): the Tendermint voting core (blue) interleaved with the attestation layer (orange), selective relay (red), and accusation broadcast (purple). Algorithm 1 CoreExtract(G): deterministic membership extraction
attackers). A mutually attested, audited edge to an honest neighbor w certifies that w genuinely received q’s vote; hence q’s silence count satisfies s(q) ≤ (n − t) − (n − τA − t) = τA . ■ Theorem 5 (Vigil’s identification threshold). In synchronous views with honest leaders, KSI (V IGIL) = τA +1; with τA = f this matches the universal lower bound of Theorem 2 exactly. Proof. (≤) Contrapositive of Lemma 3 per observer, then counting: if s(q) ≥ τA +1, then for every honest observer p (including the silenced ones, who filter q outright), q fails the core-degree bound in G p : an honest w ∈ Sq contributes no surviving edge to q, by truthful mirror bits and symmetrization, so q’s audited degree is at most n − 1 − s(q) < n − τA − 1. Hence q ∈ / K p for all n − t > n/2 honest observers (using t ≤ τA < n/2), and all of them accuse q. (≥) Conversely, an adversary keeping s(q) ≤ τA for all its nodes preserves every Byzantine node’s degree ≥ n − τA − 1 in every non-silenced observer’s graph (colluders share votes and truthfully attest internal edges, Sec. 5.4), so such nodes stay inside those cores and fall short of majority accusation. ■ Lemma 4 (Agreement by counting). Although K p varies across observers, Lemma 2 gives H ⊆ K p for all honest p. Hence: (i) no honest node is ever accused by an honest node (accusations target only Vp \ K p and filtered nodes); (ii) if q∈ / K p for every honest p, then q is accused by all n −t > n/2 honest nodes: majority accusation. ■ Versus cliques: the core is a superset of every clique of size ≥ n − τA (soundness can only improve), achieves the optimal KSI from degrees alone, and its uniqueness eliminates both NP-hardness and greedy extraction’s adversarial failure modes.
1: G = (V, E): symmetrized attestation graph 2: repeat 3: remove every v ∈ V with deg(v) < n − τA − 1 4: until fixpoint 5: return remaining vertex set K
The surviving structure is an undirected graph G p = (Vp , E p ): vertices are nodes that passed the validity filter, and {u, w} ∈ E p iff bmu [w] = bmw [u] = 1 after symmetrization. Lemma 1 (Honest clique). In a synchronous view with an honest leader, for every honest p: all n − t honest nodes are in Vp , and every two honest nodes are adjacent in G p . Proof. Honest nodes broadcast votes and truthful bitmaps; synchrony delivers them by the attestation deadline; mutual truthful bits survive symmetrization. ■ Note that G p is local: Byzantine nodes may send different bitmaps to different honest nodes, so G p and G p′ may differ. All guarantees below are stated per honest observer and then combined by counting.
5.3
Deterministic Membership Extraction
Define the membership set K p as the (n − τA − 1)-core [34] of G p : the unique maximal subgraph in which every vertex has degree ≥ n − τA − 1. It is computed by iterated pruning (the bitmap-count filter of the attestation layer is precisely the first pruning round): With a bucket queue this runs in O(|V | + |E|) = O(n2 ) time (bit-parallel over adjacency rows, O(n2 /w) words) and is order-independent: the core is unique regardless of pruning order [20]. Lemma 2 (Soundness: all honest survive). In a synchronous view with an honest leader, H ⊆ K p for every honest observer p, deterministically. Proof. By Lemma 1 the n − t honest vertices are pairwise adjacent, so as long as all of H remains, every honest vertex has degree ≥ n −t − 1 ≥ n − τA − 1 within H alone (using t ≤ τA ). Pruning removes only vertices of degree < n − τA − 1; by induction on pruning steps, no honest vertex is ever removed. ■ Lemma 3 (Effectiveness: core members talked). Every q ∈ K p has, in G p , at least n − τA − 1 mutually attested and challenge-audited (Sec. 5.4) neighbors, of which at least n − τA − t are honest (at most t − 1 of them can be fellow
5.4 Challenge–Response: Auditing Claimed Receipts Bitmaps are claims, and Byzantine nodes will inflate them: an all-ones bitmap costs nothing and maximizes q’s degree. Vigil audits claims before they enter the graph. After collecting bitmaps, each node p challenges every q it might admit into K p , on its uncorroborated positions: the indices i with bmq [i] = 1 for which p does not itself hold vote i. q must reply with the claimed signed votes themselves, and p verifies each signature. A missing or invalid vote removes q from p’s graph (and marks it for accusation); a valid reply both proves possession and hands p the votes it lacked. Positions 7
p can corroborate need no audit: there the edge’s evidentiary weight rests on the counterparty’s mirror bit and the vote’s own signature (Sec. 6.3). One challenge per audited pair adds O(1) authenticators and O(n) bits; a reply returns at most the challenged votes, and in the common case no uncorroborated position exists, so the challenge phase is empty. The audit surface resists inflation: a Byzantine q inflating uncorroborated claims merely draws challenges it cannot answer and is discarded, and each audited pair exchanges at most one challenge and one reply per view regardless of adversarial bitmaps. Lemma 5 (Audit security). Under existential unforgeability of the vote signatures, a node q whose reply verifies holds every challenged vote, except with negligible probability. Proof. The reply exhibits the signed votes themselves; producing a vote q does not hold requires forging its signature. Inconsistent replies to different observers are individually verified, so they only remove q from more graphs. ■ What audits do and do not prove. A passed audit proves q possesses the votes, not that it received them in the voting phase (colluders may relay). This is precisely enough: possession certifies the incoming half of q’s edges, honest mirror bits certify the outgoing half, and symmetrization requires both. The colluder-relay loophole lets q at most shrink its silence footprint by actually delivering votes, which is not an attack. Observer-selective audit behavior only removes q from more graphs, and Theorem 5’s (≤) counting rests on silenced honest nodes’ mirror bits, which no audit outcome restores; audit results never need to agree across observers.
5.5
quorum-splitting attack that defeats prior forwarding schemes (Sec. 2). (iii) Majority accusations only: weaker thresholds are fragile under jitter (Definition 3); Lemma 4 delivers the majority bar without inter-observer agreement on K.
6
We analyze soundness, identification, and communication in synchronous views with honest leaders; Sec. 7 removes the assumption via standard leader rotation.
6.1 Soundness and Liveness-Violation Accountability Theorem 6 (Soundness). In synchronous views, honest nodes never accuse honest nodes; consequently no honest node is ever majority-accused within a synchronous view. Proof. If the leader is honest, Lemma 2 puts every honest node in every honest observer’s cores for both rounds, so no honest node appears in any honest accusation bitmap. If the leader is Byzantine and silent toward every honest node, no honest node votes and honest nodes accuse only the leader; if it is silent toward only some honest nodes, the echo relay (Sec. 5, step 1 of Algorithm 2) delivers the proposal to every honest node by 3∆, so every honest node votes and Lemma 2 applies as in the honest-leader case; equivocation is caught by the echo relay and again only the leader is accused. Byzantine accusations against honest nodes number at most t ≤ f < n/2 and never reach a majority. ■ Per-view accusations in genuinely asynchronous views can be noisy (W3, S2); Theorem 10 shows the windowed conviction certificate remains sound for any x < 1/2 regardless. Theorem 7 (Accountability under excessive faults). Consider a synchronous view with an honest leader in which at least one honest node suffers a (timely) liveness violation. Then the corruption count is super-threshold, t ≥ ⌈n/3⌉ > f . If moreover t ≤ τA , then at least ⌈n/3⌉ Byzantine nodes are majority-accused and no honest node is accused. Proof. By Lemma 3 and the selective relay, every node q with s(q) ≤ τA delivers its vote to at least n − t − τA honest nodes; since t ≤ τA , all honest nodes lie in each other’s cores (Lemma 2, which is stated in terms of the actual corruption count t and needs only t ≤ τA ), so the relay step distributes q’s vote to every honest node. Hence every honest node ends the round holding the votes of all nodes with s(·) ≤ τA . If some honest node still lacks the quorum Q = ⌊2n/3⌋ + 1, then the number of nodes with s(·) > τA is at least n − ⌊2n/3⌋ = ⌈n/3⌉. Honest nodes have silence count 0, so all of these are Byzantine, establishing t ≥ ⌈n/3⌉; the counting argument of Theorem 5’s (≤) direction (which requires only that the n − t honest accusers form a majority, i.e. t < n/2, guaranteed by t ≤ τA < n/2) majority-accuses each of them, while Lemma 2/Theorem 6 exclude honest nodes. ■
Selective Forwarding and Accusation
After extracting K p and completing audits, p repairs gaps inside K p only: for every q ∈ K p whose bitmap shows a missing vote of some w ∈ K p that p holds, p forwards w’s vote to q. Received relays are accepted only from/for members of the receiver’s own core. When no silence occurred, bitmaps inside the core are complete and nothing is forwarded: the common case costs zero relays. Sec. 6 bounds the worst case. At the view’s end, p broadcasts a signed accusation bitmap: the leader alone if no valid proposal arrived; otherwise ev(1) (2) ery node outside K p ∩ K p (the cores of the two voting rounds). Accusation certificates are the multisets of these signed bitmaps; majority accusation of q means > n/2 signers accuse q.
5.6
Analysis in Synchronous Views
Design Rationale
Three choices deserve emphasis. (i) Evidence during normal operation: accusation bitmaps flow every view, so Vigil punishes potential violations (Definition 4) with no separate forensic phase. (ii) Membership before forwarding: K p is fixed before any relay is accepted, so a vote withheld in the voting phase and injected during relay is discarded, closing the 8
Three remarks. First, under t ≤ f < n/3 the premise is unsatisfiable: Vigil renders honest-leader synchronous views violation-free, itself a guarantee. The theorem’s content is the excessive-fault regime f < t ≤ τA , where a violation implies super-threshold corruption and the protocol still names ⌈n/3⌉ culprits, matching Theorem 3’s cap. (These are the same nodes Theorem 5 majority-accuses — every node with s(·) > τA — so nothing here exceeds Theorem 3’s cap on what any protocol can guarantee.) Second, for t > τA the guarantees lapse and we claim nothing; third, evidence is produced in the same view as the violation.
6.2
of the honest nodes. Proof sketch. Each of the n − t − s nontargeted honest relayers detects, from W -members’ truthful bitmaps, exactly the f ′ votes each target misses and unicasts them; duplicates across relayers are the price of the guaranteed delivery established by Corollary 2. The closed-form maximization (C increasing in f ′ ; ∂C/∂s = 0 at s = (n −t)/2) is in Appendix C. ■ Lemma 6 (Extremal zeroing patterns). Charge each Byzantine q a zeroing budget b(q) = |Sq ∪ Dq | ≤ τA , where Sq is its silenced set and Dq the honest senders whose receipt it falsely denies (Sec. 3.2); both zero edges incident to q. Over all patterns, the relay cost is C = ∑q b(q) n − t − b(q) , maximized exactly when every b(q) = min(τA , ⌊(n − t)/2⌋); the common-target configuration of Theorem 9 attains it, so C∗ is the global worst case over silence, denial, and mixtures. Proof. Every zeroed pair, w ∈ Sq (relayers ship q’s vote to w) or w ∈ Dq (relayers ship w’s vote to q), is repaired by exactly the honest observers whose graphs retain q: either condition makes the validity filter (Sec. 5.2) discard q at the affected observer. Each pair thus recruits n − t − b(q) relayers, independently of every other silencer: the cost is separable, each q contributing the concave parabola b(q)(n − t − b(q)). ■ Remark (denial does not amplify). False denial looks like the cheaper lever, since the denied w is honest and all n − t honest nodes hold its vote. The validity filter closes exactly this gap: a denier is discarded from every denied observer’s graph, shrinking its relayer pool to n −t − b(q), the same as a silence pair; S4 confirms this at equality. Refusing denial-triggered relays is impossible: by Theorem 1’s mirror symmetry a fabricated non-receipt is indistinguishable from a genuine one. Proposition 4 (Sub-threshold griefing floor). An adversary keeping f ′ nodes silent toward exactly s ≤ τA common targets in every view (i) is never majority-accused (Theorem 5, (≥)), (ii) causes no liveness violation (the relay completes every honest vote set, Theorem 7), and (iii) forces C( f ′ , s) relay authenticators per view, indefinitely, up to C(t, min(τA , ⌊(n − t)/2⌋)), a cap covering silence, false denial, and mixtures (Lemma 6). Sub-threshold silence is thus a pure resource-griefing surface, structural to any protocol matching Theorem 2: silence within Theorem 1’s swap budget is unaccusable — and Vigil accuses none of it up to width τA (Theorem 5, (≥)) — yet leaving it unrepaired forfeits liveness (Theorems 1, 4). What a protocol can do is price the grief exactly and attribute it via the relay rule (mitigations, Sec. 9); certificates below f +1 remain forbidden by Theorem 2. ■ The gap between Theorem 8 and Theorem 9 is the paper’s thesis in numbers (Table 3): the unavoidable cubic cost (Corollary 2) is confined to executions in which the adversary actually mounts a maximal selective-silence attack, and by Theorem 5, mounting it at scale s > τA converts the cost into convictions instead. Proposition 4 is the honest fine print. An adversary may sustain the sub-threshold cost forever without
Communication
Theorem 8 (Optimistic cost). In a synchronous view with an honest leader, if no node is selectively silent (in particular if Byzantine nodes are completely silent or absent), then no vote is ever forwarded, and the per-view authenticator overhead of Vigil’s accountability layer over plain Tendermint is O(n) per node. Proof. Completely silent nodes are removed by the validity filter of Sec. 5.2 at every honest observer identically; among the remaining nodes, every bitmap is complete over the core, so the relay condition (a core member missing a core member’s vote) never fires. The added traffic per node is: one bitmap broadcast, an empty challenge phase (every claimed receipt is corroborated, Sec. 5.4), and one accusation bitmap: O(n) authenticators of O(n) bits. ■ Theorem 9 (Cost under coordinated common-target silence, closed form). Consider an execution with a coalition of t corrupted nodes, of which f ′ ≤ t execute selective silence toward a common set W of s = |W | honest nodes, s ≤ τA , while the remaining t − f ′ coalition members send no relays (larger s triggers Theorem 5 and removes the silencers from every core, stopping all relays on their behalf). The relay traffic is C( f ′ , s) = (n − t − s) · s · f ′ authenticators, maximized at f ′ = t, s = min(τA , ⌊(n − t)/2⌋) (Figure 4): guaranteed repair counts only honest relayers, so the pool is the n − t − s non-targeted honest nodes. C is increasing in f ′ ≤ t and, at fixed f ′ , in the pool size, so over all executions with t ≤ f the cost is maximized by the full coalition, f ′ = t = f ; every closed form below is quoted at that point, and we write f for t accordingly. The unconstrained continuous optimum is C∗ =
f (n − f )2 n3 = at f = n/3. 4 27
(1)
For the canonical parameterization τA = f , n = 3 f + 1, the integer maximizer is s = ⌊(n − f )/2⌋ = τA = f , giving the exact ∗ = f 2 ( f +1) ≈ n3 /27, below the unconstrained worst case Cint optimum f (n− f )2 /4 by 1+1/(4 f ( f +1)) (0.03% at f = 30). This is the Θ(n3 ) of Corollary 2, incurred only under a coordinated attack by the full coalition against a targeted third 9
(a) relay cost at fixed f ′
(b) full-width relay cost vs. τA
7
Cross-View Identification under x-Partial Synchrony
Figure 4: Closed forms of Theorem 9. (a) Relay traffic C( f ′ , s) = (n − t − s) s f ′ at t = f (normalized by n3 ; n = 3 f + 1, τA = f ): a concave parabola in s, shrinking as the attack narrows. (b) The full-width relay cost C( f , τA ) (the griefing cap while τA ≤ ⌊(n − f )/2⌋), normalized to its value at τA = f (dotted verticals), for τA ∈ [ f , n/2): the relay budget moves by at most ≈ 10% over the whole range, so the real price of raising τA is the wider legal-silence width, not bandwidth (KSI = τA +1 and the margin n − τA − f vary linearly).
A single synchronous view suffices to convict a node that silences more than τA honest peers in that view (Theorem 5), and Vigil generates that evidence online in whichever synchronous views the schedule provides. This per-view capability survives for any asynchrony fraction x < 1, a strictly larger regime than liveness accountability’s x < 1/2 [1]. What a single view cannot provide is a certificate that convinces a third party: an accusation bitmap from one view might come from an asynchronous view, where honest nodes miss messages and accuse innocent peers. This section aggregates per-view accusations across a window into transferable certificates; the aggregation needs synchronous views to outnumber asynchronous ones within the window, so its guarantees are stated for x < 1/2.
Guarantee
Result
Matching bound
7.1
No false accusation KSI = τA + 1 Violation IDs ≥ ⌈n/3⌉ Optimistic O(n)/node Worst case ≤ n3 /27 Grief priced Cross-view, x < 1/2
Thm. 6 (sync.), 10 Thm. 5 Thm. 7 Thm. 8 Thm. 9, Lem. 6 Prop. 4 Thms. 10–12
— ≥ f +1 (Thm. 2) ≤ ⌈n/3⌉ (Thm. 3) — Θ(n3 ) one-shot (Cor. 2) structural (Thm. 2) —
One Vigil view spans L = 16∆, which we take as the period granularity ∆′ of the x-partially-synchronous model. Fix a window of m = g(∆′ ) consecutive views aligned to view boundaries, of which more than a (1 − x) fraction are synchronous. Assume for exposition that all leaders in the window are honest; the super-view argument of [1] removes this at a Kviews -factor cost in window length (group views so that each group contains an honest leader w.h.p., and re-read "view" as "super-view"). Each honest node retains all signed accusation bitmaps of the window and runs BlameAccounting (steps 1–5 below) at its end. Parameters: the opening threshold AccK ≤ τA (aggregation proceeds only if every view’s conviction set contains at least AccK nodes), and x. Setting AccK ≤ f targets threshold coalitions; larger values, up to τA , are legal and only make the gate harder to open.
Table 3: V IGIL’s guarantees and the bounds they match.
conviction; Vigil prices and attributes that grief but, like every protocol by Theorem 2, cannot certify it.
6.3
Accounting Honestly for Metadata
7.2
Byte and bit counts below adopt the same per-node, per-view convention as the authenticator count: a node’s cost is what it sends, with a broadcast to n peers counted once per transmitted copy. Under it the attestation layer adds Θ(n2 ) bits of metadata per node per view plus O(n) constant-size challenge unicasts: O(n) authenticators, but not linear in bits; in bytes, the common case totals ≈ 3.2× plain Tendermint (W1). Sec. 8 reports both currencies. Appendix C details the accounting, a lossless run-length bitmap encoding, and why auditing only uncorroborated positions changes neither direction of Theorem 5. The audit is load-bearing exactly where an observer lacks corroborating material, as in the fail-closed handling of asynchronous views (Sec. 7). Appendix C also details three byproducts: a locally checkable, false-positive-free asynchrony witness, stable-peer discovery via core intersection, and the relay-phase injection defense of Sec. 5.6(ii).
Setting
The Aggregation Algorithm
BlameAccounting runs five steps (full statements in Appendix C): (1) View filtering: discard any view in which more than τA nodes issue broad accusations; by Theorem 6 only Byzantine nodes do so in synchronous views, so no synchronous view is ever discarded, while views of pervasive asynchrony fall out. (2) Conviction sets: for each retained view u, let Pu be the nodes accused by at least n − τA signers (Byzantine-only in synchronous views). (3) Opening gate: let f ′ = minu |Pu |; abort if f ′ < AccK (per-view online accountability continues regardless). (4) Consistency re-filtering: when 2 f ′ − τA > 0, keep only views whose conviction set intersects another’s in ≥ 2 f ′ − τA elements for more than an x fraction of the retained views U ′ ; synchronous views form a clique there and survive. (5) Windowed conviction: convict every node appearing in Pu for strictly more than an x̂ fraction of retained views, where the operational con10
viction bar x̂ is configured to the model’s asynchrony bound, x̂ = x. We write x for both below, and distinguish them only in W3, where x̂ is swept at a fixed measured asynchrony. The signed bitmaps of those views form a self-verifying certificate: replaying steps 1–5 over the embedded set reproduces the guilty set, and the filters only ever discard asynchronous views.
discarded, no honest node is convicted, and at least ′ f − tx , f ′ > tx 1−x 0, f ′ ≤ tx
(3)
Byzantine nodes are convicted. Proof sketch. With silence exceeding KSI everywhere, every column carries ≥ f ′ mass; the row-cap division gives at most (t − f ′ )/(1 − x) unconvicted, hence at least ( f ′ − tx)/(1 − x) convicted. ■ Two boundary readings validate the formulas (Figure 7, Appendix B). At x = 0 both theorems give exactly f ′ ≥ AccK: in a fully synchronous window, everyone accused n − τA times is convicted, consistent with Theorem 5. As AccK → τA (hence f ′ → τA , at the worst case t = τA ), the convicted count approaches τA for any x < 1/2: the certificates capture the entire coalition. Persistent attackers thus face a sharp trade-off: silence broadly and be convicted within the view (Theorem 5); silence persistently and be convicted by the window certificate (Theorem 12); or confine each node’s silence to at most τA targets, at which point the relay layer makes every honest vote set whole. Silence is either harmless or priced.
Theorem 10 (Cross-view soundness). Consider a window in which more than a (1 − x) fraction of the views are synchronous, with t ≤ τA and the conviction bar set to x̂ = x < 1/2. Then no honest node is ever convicted. Proof. Honest nodes enter Pu only in asynchronous views (step 2, using t ≤ τA < n − τA ). Steps 1 and 4 never discard synchronous views, so synchronous views constitute more than (1 − x) > x of the retained set, capping any honest node’s appearance fraction at x, at or below the conviction bar. ■ The premise is load-bearing in both directions: a window whose true asynchrony fraction exceeds the configured x̂ carries no soundness guarantee, and W4 exhibits exactly that failure at the saturated boundary t = τA . Theorem 11 (Identification from accusation counts). Given x < 1/2 and f ≤ τA < n/2: if every view of the window has at least AccK nodes accused by at least n − τA signers, then BlameAccounting convicts at least
7.3 ′ f (1 + x) − (τA + t) x , 2 f ′ > τA and f ′ (1 + x) > (τA +t)x 1−x tx (2) f′ − , 2 f ′ ≤ τA and f ′ (1 − x) > t x 1 −x 0, otherwise
Scope and Parameterization
BlameAccounting targets selective silence, not liveness violations at large. In a window where stalling stems from network asynchrony rather than silence, f ′ can be small, the gate does not open, and the algorithm correctly convicts no one. Pairing Vigil with a liveness-accountability layer [1] covers that complementary case over the same accusation transport. Vigil’s signed accusation bitmaps are exactly the per-view transcript summary [1]’s window argument consumes, so the combined deployment runs one transport and two aggregators: BlameAccounting convicting selective silencers (this section), and [1]’s aggregator attributing full liveness violations. Each is sound under its own premise, and the stronger conclusion applies when both open. For x ∈ [1/2, 1), where no transferable certificate exists (Sec. 4.1), the online per-view accusations remain useful as slashing-independent signals for watchlists, peer selection (Sec. 6.3), or off-chain arbitration. The opening threshold AccK trades sensitivity against cost: AccK = n/3 + 1 (legal whenever τA ≥ n/3 + 1) opens only on certain potential liveness violations; lower values catch smaller coalitions earlier at the price of more frequent aggregation.
Byzantine nodes, where f ′ = minu |Pu | ≥ AccK is the quantity computed in step 3. Both branches are increasing in f ′ , so substituting the guaranteed f ′ = AccK yields an apriori bound in (AccK, x, τA ,t); substituting the worst case t = τA removes the dependence on the unknown t. The case split is on f ′ , not on AccK, because it records whether the consistency filter of step 4 is active. Proof sketch (counting matrix; full proof in Appendix B). Form the f × |U ′ | incidence matrix over retained views U ′ . Synchronous columns carry mass ≥ f ′ ≥ AccK; when the second filter is active, retained asynchronous columns carry ≥ 2 f ′ − τA , giving total mass ≥ ( f ′ (1 + x) − τA · x)|U ′ |, while unconvicted rows sum to ≤ x|U ′ |. Dividing the residual mass by the per-row cap (1 − x)|U ′ | bounds the unconvicted count; monotonicity in f ′ ≥ AccK yields the claim. ■
8
Theorem 12 (Identification from persistent silence). Under the same parameters, if in every view of the window at least f ′ (AccK ≤ f ′ ≤ t) Byzantine nodes are each silent toward at least KSI = τA +1 honest nodes, then BlameAccounting opens (each view yields ≥ AccK nodes accused by ≥ n − τA honest signers, synchronous or not), no view is
Evaluation
Our evaluation answers five questions. Q1: What does accountability cost when no attack occurs, and how does the cost scale with the attack’s width? Q2: Does Vigil identify selective silencers exactly at the threshold s = τA +1, with 11
8.2
no false accusations? Q3: Do cross-view certificates remain sound and effective under real asynchrony? Q4: How do communication and latency scale to large n? Q5: Can white-box adaptive strategies evade the defenses?
8.1
WAN Experimental Results
W1 (Q1): communication overhead (Fig. 5a). Byte accounting sums the serialized protocol messages (signatures included) recorded by all n− f honest nodes in one view. Permessage sizes are ≈ 405 B for a signed vote, ≈ 473 B for a signed bitmap or accusation, and ≈ 463 B for a nested relay. At n=31, f =8, τA =10, three regimes appear in silence width s. (i) s=0: zero relays at 979,166 bytes/view, about 3.2× native Tendermint (301,723) and 10.7× lower than always-forwarding accountability (AL, our control implementing [1]’s unconditional transcript-broadcast pattern in the same codebase, not [1]’s full protocol, whose pattern is itself unoptimized (Sec. 2); 10,518,672). (ii) 0 < s ≤ τA : relayed votes equal the closed form C(t, s) = (n − t − s) st at t= f =8 exactly (336 at s=2; peak 1,040 at s=τA ), within Theorem 9’s bound. (iii) s > τA : relays drop to zero as the silent set leaves every honest core. The plotted grid is even-valued, so the transition appears between s=10 and s=12; a separate odd-s run locates it at exactly s = τA +1 = 11, and the simulator confirms the same threshold at unit resolution (S1, Fig. 6b). AL relays 18–22k votes at every s. W2 (Q2): the detection threshold (Fig. 5b). At n=31, t=12 corrupted nodes (an excessive-fault run, t > ⌊(n − 1)/3⌋ = 10), τA =15, convictions flip from 0 to all t exactly at s = τA + 1 = 16, both directions of Theorem 5 on real links. AL accuses only complete silence (s=19); Vigil lowers the detectable width from n−t to τA +1. W3 (Q2, Q3): packet loss and cross-view robustness (Fig. 5c). With Tokyo in the loop (n=46, t= f =15, τA =20), average per-view loss is 3.9% (5.8% on the Tokyo links); step 1 discards five of 50 views, so the window’s measured asynchrony fraction is 0.10 — measured as the fraction of views failing the synchrony predicate of step 1, never equated with raw packet loss. Figure 5c sweeps the conviction bar x̂ of step 5 at this fixed measured asynchrony, with the per-view threshold at n−τA = 26 > n/2: honest false convictions fall from 10 at x̂=0 to zero for all x̂ ≥ 0.16 (the dotted marker in the figure, at 0.18, is the conservative operating point we would deploy), while the Byzantine convicted set shrinks with x̂, from 15 to 0 at x̂=0.49. Both halves track Theorem 10: soundness requires x̂ to dominate the true asynchrony fraction, which x̂=0 violates and every x̂ ≥ 0.16 > 0.10 satisfies. Lowering the per-view threshold to the sub-majority bar 21 < n/2 instead leaves at least 10 honest nodes falsely accused at every x̂ (measured, not plotted): Definition 3’s majority bar is necessary on lossy links. W4 (Q3): cross-view strategies (Fig. 5d). At n=46, τA =20, x̂=0.2, five Byzantine nodes are active per view, silent toward 21 fixed honest targets; rotation cycles the active set and random samples it. Rotation convicts exactly t Byzantine nodes with zero honest false convictions for every corruption count t ≤ 18; random convicts 10–12, also with none. Both degrade at the saturated boundary t = τA = 20: rotation’s
Implementation and Evaluation Design
Implementation. We implemented Vigil as a multi-module Java/Maven system (3,254 lines). Each node runs a lock-step 16∆ view loop (Figure 3): slack, proposal with equivocation echo, two voting rounds each with the bitmap, challenge, reply, and relay steps, accusation, and closing slack. Core extraction prunes the (n−τA −1)-core over BitSet adjacency rows; challenges fire only for uncorroborated positions and replies return the claimed signed votes, verified by signature (Sec. 5.4). Adversarial strategies (fixed-, random-, and rotating-set silence, bitmap forgery, worst-case counter-accusation) are injected via per-node hooks; each view appends one metrics row to a CSV; deployment is containerized with a netem entrypoint for delay, jitter, and loss. The simulator (295 lines of Python) re-implements the same per-observer pipeline without transport or cryptography and sweeps n ≥ 103 in seconds; it forms a third realization of the protocol logic, cross-validated below. Evaluation design. The WAN prototype and the simulator divide the work by what each measures best. The WAN prototype supplies absolute performance from real-network experiments. The simulator checks measured quantities against the closed forms of Sec. 6–7 across full parameter grids; the acceptance criterion is exact equality or exact threshold location, never fitting. WAN experiments W1–W5 and simulation experiments S1–S4 map onto the questions as follows: W1 and S1 answer Q1 (Theorems 8, 9); W2, S1, and S2 answer Q2 (Theorems 5, 6, 9); W3, W4, and S3 answer Q3 (Theorems 10–12); W5 answers Q4 (Sec. 6.3, Corollary 2); S4 answers Q5 (Proposition 4, Lemma 6, and the Sec. 5.4–5.6 defenses). Statistics use 10 independent seeds with 95% confidence intervals where sampling is involved, and threshold locations are checked for seed-invariance. Throughout the evaluation, the reported corruption count is the number of nodes actually corrupted, t; runs with t > ⌊(n − 1)/3⌋ deliberately exercise the excessive-fault regime of Theorem 7 (t ≤ τA ), where the accountability guarantees persist although consensus resilience does not. WAN setup. We deployed the prototype on public clouds across Beijing, Shanghai, and Tokyo and ran W1–W5 on real WAN links (Figure 5); everywhere the Byzantine coalition counter-accuses every honest node. Beijing–Shanghai averages 24 ms (max 34 ms; loss < 1%), while the links to Tokyo average 211 ms and 64 ms, both with loss > 5%. W1/W2 use the clean Beijing–Shanghai pair. W3/W4 add Tokyo, turning genuine loss into asynchronous views that stress BlameAccounting. W5 uses a single-region Beijing deployment with netem-injected latency of 50 ± 10 ms to study large n. 12
(a) W1: relay cost
(b) W2: conviction flips at s = τA + 1
(c) W3: convictions vs. the bar x̂
(d) W4: cross-view convictions
(e) W5: communication overhead under large n
(f) W5: max confirmation latency under large n
Figure 5: WAN results (Beijing, Shanghai, Tokyo); analysis in Sec. 8.2. (a) W1: per-view bytes vs. silence width s, against Tendermint and always-forwarding accountability (AL) (n=31, f =8, τA =10). (b) W2: convicted nodes vs. s (n=31, t=12, τA =15). (c) W3: Byzantine convictions and honest false convictions vs. the conviction bar x̂, at per-view threshold n−τA =26 (n=46, t= f =15, τA =20, measured asynchrony 0.10). (d) W4: convicted nodes vs. the actual corruption count t under rotation and random silence (n=46, τA =20, x̂=0.2). (e, f) W5 (t = τA = ⌈n/3⌉): total communication and maximum confirmation latency vs. n (single-region netem). In (e) the s=τA +1 series coincides with s=0 and is hidden beneath it.
8.3
Byzantine count falls to 10 and random’s rises to 15, while 1 and 7 honest nodes respectively are convicted. This is a violation of Theorem 10’s premise, not a counterexample to it: as the margin n − τA − t shrinks to 6, honest observers in asynchronous views miss enough messages that honest nodes enter Pu in more than an x̂ fraction of retained views, i.e. the window’s effective asynchrony exceeds the configured bar. Raising x̂, or setting τA > t, restores it.
Simulation Results
S1 (Q1, Q2): relay closed form and threshold (Fig. 6a, b). On a 6 × 6 grid at n = 91, t = f = τA = 30, measured relays equal C( f ′ , s) on all 36 points (peak 27,900) and are zero under no or complete silence. In a separate configuration (n=61, t= f =20, Fig. 6b) convictions flip from 0 to all t exactly at s = τA +1 for both τA ∈ {20, 25}, at unit resolution in s and invariant across 10 seeds. Forged all-ones bitmaps do not help; no challenge fires in synchronous views, where every claim is corroborated and mirror bits carry the evidence. S2 (Q2): the majority bar (Fig. 6c). Over 10 seeds × 200 views per point (n = 61, f = 20), at injected packet-drop probability d = 2% the f +1 bar falsely accuses 91.2% ± 0.3% of honest nodes. The majority bar accuses 0.002%, an exact count rather than a sampled estimate: 2 of the 82,000 honest node-views across all seeds, with nine of ten seeds exactly zero, and no certificate is affected (Theorem 10). At d ≥ 5% even the majority bar degrades (46.5% ± 3.4% at d=5%, reaching 100% at d ≥ 10%), precisely the regime step-1 filtering discards — which is why per-view accusations are never used as certificates on their own. S3 (Q3): cross-view soundness and speed (Fig. 6d). Over a 5 × 4 grid (x̂ ∈ {0, . . . , 0.4}, f ′ ∈ {5, 10, 15, 20}; n = 61, t = f = τA = 20, 40-view windows, rotating silence), BlameAccounting convicted zero honest nodes in every cell and dominated the Theorem 12 bound everywhere, typically convicting the whole coalition. Pure-Python core extraction runs
W5 (Q4): large n (Fig. 5e, f). At s ∈ {0, τA +1} the two curves coincide (both relay nothing) and total communication grows as n2.3 , consistent with the Θ(n2 ) per-node message count of Sec. 6.3, the exponent above 2 reflecting the growing per-message bitmap payload. At s=τA /2 the total grows as n2.68 and the relay component as n3.01 : the Θ(n3 ) worst case of Corollary 2 and Theorem 9, realized end-to-end. The total exponent is the lower of the two because relaying is only ≈ 25% of the bytes at n=31 and 74.5% at n=501; asymptotically the total inherits the cubic term. At n=501 the relay overhead reaches 1.61 GB/view, 74.5% of the 2.16 GB/view total (about 31.5× Tendermint’s 68.5 MB/view). Maximum confirmation latency stays near 1.0 s at n=501 for s ∈ {0, τA +1} (about 4.5× Tendermint) and rises to 6.294 s at s=τA /2, of which relay processing takes 5.38 s and core extraction only 62 ms: the latency under attack comes from the forwarding path. Single-region netem does not reproduce crossregion loss patterns, so W5 supports the scaling exponents, not absolute-latency extrapolation. 13
(a) S1: relay vs. C( f ′ , s)
(b) S1: flips at s = τA + 1
f = 20
f = 10
f = 25
f = 15
f = 30
0
0
relayed votes
0
0
0
20000 15000 10000 5000 5
10
15 20 s (silence width)
25
30
20.0 17.5 15.0 12.5 10.0 7.5 5.0 2.5 0.0
(c) S2: false accusations
0
5
(d) S3: convictions vs. bound
100
τA = 20 τA = 25
honest false-accusation rate (%)
f =5 0
25000
Byzantine nodes majority-accused
measured (dashed: closed form)
10
15 20 25 30 s (silence width)
35
80 60 40 20 0
+1 bar majority bar ( > n/2) f
0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0 drop probability d (%)
40
Figure 6: Simulation results; analysis in Sec. 8.3. (a) S1: measured relay traffic (markers) vs. the closed form C( f ′ , s) (dashed) (n=91, t= f =τA =30). (b) S1: convicted nodes vs. s (n=61, t= f =20; dotted verticals at s = τA +1 for τA ∈ {20, 25}). (c) S2: honest false-accusation rate vs. drop probability d under the f +1 and majority bars (mean ± 95% CI, 10 seeds; n=61, t= f =τA =20). (d) S3: cross-view convictions (solid) vs. the Theorem 12 bound (dashed). n = 2000 in 20 ms (∼ n2 ) and dropped zero honest nodes in every run (Lemma 2). S4 (Q5): adaptive white-box adversaries. Four strategies optimized against the protocol’s internals (n=61, t= f =τA =20, 3 seeds each; every criterion is exact equality, so 3 suffice). (A1) Relay-phase injection (withhold in the voting phase, inject during relay) is structurally inert: cores and accusations are fixed before any relay is accepted (Sec. 5.6(ii)), and the outcome is bit-identical to the baseline. (A2) Threshold-pinned silence at s = τA is never accused and induces exactly C(t, τA ) = 8,400 relays per view: Proposition 4’s griefing floor, measured. (A3) Bitmap forgery on top of super-threshold silence changes nothing; all t remain accused (Sec. 5.4). (A4) Pure denial-griefing (falsely denying τA honest votes) is never accused and induces exactly 8,400 relays, not the naive t τA (n−t) = 16,400: Lemma 6’s symmetric ejection, confirmed at equality. A4 is also a methodological note. Our first analysis of the denial channel predicted the 2× constant, and the exact-equality harness falsified it before publication.
9
the full-width relay cost C( f , τA ) moves by at most ≈ 10% (at n=31, f =8, moving τA from 8 to 10 raises it from 960 to 1,040 relays/view, W1, while restoring a two-node excessivefault margin). Bandwidth is therefore not the binding constraint. Rule of thumb: set τA to the largest corruption the deployment should survive accountably. Sub-threshold griefing. Proposition 4 gives the first explicit pricing of the residual surface Theorem 2 makes structural: sub-threshold silence is unaccusable yet must be repaired. The mitigations (watchlisting, rate-limiting, priced relay) use attribution the protocol already computes; making them slashing-grade would contradict Theorem 2. Link observability and the adaptive-relay gap. The lower bounds assume nodes cannot observe third-party links; trusted relays or attested telemetry escape the model and can beat KSI = f +1. Corollary 2 covers one-shot, feedback-free repair only. For multi-round repair driven by receipt feedback, the picture we expect is a dichotomy: against a deterministic relay schedule, a static adversary can place its corruptions as a contiguous block of the schedule so that some pairs are served by up to f defaulting relayers in a row, keeping the amortized cost cubic; against a schedule derived from per-view randomness revealed after corruption, each pair is served by an honest relayer within O(log n) expected rounds, and the sub-threshold griefing cost of Proposition 4 drops to O(n2 ) in expectation, the same order as the unconditional cost of [1]. We are preparing an extended version establishing this dichotomy; the present bounds and Vigil’s relay rule are unaffected. Also left open is adaptive corruption: Theorem 1’s coupling fixes the Byzantine set upfront and cannot express corrupting nodes after observing bitmaps. Limitations. (i) The Θ(n3 ) bound covers feedback-free repair only; (ii) griefing is priced, not prevented (Proposition 4); (iii) Θ(n2 ) bits of idle metadata (Sec. 6.3) and 16∆ views pending pipelining; (iv) Lemma 6’s denial branch is verified in simulation (S4), not on WAN; (v) link non-observability is assumed; (vi) corruption is static (Sec. 3.2); (vii) membership is fixed; reconfiguration is future work; (viii) Theorem 1’s swap budget means the impunity width it certifies for a
Discussion
Latency and τA . Vigil’s view spans L = 16∆ against Tendermint’s ≈ 4∆ for the same propose/echo/two-vote core. This is a real cost but a schedule artifact: every theorem operates on the signed bitmaps of a completed voting round, so nothing in Sec. 4–7 requires the audit phases (12∆ of Figure 3) to run inside the view they audit, and attestation traffic is disjoint from voting traffic, so the pipelines can share wall-clock slots. Running the audit one view behind voting thus restores ≈ 4∆ views at a one-view evidence delay (sketch: Appendix D; implementing it is future work). The accountability resilience trades off similarly. Setting τA = f minimizes KSI and the griefing budget but empties Theorem 7’s excessive-fault regime and saturates the W4 margin; raising it buys accountability up to t ≤ τA and margin n − τA − f at the price of a wider legal-silence width. Figure 4b quantifies the trade-off from the closed form: over the whole admissible range τA ∈ [ f , n/2) 14
single silencer, f , shrinks to f − t + 1 per node for a coalition of t simultaneous silencers — Theorem 2’s lower bound is unaffected (it uses t=1), but joint sub-threshold patterns may be refutable by arguments outside our model.
10
[3] Pierre Civit, Seth Gilbert, and Vincent Gramoli. Polygraph: Accountable Byzantine agreement. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 403–412, 2021. [4] Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, and Pramod Viswanath. BFT protocol forensics. In Proceedings of the ACM Conference on Computer and Communications Security (CCS), pp. 1722–1743, 2021.
Conclusion
[5] Joachim Neu, Ertem Nusret Tas, and David Tse. The availabilityaccountability dilemma and its resolution via accountability gadgets. In Financial Cryptography and Data Security (FC), pp. 541–559, 2022.
Selective silence stalls victims while preserving the attacker’s standing. We mapped its limits (an identification threshold of exactly f +1, Θ(n3 ) feedback-free repair, an uncloseable griefing surface) and matched them with Vigil, which majorityaccuses every node silencing more than τA honest peers and forwards only in proportion to actual attacks. The broader lesson: even misbehavior with no cryptographic residue can be priced, once everyone auditably commits to what it heard.
[6] Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 173–186, 1999. [7] Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. arXiv:1807.04938, 2018. [8] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. HotStuff: BFT consensus with linearity and responsiveness. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 347–356, 2019.
Ethics Considerations
[9] Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: A scalable and decentralized trust infrastructure. In Proceedings of the 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 568–580, 2019.
This work analyzes and strengthens defenses of permissionless and permissioned consensus systems; it introduces no new attack capability. Selective silence is executable today by any Byzantine participant, and our lower bounds show what no defender can detect rather than how to attack. The adversarial strategies in our implementation are injected via test hooks in our own deployment; no third-party network or system was probed. Proposition 4 documents a griefing surface that is structural to every protocol in the model (Theorem 2), so disclosure does not advantage attackers over the status quo; the accompanying mitigations are provided. No human subjects, personal data, or production systems are involved.
[10] Assia Doudou, Benoit Garbinato, Rachid Guerraoui, and Andre Schiper. Muteness failure detectors: Specification and implementation. In Dependable Computing – EDCC-3, pp. 71–87, 1999. [11] Andreas Haeberlen, Petr Kouznetsov, and Peter Druschel. PeerReview: Practical accountability for distributed systems. In Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP), pp. 175–188, 2007. [12] Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pp. 153–168, 2009.
Artifact Availability
[13] Vassilis Zikas, Sarah Hauser, and Ueli Maurer. Realistic failures in secure multi-party computation. In Theory of Cryptography: 6th Theory of Cryptography Conference (TCC), pp. 274–293, 2009.
The complete artifact will be released publicly upon publication. It contains the Java implementation, the Python simulator, the analysis scripts and closed-form validators (including a standalone script that re-verifies, by exhaustive enumeration, every closed form and identity quoted in the paper), the container and multi-region deployment recipes (including netem configurations distinguishing injected from naturally occurring loss), the adversarial-strategy hooks, and the raw per-view CSV logs behind every figure, with per-message-type byte accounting. All simulation results are exactly reproducible by construction (deterministic pipeline, no fitting); WAN results include the recorded link conditions.
[14] Julian Loss and Gilad Stern. Zombies and ghosts: Optimal Byzantine agreement in the presence of omission faults. In Theory of Cryptography Conference (TCC), pp. 395–421, 2023. [15] Julian Loss, Kecheng Shi, and Gilad Stern. Consensus in the presence of overlapping faults and total omission. In Theory of Cryptography Conference (TCC), pp. 353–382, 2024. [16] Alejandro Ranchal-Pedrosa and Vincent Gramoli. Basilic: Resilientoptimal consensus protocols with benign and deceitful faults. In Proceedings of the IEEE 36th Computer Security Foundations Symposium (CSF), pp. 91–106, 2023. [17] Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros. pod: An optimal-latency, censorship-free, and accountable generalized consensus layer. In 39th International Symposium on Distributed Computing (DISC), LIPIcs, vol. 356, pp. 4:1–4:24, 2025.
References
[18] Zhuolun Xiang, Andrei Tonkikh, and Alexander Spiegelman. Prefix consensus for censorship-resistant BFT. arXiv:2602.02892, 2026.
[1] Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Luca Zanolini. Accountable liveness. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 3431–3445, 2025.
[19] Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis. SoK: Consensus in the age of blockchains. In Proceedings of the ACM Conference on Advances in Financial Technologies (AFT), pp. 183–198, 2019.
[2] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. arXiv:1710.09437, 2017.
15
[20] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3), pp. 417–427, 1983.
[37] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: DAG BFT protocols made practical. In Proceedings of the ACM Conference on Computer and Communications Security (CCS), pp. 2705–2718, 2022.
[21] Tiantian Gong, Gustavo Franco Camilo, Kartik Nayak, Andrew LewisPye, and Aniket Kate. Recover from excessive faults in partiallysynchronous BFT SMR. In Proceedings of the 34th USENIX Security Symposium (USENIX Security 25), pp. 4147–4166, 2025.
[38] Andreas Haeberlen and Petr Kuznetsov. The fault detection problem. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS), pp. 99–114, 2009. [39] Kim Potter Kihlstrom, Louise E. Moser, and P. Michael Melliar-Smith. Byzantine fault detectors for solving consensus. The Computer Journal, 46(1), pp. 16–35, 2003.
[22] Pierre Civit, Daniel Collins, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira, and Pouriya Zarbafian. Scalable accountable Byzantine agreement and beyond. In Proceedings of the 2026 IEEE Symposium on Security and Privacy (S&P), pp. 1215–1234, 2026.
[40] Kenneth J. Perry and Sam Toueg. Distributed agreement in the presence of processor and communication faults. IEEE Transactions on Software Engineering, 12(3), pp. 477–482, 1986.
[23] Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. Repeated agreement is cheap! On weak accountability and multishot Byzantine agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 15–27, 2025.
[41] Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Michael Dahlin, Jean-Philippe Martin, and Carl Porth. BAR fault tolerance for cooperative services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP), pp. 45–58, 2005. [42] Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, and Jovan Komatovic. As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy! In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 560–570, 2022.
[24] Andrew Lewis-Pye and Tim Roughgarden. Beyond optimal faulttolerance. In 7th Conference on Advances in Financial Technologies (AFT 2025), LIPIcs, vol. 354, pp. 15:1–15:23, 2025. [25] Lewis Tseng, Qinzi Zhang, Saptaparni Kumar, and Yifan Zhang. Exact consensus under global asymmetric Byzantine links. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 721–731, 2020.
[43] Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X. Zhang. Combining GHOST and Casper. arXiv:2003.03052, 2020. [44] Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming. 2nd ed., Springer, 2011.
[26] Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. DARE to agree: Byzantine agreement with optimal resilience and adaptive communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 145–156, 2024.
[45] Joachim Neu, Ertem Nusret Tas, and David Tse. Ebb-and-flow protocols: A resolution of the availability-finality dilemma. In Proceedings of the 42nd IEEE Symposium on Security and Privacy (S&P), pp. 446– 465, 2021.
[27] Preston Vander Vos, Alberto Sonnino, Giorgos Tsimos, Philipp Jovanovic, and Lefteris Kokoris-Kogias. BlueBottle: Fast and robust blockchains through subsystem specialization. arXiv:2511.15361, 2025.
Appendix roadmap. Appendix A gives the full induction behind Theorem 1’s twin executions. Appendix B proves the counting bounds of Theorem 11 and plots the cross-view closed forms (Figure 7). Appendix C collects the deferred proofs (Theorems 3, 4, 9; Corollary 2; Lemma 5), the full five-step statement of BlameAccounting, the metadata accounting, and three byproducts. Appendix D lists the per-view pseudocode (Algorithm 2) and evidence pipeline (Figure 8), sketches the pipelined schedule of Sec. 9, and summarizes the closed-form verifier’s coverage.
[28] Baolin Li, Huiping Sun, and Zhong Chen. GALUPA: Gossiping aggregated locking and output proofs for accountability in BFT. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS), 2026. [29] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3), pp. 382–401, 1982. [30] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), pp. 374–382, 1985. [31] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2), pp. 288–323, 1988.
A
Proof of Theorem 1 (Full Induction)
We prove the conjunction of four invariants, for all protocol ′ steps k: (I1) viewEp (k) = viewEp (k) for every p ∈ / S ∪ {q}; ′ E E (I2) stateu (k) = stateu (k) for every u ∈ / S (including q: both executions run the honest code there once inputs are aligned by the refinement); (I3) for u ∈ S, the outgoing traffic toward nodes other than q is identical in both executions; (I4) q’s processed input (messages accepted by the protocol layer) consists in both executions of exactly the messages from nodes outside S. Base case k = 0: initial states and tapes coincide by construction. Inductive step: assume the invariants at k. Every u ∈ / S ∪{q} has an identical view (I1), hence sends identical messages to
[32] Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2), pp. 225– 267, 1996. [33] Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2), pp. 130–143, 1987. [34] Stephen B. Seidman. Network structure and minimum degree. Social Networks, 5(3), pp. 269–287, 1983. [35] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Proceedings of EUROCRYPT, pp. 416–432, 2003. [36] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and Tusk: A DAG-based mempool and efficient BFT consensus. In Proceedings of the European Conference on Computer Systems (EuroSys), pp. 34–50, 2022.
16
identical recipients. Every u ∈ S runs the honest code on the view "as if q never spoke": in E this is literally u’s view (q sent nothing to u); in E ′ it is u’s view after the discard instruction removes q’s messages. These coincide, giving I3 at k+1. For q: its processed input in E is, by the refinement, exactly the traffic from nodes outside S (identical across executions by I2), while S’s traffic is discarded in E (by q’s refinement instruction) exactly as q’s traffic is discarded in E ′ (by S’s instruction); hence q’s processed views coincide (I4 at k+1), and the honest code q runs on them produces identical output toward nodes outside S (I2 at k+1 for u = q). The only traffic that differs between the executions lives on the q–S links, suppressed by q in E and discarded in E ′ ; it enters no processed view outside S ∪ {q}, and link non-observability hides its wire-level existence from every such p. Hence I1 at k+1.
B
in which every column, synchronous or not, already carries mass ≥ f ′ (silence above KSI fills each column uniformly), so no asynchronous mass is lost and the same row-cap division gives ( f ′ − tx)/(1 − x).
C
Deferred Proofs and Accounting Details
The proof of Theorem 2 appears in full in Sec. 4.4. Proof of Theorem 3 (Identification cap). The adversary selects exactly n − Q + 1 of its nodes to be completely silent and lets its remaining corrupted nodes follow the protocol to the letter. (A liveness violation under synchrony requires at least n − Q + 1 corrupted nodes to withhold votes, so the construction is within budget exactly in the regime in which the cap is testable.) Every node then receives at most Q − 1 votes, so all honest nodes violate timely liveness. The well-behaved corrupted nodes are, in every honest node’s view, literally executing the honest protocol (the execution is identical to one in which they are honest), so by Proposition 3 no protocol may accuse any of them. The accusable set is thus confined to the n − Q + 1 silent nodes. ■ Proof of Theorem 4 (Forwarding necessity). (Blocks.) Suppose blocks are not relayed. A Byzantine leader partitions the honest nodes into equal halves A and B, proposes only to A, and stays silent toward B. Every node then holds at most n/2 valid votes; all honest nodes violate liveness; A’s members can only blame the (to them unresponsive) members of B and vice versa; the two accusation sets each fall short of a majority, and each contains honest nodes. Relaying blocks (with equivocation detection) collapses this: two conflicting signed proposals form transferable proof against the leader, and a leader silent toward some nodes is repaired by the relay. (Votes.) Suppose votes are not relayed. Partition the nodes into A, B, C with |A| = |C| = t, C Byzantine and silent toward A while interacting correctly with B; here t is the actual corruption count, in the super-threshold regime ⌈n/3⌉ ≤ t ≤ τA < n/2 where the premise is satisfiable (see the parenthetical in the theorem statement). The members of A receive fewer than the quorum Q = ⌊2n/3⌋ + 1 of votes and violate liveness, while B observes nothing amiss. By Theorem 1, B’s members cannot accuse anyone; only A’s t < n/2 members can accuse C, never a majority. ■ Aggregation does not rescue the no-relay regime. Quorum certificates (threshold/multi-signatures) cannot help. Consider h = n − t honest nodes with n/2 < h < 2n/3 (possible exactly in the super-threshold regime n/3 < t < n/2 of Theorem 4), and an adversary that delivers votes so that every honest node ends with exactly 2n/3 votes, just below quorum, so all honest nodes stall. The total number of missing (honest node, vote) pairs k then satisfies n2 /6 < k < 2n2 /9, i.e., n/3 < k/t < 2n/3 per Byzantine node on average: the adversary can realize this with every Byzantine node silent toward fewer than half of the honest nodes. Each Byzantine node is then accused by fewer than n/2 nodes, so no majority
Cross-View Counting Details (Theorem 11)
This appendix gives the counting proof of Theorem 11. Let U ′ be the retained views, partitioned into synchronous S and asynchronous A, with |S| > (1 − x)|U ′ | and |A| < x|U ′ |. Form the t × |U ′ | incidence matrix M of conviction-set membership: Mq,u = 1 iff q ∈ Pu . Column masses. Synchronous columns carry mass ≥ f ′ ≥ AccK by the opening precondition and step 2. When the consistency filter is active (2 f ′ −τA > 0), a retained asynchronous view’s conviction set intersects every synchronous one in at least 2 f ′ − τA elements (else it has degree 0 in the consistency graph and falls), so asynchronous columns carry mass ≥ 2 f ′ − τA . Total mass: |M| ≥ f ′ |S| + (2 f ′ − τA )|A| = f ′ |U ′ | + ( f ′ − τA )|A| ≥ f ′ (1 + x) − τA x |U ′ |, using ( f ′ − τA )|A| ≥ ( f ′ − τA ) x|U ′ | (the coefficient is negative, so the upper bound on |A| gives the lower bound on the product). Row caps and division. A row appears in strictly more than an x fraction of U ′ iff convicted, so each unconvicted row carries mass ≤ x|U ′ | while convicted rows carry at most |U ′ |. With c convicted and t − c unconvicted rows: f ′ (1 + x) − τA x |U ′ | ≤ |M| ≤ c |U ′ | + (t − c) x |U ′ |, yielding c ≥ f ′ (1 + x) − (τA + t) x /(1 − x), monotone increasing in f ′ ≥ AccK: case 1 of the theorem. When 2 f ′ ≤ τA the filter imposes no asynchronous mass; the cruder bound |M| ≥ f ′ |S| ≥ f ′ (1 − x)|U ′ | divided by the same row caps gives c ≥ f ′ − tx/(1 − x): case 2. Both are positive exactly under the stated threshold conditions. Note that neither branch uses τA > n/3: step 2’s soundness needs only t ≤ τA < n/2, so Theorem 11 holds on the full admissible range f ≤ τA < n/2, including the optimal τA = f . Theorem 12 is the specialization 17
(a) Theorem 11 surface
(b) Thm. 11 decay with x
(c) Theorem 12 surface
(d) Thm. 12 decay with x
Figure 7: Cross-view identification at τA = 0.4n, plotted from the closed forms. (a, b) Theorem 11: minimum convictions over (AccK, x), and its decay with x at fixed AccK. (c, d) Theorem 12: the stronger premise removes the second filter, leaving two regimes and uniformly higher counts. accusation forms, and broadcasting or verifying aggregated QCs changes nothing, because no honest node possesses a valid QC to share. Aggregation compresses evidence that exists; it cannot conjure the missing votes. ■
Nodes outside cores receive nothing; duplicates across relayers are the price of guaranteed delivery established by Corollary 2 (any designated-relay scheme is plantable). Maximization: C is increasing in f ′ ; ∂C/∂s = f ′ (n − t − 2s) vanishes at s = (n − t)/2, and by concavity the integer maximizer is min(τA , ⌊(n − t)/2⌋); at the worst case t = f this is min(τA , ⌊(n − f )/2⌋); d/d f [ f (n − f )2 /4] = (n − f )(n − 3 f )/4 ≥ 0 for f ≤ n/3. ■
Proof of Corollary 2 (Θ(n3 ), feedback-free repair). In the A/B/C construction, accountability requires B’s members to relay C-region votes to A (Theorem 4), synchronizing A’s evidence so that all n − f honest nodes accuse C jointly. Could a single designated relay b ∈ B suffice, at O(n2 )? No: the adversary plants one of its nodes as b. Formally, move one Byzantine node from C into B (now |A| = |C| = t − 1) and let it behave honestly everywhere except the relay step, where it forwards nothing to A. This planted relay is silent toward only |A| < f nodes, so by Theorem 1 it is indistinguishable from an honest relay to everyone outside A; the violation persists and no majority forms. The same argument defeats any designated-relay set of size ≤ f , and, since feedback-free protocols must fix their relay sets before learning which designated relayers defaulted, any non-adaptive choice of relayers. Guaranteeing repair therefore requires every member of B to relay. Instantiating the construction at t = ⌈n/3⌉ — the smallest admissible value, and by Theorem 7 exactly the corruption count a violation forces — gives |B| = n − 2⌈n/3⌉ = Θ(n) relayers, each relaying Θ(n) votes to Θ(n) recipients: Θ(n3 ) authenticators. (The construction degenerates as t → n/2, where |B| → 0; the cubic bound is claimed at t = Θ(n) with n − 2t = Θ(n), which is the regime of interest.) Naive full forwarding matches the upper bound within this class, as does Vigil’s selective variant (Theorem 9). ■
BlameAccounting steps 1–5 (Sec. 7.2). Step 1 (view filtering). For each view, count the accusation bitmaps that blame more than τA nodes; keep the view iff this count is at most τA . In a synchronous view only Byzantine nodes issue such broad accusations (Theorem 6), so no synchronous view is ever discarded, while views with pervasive asynchrony (where many honest nodes miss many messages and say so) are discarded, which only helps. Step 2 (per-view conviction sets). For each retained view u, let Pu be the set of nodes accused by at least n − τA distinct signers in u. In synchronous views, Pu contains only Byzantine nodes: honest nodes are accused by at most t ≤ τA < n − τA signers there (using τA < n/2). Step 3 (opening gate). Let f ′ = minu |Pu | over retained views. If f ′ < AccK, abort (insufficient evidence for a window-level certificate; per-view online accountability continues regardless). Step 4 (consistency re-filtering). If 2 f ′ − τA > 0, conviction sets of any two synchronous views must intersect in at least 2 f ′ − τA elements (both are ≥ f ′ -subsets of the same t-element Byzantine set, t ≤ τA ). Build the graph on retained views with edges for pairs satisfying this, and keep only views of degree > x · |U ′ | within the retained set U ′ ; since synchronous views form a clique of size > (1 − x)|U ′ | > x · |U ′ |, none is discarded; only asynchronous views can fall. Step 5 (windowed conviction). Convict every node appearing in Pu for strictly more than an x̂ = x fraction of the retained views; the signed bitmaps of those views form the certificate, and the certificate is self-verifying: replaying steps 1–5 over the embedded AccusationSet reproduces guiltySet, and no manipulation of the embedded set can make it include an honest node (the filters only ever discard asynchronous views).
Proof of Lemma 5 (Audit security). Votes carry existentially unforgeable signatures bound to their (view, round), so exhibiting a valid signed vote proves possession, replay across views or rounds fails signature verification, and producing an unheld vote requires forgery. Inconsistent replies to different observers are individually verified, so they only remove q from more graphs. ■ Proof of Theorem 9 (closed-form maximization). Each of the n − t − s non-targeted honest relayers detects, from W members’ truthful bitmaps, exactly the f ′ votes each target misses, and unicasts them: s · f ′ authenticators per relayer.
Metadata accounting details (Sec. 6.3). The attestation layer’s n bitmap broadcasts of n bits are Θ(n2 ) bits per node 18
Algorithm 2 Vigil node, one view v (rounds r ∈ {1, 2})
(a) Bitmaps: signed receipt claims (b) Symmetrize: mutual attestation only
silent q: mirror bits kill its edges
(c) Core prune: (n − τA − 1)core, deterministic
s(q) > τA ⇒ pruned from every core
(d) Challenge: audit uncorroborated claims
forged all-ones bitmap fails the audit
1: on propose: verify leader’s block; echo-relay; if two conflicting proposals seen: accuse leader 2: voter : broadcast signed vote 3: attestation: broadcast signed bitmap bm p 4: validity-filter peer bitmaps (Sec. 5.2); symmetrize → G p (r) 5: K p ← CoreExtract(G p ) (Alg. 1) (r) 6: challenge each q ∈ K p on positions i with bmq [i]=1 and vote i ∈ / local store; verify signatures of returned votes; drop failures (r) 7: relay: ∀q ∈ K p missing vote of some (r) w ∈ K p held locally: unicast w’s vote to q (accept inbound relays only from/for own-core members) 8: accuse: broadcast signed bitmap accusing exactly (1) (2) [n] \ (K p ∩ K p ) 9: collect accusation bitmaps; on > n/2 accusers of q: emit majority-accusation certificate for q
(e) Relay & accuse: repair inside Kp ; accuse the rest
Figure 8: The V IGIL evidence pipeline. Honest nodes always survive stages (b)–(d) (Lemmas 1–2); a node silent toward more than τA honest peers is pruned from every honest observer’s core and majority-accused (Theorem 5).
Pipelined schedule sketch (Sec. 9). The audit phases of view v (bitmap, challenge, reply, relay, accuse; 12∆ in Figure 3) read only the signed votes and bitmaps of view v’s completed rounds, never the proposal or votes of view v+1. A pipelined schedule therefore overlays the attestation pipeline of view v onto the voting phases of view v+1: bitmapv alongside propose/echov+1 , challenge and replyv alongside vote1,v+1 , relayv alongside vote2,v+1 , and accusev in the closing slack. Steady-state view length returns to ≈ 4∆, and the evidence for view v completes by the end of view v+1 (a one-view delay). No theorem’s premise moves: Lemmas 1–3 and Theorem 5 quantify over the bitmaps of a fixed view and evaluate identically whether that evaluation runs inside the view or one view later; Theorem 6’s counting is per view; Theorem 8’s accounting is unchanged, since the same messages are sent and only rescheduled; and Theorems 10–12 consume signed accusation bitmaps stamped with their view number, so window aggregation is oblivious to when within the schedule they were produced. The one new consideration is bandwidth contention between overlapping phases, which affects the calibration of ∆ but no proof; implementing and measuring this schedule is the future work flagged in Sec. 9. Closed-form verification coverage. The standalone verifier shipped with the artifact re-checks, by exhaustive enumeration: the quorum identity n − Q + 1 = ⌈n/3⌉ for all n ≤ 400; Theorem 9’s integer maximizer s∗ = min(τA , ⌊(n − t)/2⌋) at t = f against brute force over all ( f ′ , s) for every f ≤ 40 and ∗ = f 2 ( f +1) and every legal τA ; the canonical worst case Cint its exact gap 1 + 1/(4 f ( f +1)) to the unconstrained optimum; Lemma 6’s per-node maximizer; Proposition 4’s cap, including the counterexample showing that C( f , τA ) alone would understate it for τA > ⌊(n − f )/2⌋ (Lemma 6’s per-node cap binds first) (at n=31, f =8, τA =15: 1,056 versus 960); the x = 0 boundary readings and x-monotonicity of Theorems 11–12; and every concrete number quoted in Sec. 8 (336; 1,040; 8,400 versus the naive 16,400; 27,900; 960; 0.002%).
per view; challenges add O(n) constant-size unicasts per node, and a reply returns the challenged signed votes, at most the votes a relay would carry anyway: O(n) authenticators but not asymptotically linear in bits. Bitmaps compress to O(#zeros) under run-length encoding in the common all-ones case. Auditing only uncorroborated positions is lossless for every theorem in Sec. 5–6. For positions p can corroborate, an edge’s evidentiary weight rests on the honest counterparty’s mirror bit and the vote’s signature, not on the audit: Theorem 5’s (≤) direction uses only the mirror bits of silenced honest nodes, and its (≥) direction concerns colluders, who pass audits anyway by sharing votes; the audit’s scope therefore changes neither side. The audit is load-bearing precisely where p lacks corroborating material: a non-participating node inflating its bitmap toward an observer that cannot cross-check, most relevantly in asynchronous views where Lemma 1 fails (Sec. 7’s fail-closed handling relies on this). In the common case no uncorroborated position exists and the challenge phase is empty. Byproducts (Sec. 6.3). (i) Asynchrony witness. If an honest observer’s graph contains no (n − τA − 1)-core of size ≥ n − τA , then by Lemma 2 the view was not synchronous: a locally checkable, false-positive-free asynchrony detector. (ii) Stable-peer discovery. The intersection of an observer’s cores across recent views is exactly the set of peers with sustained mutual connectivity, usable for topology-aware optimizations. (iii) Relay-phase injection defense. As Sec. 5.6(ii) showed, membership-before-forwarding closes the vote-injection loophole that defeats transcript-based schemes.
D
Protocol Pseudocode
Cross-view aggregation (BlameAccounting, steps 1–5) runs at window boundaries over the retained signed accusation bitmaps, per Sec. 7.2. 19
All checks pass.
20