Basalt: A Rock-Solid Byzantine-Tolerant Peer Sampling for Very Large Decentralized Networks
Authors: 
Alex Auvolat, Yérom-David Bromberg, Davide Frey, Djob Mvondo, François TaïaniAuthors Info & Claims
Alex Auvolat, Yérom-David Bromberg, Davide Frey, Djob Mvondo, François TaïaniAuthors Info & ClaimsPages 111 - 123
Abstract
Recent large-scale Byzantine-Fault-Tolerant (BFT) algorithms provide scalability at a low cost by exploiting a secure Random Peer Sampling (RPS) service: a service that provides a stream of random network nodes where no attacking entity can become over-represented. Unfortunately, producing good peer samples untainted by Byzantine behavior in a large-scale network is particularly difficult, with existing solutions unable to withstand aggressive attacks. In this paper, we propose a novel RPS algorithm, BASALT, that implements what we have termed a stubborn chaotic search over node IDs to counter attackers' attempts at becoming over-represented. Our evaluation based on a theoretical analysis, Monte Carlo simulations, and experiments on a live cryptocurrency network shows that BASALT delivers close-to-optimal protection against malicious behaviors and outperforms state-of-the-art solutions by a wide margin.
References
[1]
2020. AVA Labs, Build the Internet of Finance. https://www.avalabs.org/. Accessed: 2020-07-21.
[2]
2020. Ethereum.org. https://www.ethereum.org/. Accessed: 2020-02-20.
[3]
2020. Gecko, Official Go implementation of an AVA node. https://github.com/ava-labs/avalanchego. Accessed: 2020-07-21.
[4]
2022. Network Protocol. https://docs.avax.network/specs/network-protocol Accessed February 2023.
[5]
André Allavena, Alan Demers, and John E. Hopcroft. 2005. Correctness of a Gossip Based Membership Protocol. In ACM Symposium on Principles of distributed computing (PODC). 292--301.
[6]
Emmanuelle Anceaume, Yann Busnel, and Sébastien Gambs. 2013. On the Power of the Adversary to Solve the Node Sampling Problem. Trans. Large Scale Data Knowl. Centered Syst. 11 (2013), 102--126.
[7]
Emmanuelle Anceaume, Yann Busnel, and Bruno Sericola. 2013. Uniform node sampling service robust against collusions of malicious nodes. In IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 1--12.
[8]
Maria. Apostolaki, Marti Gian, Müller Jan, and Vanbever Laurent. 2019. SABRE: Protecting Bitcoin against Routing Attacks. In Network and Distributed System Security Symposium (NDSS). 1--15.
[9]
Maria Apostolaki, Aviv Zohar, and Laurent Vanbever. 2017. Hijacking Bitcoin: Routing Attacks on Cryptocurrencies. In IEEE Symposium on Security and Privacy (S&P).
[10]
Sarah Azouvi, Christian Cachin, Duc V Le, Marko Vukolic, and Luca Zanolini. 2022. Modeling Resources in Permissionless Longest-chain Total-order Broadcast. In Conference on Principles of Distributed Systems (OPODIS).
[11]
Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot, and Alexander Shraer. 2009. Brahms: Byzantine resilient random membership sampling. Computer Networks 53, 13 (2009), 2340--2359.
[12]
Amaury Bouchra Pilet, Davide Frey, and Francois Taiani. 2020. Foiling Sybils with HAPS in Permissionless Systems: An Address-based Peer Sampling Service. In IEEE Symposium on Computers and Communications (ISCC).
[13]
Andrei Z Broder, Moses Charikar, Alan M Frieze, and Michael Mitzenmacher. 1998. Min-wise independent permutations. In ACM Symposium on Theory of Computing (STOC). 327--336.
[14]
Graham Cormode and Shan Muthukrishnan. 2005. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms 55, 1 (2005), 58--75.
[15]
Victor Costan and Srinivas Devadas. 2016. Intel SGX Explained. Cryptology ePrint Archive, Paper 2016/086. https://eprint.iacr.org/2016/086 https://eprint.iacr.org/2016/086.
[16]
Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. 1987. Epidemic algorithms for replicated database maintenance. In ACM Symposium on Principles of distributed computing (PODC). 1--12.
[17]
Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017. Algorand: Scaling byzantine agreements for cryptocurrencies. In ACM Symposium on Operating Systems Principles (SOSP). 51--68.
[18]
Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič, and Dragos-Adrian Seredinschi. 2019. The consensus number of a cryptocurrency. In ACM Symposium on Principles of Distributed Computing (PODC). 307--316.
[19]
Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. 2019. Scalable Byzantine reliable broadcast. In International Symposium on Distributed Computing (DISC).
[20]
Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg. 2015. Eclipse attacks on bitcoin's peer-to-peer network. In USENIX Security Symposium (USENIX Security). 129--144.
[21]
Márk Jelasity, Spyros Voulgaris, Rachid Guerraoui, Anne-Marie Kermarrec, and Maarten van Steen. 2007. Gossip-based Peer Sampling. ACM Trans. Comput. Syst., Article 8 (2007).
[22]
Gian Paolo Jesi, Alberto Montresor, and Maarten van Steen. 2010. Secure peer sampling. Computer Networks 54, 12 (2010), 2086--2098.
[23]
A. Kermarrec, L. Massoulie, and A. J. Ganesh. 2003. Probabilistic reliable dissemination in large-scale systems. IEEE Transactions on Parallel and Distributed Systems 14, 3 (March 2003), 248--258.
[24]
Jon McLachlan, Andrew Tran, Nicholas Hopper, and Yongdae Kim. 2009. Scalable onion routing with torsk. In ACM conference on Computer and communications security (CCS). 590--599.
[25]
Silvio Micali, Michael Rabin, and Salil Vadhan. 1999. Verifiable random functions. In Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 120--130.
[26]
Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.
[27]
Satoshi Nakamoto. 2009. Bitcoin: A peer-to-peer electronic cash system. https://assets.pubpub.org/d8wct41f/31611263538139.pdf accessed February 2023.
[28]
Brice Nédelec, Julian Tanke, Davide Frey, Pascal Molli, and Achour Mostéfaoui. 2018. An adaptive peer-sampling protocol for building networks of browsers. World Wide Web 21, 3 (May 2018), 629--661.
[29]
M. Pigaglio, J. Bruneau-Queyreix, Y. Bromberg, D. Frey, E. Riviere, and L. Reveillere. 2022. RAPTEE: Leveraging trusted execution environments for Byzantine-tolerant peer sampling services. In IEEE 42nd International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, Los Alamitos, CA, USA, 603--613.
[30]
Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gün Sirer. 2019. Scalable and Probabilistic Leaderless BFT Consensus through Metastability. https://doi.org/10.48550/ARXIV.1906 08936
[31]
Atul Singh, Tsuen-Wan Ngan, Peter Druschel, and Dan S. Wallach. 2006. Eclipse Attacks on Overlay Networks: Threats and Defenses. In IEEE Internet Conference on Computer Communications (INFOCOM).
[32]
Guido Urdaneta, Guillaume Pierre, and Maarten Van Steen. 2011. A Survey of DHT Security Techniques. ACM Comput. Surv. 43, 2, Article 8 (Feb. 2011), 49 pages.
[33]
Spyros Voulgaris, Daniela Gavidia, and Maarten Van Steen. 2005. Cyclon: Inexpensive membership management for unstructured p2p overlays. Journal of Network and systems Management 13, 2 (2005), 197--217.
[34]
Spyros Voulgaris and Maarten van Steen. 2013. VICINITY: A Pinch of Randomness Brings out the Structure. In International Middleware Conference (Middleware), Vol. 8275. Springer, 21--40.
[35]
Spyros Voulgaris and Maarten van Steen. 2013. VICINITY: A Pinch of Randomness Brings out the Structure. In International Conference on Middleware (Middleware). 21--40.
[36]
Fan Zhang, Ittay Eyal, Robert Escriva, Ari Juels, and Robbert Van Renesse. 2017. REM: Resource-efficient mining for blockchains. In USENIX Security Symposium (USENIX Security). 1427--1444.
Index Terms
- Basalt: A Rock-Solid Byzantine-Tolerant Peer Sampling for Very Large Decentralized Networks
Recommendations
Secure Peer Sampling Service: The Mosquito Attack
WETICE '09: Proceedings of the 2009 18th IEEE International Workshops on Enabling Technologies: Infrastructures for Collaborative EnterprisesPeer sampling -- the capability of obtaining a random sample from a large population of peers -- is a basic building block for the gossip paradigm. Current peer sampling services have been designed for ''first-class'' citizens of the Internet: peers ...
Detection and mitigation of the eclipse attack in chord overlays
Distributed hash table-based overlays are widely used to support efficient information routing and storage in structured peer-to-peer networks, but they are also subject to numerous attacks aimed at disrupting their correct functioning. In this paper, ...
NAT-resilient Gossip Peer Sampling
ICDCS '09: Proceedings of the 2009 29th IEEE International Conference on Distributed Computing SystemsGossip peer sampling protocols now represent a solid basis to build and maintain peer to peer (p2p) overlay networks. They provide peers with a random sample of the network and maintain connectivity in highly dynamic settings. They rely on the ...
Comments
Information & Contributors
Information
Published In
November 2023
334 pages
ISBN:9798400701771
DOI:10.1145/3590140
Copyright © 2023 ACM.
Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Sponsors
In-Cooperation
- IFIP: International Federation for Information Processing
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 November 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- CominLabs
- Agence Nationale de la Recherche
- Région Bretagne
Conference
Middleware '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 203 of 948 submissions, 21%
Upcoming Conference
MIDDLEWARE '24
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 78Total Downloads
- Downloads (Last 12 months)78
- Downloads (Last 6 weeks)11
Reflects downloads up to 21 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in