Paper 2024/677

Asynchronous Consensus without Trusted Setup or Public-Key Cryptography

Sourav Das, University of Illinois Urbana-Champaign
Sisi Duan, Tsinghua University
Shengqi Liu, Southern University of Science and Technology
Atsuki Momose, University of Illinois Urbana-Champaign
Ling Ren, University of Illinois Urbana-Champaign
Victor Shoup, Offchain Labs

Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on cryptographic hash functions modeled as a random oracle. Our protocol has $O(\kappa n^3)$ total communication and runs in expected $O(1)$ rounds. The fact that we use only cryptographic hash functions also means that our protocol is post-quantum secure. The minimal use of cryptography and the small number of rounds make our protocol practical. We implement our protocol and evaluate it in a geo-distributed setting with up to 128 machines. Our experimental evaluation shows that our protocol is more efficient than the only other setup-free consensus protocol that has been implemented to date. En route to our asynchronous consensus protocols, we also introduce new primitives called asynchronous secret key sharing and cover gather, which may be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2024
ConsensusAsynchronyAsynchronous Common Subset
Contact author(s)
souravd2 @ illinois edu
duansisi @ mail tsinghua edu cn
shengqi @ illinois edu
atsuki momose @ gmail com
renling @ illinois edu
victor @ shoup net
2024-06-30: revised
2024-05-03: received
See all versions
Short URL
No rights reserved


      author = {Sourav Das and Sisi Duan and Shengqi Liu and Atsuki Momose and Ling Ren and Victor Shoup},
      title = {Asynchronous Consensus without Trusted Setup or Public-Key Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2024/677},
      year = {2024},
      doi = {10.1145/3658644.3670327},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.