Detectable byzantine agreement secure against faulty majorities

Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein, Adam Smith

Research output: Contribution to conferencePaperpeer-review

49 Scopus citations


It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty ("honest"), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively. These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants - using neither a trusted party nor broadcast channels. Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a "detectable Firing Squad" protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.

Original languageEnglish (US)
Number of pages9
StatePublished - 2002
EventProceedings of the Twenty - First Annual ACM Symposium on Principles of Distributed Computing PODC 2002 - Monterey, CA, United States
Duration: Jul 21 2002Jul 24 2002


OtherProceedings of the Twenty - First Annual ACM Symposium on Principles of Distributed Computing PODC 2002
Country/TerritoryUnited States
CityMonterey, CA

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Detectable byzantine agreement secure against faulty majorities'. Together they form a unique fingerprint.

Cite this