What a lovely hat

Paper 2021/810

Efficient Asynchronous Byzantine Agreement without Private Setups

Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang

Abstract

Though recent breakthroughs greatly improved the efficiency of asynchronous Byzantine agreement (BA) protocols, they mainly focused on the setting with private setups, e.g., assuming established non-interactive threshold cryptosystems. Challenges remain to reduce the large communication complexities in the absence of such setups. For example, Abraham et al. (PODC'21) recently gave the first private-setup free construction for asynchronous validated BA (VBA) with expected $\mathcal{O}(n^3)$ messages and $\mathcal{O}(1)$ rounds, relying on only public key infrastructure (PKI), but the design still costs $\mathcal{O}(\lambda n^3 \log n)$ bits. Here $n$ is the number of parties, and $\lambda$ means the cryptographic security parameter capturing the length of hash, digital signature, etc. We reduce the communication of private-setup free asynchronous BA to expected $\mathcal{O}(\lambda n^3)$ bits. At the core of our design, we present a systematic treatment of reasonably fair common randomness protocols in the asynchronous network, and proceed as: (i) We give an efficient reasonably fair common coin protocol in the asynchronous setting with only PKI setup. It costs only $\mathcal{O}(\lambda n^3)$ bit and $\mathcal{O}(1)$ asynchronous rounds, and ensures that with at least $1/3$ probability, all honest parties can output a common bit that is as if randomly flipped. This directly renders more efficient private-setup free asynchronous binary agreement (ABA) with expected $\mathcal{O}(\lambda n^3)$ bits and expected constant rounds. (ii) Then, we lift our common coin to attain perfect agreement by using a single ABA. This gives us a reasonably fair random leader election protocol with expected $\mathcal{O}(\lambda n^3)$ communication and expected constant rounds. It is pluggable in all existing VBA protocols (e.g., Cachin et al., CRYPTO'01; Abraham et al., PODC'19; Lu et al., PODC'20) to remove the needed private setup or distributed key generation (DKG). As such, the communication of private-setup free VBA is reduced to expected $\mathcal{O}(\lambda n^3)$ bits while preserving fast termination in expected $\mathcal{O}(1)$ rounds. Moreover, our result paves a generic path to private-setup free asynchronous BA protocols, as it is not restricted to merely improve Abraham et al.'s specific VBA protocol in PODC'21. Our results and techniques could be found useful and interesting for a broad array of applications such as asynchronous DKG and DKG-free asynchronous random beacon.