License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2022.16
URN: urn:nbn:de:0030-drops-176368
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17636/
Go to the corresponding LIPIcs Volume Portal

Abraham, Ittai ; Stern, Gilad

New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

pdf-format:
LIPIcs-OPODIS-2022-16.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2022.16,
  author =	{Abraham, Ittai and Stern, Gilad},
  title =	{{New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17636},
  URN =		{urn:nbn:de:0030-drops-176368},
  doi =		{10.4230/LIPIcs.OPODIS.2022.16},
  annote =	{Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds}
}

Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds
Collection: 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Issue Date: 2023
Date of publication: 15.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI