Efficient Asynchronous Byzantine Agreement without Private Setups

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


Efficient asynchronous Byzantine agreement (BA) protocols were mostly studied with private setups, e.g., pre-setup threshold cryptosystem. Challenges remain to reduce the large communication in the absence of such setups. Recently, Abraham et al. (PODC'21) presented the first asynchronous validated BA (VBA) with expected O(n3) messages and O (1) rounds, relying on only public key infrastructure (PKI) setup, but the design still costs O (λn3 logn) bits. Here n is the number of parties, and λ is a cryptographic security parameter.In this paper, we reduce the communication of private-setup free asynchronous BA to expected O(λn3) bits. At the core of our design, we give a systematic treatment of common randomness protocols in the asynchronous network, and proceed as:•We give an efficient reasonably fair common coin protocol in the asynchronous setting with only PKI setup. It costs only O (λn3) bit and O(1) 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 O(λn3) bits and O(1) rounds.•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 O(λn3) 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 O(λn3) bits while preserving fast termination in expected 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 (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 that is friendly for dynamic participation and reconfiguration.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 42nd International Conference on Distributed Computing Systems, ICDCS 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9781665471770
StatePublished - 2022
Externally publishedYes
Event42nd IEEE International Conference on Distributed Computing Systems, ICDCS 2022 - Bologna, Italy
Duration: Jul 10 2022Jul 13 2022

Publication series

NameProceedings - International Conference on Distributed Computing Systems


Conference42nd IEEE International Conference on Distributed Computing Systems, ICDCS 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


  • Byzantine agreement
  • asynchronous protocols
  • coin tossing
  • common randomness
  • random leader election


Dive into the research topics of 'Efficient Asynchronous Byzantine Agreement without Private Setups'. Together they form a unique fingerprint.

Cite this