Asynchronous Consensus without Trusted Setup or Public-Key Cryptography
Open Access
- 2 December 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 3242-3256
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(κn3) 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.Keywords
Funding Information
- Beijing Natural Science Foundation (M23015)
- National Science Foundation (2240976)
This publication has 38 references indexed in Scilit:
- Practical Asynchronous Distributed Key Generation2022
- Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with $t<n/3$ t < n / 3 , $O(n^2)$ O ( n 2 ) messages, and constant timeActa Informatica, 2016
- Constant-Size Commitments to Polynomials and Their Applications2010
- Asynchronous Veri.able Information Dispersal2006
- Short Signatures from the Weil PairingJournal of Cryptology, 2004
- Asynchronous secure computations with optimal resilience (extended abstract)1994
- Asynchronous secure computation1993
- Fast asynchronous Byzantine agreement with optimal resilience1993
- Asynchronous Byzantine agreement protocolsInformation and Computation, 1987
- Randomized byzantine generals1983