# Asynchronous Consensus without Trusted Setup or Public-Key Cryptography

Source: https://eprint.iacr.org/2024/677

## Summary

The paper presents an asynchronous Byzantine consensus protocol, an Asynchronous Common Subset (ACS) protocol, that avoids both a trusted setup and public-key cryptography such as digital signatures. Its security rests only on cryptographic hash functions modeled as a random oracle, giving O(κn³) total communication and expected O(1) rounds. The authors state that this minimal use of cryptography makes the protocol post-quantum secure and practical. In an implementation tested in a geo-distributed setting with up to 128 machines, it outperformed the only other implemented setup-free consensus protocol.

## Article

Paper 2024/677

Asynchronous Consensus without Trusted Setup or Public-Key Cryptography

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

Abstract

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.

BibTeX

@misc{cryptoeprint:2024/677, 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}, url = {https://eprint.iacr.org/2024/677} }