Paper 2024/1794
How Much Public Randomness Do Modern Consensus Protocols Need?
Abstract
Modern blockchain-based consensus protocols aim for efficiency (i.e., low communication and round complexity) while maintaining security against adaptive adversaries. These goals are usually achieved using a public randomness beacon to select roles for each participant. We examine to what extent this randomness is necessary. Specifically, we provide tight bounds on the amount of entropy a Byzantine Agreement protocol must consume from a beacon in order to enjoy efficiency and adaptive security. We first establish that no consensus protocol can simultaneously be efficient, be adaptively secure, and use $O(\log n)$ bits of beacon entropy. We then show this bound is tight and, in fact, a trilemma by presenting three consensus protocols that achieve any two of these three properties.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- consensusblockchainrandomness beacon
- Contact author(s)
-
jbonneau @ gmail com
bb @ nyu edu
mchrist @ cs columbia edu
ye2210 @ columbia edu - History
- 2024-11-04: approved
- 2024-11-02: received
- See all versions
- Short URL
- https://ia.cr/2024/1794
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1794,
author = {Joseph Bonneau and Benedikt Bünz and Miranda Christ and Yuval Efron},
title = {How Much Public Randomness Do Modern Consensus Protocols Need?},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1794},
year = {2024},
url = {https://eprint.iacr.org/2024/1794}
}
