Paper 2026/1146

Constant-Round Interactive Consistency in Dishonest Majority, or with Quadratic Communication in Honest Majority

Abstract

We present the first constant-expected-latency protocols for Interactive Consistency (IC), also known as Parallel Byzantine Broadcast, that achieve either: (1) security in dishonest majority, namely $t \leq (1-\varepsilon)n$ for any constant $\varepsilon\in \Omega(1)$; or (2) quadratic communication $O\!\left(n^2(L_{in}+\kappa)\right)$ in honest majority (i.e., $\varepsilon >1/2$). In IC, $n$ processes must agree on a vector that maps every honest process to its input of size $L_{in}$, despite up to $t$ dishonest (Byzantine) processes that may collude and behave arbitrarily. IC is the strongest one-shot distributed task: by fully determining the honest input configuration, it subsumes every other solvable one-shot task in the same model. Moreover, most multiparty computation protocols rely on IC as a building block. These guarantees are qualitatively optimal. First, Garay, Katz, Koo, and Ostrovsky (FOCS~2007) rule out constant-round protocols unless the honest fraction is constant. Second, Pease, Shostak, and Lamport (JACM~1980) rule out setup-free information-theoretic solutions once $n\leq 3t$. Thus, to overcome this barrier, we rely on cryptographic objects of size $\kappa$, obtaining correctness with all but negligible probability in $\kappa$ against any adversary running in time polynomial in $\kappa$. This includes digital signatures, for which the corresponding public keys must be published on a bulletin-board public key infrastructure before the protocol begins. Third, IC trivially requires \(\Omega(n^2L_{in})\) communication, since every honest process must learn the inputs of all honest processes. Our results follow from a single generic compiler that transforms any constant-expected-latency Byzantine Broadcast protocol into an IC protocol with the same latency profile.