Paper 2025/143

A New Way to Achieve Round-Efficient Asynchronous Byzantine Agreement

Abstract

We translate the \emph{expand-and-extract} framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting. While they use it to obtain a synchronous BA with $2^{-\lambda}$ error probability in $\lambda+1$ rounds, we make it work in asynchrony in $\lambda+3$ rounds. At the heart of their solution is a \emph{proxcensus} primitive, which is used to reach graded agreement with $2^r+1$ grades in $r$ rounds by reducing proxcensus with $2s-1$ grades to proxcensus with $s$ grades in one round. The \emph{expand-and-extract} paradigm uses proxcensus to \emph{expand} binary inputs to $2^\lambda+1$ grades in $\lambda$ rounds before \emph{extracting} a binary output by partitioning the grades using a $\lambda$ bit common coin. However, the proxcensus protocol by Fitzi et al. does not translate to the asynchronous setting without lowering the corruption threshold or using more rounds in each recursive step. We solve this by attaching \emph{justifiers} to all messages: forcing the adversary to choose between being ignored by the honest parties, or sending messages with certain validity properties. Using these we define validated proxcensus and show that it can be instantiated in asynchrony with the same recursive structure and round complexity as synchronous proxcensus. In asynchrony the extraction phase incurs a security loss of one bit which is recovered by expanding to twice as many grades using an extra round of communication. This results in a $\lambda+2$ round and a $\lambda+3$ round BA, both with $2^{-\lambda}$ error probability and communication complexity matching Fitzi et al.