BASALT: A Rock-Solid Foundation for Epidemic Consensus Algorithms in Very Large, Very Open Networks

Alex Auvolat, Yérom-David Bromberg, Davide Frey, François TaïaniOpenReview 2021 · OpenReview

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 v peers. 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

Abstract

Recent works have proposed new Byzantine consensus algorithms for blockchains based on epidemics, a design which enables highly scalable performance at a low cost. These methods however critically depend on a secure random peer sampling service: a service that provides a stream of random network nodes where no attacking entity can become over-represented. To ensure this security property, current epidemic platforms use a Proof-of-Stake system to select peer samples. However such a system limits the openness of the system as only nodes with significant stake can participate in the consensus, leading to an oligopoly situation. Moreover, this design introduces a complex interdependency between the consensus algorithm and the cryptocurrency built upon it. In this paper, we propose a radically different security design for the peer sampling service, based on the distribution of IP addresses to prevent Sybil attacks. We propose a new algorithm, $\scriptstyle{BASALT}$, that implements our design using a stubborn chaotic search to counter attackers' attempts at becoming over-represented. We show in theory and using Monte Carlo simulations that $\scriptstyle{BASALT}$ provides samples which are extremely close to the optimal distribution even in adversarial scenarios such as tentative Eclipse attacks. Live experiments on a production cryptocurrency platform confirm that the samples obtained using $\scriptstyle{BASALT}$ are equitably distributed amongst nodes, allowing for a system which is both open and where no single entity can gain excessive power.
BibTeX
@misc{auvolat2021basalt,
  author = {Alex Auvolat and Yérom-David Bromberg and Davide Frey and François Taïani},
  title = {{BASALT: A Rock-Solid Foundation for Epidemic Consensus Algorithms in Very Large, Very Open Networks}},
  year = {2021},
  eprint = {2102.04063},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.04063},
  howpublished = {OpenReview},
}
Figure