[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Robust Overlays Meet Blockchains

On Handling High Churn and Catastrophic Failures

  • Conference paper
  • First Online:
Stabilization, Safety, and Security of Distributed Systems (SSS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14310))

Abstract

Blockchains have become ubiquitous in the world of robust decentralized applications. A crucial requirement for implementing a blockchain is a reliable “overlay network” providing robust communication among the participants. In this work, we provide communication-efficient and churn-optimal (barring log factors) Byzantine-resilient algorithms for maintaining blockchain networks. Our approach utilizes an interesting “cross-layer optimization” wherein the overlay network relies on the blockchain that is built on top of it. An important contribution is a tight “half-life” analysis on the amount of churn that can be tolerated, where peers have bandwidth restrictions. Moreover, by leveraging synergies between the blockchain and the overlay network, we can provide non-trivial recovery guarantees from unexpected catastrophic failures, which include a large class of connectivity issues such as denial-of-service, or exponentially unlikely lucky streaks for Byzantine peers, etc.

V. Aradhya and S. Gilbert acknowledge the support by Singapore MOE Tier 2 Grant MOE-T2EP20122-0014.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 55.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 69.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We consider a (large) subset of honest peers because the network can get split into multiple components during a catastrophic failure (cf. Sect. 6).

  2. 2.

    The interpretation of confirmed chain is typically blockchain-specific; for example, Bitcoin deems a block to be confirmed if it is at least 6 blocks deep.

References

  1. Aradhya, V., Gilbert, S., Hobor, A.: OverChain: building a robust overlay with a blockchain. arXiv preprint arXiv:2201.12809 (2022)

  2. Augustine, J., Bhat, W.G., Nair, S.: Plateau: a secure and scalable overlay network for large distributed trust applications. In: Devismes, S., Petit, F., Altisen, K., Di Luna, G.A., Fernandez Anta, A. (eds.) Stabilization, Safety, and Security of Distributed Systems. LNCS, vol. 13751, pp. 69–83. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-21017-4_5

    Chapter  Google Scholar 

  3. Augustine, J., Chatterjee, S., Pandurangan, G.: A fully-distributed scalable peer-to-peer protocol for byzantine-resilient distributed hash tables. In: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 87–98 (2022)

    Google Scholar 

  4. Awerbuch, B., Scheideler, C.: Group spreading: a protocol for provably secure distributed name service. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 183–195. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_18

    Chapter  Google Scholar 

  5. Awerbuch, B., Scheideler, C.: Towards a scalable and robust DHT. Theory Comput. Syst. 45(2), 234–260 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. BitInfoCharts: Bitcoin Explorer (2023). https://bitinfocharts.com/bitcoin/explorer/

  7. Blockchain.com: Explorer (2023). https://www.blockchain.com/explorer

  8. Datar, M.: Butterflies and peer-to-peer networks. In: Möhring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 310–322. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45749-6_30

    Chapter  Google Scholar 

  9. Dolev, D., Hoch, E.N., van Renesse, R.: Self-stabilizing and byzantine-tolerant overlay network. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) OPODIS 2007. LNCS, vol. 4878, pp. 343–357. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77096-1_25

    Chapter  Google Scholar 

  10. Eyal, I., Sirer, E.G.: Majority is not enough: bitcoin mining is vulnerable. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 436–454. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_28

    Chapter  Google Scholar 

  11. Fiat, A., Saia, J.: Censorship resistant peer-to-peer networks. Theory Comput. 3(1), 1–23 (2007). (previously appearing in SODA 2002)

    Google Scholar 

  12. Fiat, A., Saia, J., Young, M.: Making chord robust to byzantine attacks. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 803–814. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_71

    Chapter  Google Scholar 

  13. Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10

    Chapter  Google Scholar 

  14. Guerraoui, R., Huc, F., Kermarrec, A.M.: Highly dynamic distributed computing with byzantine failures. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 176–183 (2013)

    Google Scholar 

  15. Heilman, E., Kendler, A., Zohar, A., Goldberg, S.: Eclipse attacks on bitcoin’s peer-to-peer network. In: 24th USENIX Security Symposium, pp. 129–144 (2015)

    Google Scholar 

  16. Hildrum, K., Kubiatowicz, J.: Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 321–336. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39989-6_23

    Chapter  Google Scholar 

  17. Jaiyeola, M.O., Patron, K., Saia, J., Young, M., Zhou, Q.M.: Tiny groups tackle byzantine adversaries. In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1030–1039. IEEE (2018)

    Google Scholar 

  18. Johansen, H.D., Renesse, R.V., Vigfusson, Y., Johansen, D.: Fireflies: a secure and scalable membership and gossip service. ACM Trans. Comput. Syst. (TOCS) 33(2), 1–32 (2015)

    Article  Google Scholar 

  19. Liben-Nowell, D., Balakrishnan, H., Karger, D.: Analysis of the evolution of peer-to-peer systems. In: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, pp. 233–242 (2002)

    Google Scholar 

  20. Loe, A.F., Quaglia, E.A.: You shall not join: a measurement study of cryptocurrency peer-to-peer bootstrapping techniques. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 2231–2247 (2019)

    Google Scholar 

  21. Mao, Y., Deb, S., Venkatakrishnan, S.B., Kannan, S., Srinivasan, K.: Perigee: efficient peer-to-peer network design for blockchains. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 428–437 (2020)

    Google Scholar 

  22. Marcus, Y., Heilman, E., Goldberg, S.: Low-resource eclipse attacks on ethereum’s peer-to-peer network. Cryptology ePrint Archive, Report 2018/236 (2018)

    Google Scholar 

  23. Maymounkov, P., Mazières, D.: Kademlia: a peer-to-peer information system based on the XOR metric. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 53–65. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45748-8_5

    Chapter  MATH  Google Scholar 

  24. Mitzenmacher, M.: How useful is old information? IEEE Trans. Parallel Distrib. Syst. 11(1), 6–20 (2000)

    Article  Google Scholar 

  25. Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (White Paper) (2008). https://bitcoin.org/bitcoin.pdf

  26. Naor, M., Wieder, U.: A simple fault tolerant distributed hash table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, pp. 88–97. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45172-3_8

    Chapter  Google Scholar 

  27. Naor, M., Wieder, U.: Novel architectures for p2p applications: the continuous-discrete approach. ACM Trans. Algorithms (TALG) 3(3), 34-es (2007)

    Google Scholar 

  28. Nayak, K., Kumar, S., Miller, A., Shi, E.: Stubborn mining: generalizing selfish mining and combining with an eclipse attack. In: 2016 IEEE European Symposium on Security and Privacy (EuroS &P), pp. 305–320. IEEE (2016)

    Google Scholar 

  29. Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 643–673. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_22

    Chapter  MATH  Google Scholar 

  30. Pass, R., Shi, E.: Fruitchains: a fair blockchain. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 315–324 (2017)

    Google Scholar 

  31. Poon, J., Dryja, T.: The bitcoin lightning network: Scalable off-chain instant payments (2016). https://lightning.network/lightning-network-paper.pdf

  32. Rohrer, E., Tschorsch, F.: Kadcast: a structured approach to broadcast in blockchain networks. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pp. 199–213 (2019)

    Google Scholar 

  33. Saad, M., Anwar, A., Ravi, S., Mohaisen, D.: Revisiting nakamoto consensus in asynchronous networks: a comprehensive analysis of bitcoin safety and chainquality. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 988–1005 (2021)

    Google Scholar 

  34. Saad, M., Chen, S., Mohaisen, D.: Syncattack: double-spending in bitcoin without mining power. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 1668–1685 (2021)

    Google Scholar 

  35. Saia, J., Fiat, A., Gribble, S., Karlin, A.R., Saroiu, S.: Dynamically fault-tolerant content addressable networks. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 270–279. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45748-8_26

    Chapter  Google Scholar 

  36. Saroiu, S., Gummadi, P.K., Gribble, S.D.: Measurement study of peer-to-peer file sharing systems. In: Multimedia Computing and Networking 2002, vol. 4673, pp. 156–170. International Society for Optics and Photonics (2001)

    Google Scholar 

  37. Scheideler, C.: How to spread adversarial nodes? Rotate! In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 704–713 (2005)

    Google Scholar 

  38. Tennakoon, D., Gramoli, V.: Dynamic blockchain sharding. In: 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2022)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National University of Singapore, Singapore, Singapore

    Vijeth Aradhya, Seth Gilbert & Aquinas Hobor

  2. University College London, London, UK

    Aquinas Hobor

Authors
  1. Vijeth Aradhya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Seth Gilbert
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Aquinas Hobor
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vijeth Aradhya .

Editor information

Editors and Affiliations

  1. Ben-Gurion University of the Negev, Be'er-Sheva, Israel

    Shlomi Dolev

  2. New Jersey Institute of Technology, Newark, NJ, USA

    Baruch Schieber

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Aradhya, V., Gilbert, S., Hobor, A. (2023). Robust Overlays Meet Blockchains. In: Dolev, S., Schieber, B. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2023. Lecture Notes in Computer Science, vol 14310. Springer, Cham. https://doi.org/10.1007/978-3-031-44274-2_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-44274-2_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-44273-5

  • Online ISBN: 978-3-031-44274-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation