Paper 2026/1183

Validity in Responsive Byzantine Agreement

Abstract

Byzantine Agreement (BA) protocols must ensure not only agreement and termination, but also validity: the value agreed upon should meaningfully reflect the honest parties' inputs. The choice of validity condition can change the exact resilience threshold at which BA is solvable. Tight characterizations for BA with general validity conditions are known in the partially synchronous model (PODC'23), in the synchronous model (PODC'24), and in the network-agnostic model (DISC'25). We focus on general validity for synchronous BA with responsive termination. Such protocols remain secure against up to $t_s$ byzantine corruptions, but incur a running time that depends on the actual network delay $\delta$, rather than the conservative delay bound $\Delta \gg \delta$, whenever at most $t_r \leq t_s$ parties are corrupted. We present a tight characterization of the validity properties solvable in this setting. We prove that every non-trivial validity property requires $n>2 t_r+t_s$ in authenticated settings, where a public-key infrastructure and digital signatures are available, and $n>3 t_s$ in unauthenticated settings. These threshold conditions are accompanied by a validity-dependent requirement, the responsive similarity condition: roughly, for any concrete configuration of honest inputs, there is a value that is valid for any view that a protocol could obtain from this initial configuration. We then present matching protocols in both settings, showing that these conditions are sufficient. The main technical contribution is an authenticated responsive Core-Set Agreement protocol requiring $n>2 t_r+t_s$. This threshold may place the protocol in an honest-minority regime, where prior constructions for general validity do not apply and where standard Synchronous Broadcast is not responsive. Finally, we instantiate the characterization for several standard validity notions -- weak validity, strong unanimity, convex validity, and honest-input validity.