### Authenticated Consensus in Synchronous Systems with Mixed Faults

##### 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. Currently, the only known synchronous protocol for consensus with a resilience of $n>2f+k$ is a binary consensus protocol. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated multivalued 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.

Available format(s)
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-09-05: revised
See all versions
Short URL
https://ia.cr/2022/805

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.