Paper 2024/774

Byzantine Reliable Broadcast with One Trusted Monotonic Counter

Yackolley Amoussou-Guenou, Université Paris-Panthéon-Assas
Lionel Beltrando, Sorbonne University, LIP6
Maurice Herlihy, Brown University
Maria Potop-Butucaru, LIP6, Sorbonne University
Abstract

Byzantine Reliable Broadcast is one of the most popular communication primitives in distributed systems. Byzantine reliable broadcast ensures that processes agree to deliver a message from an initiator even if some processes (perhaps including the initiator) are Byzantine. In asynchronous settings it is known since the prominent work of Bracha [Bracha87] that Byzantine reliable broadcast can be implemented deterministically if $n \geq 3t+1$ where $t$ is an upper bound on the number of Byzantine processes. Here, we study Byzantine Reliable Broadcast when processes are equipped with trusted execution environments (TEEs), special software or hardware designed to prevent equivocation. Our contribution is twofold. First, we show that, despite common belief, when each process is equipped with a TEE, Bracha's algorithm still needs $n \geq 3t+1$. Second, we present a novel algorithm that uses a single TEE (at the initiator) that implements Byzantine Reliable Asynchronous Broadcast with $n \geq 2t+1$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
TEEsByzantine Reliable Broadcast
Contact author(s)
Yackolley Amoussou-Guenou @ u-paris2 fr
lionel beltrando @ lip6 fr
maurice herlihy @ gmail com
maria potop-butucaru @ lip6 fr
History
2024-05-24: approved
2024-05-20: received
See all versions
Short URL
https://ia.cr/2024/774
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/774,
      author = {Yackolley Amoussou-Guenou and Lionel Beltrando and Maurice Herlihy and Maria Potop-Butucaru},
      title = {Byzantine Reliable Broadcast with One Trusted Monotonic Counter},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/774},
      year = {2024},
      url = {https://eprint.iacr.org/2024/774}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.