SABRE: Protecting Bitcoin against Routing Attacks

BY KEYHUNTER 05.03.2025
SABRE: Protecting Bitcoin against Routing Attacks

Routing attacks remain practically effective in the Internet today as existing countermeasures either fail to provide protection guarantees or are not easily deployable. Blockchain systems are particularly vulnerable to such attacks as they rely on working, Internet-wide communication to reach consensus. In particular, Bitcoin—the most widely-used cryptocurrency—can be split in half by any AS-level adversary using BGP hijacking.

In this paper, we present SABRE, a secure and scalable Bitcoin relay network which relays blocks worldwide through a set of connections that are resilient to routing attacks. SABRE runs alongside the existing peer-to-peer network and is easily deployable. As a critical system, SABRE design is highly resilient and can efficiently handle high bandwidth loads, including Denial of Service attacks.

We built SABRE around two key technical insights. First, we leverage fundamental properties of inter-domain routing (BGP) policies to host relay nodes: (i) in locations that are inherently protected against routing attacks; and (ii) on paths that are economically-preferred by the majority of Bitcoin clients. These properties are generic and can be used to protect other Blockchain-based systems. Second, we leverage the fact that relaying blocks is communication-heavy, not computation-heavy. This enables us to offload most of the relay operations to programmable network hardware (using the P4 programming language). Thanks to this hardware/software co-design, SABRE nodes operate seamlessly under high load while mitigating the effects of malicious clients.

We present a complete implementation of SABRE together with an extensive evaluation. Our results demonstrate that SABRE is effective at securing Bitcoin against routing attacks, even with deployments as small as 6 nodes.

I. INTRODUCTION

Cryptocurrencies, and Bitcoin in particular, are vulnerable to routing attacks in which network-level attackers (i.e., malicious Autonomous System or AS) manipulate routing (BGP) advertisements to divert their connections. Once on-path, the AS-level attacker can disrupt the consensus algorithm by partitioning the peer-to-peer network. Recent studies [15] have shown that these attacks are practical and can significantly disrupt the cryptocurrency. Specifically, any AS-level attacker can isolate ~50% of the Bitcoin mining power by hijacking less than 100 prefixes [15]. Such an attack can lead to significant revenue loss for miners and enable exploits such as double spending.

Problem Protecting against such partitioning attacks is challenging. On the one hand, local (and simple) countermeasures [15] fail to provide strong protection guarantees. These include countermeasures such as having Bitcoin clients monitor their connections (e.g., for increased or abnormal delays) or having them select their peers based on routing information. On the other hand, global counter-measures are extremely hard to deploy. For example, systematically hosting Bitcoin clients in /24 prefixes (to prevent more specific prefix attacks) requires the cooperation of all Internet Service Providers hosting Bitcoin clients (which is highly unlikely) and would increase the size of the routing tables. Even heavy protocol modification such as encrypting all Bitcoin traffic would not be enough to guarantee the system’s safety against routing attacks as the attacker can still distinguish the traffic from the headers and create a partition.

Our work In this paper we address the fundamental shortcomings of existing counter-measures. Specifically, we aim at developing techniques that can secure a system like Bitcoin against routing attacks in a way which: (i) provides strong security guarantees; (ii) is partially deployable, i.e., it should minimize the involvement of third parties; (iii) provides security benefits early-on in the deployment.

SABRE: A Secure Relay Network for Bitcoin We present SABRE, a secure relay network which runs alongside the existing Bitcoin network and which can protect the vast majority of the Bitcoin clients against routing attacks. SABRE is partially deployable and starts to be useful with as little as two relay nodes. SABRE provides strong security guarantees to any connected client—without increasing its load—by enabling it: (i) to learn the latest mined blocks; and (ii) to propagate blocks network-wide, which is essential for miners. We built SABRE based on two key insights:

Insight #1: Hosting relays in inherently safe locations The first insight is to host SABRE relay nodes in locations: (i) that prevent attackers from diverting relay-to-relay connections, guaranteeing SABRE network integrity; and (ii) that are in paths which are—from a routing viewpoint—attractive to many Bitcoin clients, thus reducing the likelihood that attackers will be able to intercept connections to the relay network. To this end, we leverage a fundamental characteristic of BGP policies, namely, that connections established between two ASes which directly peer with each other and which have no customers cannot be diverted. Only such ASes are considered for relay locations. Some of these candidates are also well-connected, making their advertisements attractive. Through a thorough measurement study (using real routing data), we show that such safe locations are plentiful in the current Internet with 2000 ASes being eligible. These ASes include large cloud providers, content delivery networks, and Internet eXchange Points which already provide hosting ser- SABRE nodes, e.g., for a fee. We also show that 6 SABRE nodes are enough to protect 80% of the clients from 96% of the AS-level adversaries (assuming worst case scenario for SABRE).

Insight #2: Resiliency through soft/hardware co-design

As a publicly-facing and transparent network designed to protect Bitcoin, SABRE is an obvious target for attackers who could, among others, craft (D)DoS attacks against its publicly-known nodes to disrupt it. The second insight behind SABRE is to leverage the fact that: (i) the content (blocks) that the relays need to propagate at any given moment in time are predictable and small in size; and that (ii) most of the relay operations are communication-heavy (propagating information around) as opposed to being computation-heavy. These two facts enable us to use caching and offload most operations to hardware, in particular, to programmable network devices. This software/hardware co-design enables SABRE relay nodes to sustain Tbps of load even when originating by malicious actors (DDoS attackers).

We show that our relay node design is practical by implementing in the P4 programming language [17], [13], the default language for programming network data planes, alongside the (UDP-based) client-side protocol. Our experiments indicate that P4 is general enough to support SABRE and the memory requirements are within the capabilities of today’s switches.

Contributions

Our main contributions are:

  • The design of SABRE, a novel relay network that prevents AS-level adversaries from partitioning it (Section III).
  • An algorithm for positioning SABRE nodes in cherry-picked ASes in order to optimize the security guarantees they provide to the system they aim at protecting, in our case Bitcoin (Section IV).
  • A novel software-hardware co-design for SABRE relay nodes that enables them to operate under high load, with minimum software intervention (Section V).
  • A thorough measurement study showing the effectiveness of SABRE in protecting Bitcoin clients. In contrast, we show that existing relays networks provide no protection (Section VI).
  • A complete implementation of SABRE, including the P4 code to run on programmable network switches [7] along with an extension to the Bitcoin client code enabling it to connect to a SABRE node (Section VII).
  • An analysis of the incentives for candidate ASes to host SABRE nodes (Section VIII). Among others, we show that eligible candidate ASes already include well-known cloud providers, which already provide hosting services.

Generality

Although SABRE focuses on Bitcoin, which is by far the most successful cryptocurrency to date, its routing and system design principles can be applied to protect any other Blockchain systems whose connections are publicly routed over the Internet (including permissioned and encrypted ones) from routing attacks. We discuss the broader applicability of SABRE in Section IX.

II. Background

In this section, we first present an overview of BGP and how it can be misused to perform routing attacks (Section II-A). We then briefly introduce Bitcoin and the concept of relays (Section II-B).

A. Border Gateway Protocol (BGP)

The Internet consists of over 60k individual networks known as Autonomous Systems (ASes), which rely on BGP [46] to exchange information about how to reach 700k+ IP prefixes [10]. Each AS originates one or more IP prefixes which are then propagated AS-by-AS.

Policies

BGP is a single-path and policy-based protocol. Each AS selects one single best route to reach any IP prefix—including self-owned ones—that it selectively exports to its neighboring ASes (omitting the AS from which it learned the route). These selection and exportation processes are governed by the business relationships each AS maintains with its neighbors. The most common business relationships are known as customer-provider and peer-peer [25]. In a customer-provider relationship, the customer AS pays the provider AS to get full Internet connectivity. The provider provides such connectivity by: (i) exporting to the customer all its best routes; and (ii) exporting the prefixes advertised by the customer to all its neighbors. In a peer-peer relationship, the two ASes connect only to transfer traffic between their respective customers and internal users. They therefore only announce their own prefixes, and the routes learned from their customers to each other. Regarding route selection, an AS prefers customer-learned routes over peer-learned ones and peer-learned routes over provider-learned ones. If multiple equally-attractive routes exist (e.g., if two customers announce a route to the same prefix), an AS favors the route with the minimum AS path length towards the prefix before relying on some arbitrary tie-break [46].

Hijack

BGP routers do not validate route advertisements. Any malicious AS can create fake advertisements, known as BGP hijacks, for any prefix, and advertise them to its neighbors. Hijacks constitute an effective way for an AS to redirect traffic directed to given destinations.

We distinguish two types of hijacks according to whether the fake announcement contains: (i) a more-specific (longer) prefix than a legitimate one; or (ii) an existing (equally specific) prefix. In the former case, the hijacker AS will attract all the traffic addressed to the more-specific prefix, independently from its position in the Internet topology. This is because routers forward traffic according to the most specific matching prefix. In the latter case, the rogue advertisement will compete with the legitimate one. The amount of diverted traffic then depends on the relative positions of the attacker and the victim in the Internet topology.

Fig. 1: The effectiveness of a malicious AS in diverting traffic using BGP hijacks depends on its position and on whether it originates existing prefixes or longer ones. Here, AS 2 attracts traffic from all ASes when originating 7/24 (a), but only from AS 1 and 3 when originating 7/8 (b).

More-specific hijacks are more powerful but come with drawbacks. First, such attacks are more visible since the hijacked prefixes propagate Internet-wide. In contrast, existing prefixes propagate in smaller regions [28]. For instance, in Fig. 1b, while AS 4 and AS 5 learn about the hijacked prefix, they do not propagate it further as they prefer the legitimate announcement over it. Second, network operators often filter BGP advertisements whose prefixes are longer than /24 [34], thus preventing more-specific attacks against existing /24. Of course, an attacker can still advertise the /24, i.e., an existing prefix.

By default, hijacking a prefix creates a black hole at the attacker’s location. However, the attacker can turn a hijack into an interception attack and make herself a man-in-the-middle (MITM) by preserving at least one path to the legitimate origin [45], [29]. For instance, in Fig. 1a, AS 2 could selectively announce 7/8 to AS 1 to keep a working path to the legitimate origin via AS 3. Observe that AS 2 cannot achieve the opposite interception attack, i.e., divert the traffic from AS 3 and redirect it to AS 1 instead, as it does not learn a path to the legitimate origin via AS 1.

B. Bitcoin

Bitcoin is a decentralized transaction system which relies on a randomized peer-to-peer network to implement a replicated ledger, the Blockchain, which keeps track of the ownership of funds and the balance of each Bitcoin address. The Bitcoin network disseminates two types of information: transactions and blocks. Transactions are used to transfer value from one address to another, while blocks are used to synchronize the state of the system. Bitcoin peers are identified by their IP address, connect to each other using TCP, and exchange data in plain text. Bitcoin comprises around 10k publicly reachable peers [9], and 10× more NATed peers [16].

Blocks are created by miners and contain the latest transactions as well as a Proof-of-Work (PoW). A PoW is a computationally-heavy puzzle, unique for every new block, whose difficulty is regularly adapted such that it takes 10 minutes on average to generate a new block [42]. A newly mined block is propagated network-wide and included in the blockchain according to consensus, thereby yielding a financial reward to its miner. Bitcoin participants unaware of the latest blocks will waste their mining power and can be fooled into accepting invalid transactions.

Relay networks are overlay networks maintained by a single administrative entity which run alongside Bitcoin’s peer-to-peer network. Relay networks aim at assisting the Bitcoin network, not replacing it. As an illustration, the three most well-known relays nowadays are: Falcon [3], FIBRE [2], and the Fast Relay Network (FRN) [5] and aim at speeding up block propagation. These relay networks rely on a system of high-speed relay nodes and/or on advanced routing techniques. By connecting to these relays, a client can alleviate the effects of bad network performance that may otherwise affect the time needed to acquire a new block.

III. SABRE: A SECURE RELAY NETWORK FOR BITCOIN

SABRE is a transparent relay network protecting Bitcoin clients from routing attacks by providing them with an extra secure channel for learning and propagating the latest mined block. By transparent, we mean that the IP addresses of the SABRE relay nodes will be publicly known (e.g., via a website) and that every Bitcoin client is welcome to connect to them. To benefit from SABRE, a Bitcoin client simply needs to successfully establish a connection to at least one relay node. SABRE relays contribute to block propagation by receiving, validating and transmitting new blocks to all connected clients.

To achieve its goals, the SABRE network must remain connected at all times, even under arbitrary routing or DDoS attacks. SABRE leverages two key insights to guarantee connectivity: (i) smart positioning of the relays to secure its internal connections and minimize the clients attack surface (Section III-B); and (ii) a hardware/software co-design to enable relay nodes to sustain almost arbitrary load (Section III-C). We note that these insights can be used to secure other Blockchain systems against routing attacks (Section IX). We start by describing our attack model (Section III-A).

A. Attacker Model

We consider a single AS-level attacker whose goal is to partition the Bitcoin network into two disjoint components.

$S$ and $N$. To do so, she first diverts the traffic destined to $S$ or $N$ by performing an interception attack using existing and more-specific prefixes (Section II). The attacker then: (i) identifies the Bitcoin connections by inspecting the network and/or transport layer headers (i.e., by matching on IP addresses and/or TCP/UDP ports); and (ii) drops the connections bridging the partition. Such an attacker is powerful and can effectively split the Bitcoin network into half [15]. In fact, partitioning any Blockchain system constitutes an effective DoS attack, and can result in revenue loss and allows double spending (see Section IX).

We assume that the attacker knows: (i) the IP addresses of all SABRE nodes; along with (ii) the code running on the relay nodes. As such, the attacker can also hijack the prefixes hosting relay nodes and drop all traffic destined to them. Alternatively, the attacker can perform a DDoS attack on the relay network, by directing load against its nodes aiming at exhausting their resources.

Example We illustrate the attack using Figure 2a and 2b which depict a simple AS-level topology composed of 9 ASes. ASB, ASD ASH and ASG host Bitcoin clients who establish Bitcoin connections to each other (in blue). ASX is malicious and aims at disconnecting the nodes on the left side ($S = {b1, d1, d2, d3}$) from the others ($N = {h1, g1, g2, g3}$). To that end, ASX intercepts the Bitcoin connections directed to $N$ by hijacking ASH and ASG prefixes. As a result, ASX diverts all the connections from $S$ to $N$, and some more (e.g., the connection from $h1$ to $g1$). We depict the diverted connections in red in Figure 2b. Once on-path, the attacker drops the Bitcoin traffic crossing the partition and forwards the rest normally. For instance, the attacker does not drop the connection between $h1$ and $g1$ and simply relays it from ASH to ASG untouched. Once the attack is launched, nodes in $S$ can no longer communicate with nodes in $N$: the Bitcoin network is partitioned.

B. SABRE secure network design

We now explain the routing properties of SABRE node placement that protect relay-to-relay, client-to-relay, and relay-to-client connections from being disconnected. We describe an algorithm for systematically finding such locations in Section IV.

Protecting relay-to-relay connections SABRE network is composed of relay nodes that are hosted in /24 prefix in ASes that: (i) have no customers; (ii) have direct peering connections; and (iii) form a $k$-connected graph.

These constraints secure relay-to-relay connections from routing attacks for four reasons. First, they prevent any attacker from diverting traffic among relays by advertising a more-specific prefix, forcing her to compete with legitimate advertisements, namely to advertise existing prefixes. Indeed, routers will discard any advertised prefix that is longer than /24. Second, these constraints prevent any attacker from advertising an economically strictly better route than the legitimate one. This is because the ASes hosting relay nodes learn the legitimate prefixes via direct peer links and do not have customers, meaning that no malicious AS can advertise a more preferable route. Third, these constraints limit the number of malicious ASes which can advertise an equally-preferable route to only those ASes that directly peer with the ASes hosting relay nodes. Finally, they ensure that the chances for such attackers to divert relay connections decrease exponentially as $k$ (i.e., the connectivity of the relay graph) increases. Indeed, BGP routers rely on an arbitrary tie-break to select among equally-preferred routes (e.g. by choosing routes learned from the lowest peer address [46]). Assuming that the attacker is equally likely to win this tie-breaking, she would only have a $3.1%$ ($0.5^5$) probability of disconnecting a 5-connected relay network. In Section VI, we show that well-connected relay networks are numerous.

Protecting client-to-relay connections While we can selectively place relay nodes (we discuss the incentives for ASes to host relay nodes in Section VIII), we cannot re-position all Bitcoin clients (or host them in /24 prefixes). This means that client-to-relay connections cannot be made inherently secure against all possible AS-level adversaries and active routing attacks.

We protect client-to-relay connections by further restricting where we host SABRE relays to ensure that they not only meet the criteria to secure relay-to-relay connections but also that their respective advertisements will tend to be preferred by ASes with Bitcoin clients over competing ones. Doing so we can lower the amount of traffic a malicious AS can effectively divert, i.e., maximize SABRE’s coverage.

Although, individual relays are unlikely to protect an AS against all possible attackers, a set of relays can often do so. Indeed, this can happen if for each possible AS-level adversary there is a relay who can beat her by offering a better route. As the set of Bitcoin clients tend to be highly centralized [15], we show in Section VI that a relatively small relay network is enough to protect many clients.

Protecting relay-to-client connections Finally, an attacker might try to attack traffic sourced by the relay network to the Bitcoin clients. For instance, an attacker could hijack the prefixes of Bitcoin clients and drop the relay connections by matching on any relay IP address. While this attack is more cumbersome (there are way more clients than relays), it is nonetheless possible. SABRE prevents this attack by obfuscating the traffic exchanged between the clients and the relay nodes, forcing the attacker to perform full inspection (beyond L4 headers) on a possibly huge volume of diverted traffic, henceforth rendering the attack highly impractical compared to the gain. Observe that while encrypting the already-obfuscated traffic would render even full inspection useless, encryption alone would not help as the attacker would still be able to match on the destination IP.

To obfuscate the traffic we suggest two techniques. First, the relays could modify their source IP addresses when sending to the regular clients. This is possible as SABRE uses connectionless communications between the relays and the clients, enabling clients to accept packets with a different source IP than the one they send traffic to. Second, clients could connect to the relay via a VPN/proxy service, forcing the attacker to first find the mapping between the proxy IP and the corresponding bitcoin client.

Example Using Fig. 2c, we now explain how a SABRE deployment of three relays, namely $r_1$, $r_2$ and $r_3$, protects against routing attacks such as the one shown in Fig. 2b by securing intra-relay connectivity and maximizing coverage.

With respect to Fig. 2a, each Bitcoin client is now connected to a least one relay node in addition to maintaining regular Bitcoin connections. Here, nodes $g_1$, $g_2$, $g_3$ are connected to relay $r_1$ while node $g_1$ is also connected to node $r_3$. Hosted in ASes that peer directly, relay-nodes protect their internal connectivity against ASX’s hijacks. For instance, consider that ASX advertises the /24 prefix covering $r_1$ to ASC. Since ASX is a provider of ASC, ASC discards the advertisement as it prefers to route traffic via a peer instead. At the same time, forming a 2-connected graph allows the relay network to sustain any single link cut. This can be caused by a failure, an agreement violation or an unfiltered malicious advertisement from another direct peer such as ASF to ASD. Observe that this would not hold if $r_2$ was not deployed. Finally, the exact positioning of relays is such that the paths towards them are more preferred over those of the attacker. As an illustration, ASX can divert the connection from ASG to ASD by advertising a path with a better preference (as a peer) than the one originally ASG uses (a provider route, via ASF). Even so, ASX cannot divert the connection from ASG to ASB. Indeed, ASG will always prefer its customer path over any peer path.

C. SABRE resilient software/hardware node co-design

As a publicly-known and accessible relay network, SABRE nodes should be able to sustain high load, either caused by legitimate Bitcoin clients or by malicious ones who try to exhaust their resources. To scale, SABRE nodes rely on software/hardware co-design in which most of the operations are offloaded to programmable network switches (e.g., P4-enabled ones). As an illustration, in Fig. 3 two SABRE nodes are connected to each other and to some Bitcoin clients. One client talks directly to the controller via the switch, while the others only to the switch.

Particularly, SABRE’s relay design is based on the observations that: (i) the content that needs to be cached in relay node is predictable and small in size, consisting in the one or two blocks of 1MB that were most recently mined; and (ii) most of the relay operations are communication-heavy, consisting in propagating the latest known block to many clients and distinguishing the new one. The former allows effective caching (extremely high hit rate) while the latter allows for a partially hardware implementation in programmable network devices. This software/hardware co-design enables SABRE nodes to operate at Tbps and therefore sustain large DDoS attacks. Indeed, Barefoot Tofino programmable network devices can deal with as much as 6.5 Tbps of traffic in the backplane [7].

While using programmable network devices enable high performance, it does not make it easy due to the lack of a broad instruction set and the strict limitations with respect to memory and number of operations per packet. We overcome these limitations with three techniques. First, our software/hardware design seamlessly blends in hardware and software operations, enabling to automatically escalate operations that cannot be done in the switch to a software component. In SABRE, only the validation of new blocks (which happen once every 10

minutes) needs to be escalated while all other requests are served by the hardware over a UDP-based protocol. Second, our implementation relies on optimized data structures which are both memory efficient and require a fixed number of operations per-access. Third, we heavily precompute and cache values that would need to otherwise be computed on the switch (e.g., UDP checksums).

IV. SABRE Secure Network Design

In this section, we formally define the problem statement of selecting the relay hosting ASes (Section IV-A) so as to minimize the possibility of a successful routing attack against Bitcoin before presenting an algorithm for solving it in Section IV-B and IV-C.

A. Problem Statement & Challenges

The security provided by SABRE depends on: (i) how secure the intra-relay connectivity is, i.e., how many connections an AS-level adversary needs to hijack to disconnect the graph; and (ii) how much of the Bitcoin network is covered, i.e., how likely it is that an AS-level adversary will be able to prevent each particular client from connecting to all relay nodes.

Thus, given a level of intra-relay connectivity to achieve (e.g., 2-connectivity), our goal is to maximize the Bitcoin coverage. Formally, we define our problem as follows:

Problem statement Let ( G = (\mathcal{AS}, E) ) be the AS-level topology graph in which vertices (( \mathcal{AS} )) correspond to ASes and edges (( E )) to inter-AS links. Let also ( B \subseteq \mathcal{AS} ) be the subset of ASes that host Bitcoin clients and ( R \subseteq \mathcal{AS} ) be the subset of ASes that have no customers. Finally, let ( G’ = G[R, E’] ) be the subgraph of ( G ) induced by ( R ) and the subset ( E’ \subseteq (R \times R) ) of peer-peer inter-AS links. We define ( A = \mathcal{AS} \times B ) as the set of all attack scenarios, namely all pairs of ASes ( (a, b) ) in which ( a ) acts as AS-level adversary for AS ( b ) with Bitcoin clients. Let ( S: R \rightarrow A ) be a function which, given a candidate relay AS, finds the subset ( \alpha \subseteq A ) of attack scenarios that this candidate AS protects against. Let furthermore ( C: \mathcal{P}(A) \rightarrow R ) be a function (( \mathcal{P}(\cdot) ) denotes the power set) which, given a set of attack scenarios ( \alpha \subseteq A ), quantifies their significance for the Bitcoin system by computing the sum of all scenarios in ( \alpha ) weighted by the number of Bitcoin clients hosted in the victim AS, i.e., ( C(\alpha) = \sum_{(x, v) \in \alpha} w_v ) where ( w_v ) is the number of Bitcoin clients in AS ( v ).

We want to find the subgraph ( G” = G'[R’] ) of ( R’ \subseteq R ) such that ( |R’| = N; G” ) is ( k )-connected; and ( C(\bigcup_{r_i \in R’} S(r_i)) ) is maximized. Put differently, we aim—for a fixed number of relays ( N ) and relay inter-connectivity ( k )—at maximizing the number of attack scenarios Bitcoin clients are protected against.

Challenges Solving the above problem optimally is challenging for at least three reasons. First, the effectiveness of any subset of relays ( R’ ) depends on the union of the sets of the attack scenarios each relay ( r \in R’ ) protects against. As these are in general not disjoint, this problem reduces to the maximum coverage problem. Second, finding ( k )-connected subgraphs in a random graph is difficult [20]. Third, one needs to be able to predict the forwarding path from each AS with Bitcoin clients to a relay considering any possible attacker.

We develop a heuristic to address the first two challenges (Section IV-B) and an algorithm for finding the possible attack scenarios for every attacker (Section IV-C).

B. Positioning SABRE Relays

Given a number ( N ) of relays and their desired connectivity ( k ), our algorithm returns a set of ASes ( R’ ) in which to host relays such that the connectivity and size requirements are met and weighted coverage is maximized. This maps to the maximum coverage problem with an additional connectivity constraint. Thus, we use a greedy approach, shown to be effectively optimal for the maximum coverage problem [24].

Our algorithm starts with an empty set ( R’ ) and the set of candidate ASes ( R ) which satisfy the constraints listed in Section III-B and are also contained in at least one ( k )-connected subgraph of at least ( N ) nodes, as only those can host one of the relay nodes of a ( k )-connected network of ( N ) relays. It then iteratively adds relays to ( R’ ) to maximize the number of covered attack scenarios while preserving ( k )-connectivity for ( R’ ). This simple procedure runs in ( O(N) ) and works well in practice (Section VI).

In particular, in each round, we first select as candidates ( R’k \subseteq R_k \setminus R’ ) which are connected with at least ( \min{k, |R’i|} ) of the already-selected ASes in ( R’ ). Then we add the candidate ( r \in R’k ) that offers the maximum weighted extra coverage to ( R'{\text{new}} = R’ \cup {r} ), i.e., the one with the maximum ( C(\bigcup{r_i \in R’{\text{new}}} S(r_i)) – C(\bigcup_{r_i \in R’} S(r_i)) ) and we update the ( R’ := R’_{\text{new}} ). When we have selected all candidates, so that ( |R’| = N ), we return ( R’ ).

We show in Section VI, that the resulting relay networks can readily protect between 80% to 98% of the existing Bitcoin clients (depending on the internal connectivity and number of deployed nodes) from 99% of the potential attackers. The complete pseudocode can be found in the Appendix A, Algo. 1.

While our algorithm’s goal is to minimize the attack vector rather than maximizing the deployment incentives, we discuss those in Section VIII.

Having explained how we can position SABRE relays based on the attack scenarios they cover, we now describe how we compute these scenarios for each relay, i.e., how we implement the function $S$. Specifically, we now describe how we compute the set of AS-level adversaries which can successfully hijack traffic sourced from an AS hosting Bitcoin clients (say $AS\ V$) and destined to a relay AS (say $ASR$).

Our algorithm is based on the observation that if the fake advertisement reaches the victim ($AS\ V$), it will do so via the same propagation path as any other prefix advertised by the attacker $ASM$ and will thus share its preference characteristics. Therefore, to check whether the traffic from $AS\ V$ to $ASR$ with the path from $AS\ V$ to $ASM$. If the path to $ASM$ is more preferred by the last AS that the two paths have in common, then $ASM$ can successfully hijack traffic from an $AS\ V$ to $ASR$. This is because the last AS decides which of the two routes to use and advertise further. Observe, that the last ancestor is $AS\ V$ itself if the paths from $AS\ V$ to $ASR$ and to $ASM$ are disjoint. The preference comparison is based on business relations among the on-path ASes and on the path length; namely, customers are preferred over peers; peers over providers; and shorter paths over longer ones.

As an example, Figure 4 illustrates an AS-topology which is augmented with the economic agreements between ASes. Arrows are reversed with respect to the money flow (if any) with providers being at the top and customers at the bottom. The different shades illustrate how preferred advertisements originating from certain ASes are compared to others in the eyes of $AS\ V$. White is the most preferred and black the least. For example, $AS\ V$ would prefer an advertisement from its customer $ASA$ over any other advertisement ($ASA$ is white). Thus, if a relay is hosted in $ASA$, no AS can divert the connection to it. Among different originators that are reachable via a customer, the shortest path will be preferred. As such, the first layer of customers is lighter than the second, meaning that if a relay is hosted in, say, $ASE$, all of $ASA$, $ASB$, $ASC$, $ASD$ and possibly $ASF$ and $ASG$ are effective possible attackers. Similarly, if a relay is hosted in $V$’s peer, namely $ASH$, all the ASes in the customer cone of $ASA$ are possible attackers, as are ASes of shorter path length in the peer cone. Finally, if the relay is reached via a provider, length is not always relevant: In our example, $ASM$’s advertisement will be less preferred than those from $ASA$-$ASH$, and even less preferred than $ASL$’s one. Although both paths are via a provider, namely $ASI$, and the path to $ASM$ is shorter, the victim will not use it. This is because $ASI$, which is the last common AS of the two paths, prefers the path via $ASJ$ and will not advertise $ASM$. The complete pseudocode can be found in the Appendix A, Algo. 2.

V. SABRE RESILIENT RELAY NODE DESIGN

While a sophisticated software-based implementation of the relay node might work(^2), it will have 2-3 orders of magnitude lower throughput [31] compared to a hardware-based approach making it especially vulnerable to DDoS attacks. On the contrary, a hybrid implementation which utilizes programmable network devices can scale to billions of packets per second and mitigate malicious client directly in the data-plane, namely before they can reach the software component.

In this section, we explain the software/hardware co-design behind a SABRE relay node (Section V-A) and its operations (Section V-B). While the protocol itself is specific to Bitcoin, similar techniques can be applied in other systems. We further discuss this issue in Section IX.

A. Hardware/Software Co-Design

Figure 5 illustrates SABRE’s software/hardware co-design. It is composed of a programmable switch connected to a modified Bitcoin client, the Controller.

The switch is responsible for: (i) serving client connections; (ii) protecting the controller from malicious clients; (iii) propagating blocks; and (iv) distinguishing new blocks from old ones. In contrast, the controller is responsible for validating new blocks, advertising them to the connected clients and updating the switch memory accordingly.

Relay clients establish UDP connections with the switch and rarely regular Bitcoin connections (over TCP) with the controller. Switches only allow approved Bitcoin clients to establish connections with the controller. As most clients “consume” blocks rather than producing them, we expect most clients to only interact with SABRE through UDP connections.

SABRE’s UDP-based protocol is composed of 8 messages: SYN, SYN/ACK, ACK, NCONN, GET_SEQ, ADV, UPD and BLK. Similarly to TCP, SYN, SYN/ACK, ACK are used to prevent spoofing attacks. NCONN is used for notifying

(^2)we discuss the possibility of a software deployment of SABRE in \S VIII

the controller of new connections. GET_SEQ, BLK and ADV relate to block management. Specifically, GET_SEQ enables a client to request a particular segment of a block which is sent as a BLK, while ADV enables a client to advertise a newly mined block to the relay. Finally, a BLK message is also used by the controller after an UPD to update the switch with the latest block.

The switch maintains three data structures to manage client connections and track down anomalies: PeerList, Whitelist, Blacklist. PeerList contains information about connected clients, i.e., those who successfully established the three-way handshake. In contrast, Whitelist maintains information of clients that are allowed to communicate with the controller directly, while Blacklist contains clients that have misused the relay and are banned. The switch also maintains one data structure to store the latest block(s): BlockMem. BlockMem is stored in indexed segments of equal size together with a precomputed checksum for each segment to allow the switch to timely reply with the requested segment avoiding additional computations. Moreover, the switch contains two components devoted to anomaly detection: SentLimit and CheckSecret. SentLimit, detects clients that requested a block too many times, while CheckSecret calculates a hash for verifying whether the clients is using its true IP to connect to the relay node, during the handshake. Finally, the switch also maintains one data structure for checking whether an advertised hash is known: Memhash.

In the following, we describe the different operations performed by the relay and how each of them modifies each of the data structures. In Section VII, we show that our design can sustain 1M malicious and 100k benign client connections with less than 5 MB of memory in the switch. This memory footprint is only a fraction of the memory offered by programmable switches today (tens of megabytes [32]), allowing the switch to implement other applications as well.

B. Relay operations

We now describe SABRE relay operations in detail. The client and controller are extended versions of the default Bitcoin client and the switch is implemented in P4 [17]. Our protocol defines four operations: (i) how regular Bitcoin clients connect to a relay node; (ii) how a relay node propagates blocks back to them; (iii) how a relay node receives and validates blocks transmitted by the clients; and (iv) how the controller updates the switch memory upon the reception of a new valid block. For each operation, the switch ensures that the relay’s resources are not maliciously exhausted.

Managing client connections

In order to avoid spoofing attacks, Bitcoin clients initialize connections to relay nodes using a three-way handshake as shown in Figure 6a. As for a normal TCP connection, the client first sends a SYN packet. Upon receiving the SYN, the switch echoes back a secret value calculated using the client’s IP address and UDP port in a SYN/ACK packet. The client then includes this secret value in the final ACK packet as a proof that it owns the source IP address that it is using.

Upon successfully completing the handshake, the switch adds an entry for the client’s IP and port number in the PeerList and notifies the controller via a NCONN message. The PeerList is implemented as Bloom filter (BF) for memory efficiency. As such, it enables the switch to verify that an incoming packet belongs to an established connection and drop it otherwise. BFs do not support listing all inserted items. as such the controller needs to store the connections for future use (e.g., advertising new blocks and updating the PeerList).

Learning new blocks

Relay nodes need to learn new blocks that are mined. New blocks are transmitted to the relays from regular clients. Being a network device with limited computational capabilities, the switch is unable to validate blocks. Thus, advertised blocks need to be transmitted to the controller after they have been filtered by the switch.

As illustrated in Fig. 7a, the node advertises a block by its hash to the switch using an ADV message. The switch checks whether the hash is already known using the HashMem. If the hash is not known, then the switch asks the client to connect to the controller with a CTR message and stores its IP in the Whitelist. If the transmitted block is legitimate the client’s IP will stay in the whitelist for four days. The client connects to the controller as if it was a regular Bitcoin client, while the switch forwards the TCP traffic to the controller. The switch only allows packets from white-listed clients to reach the controller. Observe that a malicious miner cannot monopolize or overload the controller with its connections as even a pool with 30% of the hash power cannot keep more than 172 whitelisted clients in any given moment.

Yet, a malicious miner might still try to engineer block races.

Fig. 7: BTC client advertises a new Block. The switch identifies it as an unknown block. The client gets white-listed and is thus permitted to connect directly to the controller as if it were a regular BTC client. If the received Block is valid: (b) the controller updates the switch using an UPDATE message carrying the Block’s hash followed by a BLK messages carrying the data.

by flooding the relay node with multiple blocks simultaneously which will need to be validated by the controller. To shield against this attack, the switch keeps the number of active nodes that are white-listed. When this number exceeds a predefined threshold set based on the controller’s hardware capabilities, the switch will stop whitelisting new clients. In this case, the controller receives blocks from the nodes that are already white-listed. These nodes should be diverse enough, with respect to mining power origin, to keep the relay up-to-date, thanks to the expiry mechanism in the Whitelist. For instance, any pool with at least 0.17% of mining power can keep at least one node in the Whitelist forever. In essence, the switch implements a simple yet efficient reputation-based access-list to protect the controller from Sybil attacks.

Updating switch with a new block If a newly-transmitted block is valid, the controller updates the switch’s memory with a new mapping between segment ID and block segment data that corresponds to a particular block hash. The switch can then transmit the segments to the clients upon requests. Observe though that the switch sends data to a UDP socket. Thus, the IP and UDP checksums need be correct for the packet to be accepted. The UDP checksum is calculated using a pseudo-header and the one’s complement sum of the payload split into 16 bits segments. Because computing this in the switch would result in too many computations, we cache the precomputed the one’s complement sum of the block segment together with the segment itself. Using this value the switch needs only to add the header parts that are different per client.

Figure 7b illustrates the sequence of packets the controller sends to update the switch. Initially, it sends an UPDATE message containing the new hash. This first message tells the switch to prepare its state for the new block. The next messages are sent to transmit each of the segments of the block as well as a precomputed one’s sum of it.

Propagating a newly-learned block The relay node advertises new blocks to all its connected clients who can then request a block segment-by-segment. Blocks are transmitted in multiple individual segments for three reasons: (i) to allow clients to request lost segments independently; (ii) to avoid loops in the data plane which would be otherwise needed as the block does not fit in one packet; and (ii) to protect against amplification attacks.

As illustrated in Figure 6b, the controller sends an INV message which is forwarded by the switch. This INV message contains the hash of the new block as well as the number of segments necessary. In the example, the relay advertises hash #5 which is composed of 23 segments. If the Bitcoin client is unaware of the advertised block, it requests it using a GET_SEG message containing the hash of the block and each of the 23 segment IDs. In the example, the client first requests the segment of ID:1 of the block with hash #5 then the segment of ID:2 and so on. If either the GET_SEG or the SEG is lost the client will simply request the corresponding segment again.

As a protection mechanism, the switch bans clients that request a block multiple times. To that end, all requests traverse a heavy-hitter detector, namely SentLimit. In SABRE, we just reuse a component optimized for programmable switches [47] which can operate with just 80KB of memory.

VI. NETWORK ARCHITECTURE EVALUATION

In this section, we evaluate SABRE’s efficiency in protecting Bitcoin against routing attacks. Specifically, we answer the following questions: How effective is SABRE in preventing routing attacks targeted against the entire network and individual clients? How does this effectiveness change with the size and the connectivity of the SABRE network? How does SABRE stand out against other relay networks and known counter-measures?

We found that even a small deployment of 6 single-connected SABRE nodes can prevent 94% of ASes in the Internet from isolating more than 10% of the Bitcoin clients; while larger deployments of 30 relays that are 5-connected can prevent more than 99% of the ASes from isolating more than 20% of Bitcoin clients. In addition, we show that existing relay networks, like Falcon [3] and FIBRE [2], offer no protection against routing attacks. Finally, we show that SABRE provides security level on-par with hosting all clients in /24, an effective but clearly impractical solution.

We start the section by describing our methodology (Section VI-A) before presenting our results in detail.

A. Methodology

Datasets Our evaluation relies on a joint dataset combining routing and bitcoin information. Regarding routing information, we rely on the AS-level topology and AS-level policies provided by CAIDA [1], collected in May 2018. We rely on the routing tree algorithm [29] to compute the forwarding path followed between any two ASes. We consider that the paths originated by an attacker AS are systematically picked at the tie-breaking state of the BGP decision process (the worst-case for SABRE)(^4). Regarding Bitcoin information, we rely on the IPs of Bitcoin clients from [8] along with the IPs of existing relay nodes from [2], [3], both collected in May 2018.

We merge the two datasets by associating each Bitcoin IP to the AS advertising the most-specific IP prefix covering it (using the routes collected by RIPE BGP collectors [4]).

B. SABRE security efficiency

SABRE protects against network-wide partitions To evaluate how effective SABRE is against adversaries that wish to partition the Bitcoin network, we quantify how likely it is for a random adversary to be able to disconnect multiple clients from the relay network. The fraction of clients a particular AS can disconnect from the relays poses an upper bound to the maximum partition that she can create in the Bitcoin network, as Bitcoin nodes connected to the relay network cannot be partitioned.

Fig. 8 illustrates how protected the Bitcoin network is depending on the size (N) and internal connectivity (k) of the SABRE network. The graph shows, for each given fraction (y) of Bitcoin nodes, what percentage of ASes would be able to independently disconnect it from SABRE.

For (N = 20, k = 1), less than 3% of ASes are able to prevent a considerable fraction of Bitcoin clients (15%) from connecting to the relay network. In contrast, more than 90% of the clients can be isolated by any AS in the current network [15].

(4)Results for the opposite case, where tie-breaking systematically picks paths originated by relay ASes, can be found in Appendix B.

The mapping between the number of possible attackers and the partition sizes varies with the size and connectivity of SABRE. In particular, increasing the number of deployed nodes decreases the chances that adversaries can divert traffic successfully. On the other hand, decreasing the intra-connectivity requirements (i.e., the value of (k)) allows our algorithm (Section IV) to select from a larger set of relays and thus to form a more effective SABRE. This creates an interesting trade-off between how secure the intra-relay connectivity is and how well the relays cover the existing Bitcoin network. For example, while a SABRE of 6 relays that are connected in full-mesh (5-connected graph) is extremely hard to partition, as the AS-level adversary would need to divert 5 peer-to-peer links, it enables more AS-level adversaries to disconnect a large part of Bitcoin clients from SABRE. For example, 3% of ASes can potentially create a partition including 22% of Bitcoin nodes. In contrast, a 1-connected SABRE allows fewer attackers to perform severe attacks—only 1% of ASes could create a 12% partition—but can be partitioned by a single link failure or successful hijack from a direct peer.

SABRE protects most individual clients To evaluate how effective SABRE protects individual clients, we look at how likely it is for Bitcoin clients to be prevented by a random AS-level adversary from reaching all relay nodes.

Fig. 10 shows, for a given percentage of ASes, what percentage of Bitcoin clients could be attacked and disconnected from SABRE by this percentage of ASes.

We see that 80% of the clients are protected from 96% of the AS-level adversaries even with a SABRE network of only 6 nodes that are 5-connected. There is again a trade-off between secure intra-connectivity and the coverage of Bitcoin clients. For example, a SABRE of 6 1-connected nodes protects 90% of Bitcoin clients from 92.5% of ASes, while a fully connected 6-node SABRE protects from only 89.5% of ASes. Interestingly, increasing connectivity from (k = 3) to (k = 5) does not decrease the protected clients significantly while making disconnecting the relay network almost impossible.

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO