Vigil: Accountable Liveness against Selective Silence

BFT accountability is well understood for safety violations, and recent work attributes global liveness violations; \emph{recipient-selective} 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 $K_{\mathrm{S}\mathrm{I}}\ge f+1$ on the \emph{silence identification threshold}; moreover, any feedback-free repair after a silence-induced violation costs $\mathrm{\Theta }(n^3)$. Positively, $\text{textsc}Vigil$, 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 $\mathrm{\Theta }(n^2)$ bitmap metadata bits per node), relays in proportion to the attack’s width (sub-threshold silence can force up to $n^3\mathrm{/}27$ relays per view, a cost we price exactly), and majority-accuses any node silent toward more than a tunable resilience ${\tau }_A$ of honest peers ($K_{\mathrm{S}\mathrm{I}}={\tau }_A+1$, optimal at ${\tau }_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\mathrm{\%}$ loss, an $f+1$ accusation bar falsely accuses $91.2\mathrm{\%}$ of honest nodes, while our majority bar accuses $0.002\mathrm{\%}$.