Paper 2022/805

Authenticated Consensus in Synchronous Systems with Mixed Faults

Ittai Abraham
Danny Dolev, Hebrew University of Jerusalem
Alon Kagan, Hebrew University of Jerusalem
Gilad Stern, Hebrew University of Jerusalem
Abstract

Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if $n>2f$ for $f$ Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if $n>3f+2k$ for $f$ Byzantine faults and $k$ crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to $f$ Byzantine faults and $k$ crash faults if $n>2f+k$. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that $n>2f+k$ is optimally resilient for consensus and state machine replication protocols.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
consensus state machine replication mixed faults synchrony lower bounds
Contact author(s)
iabraham @ vmware com
danny dolev @ mail huji ac il
alon kagan @ mail huji ac il
gilad stern @ mail huji ac il
History
2022-06-23: approved
2022-06-21: received
See all versions
Short URL
https://ia.cr/2022/805
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/805,
      author = {Ittai Abraham and Danny Dolev and Alon Kagan and Gilad Stern},
      title = {Authenticated Consensus in Synchronous Systems with Mixed Faults},
      howpublished = {Cryptology ePrint Archive, Paper 2022/805},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/805}},
      url = {https://eprint.iacr.org/2022/805}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.