File(s) not publicly available

How Byzantine is a Send Corruption?

conference contribution
posted on 2023-11-29, 18:26 authored by Karim Eldefrawy, Julian LossJulian Loss, Ben Terner
Consensus protocols enable n parties, each holding some input string, to agree on a common output even in the presence of corrupted parties. Recent work has pushed to understand the problem when a majority of parties may be corrupted thus providing higher resilience, and under various forms of corruptions. Zikas, Hauser, and Maurer introduced a model in which receive-corrupt parties may not receive messages sent to them, and send-corrupt parties may have their sent messages dropped. Otherwise, receive-corrupt and send-corrupt parties behave honestly and their inputs and outputs are constrained by the security definitions. Zikas, Hauser, and Maurer gave a perfectly secure, linear-round protocol for n>trcv+tsnd+3tbyz , where trcv , tsnd , and tbyz represent thresholds on receive-, send-, and byzantine-corruptions. We present the first expected constant-round protocol in the general corruption model tolerating n>trcv+2tsnd+2tbyz . In comparison, all current sublinear round consensus protocols fail if there exists even a single party which cannot communicate with some honest parties, but whose output must be consistent with the honest parties. While presenting our protocol, we explore the pathology of send-corruptions and characterize the difficulty of dealing with them in sublinear-round protocols. As an illustrative and surprising example (even though not in sublinear rounds), we show that the classical Dolev-Strong broadcast protocol degrades from tolerating tbyztrcv+tsnd+2tbyz when we constrain the adversary to either drop all or none of a sender’s messages in a round (we denote this model by spotty send corruptions). To our knowledge, our protocol for the spotty send corruption model is thus the first sublinear-round consensus protocol for a majority of online faulty parties in any model. Because we are unable to prove optimality of our protocol’s corruption budget in the general case, we leave open the question of optimal corruption tolerance for both send-corruptions and byzantine-corruptions.


Preferred Citation

Karim Eldefrawy, Julian Loss and Ben Terner. How Byzantine is a Send Corruption?. In: International Conference on Applied Cryptography and Network Security (ACNS). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on Applied Cryptography and Network Security (ACNS)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3963, title = "How Byzantine is a Send Corruption?", author = "Eldefrawy, Karim and Loss, Julian and Terner, Ben", booktitle="{International Conference on Applied Cryptography and Network Security (ACNS)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager