Abstract
We propose a novel two-tiered overlay network design called plateau. It has two levels: a small upper-level that regulates entry of new nodes into the network, and a lower-level comprising all nodes. The lower level is a well-connected expander that is ideal for building peer-to-peer distributed trust applications. It is designed to be secure despite the presence of adversarial Byzantine nodes and resilient to large amounts of churn. The good nodes only need to communicate with their neighbors in the network, thus making plateau fully distributed. Membership in the network must be earned through proof-of-work that is verified by the upper-level nodes. Plateau is robust despite heavy churn controlled by an adversary, i.e., up to \( C = {\text {poly}}(n)\) number of nodes can join and leave the network per round without disrupting the network structure; n is the total number of good nodes in the network. As long as the compute power controlled by the Byzantine adversary is bounded, the number of Byzantine nodes in the network is kept in check and, more importantly, they will not be able to disrupt the structure or functioning of the overlay network. Additionally, we show that all resources needed to operate this network is bounded polylogarithmically with respect to n.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We say that an event E holds with high probability (whp) if \({\text {Prob}}[E] \ge 1 - 1/n^\eta \) for any fixed parameter \(\eta \) that is independent of n, but may depend on constants used in the algorithm.
- 2.
We use the term whiteboard to abstract out the ability to expose information about the network to the world. This is a crucial requirement for any network to handle churn. Otherwise, new nodes will not know where to connect. In current cryptocurrency systems like Bitcoin, we have specialized servers called seeders that provide this service [8]. Other alternatives include using the blockchain itself to expose this information [1]. The main design issue is to ensure that the whiteboard only needs to store a bounded amount of information and that updates to the whiteboard are not too fast.
- 3.
Our design is sufficiently robust to admit variation between the number of nodes joining and leaving as long as the total number of good nodes stays bounded within some reasonable \(\varTheta (n)\).
- 4.
This is a simplifying assumption. We can also model the compute power required to solve a puzzle as an exponential random variable.
References
Aradhya, V., Gilbert, S., Hobor, A.: OverChain: building a robust overlay with a blockchain (2022). https://arxiv.org/abs/2201.12809
Augustine, J., Chatterjee, S., Pandurangan, G.: A fully-distributed scalable peer-to-peer protocol for Byzantine-resilient distributed hash tables. In: SPAA, pp. 87–98 (2022)
Augustine, J., Pandurangan, G., Robinson, P., Roche, S.T., Upfal, E.: Enabling robust and efficient distributed computation in dynamic peer-to-peer networks. In: FOCS (2015)
Augustine, J., Sivasubramaniam, S.: Spartan: a framework for sparse robust addressable networks. In: 2018 International Parallel and Distributed Processing Symposium (IPDPS), pp. 1060–1069 (2018)
Awerbuch, B., Scheideler, C.: The hyperring: a low-congestion deterministic data structure for distributed environments. In: SODA (2004)
Awerbuch, B., Scheideler, C.: Towards a scalable and robust DHT. Theory Comput. Syst. 45(2), 234–260 (2009)
Bagchi, A., Bhargava, A., Chaudhary, A., Eppstein, D., Scheideler, C.: The effect of faults on network expansion. Theory Comput. Syst. 39(6), 903–928 (2006)
Bitcoin P2P network official documentation. https://developer.bitcoin.org/devguide/p2p_network.html. Accessed 25 Apr 2022
Bortnikov, E., Gurevich, M., Keidar, I., Kliot, G., Shraer, A.: Brahms: Byzantine resilient random membership sampling. Comput. Netw. 53(13), 2340–2359 (2009)
Croman, K., et al.: On scaling decentralized blockchains. In: Clark, J., Meiklejohn, S., Ryan, P.Y.A., Wallach, D., Brenner, M., Rohloff, K. (eds.) FC 2016. LNCS, vol. 9604, pp. 106–125. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53357-4_8
Drees, M., Gmyr, R., Scheideler, C.: Churn-and DoS-resistant overlay networks based on network reconfiguration. In: SPAA 2016, pp. 417–427. ACM (2016)
Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM J. Comput. 26(4), 873–933 (1997)
Fiat, A., Saia, J.: Censorship resistant peer-to-peer networks. Theory Comput. 3(1), 1–23 (2007). https://doi.org/10.4086/toc.2007.v003a001. https://www.theoryofcomputing.org/articles/v003a001
Gkantsidis, C., Mihail, M., Saberi, A.: Random walks in peer-to-peer networks: algorithms and evaluation. Perform. Eval. 63(3), 241–263 (2006). P2P Computing Systems
Guerraoui, R., Huc, F., Kermarrec, A.M.: Highly dynamic distributed computing with Byzantine failures. In: PODC 2013 (2013)
Gupta, D., Saia, J., Young, M.: Resource burning for permissionless systems (invited paper). In: Richa, A.W., Scheideler, C. (eds.) SIROCCO 2020. LNCS, vol. 12156, pp. 19–44. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-54921-3_2
Gupta, D., Saia, J., Young, M.: Bankrupting sybil despite churn. In: ICDCS, pp. 425–437 (2021)
Heilman, E., Kendler, A., Zohar, A., Goldberg, S.: Eclipse attacks on bitcoin’s peer-to-peer network. In: 24th USENIX Security Symposium (USENIX Security 2015) (2015)
Imtiaz, M.A., Starobinski, D., Trachtenberg, A., Younis, N.: Churn in the bitcoin network: characterization and impact. In: 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pp. 431–439 (2019)
Jacob, R., Richa, A., Scheideler, C., Schmid, S., Täubig, H.: SKIP+: a self-stabilizing skip graph. J. ACM 61(6), 36:1–36:26 (2014)
Jacobs, T., Pandurangan, G.: Stochastic analysis of a churn-tolerant structured peer-to-peer scheme. Peer-to-Peer Netw. Appl. 6(1) (2013)
Jesi, G.P., Montresor, A., van Steen, M.: Secure peer sampling. Comput. Netw. 54(12), 2086–2098 (2010)
Johansen, H.D., Renesse, R.V., Vigfusson, Y., Johansen, D.: Fireflies: a secure and scalable membership and gossip service. ACM Trans. Comput. Syst. 33(2) (2015)
Kuhn, F., Schmid, S., Wattenhofer, R.: Towards worst-case churn resistant peer-to-peer systems. Distrib. Comput. 22(4), 249–267 (2010)
Law, C., Siu, K.Y.: Distributed construction of random expander networks. In: IEEE INFOCOM 2003, vol. 3, pp. 2133–2143 (2003)
Mahlmann, P., Schindelhauer, C.: Peer-to-peer networks based on random transformations of connected regular undirected graphs. In: SPAA, pp. 155–164 (2005)
Mao, Y., Deb, S., Venkatakrishnan, S.B., Kannan, S., Srinivasan, K.: Perigee: efficient peer-to-peer network design for blockchains. In: PODC 2020, pp. 428–437 (2020)
Micali, S., Rabin, T.: Collective coin tossing without assumptions nor broadcasting. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 253–266. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_18
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2009)
Neudecker, T.: Characterization of the bitcoin peer-to-peer network (2015–2018). Technical report. 1, Karlsruher Institut für Technologie (KIT) (2019)
Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter peer-to-peer networks. IEEE J. Sel. Areas Commun. 21(6), 995–1002 (2003)
Pandurangan, G., Robinson, P., Trehan, A.: DEX: self-healing expanders. Distrib. Comput. 29(3), 163–185 (2016)
Pandurangan, G., Trehan, A.: Xheal: a localized self-healing algorithm using expanders. Distrib. Comput. 27(1), 39–54 (2014)
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. Comput. Commun. Rev. 31(4), 161–172 (2001)
Rowstron, A., Druschel, P.: Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Guerraoui, R. (ed.) Middleware 2001. LNCS, vol. 2218, pp. 329–350. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45518-3_18
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. Comput. Commun. Rev. 31(4), 149–160 (2001)
Stutzbach, D., Rejaie, R.: Understanding churn in peer-to-peer networks. In: SIGCOMM, New York, NY, USA (2006)
Vadhan, S.P.: Pseudorandomness. Found. Trends® Theor. Comput. Sci. 7(1–3), 1–336 (2012)
Zhao, B.Y., Kubiatowicz, J., Joseph, A.D.: Tapestry: a fault-tolerant wide-area application infrastructure. Comput. Commun. Rev. 32(1), 81 (2002)
Acknowledgements
We thank Seth Gilbert and Aquinas Hobor for preliminary discussions in which they suggested the idea of using a whiteboard to facilitate new nodes joining the network. The first author was supported in part by Extra-Mural Research Grant (file number EMR/2016/003016) and MATRICS grant (file number MTR/2018/001198). He is currently supported by the potential Centre of Excellence in Cryptography Cybersecurity and Distributed Trust (CCD) under the IIT Madras Institute of Eminence scheme. The third author worked on this project as an intern at IIT Madras supported by an Information Security Education and Awareness (https://isea.gov.in/) Phase II project (CCECEP22VK &CPCSE1415).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Augustine, J., Bhat, W.G., Nair, S. (2022). 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. SSS 2022. Lecture Notes in Computer Science, vol 13751. Springer, Cham. https://doi.org/10.1007/978-3-031-21017-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-21017-4_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21016-7
Online ISBN: 978-3-031-21017-4
eBook Packages: Computer ScienceComputer Science (R0)