Paper 2024/1794 Original: eprint.iacr.org/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.
- History
- 2025-01-05: last updated
- 2024-11-02: published
- Short URL
- https://ia.cr/2024/1794
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}