Paper 2023/038
On the Amortized Communication Complexity of Byzantine Broadcast
Abstract
Designing an efficient solution for Byzantine broadcast is an important problem for many distributed computing and cryptographic tasks. There have been many attempts to achieve sub-quadratic communication complexity in several directions, both in theory and practice, all with pros and cons. This paper initiates the study of another attempt: improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We present a protocol that achieves optimal amortized linear complexity under an honest majority. Our core technique is to efficiently form a network for disseminating the sender's message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- ConsensusByzantineBlockchain
- Contact author(s)
-
atsuki momose @ gmail com
renling @ illinois edu
runting @ gmail com
junwan @ mit edu
xiangzhuolun @ gmail com - History
- 2023-01-19: approved
- 2023-01-11: received
- See all versions
- Short URL
- https://ia.cr/2023/038
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/038,
author = {Atsuki Momose and Ling Ren and Elaine Shi and Jun Wan and Zhuolun Xiang},
title = {On the Amortized Communication Complexity of Byzantine Broadcast},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/038},
year = {2023},
url = {https://eprint.iacr.org/2023/038}
}
