Paper 2023/954

Zombies and Ghosts: Optimal Byzantine Agreement in the Presence of Omission Faults

Julian Loss, CISPA Helmholtz Center for Information Security
Gilad Stern, The Hebrew University of Jerusalem
Abstract

Studying the feasibility of Byzantine Agreement (BA) in realistic fault models is an important question in the area of distributed computing and cryptography. In this work, we revisit the mixed fault model with Byzantine (malicious) faults and omission faults put forth by Hauser, Maurer, and Zikas (TCC 2009), who showed that BA (and MPC) is possible with $t$ Byzantine faults, $s$ send faults (whose outgoing messages may be dropped) and $r$ receive faults (whose incoming messages may be lost) if $n>3t+r+s$. We generalize their techniques and results by showing that BA is possible if $n>2t+r+s$, given the availability of a cryptographic setup. Our protocol is the first to match the recent lower bound of Eldefrawy, Loss, and Terner (ACNS 2022) for this setting.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
consensusmixed faultsByzantine faultsomission faultssynchronous protocols
Contact author(s)
loss @ cispa de
gilad stern @ mail huji ac il
History
2024-02-19: revised
2023-06-18: received
See all versions
Short URL
https://ia.cr/2023/954
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/954,
      author = {Julian Loss and Gilad Stern},
      title = {Zombies and Ghosts: Optimal Byzantine Agreement in the Presence of Omission Faults},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/954},
      year = {2023},
      url = {https://eprint.iacr.org/2023/954}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.