TL;DR
This paper introduces BASALT, a novel peer sampling service designed for large, open networks that aims to provide Byzantine fault tolerance without relying on costly Proof-of-Stake mechanisms. BASALT uses a "stubborn chaotic search" and hierarchical IP address ranking to ensure fair peer selection, making it resilient to Sybil attacks and enabling more open, cost-effective decentralized systems.
What Problem Does This Paper Address?
Decentralized systems, particularly those using blockchain technology, need to be Byzantine Fault Tolerant (BFT) to resist malicious actors. Epidemic BFT algorithms offer a promising path to scalability and efficiency, but they critically depend on a secure random peer sampling (RPS) service. This service must provide a stream of random network nodes where no single attacker can gain undue influence. Current solutions often use Proof-of-Stake (PoS) for security, which limits network openness by requiring participants to have significant stake, leading to an oligopoly. Furthermore, PoS creates a tight coupling between the consensus algorithm and the cryptocurrency itself. This paper addresses the need for a truly open, secure, and cost-effective RPS service that can support epidemic BFT algorithms without the limitations of PoS.
Methods
BASALT employs a three-pronged approach:
- Stubborn Chaotic Search: This is the core sampling mechanism. Nodes maintain a "view" of
vpeers. For each slot in their view, they use a random "seed" to define a ranking function. They then greedily exchange neighbor lists with other peers to find nodes that best match these ranking functions. This process is designed to make it difficult for attackers to manipulate the target graph. - Hit Counter Hardening Mechanism: To prevent intermediate views from being biased towards Byzantine nodes, a hit counter tracks how often a peer has appeared in incoming messages. Nodes prioritize contacting peers with lower hit counts, making it harder for malicious nodes to artificially inflate their presence.
- Hierarchical Ranking: To counter Sybil attacks, especially institutional ones where attackers control large IP address blocks, BASALT uses a hierarchical ranking function. This function considers IP address prefixes at different levels (e.g., /8, /16, /24) before looking at individual addresses. This biases sampling towards nodes in different subnets, making it prohibitively expensive for an attacker to control a significant fraction of the network's IP space.
Datasets
The paper uses data from the GeoLite2 ASN CSV Database for its numerical analysis of institutional attacks. They also conduct Monte Carlo simulations and a live deployment on the AvalancheGo engine.
Key Insights and Ideas
- Decoupling Security from Stake: The most significant insight is that Byzantine-tolerant peer sampling can be achieved without Proof-of-Stake, enabling truly open and permissionless systems.
- IP Address Structure as a Defense: Leveraging the hierarchical structure of IP addresses is a novel and effective way to defend against institutional Sybil attacks, which are concentrated in specific address blocks.
- Stubbornness in Search: The "stubborn chaotic search" is a clever way to ensure nodes continuously strive for better peer samples, even in adversarial conditions, by greedily updating their views.
- Hit Counters for Resilience: The hit counter mechanism provides a practical defense against temporary biases caused by Byzantine flooding, making the system more robust during convergence.
Key Results
- Theoretical Analysis: BASALT's theoretical model shows that the proportion of Byzantine nodes in samples is kept very close to the attacker's theoretical optimal power
f, even in adversarial scenarios. - Numerical Analysis: For institutional attacks, BASALT's hierarchical ranking reduces an attacker's power significantly. For example, controlling a major ISP's IP blocks would reduce an attacker's influence from over 99.99% to around 21% (with 1000 honest nodes).
- Simulations: Monte Carlo simulations demonstrate that BASALT consistently produces samples with fewer Byzantine nodes than the competing Brahms algorithm across various attack forces, sampling rates, and view sizes. BASALT also converges faster to high-quality network states.
- Live Deployment: A live experiment on the Avalanche network showed that BASALT significantly reduced the proportion of adversarial samples to about 1.13%, compared to 17.5% for a uniform sampling method. The live experiment also revealed that BASALT samples nodes more evenly across IP prefixes, unlike PoS-based sampling which favors wealthy participants.
Limitations and Future Work
- Network-Level Attacks: The paper acknowledges that it does not consider network-level attacks like BGP hijacks, though it discusses potential defenses.
- Eclipsed Nodes: While BASALT aims to prevent isolation, the paper notes that enabling eclipsed nodes to continue functioning normally in the face of network attacks remains an open problem.
- Bootstrapping: The paper briefly touches upon the challenge of bootstrapping a BASALT network with enough nodes to effectively counter botnet attacks, drawing a parallel to PoW cryptocurrencies.
- Future Work: The authors believe their work is an important contribution to epidemic BFT algorithms and expect continued development in this area, motivated by performance gains. They suggest that future research could explore further mechanisms to address network-level attacks and improve bootstrapping.
Summary updated