Alex Auvolat

Yérom-David Bromberg

Davide Frey
email: davide.frey@inria.fr

François Taïani
email: francois.taiani@irisa.fr

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

Keywords: Gossip, Peer Sampling, Distributed System, Byzantine tolerance, Consensus

Recent works have proposed new Byzantine consensus algorithms for blockchains based on epidemics, a design which enables highlyscalable 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, 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 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 BASALT are equitably distributed amongst nodes, allowing for a system which is both open and where no single entity can gain excessive power.

INTRODUCTION

Blockchain-based systems, such as cryptocurrencies [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] and smart contract platforms [START_REF]Ethereum[END_REF], are said to be Byzantine Fault Tolerant (BFT for short), i.e. they are able to resist to attacks from malicious participants (called Byzantine nodes), making it arbitrarily hard for instance for an attacker to forge false transactions or revoke already committed transactions. In particular, decision power over the blockchain's state must be spread over various network participants in order to prevent an attacker from obtaining full control over the system.

The breakthrough made by Bitcoin [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] allowed for Byzantine fault-tolerance to be achieved in a truly open network, using a Proofof-Work system that requires participants to solve computationally intensive crypto-puzzles. The difficulty of these crypto-puzzles limits the influence of individual nodes, but encourage a race for computing power, with Bitcoin reported to consume as much electricity as Austria in 2020 [START_REF]Bitcoin Energy Consumption Index -Digiconomist[END_REF]. Moreover, the throughput and latency of Proofof-Work (PoW) systems are restricted by the time between blocks, which must be long enough to ensure security. Epidemic BFT algorithms. A particularly interesting area of research in alleviating these issues with Proof-of-Work consists in a new family of BFT algorithms [START_REF] Guerraoui | The consensus number of a cryptocurrency[END_REF][START_REF] Guerraoui | Scalable Byzantine reliable broadcast[END_REF][START_REF]Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies[END_REF] that exploits epidemic mechanisms to provide large-scale protection against Byzantine behaviour. Epidemic algorithms allow for extremely fast dissemination of information in very large networks by means of stochastic peer-to-peer exchanges [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Kermarrec | Probabilistic reliable dissemination in large-scale systems[END_REF]. Epidemic BFT algorithms exploit this property by repeatedly sampling small sets of random peers in the network, which they then use to estimate the overall system's state, and ensure coordination and agreement between correct (i.e. non-Byzantine) nodes.

Epidemic BFT approaches critically depend on the availability of good network samples, in the sense that the proportion of Byzantine nodes in a sample should be kept as low as possible, and sampled nodes should be as varied as possible. Providing such samples is the role of a so-called Byzantine-tolerant, or secure, random peer sampling (RPS) service. When such a service is available, these algorithms have the potential to yield much higher throughput than PoW systems at a fraction of the cost [START_REF]Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies[END_REF].

Secure random peer sampling. Unfortunately, classical RPS algorithms [START_REF] Jelasity | Gossip-based Peer Sampling[END_REF][START_REF] Nã©delec | An adaptive peer-sampling protocol for building networks of browsers[END_REF][START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF] are not resilient to malicious behavior: Byzantine nodes can easily disrupt their execution by flooding honest nodes with Byzantine identifiers. Left unchecked, this strategy has the potential to isolate honest nodes in a so-called Eclipse attack [START_REF] Heilman | Eclipse attacks on bitcoin's peer-to-peer network[END_REF][START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF], or to partition the system. Moreover, a scheme where peers are sampled with uniform probability is vulnerable to so-called Sybil attacks [START_REF] John R Douceur | The sybil attack[END_REF] where a malicious entity creates arbitrarily many network node identifiers that it controls, thus gaining unlimited influence on the network.

Current deployments of epidemic BFT algorithms, such as the AVA cryptocurrency platform [START_REF]AVA Labs, Build the Internet of Finance[END_REF], rely on a Proof-of-Stake mechanism to ensure that nodes are sampled in a secure way, i.e. that the cost for an attacker of biasing samples in their favor is very high. However, Proof-of-Stake has several known limitations [START_REF] Zhang | REM: Resource-efficient mining for blockchains[END_REF]. In essence, Proof-of-Stake consists in building an abstraction of a closed (permissioned) system, where system membership can however evolve dynamically according to the various parties' economic investments (in the form of token staking). We argue that such an abstraction is too restrictive and in fact not required. Particularly in the case of epidemic BFT algorithms, we show that the required Byzantine-tolerant random peer sampling service can be implemented directly in a much more open fashion, without resorting to Proof-of-Stake to ensure security.

Content of this paper. In this paper, we revisit the problem of secure peer sampling in large-scale decentralized systems, and propose BASALT, a novel Byzantine-tolerant random peer sampling algorithm. BASALT exhibits close to optimal Byzantine fault tolerance, thus significantly improving on the state-of-the-art [START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF][START_REF] Paolo | Secure peer sampling[END_REF]. BASALT is designed to operate in Internet-scale permissionless systems while resisting to Eclipse and Sybil attacks. At the core of BASALT lies what we have termed a stubborn chaotic search, a greedy epidemic procedure [START_REF] Voulgaris | VICINITY: A Pinch of Randomness Brings out the Structure[END_REF] towards random nodes that are implicitly defined in a way that makes it extremely hard for malicious nodes to manipulate the decisions of correct ones. This procedure is parametrized by a target distribution on nodes based on their IP addresses, which we define to defend against Sybil attacks by institutions that own large contiguous portions of the IP address space.

We comprehensively analyze BASALT under a theoretical model based on the power 𝑓 of the attack, which captures the (ideal) probability of sampling malicious nodes as defined by the target distribution. We show that BASALT provides samples in which the proportion of malicious nodes is very close to 𝑓 , its theoretical optimum, and that 𝑓 is acceptably small in several real-world scenarios including institutional attacks and botnet attacks. We complement our theoretical model with Monte Carlo simulations that confirm our analysis. Finally, we demonstrate the feasibility and concrete benefits of our technique by deploying BASALT within a live cryptocurrency network using a prototype implementation of BASALT for AvalancheGo [START_REF]Gecko, Official Go implementation of an AVA node[END_REF], the reference engine powering the AVA cryptocurrency network [START_REF]AVA Labs, Build the Internet of Finance[END_REF][START_REF]Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies[END_REF]. Our experiments on the AVA network confirm that the samples obtained using BASALT are equitably distributed amongst nodes, allowing for a system which is both open and where no single entity can gain excessive power. Our prototype is publicly available, fully functional, and compatible with the existing AVA network without requiring any protocol changes.

PROBLEM STATEMENT

A random peer sampling (RPS) service can be defined as a service that produces a continuous stream (𝑝 𝑖 ) 𝑖 ≥0 of random nodes selected in the network. As stated above, a secure random peer sampling service is faced with the double task of (i) ensuring the largest possible diversity of peers in the stream (𝑝 𝑖 ) 𝑖 ≥0 , while (ii) limiting as much as possible the appearance of malicious nodes in (𝑝 𝑖 ) 𝑖 ≥0 .

System Model

We assume a very large system composed of nodes that can either be honest (a.k.a. correct) or malicious (a.k.a. Byzantine). Byzantine nodes may deviate arbitrarily from the prescribed protocol in order to manipulate the decisions taken by correct nodes, for instance to isolate correct nodes or to increase malicious nodes' representation in the peer sampler's output. We write 𝑄 the number of correct nodes in the system.

We consider a communication network where any node can send a message to any other node, and assume that more than a fixed fraction of the messages sent to a node by other non-malicious nodes arrive within a certain delay. Byzantine nodes may collude (share information, coordinate their behaviors), and may send arbitrary messages to an arbitrarily large number of correct nodes per time unit. They cannot however block completely the communication between two correct nodes, or read in the local memory of correct nodes.

Nodes are granted each a unique identifier, which we assume to be their IP address. We will use the same notation to refer to a node and to its identifier. We assume that Byzantine nodes may not spoof the IP addresses of other nodes, which can be prevented using a handshaking mechanism [START_REF] Ehrenkranz | On the state of IP spoofing defense[END_REF].

Sybil Attacks

Random peer sampling is often considered under the assumption of a closed, or permissioned system (e.g. [START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF][START_REF] Jelasity | Gossip-based Peer Sampling[END_REF]), where the whole set of nodes is known and the proportion of malicious nodes is equal to (or bounded by) a small fixed fraction 𝜑. In such a situation, a perfect random peer sampler could be defined as one that samples all nodes uniformly, thus returning a fraction 𝜑 of malicious nodes in the samples it produces.

This assumption is however not adapted to an open network such as the public Internet, which is more akin to a permissionless (open) system. In such a setting, an attacker may control nodes with many times more IP addresses than there are correct nodes, which may then be used to perform a Sybil attack, leading to an increased influence of the attacker in the peer sample's output. In particular, a RPS that samples peers uniformly based on their IP addresses is particularly vulnerable to such attacks.

Drawing on the classification from [START_REF] Heilman | Eclipse attacks on bitcoin's peer-to-peer network[END_REF], we will consider two paradigmatic scenarios where an attacker attempts a Sybil attack using many IP addresses:

(i) Institutional attacks, launched by an institution or an organization that owns large IP address blocks; and (ii) Botnet attacks, where many infected machines are controlled by an attacker.

The crucial difference between these two attacks is that in an institutional attack the attacker may control many IP addresses located in a limited number of continuous address blocks, whereas in a botnet attack the attacker may control a smaller number of addresses in the whole IP address space. These properties allow us to implement efficient defenses by biasing our sample selection to limit the influence of any given entity (Section 3.3). From a practical perspective, these two attacks represent the two extremes of a continuous spectrum, as most actual attacks will usually fall somewhere in the middle, a point we return to in our evaluation.

We do not consider network-level attacks such as BGP hijacks in our attack model, however we discuss these attacks and potential defenses in Section 7.

THE BASALT ALGORITHM

BASALT leverages three main components. First it employs a novel sampling approach, termed stubborn chaotic search, that exploits ranking functions to define a dynamic target random graph (i.e. a set of 𝑣 target neighbors for each node) that cannot be controlled by Byzantine nodes. Second, it adopts a hit-counter mechanism that favors the exploration of new peers even in the presence of Byzantine nodes that flood the network with their identities. Finally, it incorporates hierarchical ranking functions that ensure that nodes sample their peers from a variety of address prefixes. The first two mechanisms ensure that the number of Byzantine nodes in a node's view cannot be increased arbitrarily by attackers. This offers protection from general Byzantine behaviors including those resulting from botnet attacks, as defined above. The third mechanism ensures that nodes sample their peers from a variety of address prefixes, thereby countering institutional attacks where the attacker controls a limited number of entire address prefixes.

Table 1 shows an overview of the parameters of our algorithm and of its environment, while Algorithm 1 shows its pseudocode. For the sake of clarity, in the following, we use the generic term node to refer to protocol participants, but we use the term peer to refer to a node's neighbors or potential neighbors.

Stubborn Chaotic Search

BASALT nodes implicitly identify a dynamic target random graph by defining target neighbors using a set of random ranking functions. Then, each node greedily attempts to converge towards this implicit definition by repeatedly exchanging neighbor lists with other peers, discovering at each step peers that better match its ranking functions. In the following, we first detail the use of ranking functions to identify target neighbors. Then we discuss how nodes update these ranking functions to make the random graph dynamic.

Identifying neighbors through ranking functions. Each node maintains a view, view[•], composed of 𝑣 slots. For each slot, 𝑖 ∈ {1, . . . , 𝑣 }, it chooses a random seed, noted seed[𝑖] (line 5 of Algorithm 1, and Fig. 1) that defines a corresponding random ranking function, rank seed[𝑖] (•). We then define a node's 𝑖-th out-neighbor in the target graph as the (correct or malicious) node 𝑝 that minimizes rank seed[𝑖] (𝑝). The function rank seed[𝑖] (•) can be selected to implement specific sampling distributions. For instance, using a simple hash function rank seed[𝑖] (𝑝) = ℎ(⟨seed[𝑖], 𝑝⟩) (where angle brackets represent a tuple) leads to a uniform sampling function, since each peer identifier has the same probability of producing the lowest rank. In Section 3.3, we present how a hierarchical ranking function allows BASALT to foil institutional attacks. For simplicity, we use the shortcut of saying that a peer 𝑝 better matches seed[𝑖] than a peer 𝑝 ′ if rank seed[𝑖] (𝑝) < rank seed[𝑖] (𝑝 ′ ).

When selecting seed[𝑖], a node cannot know the corresponding target identifier. Rather, it stores, in view[𝑖], the identifier that has so far produced the smallest value of rank seed[𝑖] (view[𝑖]) amongst those seen since selecting seed[𝑖]. At startup, each node selects the best matching peers, view[𝑖], from a set of bootstrap peers (line 6). 1 Nodes then periodically exchange the current contents of their views at lines 7-9 in order to discover new peers that can serve as better matches for the slots in their views. Specifically, every 𝜏 time units 1 We discuss the influence of the composition of this bootstrap set in Section 4. (exchange interval), each correct node selects a random peer from its view and sends it a pull request (line 8) to which the recipient, if correct, replies by sending the contents of its current view (line 11). Then, the node selects another peer from its view and sends it a push message containing its current view (line 9). When it receives the reply to the pull request, the node greedily updates any slot view[𝑖] that can be brought closer to its corresponding seed, seed[𝑖], using one of the received identifiers (lines [START_REF] Voulgaris | VICINITY: A Pinch of Randomness Brings out the Structure[END_REF][START_REF] Zhang | REM: Resource-efficient mining for blockchains[END_REF]. The peer to which a push message was sent does the same on its side.

Making the graph dynamic. To generate a dynamic random graph and enable nodes to continuously generate fresh samples from the network, nodes regularly reset some of their seeds to new random values. This periodic operation, at lines 14-19, first provides the application with 𝑘 peer identifiers representing a random sample of the network (line 17), and then resets the 𝑘 corresponding slots by selecting new seeds seed[𝑟 ] (line 18). These 𝑘 slots are selected in a round-robin fashion every 𝑘/𝜌 time units. This yields 𝜌 random samples per time unit on average as indicated in Table 1. It then sets the corresponding entries, view[𝑟 ], to the identifiers from the current view that best match the new seeds (line 19). When the algorithm returns view[𝑟 ] as a sample to the application, view[𝑟 ] effectively results from a random selection amongst all the peer identifiers received since the last reset of seed [𝑟 ]. A node has no way of knowing if it has found the peer 𝑝 that best matches seed[𝑟 ] globally (i.e. its target neighbor in the random graph), but selecting which seeds to reset in a round-robin fashion and by sampling view[𝑟 ] just before resetting seed[𝑟 ], the algorithm ensures that a maximum number of identifiers have been seen for each seed when returning the corresponding sample. This optimizes the randomness of the sample for a given budget of peer exchanges and view size. 2Parameter 𝜌 controls the number of random samples per time unit, and so the number of slots whose seeds are refreshed at each time unit. With a view size of 𝑣, this means that each slot is refreshed on average every 𝑣/𝜌 time units. The value of 𝑣/𝜌 must therefore be large enough with respect to the exchange interval, 𝜏. Parameter 𝑘 controls, instead, the number of slots that are reset at the same time. A large value of 𝑘 causes the algorithm to explore many slots in parallel, thereby obtaining more diverse samples that help the 𝑘 slots converge faster together. A small value of 𝑘 (e.g. 𝑘 = 1), instead, causes the exploration to occur with most slots in a quasi converged state. This increases the probability of contacting peers that have already been contacted recently, thereby leading to slower convergence for the 𝑘 unconverged slots. Our experiments by simulation confirm that BASALT better resists the presence of Byzantine peers using a batch sampling-and-replacement strategy where 𝑘 can be as high as 𝑣/2 (in which case 𝑘/𝜌, like 𝑣/𝜌, must also be at least several exchange intervals, 𝜏), rather than replacing seeds one by one (i.e. setting 𝑘 = 1).

Hit Counter Hardening Mechanism

The graph-generation mechanism described above prevents Byzantine peers from influencing the target graph, and thus the views of correct nodes once the network has converged. However, depending on the speeds at which correct nodes discover other correct or Byzantine peers, their intermediate views may suffer from a bias in favor of Byzantine nodes. If this happens, the algorithm will tend to select malicious nodes to push to and pull from (lines 8 and 9), further slowing down convergence.

BASALT mitigates this issue by introducing a hit-counter mechanism that effectively makes the protocol harder to attack. Each node maintains a hit counter variable, hits[𝑖], for each slot 𝑖 ∈ {1, . . . , 𝑣 } in its view. A node sets hits[𝑖] to 1 when initializing the slot, as well as whenever updating view[𝑖] with a peer that better matches the corresponding seed (line 25). Every time a node receives another peer's view that also contains peer view[𝑖], it increases hits[𝑖] by one (line 23).

When deciding which neighbors to contact, a node always selects one of the peers with the lowest value of hits[𝑖] (line 27). Finally, the node increases the hit counter of the selected peer by 1 to make it less likely to be selected the next time (line 28).

This mechanism has no impact on honest nodes as they should each appear as often in expectation. However, it creates a tradeoff for (possibly colluding) malicious nodes that try to be overrepresented, as nodes attempting to appear more often will automatically be contacted less. We further discuss this aspect and the possibility of attacks on the hit counter mechanism in Section 4.3.

Hierarchical ranking

Central to Algorithm 1, the function rank seed[𝑖] (•) induces a specific sampling distribution of node identifiers. For instance, using simply a hashing function for rank seed[𝑖] (•) yields uniform node sampling. Unfortunately, uniform sampling makes it relatively easy for institutional attackers to gain an overwhelming influence in the system, by taking the control of large IP address blocks to implement Sybil attacks (Section 2.2). For instance, as we will see in Section 4.4, controlling one of the largest ISPs would grant an attacker about 10 8 IPv4 addresses, a number large enough to thwart most existing decentralized BFT systems. Such attacks, are, however, heavily concentrated in a limited number of address ranges by design (∼5700 address blocks in the above example). The key idea for countering them therefore consists in not sampling peers uniformly, but using ranking functions that induce some diversity in the sampled node identifiers, and thus reduce the probability of sampling Sybil peers.

Ranking functions and target distributions. Formally, let 𝑆 be a uniform random variable on 256-bit integers, which corresponds to the sampling of a seed. Let 𝑋 be the random variable corresponding to the best matching peer sample for 𝑆, defined as:

(1)

𝑋 = argmin 𝑝 ∈N rank 𝑆 (𝑝)
where N denotes the set of all network nodes. Depending on the definition of rank 𝑆 (𝑝), 𝑋 can implement a specific probability distribution on network nodes. This allows us to define the attacker's power, 𝑓 , as the probability of 𝑋 being a malicious node given a specific ranking function rank 𝑆 (•). If rank 𝑆 (•) is a simple hashing function, rank 𝑆 (𝑝) = ℎ(⟨𝑆, 𝑝⟩), nodes are selected uniformly, and 𝑓 corresponds to the fraction 𝜑 of malicious nodes in the system. In the more general case, this probability is no longer equal to 𝜑 but, as we will see in Section 4.1, it plays the same role in our analysis, thus we will also call 𝑓 an equivalent fraction of malicious nodes.

Selecting the ranking function. In order to counter institutional Sybil attacks, we need to select a ranking function that minimizes 𝑓 by giving malicious nodes a low probability of being selected as bestmatching peers (i.e. chosen by the distribution 𝑋 ). BASALT adopts a ranking function that spreads sampled peers amongst different subnets by exploiting the structure of IP addresses. IP addresses can indeed usually be decomposed in two parts, a prefix, that designates the subnet to which the address belongs (linked to a given Internet service provider), and a local part that identifies a node within that subnet.

A first grouped ranking function. To illustrate this intuition, suppose that 𝐺(𝑝) corresponds to the prefix of a given length of the IP address, or a country code determined from the address. The following ranking function (based on a lexicographical ordering on values) can be used to sample uniformly amongst the different values of property 𝐺(𝑝), and then uniformly amongst all the peers that have the selected value of 𝐺(𝑝):

rank 𝑆 (𝑝) = ⟨ ℎ(⟨𝑆, 𝐺(𝑝)⟩) , ℎ(⟨𝑆, 𝑝⟩) ⟩
Using such a ranking function makes an attack against BASALT harder. In order to gain a power of 𝑓 in the network, a malicious entity would need to control a large number of nodes at least in a fraction 𝑓 of all the values of 𝐺(𝑝) where network nodes exist. For instance, consider an attacker that owns a full IP address block. Uniform node sampling gives the attacker a power of 𝑓 = 𝑞 𝑛 , where 𝑞 is the size of the IP block and 𝑛 the total number of nodes in the network. In the group-based sampling model, since an address block is usually associated with a single group (a single country, a single IP address prefix), the attacker only has a power of 𝑓 = 1

|𝐺 | 𝑞 𝑔
, where |𝐺 | is the number of different groups, and 𝑔 is the number of nodes present in the particular group of the attacker's address block. This attacking power is trivially bounded by 1 |𝐺 | , and the only way to increase it consists in taking control of many IP addresses in other groups, making such an attack much more costly.

BASALT's hierarchical ranking function. In BASALT, we take the grouping approach described above one step further. We adopt a hierarchical ranking function that descends the address hierarchy by sampling uniformly at levels /8, then /16, then /24, and then finally at the level of individual addresses, defined as follows:

(2) rank 𝑆 (𝑝) = ℎ(⟨𝑆, 𝑝 8 0 ⟩), ℎ(⟨𝑆, 𝑝 16 0 ⟩), ℎ(⟨𝑆, 𝑝 24 0 ⟩), ℎ(⟨𝑆, 𝑝⟩)

where 𝑝 𝑖 0 corresponds to the prefix constituted of the 𝑖 most significant bits of 𝑝's IP address. The efficiency of this ranking function in countering institutional Sybil attacks is demonstrated numerically in Section 4.4.

THEORETICAL ANALYSIS

We now use a theoretical continuous model to estimate the value of 𝐵(𝑡), the probability at a time 𝑡 that a given slot of a correct process contains a Byzantine peer identifier, as a function of 𝑓 , the attacker's power. The use of 𝑓 allows us to apply the same analysis to institutional and botnet attacks in a unified reasoning.

Parameters, Notations and Assumptions

4.1.1 Scenario parameters and node distribution. We first consider an ideal 'uniform' botnet attack, in which Byzantine identifiers follow the same distribution as those of honest nodes. This situation corresponds for instance to a scenario in which a botnet indiscriminately targets the same kind of nodes (e.g. personal machines) as those making up the rest of the system. In this case, the attacker's power 𝑓 that we introduced in Section 3.3 is simply equal to the fraction of Byzantine nodes in the network, and is independent of BASALT's hierarchical ranking function. To analyze this attack, we note 𝑛 the total number of network nodes (i.e. the network size), the product 𝑓 𝑛 denotes the number of Byzantine nodes, and 𝑄 = (1 -𝑓 )𝑛 denotes the number of correct nodes.

In the case of an institutional attack, the attacker's power 𝑓 depends on the distribution of the address blocks it controls, and represents the probability of selecting a Byzantine identifier using the ranking function rank 𝑆 (𝑝) in the hypothetical case that all identifiers in the network are known (Eq. 1). In this scenario, we define 𝑛 as an equivalent network size, defined as 𝑛 = 𝑄 1-𝑓 , where 𝑄 still denotes the number of correct nodes. These definitions satisfy the equality 𝑄 = (1 -𝑓 )𝑛, as in the (uniform) botnet attack, and will allow us to apply the same analysis seamlessly.

The two above scenarios represents the extreme cases of a wider spectrum of attacks. In particular, botnet attack might not be uniform, as the identifiers controlled by a botnet might be biased towards certain blocks (e.g. in the case of botnet built by targeting certain organization, or specific vulnerabilities) that differ from those of honest nodes. In such hybrid cases, the reasoning for institutional attacks applies.

4.1.2 Notations. The probability 𝐵(𝑡) of selecting a Byzantine node in a given slot of a node 𝑝 at time 𝑡 depends on two sets of identifiers: the set of correct identifiers seen at a time 𝑡 by 𝑝 on this slot since the last reset, noted C(𝑡), and the set of Byzantine identifiers seen by 𝑝 over the same period, noted B(𝑡).

One key observation is that, for a fixed C(𝑡), 𝐵(𝑡) increases as 𝑝 hears of new Byzantine identifiers and B(𝑡) grows, i.e. C(𝑡) = C(𝑡 ′ ) ∧ B(𝑡) ⊆ B(𝑡 ′ ) =⇒ 𝐵(𝑡) ≤ 𝐵(𝑡 ′ ), so that for a given C(𝑡), 𝐵(𝑡) is maximum when the node 𝑝 has learned all Byzantine identifiers circulating in the system.

In the following analysis, we therefore assume a worst case scenario in which correct nodes have been flooded with all existing Byzantine identifiers. (We discuss the actual implementation of this worst case scenario in Section 4.2.1.) For botnet attacks, we have assumed that correct and Byzantine identifiers follow the same distribution, implying that

𝐶(𝑡) = 𝑐(𝑡) 𝑏 max + 𝑐(𝑡) , (3)
where 𝑏 max is the total number of Byzantine identifiers, i.e. 𝑏 max = 𝑓 𝑛. (See Appendix A for a detailed derivation.) For institutional attacks, we assume that the distribution of correct nodes is independent of the sampling distribution introduced by rank(), and we approximate 𝐶(𝑡) using the same form as Eq. 3, where 𝑏 max becomes an equivalent number of Byzantine identifiers. Considering the case when 𝑝 knows all correct nodes (𝑐(𝑡) = 𝑄), and having defined 𝑛 = 𝑄 1-𝑓 , we derive 𝑏 max = 𝑓 × 𝑄 1-𝑓 , and hence 𝑏 max = 𝑓 𝑛 in this case as well, where 𝑛 is now the equivalent network size introduced above.

In both attacks, the probability of selecting a Byzantine node, 𝐵(𝑡), becomes therefore driven by the number of correct identifiers known to 𝑝, 𝑐(𝑡) = |C(𝑡)|, and the same system equation can be used to study both cases (modulo the redefinition of 𝑛 for institutional attacks).

Assumptions.

For simplicity, we study a version of BASALT without the hit counter-based hardening mechanism, and later discuss its impact in Section 4.3. Algorithm 2 shows the pseudocode corresponding to the hit counter-less version being analyzed. To approximate the system's behavior, we will reason using the mean values of 𝑐(𝑡) over all nodes and slots, and assume that the values of individual nodes tend to concentrate around their means in practice with high probability, as is usually the case in such stochastic systems.

Analysis of the Core Mechanism

We first discuss in more detail the worst-case attack on the BASALT algorithm. We then study the risk of a node becoming isolated under this attack model (i.e. of an Eclipse attack succeeding), before moving on to studying the convergence properties of BASALT assuming no node is ever isolated.

Identifying the Worst-Case Attack.

To identify the worst case attack, we observe that attackers cannot influence the choices correct nodes make (at line 6 of Algorithm 2, and at lines 16-18 of Algorithm 1); thus they can only manipulate the peer-sampling process by increasing their representation in the views of correct nodes, i.e. the value of 𝐵(𝑡). The fact that 𝐵(𝑡) grows with the set of Byzantine identifiers the node is aware of, B(𝑡), suggests that the worst case scenario arises when Byzantine nodes flood the network with their identifiers in order to increase B(𝑡) as much as possible. We model this attack scenario as follows:

• A malicious node that receives a pull request returns a view composed of 𝑣 nodes selected uniformly at random amongst the malicious nodes. • Regularly, a malicious node sends a push request to randomly selected correct peers, containing similarly a view of 𝑣 uniformly random malicious peers. We define the force of the attack, 𝐹 (distinct from the attacker's power, 𝑓 ), as the ratio between the number of push requests sent by a Byzantine node and number of push requests sent by a correct node in a given time interval. For example, if a Byzantine node sends push requests at the same rate as correct nodes, a force of 𝐹 corresponds to sending requests to 𝐹 distinct correct nodes rather than to only one. Alternatively, the force of the attack can also model a situation in which Byzantine nodes send requests more often, or where the network loses more messages from correct nodes than from Byzantine ones.

The worst case corresponds to an arbitrarily large value of 𝐹 , arising when correct nodes receive all the identifiers of Byzantine peers in any arbitrarily small (but non-empty) time interval. This means that apart from the initial state, B(𝑡) is constant, and its effect can be captured by the term 𝑏 max = 𝑓 𝑛 to compute the probabilities of selecting a correct (resp. Byzantine) peer in a slot of a node's view. We recall that 𝑓 𝑛 represents the total/equivalent number of Byzantine nodes depending on the attack considered. The analysis that follows shows that even in this case, BASALT causes 𝐵 to converge to a value that is only slightly larger than the attacker's power, 𝑓 . The experimental results of Section 5 analyze instead the actual performance with finite values of 𝐹 . 4.2.2 Bounding the Probability of Isolation. We start by showing that nodes have a low probability of being isolated. Isolation can happen in two ways: either when a node joins the network for the first time, or when it evicts all correct peers from its view and replaces them with Byzantine peers.

Isolated joining node. In the first case, the unfortunate joining node receives all of the identifiers of Byzantine nodes as soon as it joins. At time 𝜖 after joining we have B(𝑡) becomes maximal and 𝑐(𝜖) = (1 -𝑓 0 )𝐼 , where 𝑓 0 is the fraction of Byzantine nodes in the bootstrap sample and 𝐼 is the size of the bootstrap sample. Since we defined 𝐵(𝑡) as the probability of a given slot in the view being occupied a Byzantine peer, we can write the probability that a node has only Byzantine neighbors as 𝐵(𝑡) 𝑣 .

𝐵(𝑡)

𝑣 = 𝑏 max 𝑏 max + 𝑐 𝑣 = 1 1 + (1 -𝑓 0 ) 𝐼 𝑓 𝑛 𝑣 (4)
We can reduce this probability exponentially by increasing 𝑣, by increasing 𝐼 or by assuming a lower 𝑓 0 . For instance, supposing 𝑓 0 = 50% of malicious nodes in our bootstrap peer list, by taking a view size of 𝑣 = 200 and a bootstrap peer list size 25% of the number of malicious nodes in the network (𝐼 = 1 4 𝑓 𝑛), this probability becomes smaller than 10 -10 . Supposing for instance a network of size 𝑛 = 10000 with a fraction 𝑓 = 0.1 of Byzantine nodes, this only requires a bootstrap set of size 𝐼 = 250 nodes, of which only 125 are required to be correct.

Convergence to isolated state. The second way for a node to become isolated results from resetting the seeds for the slots that still contain correct peers to new seeds that select Byzantine nodes. When such a reset occurs, the probability that all of the non-reset slots are already owned by Byzantine peers is equal to 𝐵(𝑡) 𝑣-𝑘 = 𝑏 max 𝑏 max +𝑐(𝑡 )

𝑣-𝑘

. When the number of correct nodes seen locally, 𝑐(𝑡), is large enough, this probability is negligible.

Let us now study the value of 𝑐(𝑡) at the time of a reset, depending on the value of 𝑐(𝑡) at the time of the previous reset. For this analysis, we look at a single node of the network and make the hypothesis that other network nodes are well-converged. As we discuss in Sections 4.2.3 and 5, this implies that the fraction of Byzantine nodes in their views approaches 𝑓 with appropriate algorithm parameters. We write 𝑐 0 the value of 𝑐(𝑡) at the previous reset. The expected number of correct peer identifiers received during the period between the two resets is lower bounded by 𝑘 𝜌 𝑣 𝜏 𝑐 0 𝑓 𝑛+𝑐 0 (1 -𝑓 ). If we write ∆𝑐 the corresponding increase in 𝑐(𝑡), i.e. the number of distinct correct peer identifiers received during this time period, we obtain:

∆𝑐 ≥ 𝑘𝑣𝑐 0 (1 -𝑓 )(𝑄 -𝑐 0 ) 𝑄𝜏𝜌(𝑓 𝑛 + 𝑐 0 ) + 𝑘𝑣𝑐 0 (1 -𝑓 ) (5)
(see Appendix B for the full derivation).

Suppose for instance a network of 𝑛 = 10000 nodes with a proportion 𝑓 = 0.1 of malicious nodes, with algorithm parameters 𝑣 = 100 and 𝑘 = 50. In this system, taking 𝜏 = 1 and 𝜌 = 1, and supposing that the node we are considering has just joined the network and knows only of 𝑐 0 = 𝑓 0 1 4 𝑓 𝑛 = 125 correct node identifiers, we obtain that ∆𝑐 ≥ 467, i.e. 𝑐(𝑡) at the next reset is expected to be at least 592. 𝐵(𝑡) 𝑣-𝑘 is smaller than 10 -10 as soon as the number 𝑐(𝑡) of correct node identifiers seen is more than 585. In other words, the probability that the node becomes isolated at the next reset is negligible. This guarantee can be made even stronger by increasing the view size 𝑣. Moreover, if the node is already in a better-converged state with a relatively large 𝑐 0 , the probability of becoming isolated during a reset becomes even smaller.

Non-Isolated

Execution. Now that we have shown that the probability of a node becoming isolated can be made arbitrarily low, we make the following assumption in the rest of the analysis. ASSUMPTION 1. No node is isolated, and all nodes have at least some correct neighbors. In particular, 𝐵(𝑡) 𝑣 is negligible at all times 𝑡.

Deriving a continuous model. When Assumption 1 holds, and in the worst-case scenario discussed above (Byzantine nodes have propagated all their identities to all correct nodes) B(𝑡) is constant, and its effect captured by the term 𝑏 max , which allows us to write the evolution of 𝑐(𝑡) over time as a differential equation, as the sum of contributions resulting from the various parts of the system.

• Pull exchange: every 𝜏 rounds, a node pulls from one peer in its view, which replies by sending 𝑣 node identifiers. With probability 𝐵(𝑡), the node contacts a Byzantine peer. In this case, it receives only Byzantine peer identifiers that it is already aware of (by the worst-case assumption 𝑏 max = 𝑓 𝑛).

With probability 𝐶(𝑡), the node contacts instead a correct peer. In this case, each returned identifier will itself be correct with probability 𝐶(𝑡), and if correct, it will have a probability

𝑐(𝑡 )

(1-𝑓 )𝑛 of being already known ((1 -𝑓 )𝑛 being the total number of correct nodes). Thus we can express the variation of 𝑐(𝑡) over time as a result of a pull operation as follows:

𝑑𝑐 𝑑𝑡 = 1 𝜏 𝐶(𝑡) 2 𝑣 1 - 𝑐(𝑡) (1 -𝑓 )𝑛 .
• Push exchange: every 𝜏 rounds, a node pushes to a random node in its view. This push has a 𝐶(𝑡) probability of being sent to a correct node. In this case we can apply the same reasoning as above and derive the same contribution to 𝑑𝑐 𝑑𝑡 . • Sampling and view renewal: every 𝜌 rounds, a node resets one of its 𝑣 slots and forgets the identifiers collected for this slot. Let us write 𝑐(𝑡) as 𝑐(𝑡) = 1 𝑣 𝑣 𝑖=1 𝑐 𝑖 (𝑡), where 𝑐 𝑖 (𝑡) is the number of correct nodes taken into account by slot 𝑖. Then a single 𝑐 𝑖 is set to zero every 𝜌 rounds. On average, this yields the following contribution to 𝑑𝑐 𝑑𝑡 : 𝑑𝑐 𝑑𝑡

= -𝜌

𝑐(𝑡) 𝑣

.

By summing all three above contributions, we obtain our final differential equation:

𝑑𝑐 𝑑𝑡 = 1 𝜏 2𝐶(𝑡) 2 𝑣 1 - 𝑐(𝑡) (1 -𝑓 )𝑛 -𝜌 𝑐(𝑡) 𝑣 . (6)
Solving the continuous model. We now solve Equation 6under Assumption 1 and show that the network converges to a state where the proportion 𝐵 of Byzantine peers in nodes' views is small even for arbitrarily large values of the attack force, 𝐹 . To this end, we can express 𝑑𝐵 𝑑𝑡 as 𝑑𝐵 𝑑𝑡 = -𝑏 max (𝑏 max +𝑐) 2 𝑑𝑐 𝑑𝑡 , and by substituting 𝑑𝑐 𝑑𝑡 from Equation 6, we obtain:

(7) 𝑑𝐵 𝑑𝑡 = 𝐵(1 -𝐵) 𝜌 𝑣 - 2𝑣(1 -𝐵)(𝐵 -𝑓 ) 𝜏 𝑓 (1 -𝑓 )𝑛
To study the constant regime of this system, we write 𝑑𝐵 𝑑𝑡 = 0 and exclude the solutions 𝐵 = 0, which is not compatible with 𝑏 max = 𝑓 𝑛, and 𝐵 = 1, which corresponds to the case where Byzantine nodes take over the whole network. We also simplify by setting 𝜏 = 1 as its role is symmetrical with that of 𝜌. We obtain after a few steps:

(8) (1 -𝐵)(𝐵 -𝑓 ) = 𝜌 𝑓 (1 -𝑓 )𝑛 2𝑣 2
.

The equation exhibits two roots 𝐵 1 < 𝐵 2 .

(

) 𝐵 1,2 = 1 2 1 + 𝑓 ∓ √ (1 -𝑓 ) 2 -2 𝜌 𝑓 (1 -𝑓 )𝑛 𝑣 2 9
When the quantity on the right-hand side of Equation 8 approaches zero, 𝐵 1 approaches 𝑓 from above, while 𝐵 2 approaches 1 from below. Since 𝑑𝐵 𝑑𝑡 > 0 for 𝐵 < 𝐵 1 and 𝐵 > 𝐵 2 , while 𝑑𝐵 𝑑𝑡 < 0 for 𝐵 1 < 𝐵 < 𝐵 2 , 𝐵 1 corresponds to a stable equilibrium, while 𝐵 2 corresponds to an unstable one. So we focus our analysis on 𝐵 1 .

With respect to 𝐵 1 , the right-hand side of Equation 8represents the difference between the proportion of malicious peers in nodes' views, 𝐵(𝑡), and their overall proportion in the network, 𝑓 . Ideally, we want to keep this quantity as small as possible, making 𝐵 only slightly larger than 𝑓 .

To this end, we observe that the term

𝜌 𝑓 (1-𝑓 )𝑛 2𝑣 2
shrinks proportionally to the square of the view size, 𝑣 2 . Thus, choosing a large enough view size allows the network to converge to a globally well mixed state where Byzantine nodes control only slightly more peers in the view than their overall proportion in the network. Moreover, in order to obtain the same stable state value of 𝐵, for fixed values of 𝑓 and 𝑛, the view size 𝑣 should grow proportionally to the square root of the sampling rate √ 𝜌, while, for fixed values of 𝑓 and 𝜌, it needs to increase proportionally to √ 𝑛.

Analysis of the Hardening Mechanism

BASALT's hit counter-based hardening mechanism allows nodes to detect which peers have appeared more often in incoming messages, and prioritize other peers for network exploration. In the case of a standard attack, where malicious peers flood their own identifiers, the hit counter favors the choice of correct peers over malicious ones.

However, the fact that we analyzed a simplified version of BASALT without the hardening mechanism raises the legitimate question of whether the hit counter may degrade the security of the approach by enabling some other attack. To answer this question, let us consider a malicious node or a coalition of malicious nodes that want to influence the sampling operations performed by a correct node.

We start by observing that malicious nodes can neither write nor read the local memories of correct nodes. So they cannot influence 9, with a view size of 𝑣 = 100 and a sampling rate of 𝜌 = 1.

sampling operations directly: their only strategy consists in trying to convince a target correct node that some of the correct peers in its view are malicious by increasing their hit counters. To this end, malicious nodes can repeatedly advertise the identifiers of correct peers. But again, they cannot guess which correct peers are in the target correct node's view slots. So their only option consists in advertising a possibly large random set of correct peers in the hope that some of them will be in the correct node's view. But even this turns out to be counterproductive. If malicious nodes advertise a large number of correct identifiers, it is indeed possible that they may increase the hit counter of some entries in the target's view. But they do so at the cost of increasing their target's value of 𝑐(𝑡), i.e. the number of correct peers known to it. Since we already assumed the worst case scenario of 𝑏 max = 𝑓 𝑛, the increase in 𝑐(𝑡) can only decrease 𝐵(𝑡) thereby making the attack counterproductive.

Numerical Analysis: Institutional Attacks

To illustrate the robustness of BASALT's hierarchical ranking function against an institutional attack, we calculate the power 𝑓 (here an equivalent fraction of malicious nodes) of a real-world attacker using data from the GeoLite2 Block/ASN dataset [START_REF]GeoLite2 ASN CSV Database[END_REF], and use the equilibrium formula of Equation 9(𝐵 1 ) to compute the proportion of Byzantine nodes that BASALT would return in such a scenario. We assume that the attacker is an internet autonomous system (AS), that exploits all the IP addresses it owns to attack BASALT, and that a certain number of honest nodes (100, 1000, 10000) are uniformly spread amongst the remaining currently active IP addresses. Table 2 shows the power 𝑓 of such an attacker, supposing that the attacker is the Internet AS with the largest number of currently active addresses (106 million in the dataset we used, spread over 5739 blocks). This calculation shows that the hierarchical sampling method reduces the power of the attacker down to 21% when only 1000 honest nodes run BASALT, where it would have been above 99.99% (i.e. full control on the network) using uniform sampling. Figure 2 shows the corresponding probability that BASALT will return Byzantine nodes by applying Equation 9for the 100 biggest Internet ASes, assuming 1000 uniformly spread honest nodes.

EXPERIMENTAL EVALUATION

We complement our theoretical analysis with Monte Carlo simulations that illustrate BASALT's dynamic behaviour. In this section, we focus on simulating a permissioned system with a known fraction of malicious nodes. We do not simulate the IP address distribution and use the uniform ranking function. As explained above, our observations can be transposed to a permissionless setting, where the attacker's power defined by the hierarchical ranking function plays the role of an equivalent fraction of malicious nodes. We show that BASALT consistently produces samples with fewer malicious peers than the state-of-the-art algorithms Brahms [START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF] and SPS [START_REF] Paolo | Secure peer sampling[END_REF] over a wide range of scenarios. We also show that BASALT converges faster on metrics quantifying the random connectivity of the graph generated by the algorithm, such as the clustering coefficient and mean path length. These metrics are relevant for information dissemination and may thus have an influence on the convergence time of epidemic agreement algorithms.

Experimental Setting

We evaluate the tested algorithms by simulating a system with 𝑛 nodes, of which a fraction 𝑓 implement the malicious behaviour described in Section 4.2.1. We do not simulate message loss or variable link latencies, as our model parameter 𝐹 (the attack force) already integrates the possibility of message loss (see Section 4.2.1), and variable link latencies can also be modeled as losing messages that arrive after a certain delay. We do not simulate node churn, but consider instead an extreme scenario in which all nodes have just joined the system-this can be seen as an ultimate churn event, in which all nodes are replaced. We vary the two parameters 𝑣, the view size, and 𝜌, the sampling rate, of the algorithm, as well as the force of the attack, 𝐹 . We fix the exchange interval to 𝜏 = 1 (1 simulation time step). Unless stated otherwise, we use 𝐹 = 10 and 𝜌 = 1. All algorithms were implemented in a same simulation framework written in Rust, totaling about 2500 lines of code 3 .

We compare BASALT (Algorithm 1) and its variant without the hardening mechanism (Algorithm 2, BASALT-simple) to two stateof-the-art competitors: Brahms [START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF] and SPS [START_REF] Paolo | Secure peer sampling[END_REF].

SPS was unable to function at all in the tested scenarios: for instance for 𝑛 = 1000, 𝑓 = 30%, and even with an attack force 𝐹 of 0, 90% of correct nodes become isolated in the network rapidly using SPS and remain so during the whole simulation. In contrast, both BASALT and Brahms were able to prevent all correct nodes from becoming isolated. We have thus decided to exclude SPS from our comparison charts, and concentrate on the comparison of BASALT against Brahms.

To compare Brahms and BASALT on similar grounds, we add to the Brahms algorithm a mechanism that resets some of the hash functions regularly, using the same round-robin strategy as BASALT. Without such a mechanism Brahms would always return the same fixed set of samples, limiting its usability as a random peer sampling algorithm. As we will show just below, adding a reset rate to Brahms makes it less resilient to malicious nodes. In terms of communication overhead, Brahms and BASALT have the same cost. Indeed, both algorithms send a set of peer identifiers of size 𝑣 when replying to a pull request. For push requests, BASALT uses larger messages since Brahms does not send the view with a push message, only the sending node's identifier, whereas we send the whole view of size 𝑣. However, supposing 𝑣 = 200 (the maximum in our experiment) and node identifiers of size 4 bytes (such as IPv4 addresses), the size of the communicated information is smaller than one MTU (maximum transmission unit, i.e. maximum size of a single packet, which is about 1500 bytes on the Internet), thus the same number of Internet packets need to be sent by both algorithms.

Proportion of Byzantine Samples

In our first experiment, we measure the number of Byzantine nodes present in correct nodes' samples on average after 200 simulation time steps. For this experiment, we simulate a network of 𝑛 = 10000 nodes. We fix base parameter values of 𝑓 = 10% of malicious nodes, a sampling rate of 𝜌 = 1, a view size of 𝑣 = 160 and an attack force of 𝐹 = 10. We then vary the parameters 𝑓 , 𝜌, 𝑣 and 𝐹 individually. Figure 3 shows how this proportion evolves for the three algorithms evaluated, as one of the parameters 𝑓 , 𝜌, 𝑣 and 𝐹 varies.

Plot 3a shows how the algorithms behave when the proportion of Byzantine nodes in the system varies. BASALT provides close to optimal proportions of Byzantine samples even with many Byzantine nodes, whereas Brahms fails to contain the attack in this domain. Plot 3b shows the sensitivity of the algorithms to the force of the attack 𝐹 . These plots show that BASALT is almost insensitive to 𝐹 , whereas Brahms shows an increasing proportion of Byzantine samples when 𝐹 increases.

Plot 3c shows how the algorithms behave for various values of the sampling rate 𝜌. For low values of 𝜌, both Brahms and BASALT are able to converge to high quality samples, however such a setting does not provide much utility as the algorithm is unable to frequently return new samples to the application. Increasing the sampling rate 𝜌 results, however, in more disruption of the views, where view slots have a higher risk of being reset before they converge to their target peer. This disruption causes Brahms to collapse for higher values of 𝜌: the network becomes fully disconnected, and the views of correct nodes end up completely polluted by malicious peers. This plot also shows how the hit-counter variant helps BASALT attain better states when 𝜌 is high.

Plot 3d shows how the algorithms behave for various view sizes. For small view sizes, all algorithms are unable to keep the network in a connected state and correct nodes all end up isolated. The plots show that BASALT can keep the network connected using smaller views than Brahms.

Evaluating Convergence Speed

In this second experiment, we study the speed at which the algorithms converge to good network states, where they provide samples with low proportions of malicious nodes. Figure 4 shows the time that Brahms and BASALT take to converge to proportions of Byzantine samples that are within 25% of the optimal proportion, for 𝑛 = 1000, 𝑣 = 100, 𝐹 = 10 and 𝜌 = 1 and for varying proportions of Byzantine nodes in the network. We show that the convergence time of BASALT remains low for up to 30% of Byzantine nodes, whereas Brahms takes much longer to converge (starting at 20% of Byzantine nodes, it did not converge within the experiment's time).

Figure 5 shows the evolution of several metrics through time, starting with the number of Byzantine nodes in the view, in our experiment for 𝑛 = 10000, in a favorable situation with 𝑓 = 10%, 𝜌 = 0.5 and 𝐹 = 1. These plots show that BASALT converges much faster than Brahms to a good network state (Brahms does not converge according to the previous criterion within the time of the experiment). The other plots show metrics for graph quality, where the algorithms exhibit a similar convergence behaviour: clustering coefficient, mean path length and the concentration of in-degrees measured by the difference between the last and the first decile. The clustering coefficient is computed by averaging the local clustering coefficient of correct nodes in a graph where malicious nodes are assumed to be all connected to one another. The mean path length is measured in a graph where malicious nodes are assumed to have no connection in either direction, which models the situation where they do not cooperate in transmitting information between correct nodes.

Node Isolation vs. Sampling Rate

We have seen earlier (Plot 3c) that both Brahms and BASALT are sensitive to increased sampling rates, and return more malicious samples when the sampling rate, 𝜌, is high, with Brahms failing completely for too large values of 𝜌.

To investigate this effect further, we run both algorithms for various values of 𝑣 and 𝜌, and plot the maximum value of 𝜌 that can be used for a given 𝑣 without causing a network partition. More precisely, a run for a given set of parameters 𝑣, 𝜌 is successful if starting from half of the allocated simulation time, no correct node is ever isolated by the malicious peers. Otherwise it is failed. We plot the successful runs with highest values of 𝜌 for a given 𝑣. The results of this experiment are shown in Plot 6 for 𝑁 = 10000, 𝑓 = 10% and 𝐹 = 10. The areas delineated in Plot 6 correspond to the parameter sets that give successful runs. Our results show that for similar view sizes, BASALT achieves much higher sampling rate than Brahms, thus providing more utility to the application.

LIVE DEPLOYMENT

We implemented BASALT in the AvalancheGo engine [START_REF]Gecko, Official Go implementation of an AVA node[END_REF], the main implementation of the AVA network [START_REF]AVA Labs, Build the Internet of Finance[END_REF] which uses the Avalanche consensus algorithm 4 . We picked AVA, as it is the main cryptocurrency network that uses an epidemic, sampling-based consensus, which is the target use case of BASALT. Our implementation, a 500lines patch to the Go source code of AvalancheGo, replaces peer sampling based on stake in a proof-of-stake system by peer sampling based on BASALT, including the hierarchical ranking function described in Section 3.3.

Our implementation integrates seamlessly with the AVA protocol and is fully compatible with the existing network. Our implementation supports managing current outgoing connections according to the BASALT algorithm, instead of keeping connections open to all reachable network nodes as done by the original AvalancheGo implementation 5 .

To show that BASALT can be applied as a sampling method that reduces the risk of an institutional attack, we ran a 10-hour experiment where we launched 100 "adversarial" Avalanche nodes on the public AVA network (corresponding to about 20% of total active nodes) in an attempt to bias sampling in their favor using a Sybil attack against one of our nodes. The nodes we launched all had IP addresses located in the same /24 prefix, owned by our research institution. Samples were measured at witness nodes running the BASALT sampling algorithm, as well as the non-hierarchical variant of BASALT and a sampling algorithm based on full network knowledge. Results shown in Table 3 show that using BASALT, the 4 Our code is publicly available at https://github.com/basalt-rps/avalanchego-basalt. Our implementation is forked from the official AvalancheGo repository [START_REF]Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies[END_REF]. Our changes are identified by "Basalt RPS Authors". 5 Unfortunately, we had to disable this behaviour as it led to too many connection attempts and some nodes appeared to have banned our IP addresses as a consequence. A simple modification allows our code to never close connections intentionally: the view maintained by BASALT is only used to sample peers for the Avalanche consensus algorithm, and connections are kept in the background to nodes that have been removed from the view. probability of sampling one of our adversarial nodes is brought to about 1%, meaning that the influence of our nodes in the network is extremely limited.

To show the wider benefit of BASALT, we plot in Figure 7 the number of times the various nodes of the AVA network were sampled in the experiment. Sorting nodes by a density metric which counts the number of other nodes in the same /8, /16 and /24 prefix reveals that nodes which are isolated in their prefix (on the left of the graph) are sampled more often than nodes which share their IP prefixes with other nodes (on the right). However all network nodes have a chance of being sampled, and no single node is sampled exceedingly more often than others. This stands in contrast with Proof-of-Stakebased sampling, where sampling frequency is proportional to the stake invested, a mechanism that gives disproportionate power to rich nodes and totally excludes nodes that are not able to invest any stake in the network.

DISCUSSION AND RELATED WORK

Random peer sampling in non-adversarial settings is a well-studied problem [START_REF] Jelasity | Gossip-based Peer Sampling[END_REF][START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF]. Surprisingly, very few works have sought to develop Byzantine-tolerant RPS protocols.

State-of-the art methods such as Brahms [START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF] and Secure Peer Sampling [START_REF] Paolo | Secure peer sampling[END_REF] (SPS) are based on a classical RPS algorithm, to which is adjoined a mechanism that tries to correct for the over-representation of malicious nodes. In Brahms, the view is not updated if a peer has received more than a certain number of push messages in a given time slot. Albeit vaguely similar to our hit counter mechanism, Brahms' approach can only work if we assume that malicious nodes have limited total firing power and must therefore target their attack on a specific victim node. Otherwise, they would be able to simply flood the whole network with many pushes and halt the peer sampling algorithm completely. In SPS, nodes try to build some statistical knowledge on node behaviour; however, this mechanism is unable to cope with attacks where malicious nodes send so many messages that correct nodes do not have the time to gather sufficient statistics to block them before becoming isolated. Our protocol, on the other hand can effectively handle these attacks. Moreover, the majority of these systems do not address risks that exist in real-world networks, such as Sybil attacks. To our knowledge, the only exception is HAPS [START_REF] Taiani | Foiling Sybils with HAPS in Permissionless Systems: An Address-based Peer Sampling Service[END_REF], which is designed specifically to handle Sybil attacks. HAPS, however, only addresses Sybil attacks in which attackers are concentrated in a few IP blocks ("institutional attacks"), by using random walks on a carefully crafted probabilistic tree. Due to its design, it is not immediately clear how HAPS could be extended to counter attackers that are spread out, which BASALT does thanks to its stubborn chaotic search.

Recent works on blockchains have also brought to lighten the risk of attacks at a more fundamental level than those described in Section 2.2. Network adversaries are malicious entities that gain control of part of the routing infrastructure (internet autonomous systems, or ASes), in which case they can intercept and modify all the traffic that they are routing, or attack the routing algorithm itself by advertising Internet prefixes that they do not own, thus attracting traffic that should have gone through another path, a so-called BGP hijack [START_REF] Maria | Hijacking Bitcoin: Routing Attacks on Cryptocurrencies[END_REF].

Note that BGP hijacking attacks are necessarily limited to one or a few IP prefixes, as large-scale routing attacks would likely bring down large parts of the Internet and would be noticed immediately. By spreading connections over a variety of IP prefixes through its rank function, BASALT builds intrinsic resilience to these attacks as at most only a small fraction of nodes' neighbors will be located in hijacked prefixes. In this way, the global BASALT network is not at risk of being taken down or manipulated by a malicious entity.

However, network attacks might also be used to target specific nodes, to remove them from the global network and make them believe false information about the network's state (an Eclipse attack). Defenses have been proposed against Eclipse attacks at the network level: for instance, the SABRE network [START_REF] Apostolaki | SABRE: Protecting Bitcoin against Routing Attacks[END_REF] proposes to use additional communication channels, in the form of a network of specialized nodes that are all connected to one another using dedicated channels, and that are located close to end-users so that they can provide a safe service directly to them even in the case of a hijack.

In the case of a blockchain, where the most crucial property to guarantee safety is that all nodes are made aware of new blocks rapidly, the SABRE method is able to help by providing reliable block delivery. For sampling-based methods that use BASALT, SABRE could provide a security mechanism at the application layer to enable detection of network attacks and stop all activity in case they happen, for instance by detecting a discrepancy between a node's local state and the state of SABRE nodes. This mechanism however cannot be used to allow eclipsed nodes to make progress in such a situation, as it does not provide the secure random peer sampling service itself. Finding mechanisms to allow nodes that are eclipsed by a network attack to continue functioning normally when running a sampling-based algorithm is, to the best of our knowledge, still an open problem.

Finally, one could argue that it will be hard to bootstrap a BASALT network containing enough nodes to effectively counter botnet attacks. We note that this problem is exactly the same as in PoW-based cryptocurrencies, as an attacker that gains > 50% of the network's hashing power can overturn the network in their favor (which is easy to do for smaller cryptocurrencies that don't have a lot of hashing power allocated to them). A PoW-based cryptocurrency network is secured by members investing in providing lots of hashing power, as is the case e.g. for Bitcoin, in order to make a > 50% attack so costly that it is impossible in practice (or simply not worth it compared to the value of the cryptocurrency that could be stolen). A BASALTbased cryptocurrency is similarly secured by participants investing in running as many nodes as possible from many different IP prefixes, which they have an incentive to do in order to keep the system safe. Moreover, BASALT has the advantage that this investment does not require the waste of tremendous quantities of energy.

CONCLUSION

We have presented a new algorithm for Byzantine-tolerant random peer sampling on the Internet that uses biased sampling to prevent Sybil attacks. Such an algorithm can be used to implement samplingbased consensus algorithms such as Avalanche. Contrary to sampling algorithms based on Proof-of-Stake, such as those currently in use on the AVA network, BASALT allows the network to be truly open by allowing any Internet user to join the consensus without having to own any cryptocurrency tokens. We expect that in the future the line of research around Byzantine fault-tolerant algorithms based on epidemics will continue to see new developments motivated by gains in performance, and thus we believe that we have brought an important contribution to making such methods applicable in large-scale open networks.

A 𝐶(C, B) IN A BOTNET ATTACK

The probability 𝐶(C, B) depends on the distribution of correct and Byzantine identifiers across the three levels of blocks used in Equation 2. We fix one node 𝑝 selected randomly amongst C ∪ B, and write selected(𝑝) the event that 𝑝 is selected by the ranking function rank 𝑆 (•): selected(𝑝) ≡ 𝑝 = argmin 𝑞 ∈ C∪B rank 𝑆 (𝑞) .

With this notation we have 𝐶(C, B) = Pr ( 𝑝 ∈ C | selected(𝑝) ).

In our model, a botnet attack corresponds to the (ideal) case in which Byzantine and honest nodes follow the same distribution across IP blocks. As a result, they are indistinguishable from the point of view of rank 𝑆 (•), which means here that the events 𝑝 ∈ C and selected(𝑝) are independent. This independence implies that 𝐶(C, B) = Pr (𝑝 ∈ C|selected(𝑝))

= Pr (𝑝 ∈ C)

= |C| |C|+|B| . (11)
B DERIVING EQUATION ( 5)

Based on the result from the coupon collector's problem, the expected number of uniformly distributed (non-distinct) correct peer identifiers that must be received in order to learn ∆𝑐 new distinct correct peer identifiers amongst 𝑄, when 𝑐 0 are already known, is:

(12) 𝑄 𝑄 -𝑐 0 + 𝑄 𝑄 -𝑐 0 -1 + • • • + 𝑄 𝑄 -𝑐 0 -∆𝑐 + 1
The number of uniformly distributed peer identifiers received between the two resets is at least the following expression: where 𝑘 𝜌 is the duration of the considered time slice, 𝑣 is the number of peer identifiers exchanged at each exchange step, 𝜏 is the time between two exchange steps, 𝑐 0 𝑓 𝑛+𝑐 0 is the probability that the exchange was conducted with a correct peer, and (1 -𝑓 ) is the probability that each of the peers of the returned view is correct.

We bound the value of (12) as follows:

Algorithm 2 : 6 𝑖

 26 Simplification of Algorithm 1 for theoretical analysis of Section 4.2 1 function updateSample([𝑝 1 , . . . , 𝑝 𝑣 ]) 2 for 𝑖 ∈ 1, . . . , 𝑣 do 3 for 𝑝 ∈ [𝑝 1 , . . . , 𝑝 𝑣 ] do 4 if view[𝑖] = ⊥ or ℎ(⟨seed[𝑖], 𝑝 ⟩) < ℎ(⟨seed[𝑖], view[𝑖]⟩) then view[𝑖] ← 𝑝 5 function selectPeer() ←rand(1, . . . , 𝑣); return view[𝑖]

Figure 3 :

 3 Figure 3: Our algorithm (boxes, blue) consistently provides samples that contain fewer Byzantine nodes than our competitor, Brahms, in a variety of situations. A proportion of 1 of Byzantine samples, as exhibited in Fig 3a for the highest values of 𝑓 , corresponds to a situation where malicious nodes are able to cause a network partition. Results shown for a network size of 10000 nodes, with a base proportion 𝑓 = 0.1 of malicious nodes. Base values for other parameters are 𝑣 = 160, 𝜌 = 1, 𝐹 = 10. BASALT corresponds to the complete version of our algorithm, whereas BASALT-simple corresponds to Algorithm 1 without the hardening mechanism (modifications of Algorithm 2).

Figure 4 :

 4 Figure 4: Time to convergence within 25% of optimal proportion of Byzantine samples, for 𝑛 = 1000, 𝑣 = 100 (on the right part, Brahms does not converge within experiment time)

Figure 5 :Figure 6 :

 56 Figure5: Algorithm convergence on several graph quality metrics, for 𝑛 = 10000, 𝑓 = 10%, 𝐹 = 1, 𝜌 = 0.5, 𝑣 = 160. On all metrics, lower is better: we see that BASALT converges much more rapidly than Brahms.

Figure 7 :

 7 Figure 7: Behaviour of AvalancheGo modified with BASALT running on the public AVA network, 5-hour experiment. On the left, nodes that are alone in their IP prefix are sampled the most frequently. On the right, nodes that belong to IP prefixes where other network nodes are present are sampled less often.

( 14 )( 1 -

 141 [START_REF] Guerraoui | The consensus number of a cryptocurrency[END_REF] ≤ ∆𝑐 𝑄 𝑄 -𝑐 0 -∆𝑐 Moreover, we have (12) ≥ (13). Thus: 𝑓 )thus ∆𝑐𝑄𝜏𝜌(𝑓 𝑛 + 𝑐 0 ) ≥ 𝑘𝑣𝑐 0 (𝑄 -𝑐 0 -∆𝑐)(1 -𝑓 ) thus ∆𝑐 ≥ 𝑘𝑣𝑐 0 (1 -𝑓 )(𝑄 -𝑐 0 ) 𝑄𝜏𝜌(𝑓 𝑛 + 𝑐 0 ) + 𝑘𝑣𝑐 0 (1 -𝑓 )which is the result of Equation (5).

Table 1 :

 1 Parameters of the BASALT algorithm and of its environment.

		Environment parameters
	𝑛	Number/equivalent number of nodes	1000, 10000
	𝑓	Fraction/equivalent fraction of malicious nodes	10%, 30%
	𝑄	Number of correct nodes	= (1 -𝑓 )𝑛
	𝐹	Attack force (described in Sec. 4.2.1)	≥ 0
		Algorithm parameters
	𝑣	View size	50 to 200
	𝜏	Exchange interval	1 time unit
	𝜌	Sampling rate (peers per time unit)	∼ 1
	𝑘	Replacement count	up to 𝑣/2
		Theoretical model variables
	𝑡	Time
	𝑐(𝑡 )	Number of correct node identifiers seen	0 ≤ 𝑐(𝑡 ) ≤ 𝑄
	𝑏(𝑡 )	(Equivalent) number of malicious node identifiers seen	0 ≤ 𝑏(𝑡 ) ≤ 𝑓 𝑛
	𝐵(𝑡 )	Probability of sampling a Byzantine node	=	𝑏(𝑡 ) 𝑏(𝑡 )+𝑐(𝑡 )

Table 2 :

 2 Institutional attack: power 𝑓 of the adversary, defined as the equivalent fraction of malicious nodes, for different sampling methods, supposing biggest Internet service provider as an adversary (∼ 10 8 IP addresses, distributed over 5739 blocks), on the IPv4 network. Data sourced from the GeoLite2 Block/ASN dataset.

	# of honest IPs (𝑄)	100	1000	10000
	Uniform		99.9999% 99.999% 99.99%
	By /8 prefix		49%	28%	27%
	By /16 prefix		95%	64%	17%
	By /24 prefix		99.98%	99.8%	98%
	Hierarchical		47%	21%	10%
	Probability of Byzantine samples (lower is better)	0.0 0.2 0.4 0.6 0.8 1.0	10 7 Number of attacker IP addresses uniform by /16 prefix hierarchical (B s )	10 8

Figure

2

: Institutional attack: probability of sampling a Byzantine node with different ranking functions, calculated for the 100 biggest Internet ASes supposing that each of them is the attacker, and that 1000 honest nodes are uniformly spread amongst remaining IP address space. Data sourced from the GeoLite2 Block/ASN dataset. Horizontal axis: number of IP addresses controlled by the AS. The sampling probability is calculated from the equivalent fraction by using Equation

Table 3 :

 3 Observed proportion of samples that are nodes controlled by the adversary in our live experiment (seeSection 6)

	Algorithm	Adversary samples
	Full knowledge uniform sampling	18.4%
	BASALT-uniform	17.5%
	BASALT (hierarchical)	1.13%
	True proportion of Byzantine nodes	18.8%

Other than using more memory, increasing the view size has a non-negligible networking cost as one would typically keep an open TCP connection ready for each peer of the current view. Alternatively, the samples' randomness could be increased by keeping a log of recently closed connections and re-injecting these peer identifiers when selecting new seeds.

https://github.com/basalt-rps/basalt-sim.