Document Open Access Logo

New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

Authors Ittai Abraham, Gilad Stern

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.16.pdf
  • Filesize: 0.65 MB
  • 18 pages

Document Identifiers

Author Details

Ittai Abraham
  • VMWare Research, Herzliya, Israel
Gilad Stern
  • The Hebrew University of Jerusalem, Israel

Funding

  • Stern, Gilad: This work was supported by the HUJI Federmann Cyber Security Research Center in conjunction with the Israel National Cyber Directorate (INCD) in the Prime Minister’s Office.

Cite AsGet BibTex

Ittai Abraham and Gilad Stern. New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.OPODIS.2022.16

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • consensus
  • crusader broadcast
  • Byzantine fault tolerance
  • blockchain
  • synchrony
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ittai Abraham, TH Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 317-326, 2019. Google Scholar
  2. Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Validated asynchronous byzantine agreement with optimal resilience and asymptotically optimal time and word communication, 2018. URL: https://doi.org/10.48550/arXiv.1811.01332.
  3. Ittai Abraham and Kartik Nayak. The dolev and reischuk lower bound: Does agreement need quadratic messages? https://decentralizedthoughts.github.io/2019-08-16-byzantine-agreement-needs-quadratic-messages/, 2019.
  4. Lear Bahack. Theoretical bitcoin attacks with less than half of the computational power (draft), 2013. URL: https://doi.org/10.48550/arXiv.1312.7013.
  5. Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. arXiv preprint, 2017. URL: http://arxiv.org/abs/1710.09437.
  6. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference, pages 524-541. Springer, 2001. Google Scholar
  7. Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pages 1-12, 1987. Google Scholar
  8. Danny Dolev. The byzantine generals strike again. Journal of algorithms, 3(1):14-30, 1982. Google Scholar
  9. Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. Journal of the ACM (JACM), 32(1):191-204, 1985. Google Scholar
  10. C Dwork, D Peleg, N Pippenger, and E Upfal. Fault tolerance in networks of bounded degree. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC '86, pages 370-379, New York, NY, USA, 1986. Association for Computing Machinery. URL: https://doi.org/10.1145/12130.12169.
  11. Ittay Eyal and Emin Gun Sirer. Majority is not enough: Bitcoin mining is vulnerable, 2013. URL: https://doi.org/10.48550/arXiv.1311.0243.
  12. Michael J Fischer, Nancy A Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26-39, 1986. Google Scholar
  13. Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Annual international conference on the theory and applications of cryptographic techniques, pages 281-310. Springer, 2015. Google Scholar
  14. Vassos Hadzilacos and Joseph Y Halpern. Message-optimal protocols for byzantine agreement. In Proceedings of the tenth annual ACM symposium on Principles of distributed computing, pages 309-323, 1991. Google Scholar
  15. Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg. Eclipse attacks on bitcoin’s peer-to-peer network. In 24th USENIX Security Symposium (USENIX Security 15), pages 129-144, 2015. Google Scholar
  16. R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 565-574, 2000. Google Scholar
  17. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. In SODA '06, 2006. Google Scholar
  18. Joshua A Kroll, Ian C Davey, and Edward W Felten. The economics of bitcoin mining, or bitcoin in the presence of adversaries. In Proceedings of WEIS. Washington, DC, 2013. Google Scholar
  19. Yuval Marcus, Ethan Heilman, and Sharon Goldberg. Low-resource eclipse attacks on ethereum’s peer-to-peer network. Cryptology ePrint Archive, 2018. Google Scholar
  20. Atsuki Momose and Ling Ren. Optimal communication complexity of authenticated byzantine agreement. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 32:1-32:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.32.
  21. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review, page 21260, 2008. Google Scholar
  22. Boris Pittel. On spreading a rumor. SIAM Journal on Applied Mathematics, 47(1):213-223, 1987. Google Scholar
  23. Peter Robinson, Christian Scheideler, and Alexander Setzer. Breaking the ̃ω(√n) barrier: Fast consensus under a late adversary. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA '18, pages 173-182, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3210377.3210399.
  24. Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1-32, 2014. Google Scholar
  25. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. Hotstuff: BFT consensus with linearity and responsiveness. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 347-356. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331591.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact