Paper 2022/730

New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

Ittai Abraham, VMWare Research
Gilad Stern, Hebrew University of Jerusalem

In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks (even against omission faults) requires at least a quadratic number of messages to be sent by nonfaulty parties. In contrast, many blockchain systems achieve consensus with seemingly linear communication per instance against Byzantine faults. We explore this dissonance in three main ways. First, we extend the Dolev-Reischuk family of lower bounds and prove a new lower bound for Crusader Broadcast protocols. Our lower bound for crusader broadcast requires non-trivial extensions and a much stronger Byzantine adversary with the ability to simulate honest parties. Secondly, we extend our lower bounds to all-but-$m$ Crusader Broadcast, in which up to $m$ parties are allowed to output a different value. Finally, we discuss the ways in which these lower bounds relate to the security of blockchain systems. We show how Eclipse-style attacks in such systems can be viewed as specific instances of the attacks used in our lower bound for Crusader Broadcast. This connection suggests a more systematic way of analyzing and reasoning about Eclipse-style attacks through the lens of the Dolev-Reischuk family of attacks.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. OPODIS 2022
Byzantine Agreement Crusader Agreement lower bounds eclipse attacks blockchain protocols
Contact author(s)
iabraham @ vmware com
gilad stern @ mail huji ac il
2022-11-08: revised
2022-06-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ittai Abraham and Gilad Stern},
      title = {New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2022/730},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.