{'fraction_non_alphanumeric': 0.0284234203530775, 'fraction_numerical': 0.008029445845545635, 'mean_word_length': 4.712194362248871, 'pattern_counts': {'":': 1, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Contra-*: Mechanisms for Countering Spam Attacks on Blockchain Memory Pools

Blockchain-based cryptocurrencies, such as Bitcoin, have seen on the rise in their popularity and value, making them a target to several forms of Denial-of-Service (DoS) attacks, and calling for a better understanding of their attack surface from both security and distributed systems standpoints. In this paper, and in the pursuit of understanding the attack surface of blockchains, we explore a new form of attack that can be carried out on the memory pools (mempools) and mainly targets blockchain-based cryptocurrencies. We study this attack on Bitcoin mempool and explore the attack effects on transactions fee paid by benign users. To counter this attack, this paper further proposes Contra-*:, a set of countermeasures utilizing fee, age, and size (thus, Contra-F, Contra-A, and Contra-S) as prioritization mechanisms. Contra-*: optimize the mempool size and help in countering the effects of DoS attacks due to spam transactions. We evaluate Contra-* by simulations and analyze their effectiveness under various attack conditions.


Introduction
Blockchain technology promises to redefine trust in distributed systems by serving as a tamper-proof and transparent public ledger that is easily verifiable and difficult to corrupt. Blockchains use an append-only model backed by Proof-of-Work (PoW), augmenting trust in decentralized Peer-to-Peer (P2P) settings. Due to such features, blockchains are used in cryptocurrencies, smart contracts, auditing applications, decentralized-data storage, cloud, Internet of Things (IoT) and Anti-Counterfeit solutions [2,3,4,5]. The most widespread use of blockchains can be found in crytocurrencies, e.g., Bitcoin, Ethereum, Zcash, Litecoin, Altoins, etc. [6,7,8].
Although blockchains are publicly verifiable and tamperproof, they are vulnerable to attacks [9]. Moreover, since blockchains are most widely used in digital currencies, attackers have a high incentive to exploit them. The cryptocurrency market has experienced a massive growth in the last two years [10], while the number of attacks has also increased [11], including multiple 51% (majority) attacks, selfish mining, double-spending, block withholding, block forks and distributed denial-of-service (DDoS) attacks [12,13,14,15]. Vasek et al. [16] pointed out that DDoS is the most prevalent form of attack that afflicts the Bitcoin users.
In Bitcoin, DDoS attacks are launched against miners, users, and currency exchanges [17]. In P2P systems, DDoS attacks may take various forms. For example, users or miners can be re-routed towards a counterfeit network, denying them access to the real network. Maria et al. [18] estimate that an attacker can isolate more than 50% of the network's hashing power by hijacking a few (<100) BGP prefixes. Moreover, attackers may exploit the blocksize limit and network throughput to prevent benign users from getting their transactions verified. In Bitcoin, the average block size is limited to 1 MB and the average time of block mining is 10 minutes. On average, the transaction size varies from 200 Bytes to 1K Bytes. 2 Under these constraints, Bitcoin can only verify three to seven transactions per second [20], in contrast to mainstream payment processors such as Visa Credit which can verify up to 2000 transactions per second. Low transaction throughput creates a competitive environment where only selected transactions get accepted into a block. It also makes Bitcoin vulnerable to flood attacks [21], where malicious users exploit the block size limit in Bitcoin (≈1 MB) 3 to overwhelm the blockchain with low-valued spam transactions. This further causes delay in verification of benign transactions. To prevent such attacks that exploit block size limit, miners in Bitcoin apply priority checks on the incoming transactions. The priority is given to the transactions which offer higher mining fee. Once high priority transactions are verified and mined into a block, low priority transactions are queued into a memory pool where they await confirmation.
In Bitcoin, memory pool (mempool) acts as a repository where all the transactions waiting to be confirmed are logged. Once a user generates a transaction, it is broadcast to the entire network. The transaction is stored into the mempool where it waits for confirmation. If the rate of incoming transactions at mempool is less than the throughput of the network (3-7 transactions/sec), there is no queue of unconfirmed transactions. Once the rate increases beyond the throughput, a transaction backlog starts at the mempool. Transactions that remain unconfirmed for long eventually get rejected. On November 11, 2017, the mempool size exceeded 115k unconfirmed transactions, resulting in USD 700 million worth of stall transaction [24]. As the mempool size grows, users pay more mining fee per transaction to prioritize their transactions.
In this paper, we identify mempool flooding as an attack that causes denial-of-service for benign users in Bitcoin. We establish a relationship between the mempool size and transaction fee, and demonstrate how attackers can use it to make benign users pay higher than the normal fee. Mempool flooding creates a state of uncertainty among users and they pay higher fee to prevent their transactions from being stuck or rejected in the network [25]. Under current settings, it is easy to flood the mempool with low value spam transactions. Although miners discard spam transactions during the mining process, there is no effective mechanism to prevent spam transactions from flooding the mempool and creating panic among the benign users. We propose Contra-* to defend against the attack. Contributions. We make the following contributions. 1 We identify the effect of mempool flooding on benign users in Bitcoin and the way that effect turns into a DoS attack. 2 We present a threat model and associated attack procedure whereby an attacker can exploit the current Bitcoin protocol to achieve his goals. 3 We propose Contra-* as countermeasures. Contra-* comes in fee-based (Contra-F), age-bases (Contra-A), and size-based (Contra-S), for transaction filtering. The three countermeasures optimize the mempool size, neutralize the attacker's capabilities, prevent mempool flooding, and put benign users at an advantage. 4 We examine the performance of our proposed countermeasures through discrete-event simulations and evaluate their performance under varying attack conditions. To the best of our knowledge, this is the first study to address the problem of mempool attacks in cryptocurrencies with new mitigations. Organization. section 2 outlines the related work, and section 3 outlines the preliminaries. In section 4 and section 5 we describe the threat model and attack procedure that lead to mempool flooding and its associated effect. A modeling framework for analyzing Contra-* as well as evaluation metrics are introduced in section 6. We propose countermeasures in section 7 with their associated analysis. Conclusion and future work are presented in section 8.

Related Work
As described earlier, well-known attacks on blockchains include selfish mining, the 51% attack, block withholding, double-spending, blockchain forks and DoS attacks. In this section, we review notable work covering those attacks, and security aspects of blockchains.
Selfish mining is a form of attack where miners choose not to publish their block after computation, hoping to mine subsequent blocks and get more reward. The problem of selfish mining has been addressed by Eyal and Sirer [26], Sapirshtein et al. [12], Solat and Potop-Butucaru [27] and Heilman [28]. Eyal and Sirer [26] proposed defense strategies to deter selfish mining attacks on blockchains. Block Withholding Attack (BWH), introduced in [29], is an attack in which miners in a pool choose to submit partial PoW, instead of the full proof. As a result, they get rewarded for participating in the pool although the pool suffers a loss due to partial solutions. Kwon et al. [30] studied a new form of attack on blockchains called Fork After Withholding (FAW) attack, an attack in which the rewards are always greater than the rewards of block withholding attacks.
The 51% attack can be launched if a mining pool in the network gains more than 50% of the network's hashing power. With more than half the hashing power of network, the attacker can prevent transactions from verification and other miners from computing a block. To address the attack, the Two Phase PoW (2P-PoW) was proposed by Eyal and Sirer [31] and was analyzed by Bastiaan [32]. Doublespending or equivocation happens when a user generates two transactions from the same inputs and sends them to two recipients [14,33]. Double-spending can be countered by using one-time signatures in blockchains.
DoS attacks have been quite prevalent [16], and are repeatedly launched against the mining pools, benign users, and currency exchanges. Johnson et al. [34] performed a game-theoretic analysis of DDoS attacks against Bitcoin mining pools. Vasek et al. [16] illustrated DoS attacks empirically on the Bitcoin system. Prior to its release on November 12, 2017, Bitcoin Gold suffered from attack [24,35]. Cryptocurrency exchanges have also been frequently targeted to prevent coin tradings [36,37,38], and no specific mitigation to those attacks is proposed.
Another form of DDoS attack on blockchain includes spamming the network with low valued dust transactions. This attack is also called the penny-flooding attack. Baqer et al. [21] performed Bitcoin stress testing to analyze the limitations of the Bitcoin network and how attackers exploit them. Similar to their work, in this paper we analyze the effect of penny-flooding attacks on users when a spam attack is carried out on the mempool of Bitcoin, and complement this analysis with countermeasures through memory pool optimization. To the best of our knowledge, this is the first study conducted to analyze the effect of spam attacks on mempool and explore their countermeasures.

Preliminaries
In this section, we review the preliminaries of this work by highlighting key operations of Bitcoin. We elaborate the terms used in Bitcoin community that are relevant to our work. We assume the reader has a basic understanding of Bitcoin operations and the role of miners in the system. Figure 1 presents an overview of transaction lifecycle in a cryptocurrency such as Bitcoin. In Bitcoin, a user generates a transaction using a spendable balance in his wallet. The spendable balance comprises of "Unspent Transaction Outputs" (UTXO's) [39] that the user previously received from other transactions. UTXO's are confirmed transactions that are part of the blockchain. To generate a new transaction, UTXO's are used as inputs and the transaction is broadcast to the entire network. When users receive a broadcast transaction, they store it into their mempool and forward it to other users. Finally, miners pick the transaction from mempool, validate the authenticity of UTXO's and mine them into a block. Once a transaction is mined, its parent UTXO is removed and the new transaction becomes a spendable UTXO of the recipient. We will refer to Figure 1 to outline the attack vectors related to mempool flooding.

Relay Fee and Mining Fee
Relay fee in Bitcoin is the minimum fee paid for a transaction to be included in a mempool. If a transaction does not include the relay fee, peers in Bitcoin do not forward the transaction to others. As such, the transaction does not make it to the mempool and never gets mined [40].
Mining fee, or transaction fee, is fee paid to a miner as an incentive to include the transaction into a block.
Mining fee of a transaction is equal to the amount remaining after the sent balance is subtracted from the spendable inputs [41]. The mining fee can be considered as an additional reward for miners. Miners tend to prioritize the transactions which pay higher mining fee. Once a transaction gets mined, the relay and mining fee are deducted from the sender's balance. The mining fee is usually greater than the relay fee.

Confirmation
Confirmation of a transaction means that a transaction has been successfully mined into a block. That is, the transaction's parent UTXO's are valid and now it is spendable in a receiver's wallet [42]. A confirmation score of a transaction, also known as the age of a transaction, is the difference between the block number in which it was mined and the most current block computed by the network. A confirmation score of 0 means that the transaction has been broadcast to the network but not mined in any block. Such a transactions is also called an "unconfirmed transaction." In Figure 1, all transactions in the memory pool remain unconfirmed before a miner selects them. As it can be seen in Figure 1, the miner confirms all transactions into a block except Transaction 2, which stays unconfirmed even after the mining process. If no miner selects Transaction 2 in the next 48 hours, it will be flushed from the mempool. Bitcoin developers discourage users from trusting an unconfirmed transaction [43]. Generally, a high age score adds to the confidence that the transaction cannot be reversed due to sufficient PoW [44]

Memory Pool
In Bitcoin, a memory pool (mempool) can be viewed as a cache that stores all unconfirmed transactions. A transaction that pays a minimum relay fee gets relayed between nodes in the network. Furthermore, every full client in the Bitcoin network has a mempool that caches the incoming transactions [45]. Once a transactions is mined, it is removed from the mempool and included in the blockchain. If a transaction does not get mined for a long time, mempools discard it. The mempool acts as a bottleneck in the network where pending transactions are stored before they are mined. As a result, if the transactions' arrival rate exceeds their mining rate, the mempool size grows and the verification gets delayed. A growing mempool size corresponds to growing unconfirmed transactions.

Dust Transactions
In the initial Bitcoin design [46], the minimum transaction input was one satoshi, or 10 −8 of a bitcoin. When the number of Bitcoin users and associated transactions increased, the threshold for the minimum transaction was raised, and is currently 5,460 satoshi [47]. Transactions with small input values are known as "dust transactions" [48], and contribute little to the exchange volume of Bitcoin but consume space in a block. Bitcoin's spam attacks often use dust transactions [21].

Throughput
The block size in Bitcoin is restricted to 1 MB. Furthermore, the average block computation time is 10 minutes, and Bitcoin adjusts its difficulty parameter every 2016 blocks (2 weeks). The difficulty adjustment is based on the aggregate hashing power of the network: on average, in 10 minutes a total transaction volume of ≈1 MB can be verified by the system. This amounts to a network throughput of 3-7 transactions per second [49]. Compared to its competitors such as Ethereum, Bitcoin's throughput is small, making it more vulnerable to spam attacks.

Mining Priority
Bitcoin addresses the problem of spam transactions by giving miners a full control over the transaction selection policy [50], inevitably leading miners to mine transactions with more fee per size. For instance, given two transactions, t i and t j , in the mempool where t i has a size of 300 bytes with 15 BTC output and pays a mining fee of 0.05 BTC, whereas t 2 has a size of 200 bytes with 3 BTC output and pays a mining fee of 0.9 BTC (transaction fee per byte becomes 0.0017 BTC/byte and 0.0045 BTC/byte for both transactions respectively), the miner will prefer t 2 , owing to more mining fee per size. Clearly, the miner's control over transaction selection prevents spam attacks on the blockchain, although no the mempool.

DoS Attack on Mempools
There are two types of DoS attacks on blockchainbased cryptocurrencies. In the classical attack, the attacker exploits the size limitation of Block (≈1 MB in Bitcoin) and the throughput of the network (3-7 transactions per second) and generates dust transactions to occupy the space in the block and prevent other transactions from mining. This type of DoS attack has been addressed by the research community [21] and there are countermeasures adopted by the miners to prevent it. The miners prioritize the transactions based on fee and select the ones that pay higher mining fee. As such, this prevents the dust transactions from occupying space in the block and preventing benign transaction from mining. The other form of DoS attack is the attack on the mempools of cryptocurrencies. In this attack, the attacker floods the mempools in Bitcoin by generating a series of unconfirmed dust transactions. Although, these transactions may be rejected by the miners eventually but their presence in mempool creates another major problem. In Bitcoin, the size of mining pool determines the fee paid to the miners. If the mempool size is big, miners have a limited choice of mining the transactions and as a result the users try to prioritize their transactions by paying higher mining fee. Therefore, if an attacker creates a situation where he floods the mempool with dust transactions, he might trap the benign users into paying a higher mining fee. On the other hand, the attacker's dust transactions get rejected by the miners due to low fee and he can launch the same attack again without being penalized. The correlation between the size of the mempool and the fee paid to the miners can be observed in Figure 2. Furthermore, this attack has been reported in the news, but it has not been addressed by the research community. To outline the fundamentals of this attack, we refer to Figure 1, in which it can be seen that the role of miners come after the mempool is filled with transactions sent by the users. One such attack on Bitcoin mempool was carried out on November 11, 2017, when the mempool was chocked with over 115k unconfirmed transactions resulting into a rise in the mining fee and transaction confirmation time [24].

Data Collection
To observe the relationship between the size of the mempool and the fee paid by the users, we used the public dataset provided by the company called "Blockchain" [51,52] which is a leading software platform that keeps record of digital assets of cryptocurrencies including Bitcoin. For our study, we gathered the dataset of mempool size and fee from January 2017 to November 2017. Blockchain monitors the size of mempool in terms of the number of transactions or the aggregate size of all the transactions. For this study, we use the number of transactions in the mempool to be our method for determining the size of the mempool. Furthermore, the fee paid to the miners is measured in bitcoins/KB per transaction. In Figure 2, we plot the results obtained from the dataset and we use the min-max normalization to scale our dataset in the range [0, 1]. The min-max scaling is conducted as z = xi−min(x) max(x)−min(x) . Our data shows that Bitcoin mempool has been attacked three times in 2017, resulting in a higher mining fee.

Threat Model
In this work, we assume that the attacker is a full Bitcoin client with a complete blockchain and a memory pool at his machine. The attacker's wallet has spendable bitcoins denoted by "UTXO's"; those bitcoins have been previously mined into the blockchain. In Bitcoin, transactions can be split into various small transactions [46]. We assume that the balance in the attacker's wallet is large enough that it can be split into fractions of dust transactions; each of those transactions is at least capable of paying the mining fee. We assume also that the attacker controls a group of sybil accounts, each with multiple public addresses. These public addresses could be used to exchange transactions during an attack. The attacker and the sybil accounts have an apriori knowledge of each others' public addresses. Furthermore, the attacker and sybils have client side software and scripts [53,54], which enable them to initiate a flood of "raw transactions" [55] in a short time span. We assume that Sybils (collectively) have a capacity of exchanging transactions at a much higher rate than the network's throughput [49].
Although, being a full client in the network, we assume that the attacker does not have the capability of mining transactions. This means that the attacker does not possess enough computational power to mine a block, discard a transaction, reverse a transaction or delay other transactions from being mined. Moreover, the attacker does not have control over other benign users in the network and, as such, cannot prevent them from broadcasting their transactions and accessing mempool nor other resources in the network. The attacker is also constrained by a "budget": since every transaction requires a minimum fee to be relayed to the network, the fee limits the number of transactions that an attacker can generate. Attacker's Goal. The end goal of the attacker is to flood mempools in the network with dust transactions. The attacker will broadcast dust transactions at a higher rate than the throughput of the network. At mempools, the arrival rate corresponds to the flow of incoming transactions and the departure rate corresponds to the rate of transaction mining. The departure rate is fixed, because the average block computation time and the size of the block are currently fixed. When the arrival rate increases due to a flood of dust transactions, it results in transactions backlog. As the queue size grows, the mempool size increases accordingly. Overwhelming the mempool size alarms the benign users, who naturally start paying higher mining fee to prioritize their transactions.
Upon flooding, a secondary objective of the attacker is to reduce the cost of attack by causing the mempool to reject his transactions. For the attacker, mining transactions will result into losing the associated mining fees to the miners. However, if the transactions get rejected, the attacker will have another chance to launch attack.
In the prior work, the target of attack was either a mining pool [34], a Bitcoin exchange [56] or the blockchain itself [21], leading to various avenues of DoS attacks. In our work, on the other hand, the target of the attack is the mempool of the system outlined in Figure 1, while the potential victims in every attack are the benign users in the blockchain network who are denied service. Another distinguishing feature of this threat model is that the attacker does not want his transactions to be mined. In the analysis performed by Baqer et al. [21], the intent of the spam attack was to flood blocks in the blockchain by exploiting the block size limit. Such an attack requires transaction mining in the blockchain. In Bitcoin, the gap between the block size and the mempool size presents an opportunity that can be exploited for an attack. 4 Note that mempool flooding in the network does not require require transaction mining. Moreover, attacks exploiting block size can be effectively countered by miners while the attack on mempools cannot be countered in the same way. As transaction mining involves mining fee while the attack objective is only mempool flooding. Therefore, transaction acceptance in a block remains undesirable for the attacker in this attack. According to the taxonomy of DoS attack [59], the mempool flooding attack can be characterized as a "semantic attack of variable rate."

Attack Procedure
As mentioned earlier, when the rate of incoming transactions exceeds the network's throughput, a backlog of unconfirmed transactions builds up at the mempool. As backlog grows, competition for transaction mining also increases. Users try to prioritize their transactions by offering more fee to the miners. As a result, the fee per transaction paid to the miners increases. To facilitate usage, there are online services such as "Bitcoin Fee Estimation" [60], which estimate mempool size and the average fee paid per transaction. Therefore, a fee is recommended for users who want their transactions confirmed within desired time.
Since the mempool size affects the way users pay the mining fee, this creates an attack possibility for an attacker to exploit the mempool size and create panic among benign users. When a benign user sees the mempool size growing, the user, as a rational agent, will try to prioritize his transactions by adding more mining fees to them. Dust transactions of an attacker will eventually be rejected by the miners, to protect blockchain from spam. Although it protects the system from spam, that policy in itself also works in favor of the attacker, since the attacker loses no bitcoins as a result of enforcing this policy. On the other hand, benign users end up paying more than the required fee to get their transactions confirmed. Upon rejection, the attacker can re-launch the attack multiple times. Notice that one of the addresses as an output is used as the input address to the next transaction. The difference in the output balance and input balance is the fee paid by the transaction. The figure shows that unconfirmed transactions can be spent prior to confirmation and while they may not be selected by the miners, they still overwhelm the mempool. This depicts the attack model where Sybils exchange unconfirmed transactions at a high rate. Figure 2, there is a high correlation between the mempool size and the transaction fee paid to the miners. In May, August and November 2017, it was reported [61,24] that Bitcoin was under spam attack of unconfirmed transactions which led to higher mining fee. From Figure 2, it can be observed that during those months the size of the mempool was much larger than the average size. As a result, the mining fee pattern also followed similar growing trend as the mempool size. In December 2017, the problem of mempool flooding with was highlighted by crypto analysts [62,63] suggesting that it was an attempt to increase the mining fee and drive the users away from Bitcoin. To further establish the relationship between the mining fee and the mempool size, we computed Pearson correlation [64] on our dataset. The Pearson correlation coefficient is defined as

As shown in
, and from our dataset, we observed a high correlation of 0.69 between the mempool size and the mining fee.
As a result, we conclude that overwhelming the mempool size can also lead to other problems in the blockchain. In November 2017, when the mempool was flooded, USD 700 million worth of bitcoins remained stuck in the pool for two days [35]. Delay in verification can create multiple problems, including possibilities of double-spending.
As described in the threat model, the objective of the attacker is to maximize the size of the mempool and minimize the cost of the attack. The cost of the attack is the fee paid to the miner if a transaction gets mined in a block. The fee consists of the relay fee 5 and the mining 5 The relay fee is a cap implemented by nodes to filter spam transactions. The relay fee threshold can be adjusted in the Bitcoin.conf file [40]. Typically, if a node receives a transaction with 0 fee, the node discards the transaction and does not forward it to other nodes. Therefore, it protects the network from spam transactions. Realizing this utility, we consider the relay fee for our model. fee. Higher fee increases the priority of transaction and chances of a transaction mining [65]. To avoid that, the attacker will design his transactions in a way that they are less likely to be prioritized by miners. At the same time, the attacker wants his transactions to stay in the mempools for as long as possible. As such, this attack can be carried out in two phases: the distribution phase and the attack phase.

The Distribution Phase
In the distribution phase, the attacker estimates the minimum relay fee of the network, divides his spendable bitcoins ("UTXO's") into various transactions and sends them to the sybil accounts. This can be done in two ways. 1) The attacker may generate a dust transaction from previous UTXO, send it to a sybil wallet and get the change back as a new transaction. The attacker uses the change as new input balance and repeats the procedure multiple times for all sybil addresses. 2) An alternative way is to use the spendable balance and generate a series of outputs to all the addresses of sybil nodes. Unlike the previous method, this will result in only one transaction to all the sybil outputs. Transactions of this nature are known as "sendmany" transactions [66], because the user is sending bitcoins to various addresses within one transaction. Since the aim of the attacker is to generate as many transactions as possible, he will not opt for "send many" option. All transactions to the sybil wallets will be generated independently. The transactions made in the distribution phase will have input "UTXO's", which will be previously mined in the blockchain. Hence, these transactions will have greater-than-zero age (confirmation score), and will be capable of paying the minimum mining fee.

The Attack Phase
Once the distribution phase is completed, all sybil accounts will have sizable balance in their wallets. In the attack phase, all sybils will carry out "raw transactions" [55] from the balance received in the distribution phase. Sybils will generate dust transactions and exchange them with each other. To maximize the severity of attack, they will prefer to have one recipient per transaction. The rate of transactions will be much higher than the throughput of the network. As a result, the arrival rate of the transactions at the mempools will be higher than the departure rate of mined transactions. This will increase the transaction backlog and the size of the mempools over the duration of the attack. The attack will be carried out until all the spam transactions get into the mempools. The transactions made in the attack phase will have the transactions of distribution phase as input "UTXO's". These inputs will still be awaiting confirmation in the blockchain. As such, their confirmation factor or age score will be zero.

Attack Illustration
In Figure 3, we provide an illustration of such an attack whereby unconfirmed transactions were exchanged. The letter "U" (in red) shows the unconfirmed transaction. As shown in Figure 3, various transactions were generated to flood the mempool within a short time duration. The user started with one confirmed transaction in the blockchain. The transaction was later split into two transactions (the distribution phase). Out of the two resulting transactions, one was immediately spent. Moreover, the spent transaction was unconfirmed, thus the letter "U" encoded (in red) was used to denote its status. Among all the transactions exchanged, each transaction paid a fee of 8.27 USD, 0 USD, and 4.97 USD, respectively. Compared to the value exchanged in each transaction, the percentage of fee was 0.01%, 0%, and 0.01%. All these transactions had zero confirmation score. The attack phase in depicts a similar case where sybils exchange such transaction at a high rate.

Attack Cost
As mentioned earlier, one of the objectives of attacker is to minimize the attack cost. To be able to achieve that, the attacker requires transactions to be part of the mempool but not part of the blockchain. This can be achieved by adding the minimum relay fee (R f ) to each transaction but not the minimum mining fee (M f ). The relay fee is necessary for a transaction to be broadcast to all peers in the network and be accepted by the mempool. If the attacker adds the mining fee, his transactions will attain priority from a miner and might get mined. To avoid that, the sybils only pay the relay fee. If a transaction has i inputs, where each input contributes a size of k Bytes, and o outputs, where each output contributes a size of l Bytes, then the total size of the transaction S and its associated cost C are determined by (1)-(2), respectively.
Assuming that the attacker is limited by a budget B (BTC) and minimum transferable value set by the network as T min , then, using (2), the total number of transactions T a that the attacker can generate can be computed in (3). At the time of writing of this paper, the minimum transferable value in Bitcoin was 5460 Satoshis [47].
Now we look at the system from standpoint of a benign user. A benign user who intends to get his transaction mined into the blockchain pays relay fee for transaction broadcast and mining fee as an incentive to the miner. For such a user, contributing a total T transactions, the cost incurred per transactions and the total cost of all transactions T l [R f + M f ] can be derived using (4) and (5) .
As mentioned in the threat model (section 4), the aim of the attacker is to increase the cost per transaction paid by the benign user (4). A benign user will aim to have his transactions mined, therefore he will pay relay fee and a high mining fee. The attacker will only aim to get his transactions into the mempool and eventually not get mined, so he will only pay the relay fee. In these settings, the maximum loss an attacker can incur would happen if all his transactions get mined. The cost in such a case will be equal to the product of the total number of transactions and the relay fee (T a × R f ). The attacker can re-launch the same attack with a new balance of B − (T a × R f ). If a portion of the attacker's total transactions t a gets mined, where t a ≤ T a , then the attacker would be able to relaunch the attack with new balance of B − (t a × R f ).

Modelling The Mempool Attack
As mentioned in section 3, mempool acts as a buffer for unconfirmed transactions, where the incoming transactions denote the arrival, and transaction mining represents the departure process. As long as the arrival process is within the bounds of system's throughput (3-7 transactions per second), the mempool queue remains stable and there is no transaction backlog. However, as shown in our threat model, the attacker overflows the buffer by accelerating the arrival process and increasing the queue size. Therefore, to construct effective countermeasures, it is useful to formulate this abstraction as a queuing theory problem with necessary mathematical primitives. To that end, we model the mempool attack as Lyapunov optimization problem that encapsulates the attack procedure and provides a roadmap towards the attack countermeasures.

Lyapunov Optimization
Lyapunov optimization is a popular scheme applied to the field of dynamic control systems for time-average optimization under stability constraints [67]. In queuing networks, Lyapunov drift is used to model the queues while optimizing time-average performance objectives such as the energy or the throughput. Subject to the queue stability, i.e., lim t→∞ is the queue backlog at t, the time-average Lyapunov optimization (i.e., drift-plus-penalty (DPP) [68,69]) is defined as: where y o [t] is the objective function at t. Based on DPP, this time-average optimization subject to queue stability can be formulated as the following decision-making framework: where α[t] is possible decision at t, α * [t] is time-average optimal decision at t, A is a set of possible decisions, V is tradeoff coefficient between optimization criteria and stability, To apply this scheme to the mempool attack, we first model the mempool as a queue and show the arrival and departure processes. We present our design model in Figure 4, where the arrival process consisting of benign and malicious transactions is denoted by a[t], the departure process is denoted by b[t], and the mempool is denoted by Q[t]. Since the mining rate eventually determines the throughput of the network, therefore, we use throughput as the departure process. The control shown in the red allows us to apply countermeasures and modify the queue size. Our objective is to minimize the time-average size, subject to the queue stability. Queue stability can be achieved by removing malicious transactions or limiting the total number of transactions in the queue. The cost is the unwanted removal of benign transactions as an outcome of the applied countermeasure. Therefore, we have two cases that represent the state of the mempool. In the first case, when the mempool is idle, the applied control policy should only remove a small number of transactions to fulfill the objective function of time-average cost minimization. In the second case, when mempool is flooded, the applied control policy should remove a large number of transactions to guarantee mempool size stability. With these objectives, the Lyapunov-based DPP changes to (7) is updated to (8) The formal attack model provides us the following key insights that can be used to develop effective countermeasures for the DoS attack: 1. The mempool acts as a buffer for incoming transactions. Therefore, the countermeasure policy should not only reduce the number of malicious transactions but also ensure the queue stability to ensure operational consistency. 2. Since the network throughput is constant, therefore, we cannot control the rate of outgoing transactions. As such, our countermeasures must be applied at the control knob of the queue.

Evaluation Parameters
We use the following parameters to examine effectiveness of Contra-*; Contra-F, Contra-A, and Contra-S. Precision. Precision is the measure of relevant information obtained from an experiment with respect to the total information. Mathematically it is defined as the ratio of true positive and the sum of true positive and false positive T P T P +F P .

Recall.
Recall is the measure of relevant information obtained from an experiment with respect to the total relevant information. Mathematically, it is defined as the ratio of true positive and the sum of true positive and false negative T P T P +F N . F1 Score. F1 score uses both precision and recall and provides their harmonic average. F1 score can be computed as 2×precision×recall precision+recall Accuracy. In machine learning, accuracy measures the the strength of a classifier in determining the nature of experimental outcomes. Accuracy is can be computed as T P +T N T P +T N +F P +F N . Negative Rate. Negative rate or specificity is the measure of truly identified negatives in the complete set of negative values. Negative rate can be computed as T N T N +F N . We will use this evaluation criteria for all the experiments described in the rest of the paper.

Countering The Mempool Attack
To counter DoS on Bitcoin's mempool, we propose three countermeasures that prevent the spam on the system. The design motivation is to increase the attack cost for the attacker while keeping the operational efficiency for benign users. We develop our designs for a miner's priority and apply the priority check on transactions at the mempool level. One of the effective countermeasures against spam attack in Bitcoin is to prevent the transmission of dust transactions in the network. We envision that if mempools can discard spam transactions and stop relaying them to other mempools, the pool size can be effectively controlled and spam can be countered.

Contra-F: Fee-based Mempool Design
Fee-based design aims to optimize the size of mempool by filtering spam transactions upon arrival. As the threat model states, an attacker only intends to relay spam transactions between the mempools and does not want them to be mined. To achieve this goal, the attacker only pays minimum relay fee in transactions so that mempools accept and relay them. To prevent the transactions from mining, the attacker does not pay the mining fee. We use this insight to construct a "Fee-based Mempool Design." For this design in Algorithm 1, we assume that the mempool is initially empty when transactions begin to arrive. We also assume that each incoming transaction has its associated relay fee and mining fee. We also fix a threshold beyond which the mempool starts spam filtering. Initially, when the transactions arrive in the pool, and for each transaction, the mempool checks if the transaction pays a minimum relay fee. If the transaction pays the minimum relay fee, it is accepted and the mempool size is updated. As the transactions get added into the mempool, the size of mempool grows. When the size reaches a threshold, the mempool starts applying the fee-based policy. Now, if the incoming transaction pays both the minimum relay fee and the minimum mining fee, only then it is accepted in the mempool. The key idea behind this scheme is that only those transactions should be accepted, which eventually get mined into the blockchain. As a result, this technique puts a cap on the incoming transactions and filters spam transactions, thereby reducing mempool size. If the new size is less than the baseline size threshold then the mempool can proceed its operation from relay fee check. Otherwise, it will continue with the fee-based design.

Analysis of Contra-F
In the following, we will analyze the workings of feebased design and its utility in light of our threat model. We will limit the number of transactions an attacker can generate within his budget by increasing the mining fee threshold. We also observe how this design affects other benign users within the same network.
In the current settings of Bitcoin, where an attacker only pays the relay fee to broadcast his transactions, if the based DPP changes to (7) is updated to (8), where C(↵[t]) is power consumption when our decision is ↵[t]. If the mempool is empty (Q[t] = 0), we have to minimize our cost by permitting more arrivals. If the mempool is flooded (Q[t] ⇡ 1), we have to minimize (↵[t]) by removing malicious transactions and stabilizing the mempool size.

↵ ⇤ [t] arg min ↵[t]2A {V · C[↵[t]] + Q[t]a(↵[t])} (8)
The formal attack model provides us the following key insights that can be used to develop effective countermeasures for the DDoS attack: 1) The mempool acts as a buffer for incoming transactions. Therefore, the countermeasure policy should not only reduce the number of malicious transactions but also ensure the queue stability to ensure operational consistency. 2) Since the network throughput is constant, therefore, we cannot control the rate of outgoing transactions. As such, our countermeasures must be applied at the control knob of the queue.

COUNTERING THE MEMPOOL ATTACK
To counter DDoS on Bitcoin's mempool, we propose three countermeasures that prevent the spam on the system. The design motivation is to increase the attack cost for the adversary while keeping the operational efficiency for legitimate users. We develop our designs for a miner's priority and apply the priority check on transactions at the mempool level. One of the effective countermeasures against spam attack in Bitcoin is to prevent the transmission of dust transactions in the network. We envision that if mempools can discard spam transactions and stop relaying them to other mempools, the pool size can be effectively controlled and spam can be countered.

Fee-based Mempool Design
Fee-based design aims to optimize the size of mempool by filtering spam transactions upon arrival. As the threat model states, an attacker only intends to relay spam transactions between the mempools and does not want them to be mined. To achieve this goal, the attacker only pays minimum relay fee in transactions so that mempools accept and relay them. To prevent the transactions from mining, the attacker does not pay the mining fee. We use this insight to construct a "Fee-based Mempool Design." For this design in algorithm 1, we assume that the mempool is initially empty when transactions begin to arrive. We also assume that each incoming transaction has its associated relay fee and mining fee. We also fix a threshold beyond which the mempool starts spam filtering. Initially, when the transactions arrive in the pool, and for each those transactions should be accepted, which eventually get mined into the blockchain. As a result, this technique puts a cap on the incoming transactions and filters spam transactions, thereby reducing mempool size. If the new size is less than the baseline size threshold then the mempool can proceed its operation from relay fee check. Otherwise, it will continue with the fee-based design.

Analysis of Fee-based Mempool Design
In the following, we will analyze the workings of fee-based design and its utility in light of our threat model. We will limit the number of transactions an attacker can generate within his budget by increasing the mining fee threshold. We also observe how this design affects other legitimate users within the same network.
In the current settings of Bitcoin, where an attacker only pays the relay fee to broadcast his transactions, if the mempools employ the fee-based design, all spam transactions will be rejected. As such, the mempool will only accept the transactions which pay both the relay fee and the mining fee. Legitimate users, on the other hand, will benefit by this design, since they will always pay the relay and the mining fee, so their transactions will be accepted. Once the attacker becomes aware of the fee-based design, the only way it can carry out the attack is by adapting to the new settings and masquerading as a legitimate user. The attacker can do that by adding mining fee to each transaction. Given a budget B, adding mining fee to each transaction will reduce the total mempools employ the fee-based design, all spam transactions will be rejected. As such, the mempool will only accept the transactions which pay both the relay fee and the mining fee. Legitimate users, on the other hand, will benefit by this design, since they will always pay the relay and the mining fee, so their transactions will be accepted. Once the attacker becomes aware of the fee-based design, the only way it can carry out the attack is by adapting to the new settings and masquerading as a benign user. The attacker can do that by adding mining fee to each transaction. Given a budget B, adding mining fee to each transaction will reduce the total number of transactions T a the attacker could generate in (3) will now become From (9), we can observe that the number of transactions the attacker can generate has an inverse relationship with the total fee paid per transactions. Using that relationship, we can adjust the fee parameter and investigate how it limits the attacker's capabilities. To do that, we simulate the affect of increasing the mining fee on the volume of transactions that the mempool accepts. We allocate a fixed budget to the attacker and select thresholds of minimum mining fee and maximum mining fee. Using (3), we select a suitable budget for attacker that results into 1000 transactions with a minimum mining fee. Then, we generate 1000 benign transactions, each with a mining fee Notice that as the mining fee increases, the mempool size reduces. However increasing mining fee also affects benign transactions which is why the accuracy of detection decreases with increasing mining fee. An optimum cut-off fee can be selected from Figure 5(c) based on the trade-off between accuracy and size ratio.
normally distributed over the range of the minimum and maximum mining fee. Using a discrete-event time simulation, we increase the mining fee and monitor its affect on transactions of the attacker and the benign users. We plot the results in Figure 5, and use the confusion matrix in Table 1 to evaluate the effect of the fee-based design on the mempool. We classify the true positives and the false positives as benign and malicious transactions accepted by the mempool respectively. We classify the false negatives and the true negatives as benign and malicious transactions rejected by the mempool. We plot the results of confusion matrix in Figure 5(a). The results show that with the increase in the mining fee threshold, the mempool size (TP+FP), malicious transactions (FP) and benign transactions (TP) decrease. The trend of (FP) is explained by (9). With a fixed budget, increasing the mining fee decreases the total transactions T a . Accordingly, the size of the mempool also decreases due to fewer spam transactions (FP). However, increasing the mining fee also limits the fee-paying benign users. This, in turn, explains the trend of decreasing (TP).

Evaluation Results
Using the results from Figure 5(a) and the evaluation criteria defined above, we measure the precision and the accuracy of our design. From the plots in Figure 5(b), we observed that the accuracy increases with the mining fee to a maximum value and then decreases. Using that, we found a minimum fee cutoff corresponding to the maximum accuracy.
In Figure 5(c), we the plot accuracy and size ratio; the size ratio is the fraction of mempool transactions out of the total number of incoming transactions where a lower size ratio indicates higher size optimization. The results in Figure 5(c) show that at a fee threshold of 13, we achieve 60% accuracy, 70% size optimization, and 78% precision. Increasing the fee parameter further increases the size optimization but decreases the accuracy. Therefore, the feebased design presents a trade-off between the size efficiency and the accurate detection of malicious transactions.

Shortcomings of Contra-F
To understand the limitations of "Fee-based Mempool Design" we highlight the nature of some transactions in Bitcoin. Suppose Alice sends 10 BTC to Bob in a transaction. That transaction is yet to be verified and mined, but Bob spends them by sending 5 BTC to Charlie. For Bob's transaction to be successfully mined, its parent transaction by Alice needs to be mined first. This sequence of transactions is known as parent-child transaction [70,71]. For a child transaction to become benign, its parent transaction needs to be mined first. Oftentimes when priority factor of a parent transaction is low, the child transaction increases the mining fee to increase the overall priority factor. This process is called "Child Pays For Parent" (CPFP) [71]. For benign users, this situation might be undesirable, since more child transactions can lead to transactions getting stuck. However, the same situation can be viewed as an opportunity by the attacker to circumvent the fee-based design and carry out the same attack at a lower cost.
For transactions made in the attack phase, their parent transactions in the distribution phase need to be verified and mined. The attacker can minimize the probability of transaction acceptance in the first phase by reducing their priority factor; e.g., by paying a minimum relay fee and no mining fee. Once the parent transactions have a lower probability of acceptance in the first phase, the child transactions can increase their priority factor by increasing the relay and mining fees. As a result, and when the mempools apply the fee-based countermeasures, spam transactions of the attack phase will get in mempool. After the mempool's size reaches the baseline size threshold, the mempool will check for the incoming transactions with the minimum relay and mining fee. Since now the transactions of all sybil accounts will pay both the relay and the mining fee, they will be accepted by the mempool and the attacker will be successful.

Countermeasure.
One way to address this problem is to prioritize the incoming transactions on the basis of mining fee. Mempool can sort the incoming transactions for the fee value and accept the ones which pay higher fee.
As we increase the mining fee, the capability of attacker to produce transactions reduces (9). The attacker is constrained by the budget and increasing mining fee reduces the number of transactions he can produced. We can observe this trend in Figure 5(a). Although this reduces the number of spam transactions in the mempool and optimizes its size, it also reduces accuracy and the number of benign transactions that get accepted. As the fee parameter is increased, the capability of all the benign users to pay higher fee also decreases. To this end, the fee-based countermeasures do limit the attacker from flooding the mempool, but they also limit the number of benign transactions that successfully pass the fee threshold. To address these limitations we propose age-based countermeasures.

Contra-A's Design
To limit attacker's chances of success, we propose the "Age-based Mempool Design" which addresses the limitations of our previous model. For this design, we leverage the confirmation factor or "age" of a transaction to distinguish between benign and malicious transactions. In Bitcoin, the age of a transaction determines how many block confirmations it has achieved over time ( §3.1.3).
For this design in Algorithm 2, we assume that the baseline size threshold of the mempool has been reached, and the mempool is only accepting transactions which are paying the relay fee as well as the mining fee. Now, for each incoming transaction, we count the number of inputs or parent transactions. We initialize a variable "average age" and set its value to 0. Next, we calculate the average age of the transaction by adding the age of each parent transaction and dividing by the total number of parent transactions. This gives an estimate of confirmation score of the incoming transaction. Then, we apply a "minimum age limit" filter on the mempool. The "minimum age limit" can take any arbitrary value greater than 0. According to Bitcoin Developers Guide [72], a confirmation score of 6 is considered good for any transaction. If the transaction's mean age value fulfills the criteria of age limit, then the mempool accepts the transaction; otherwise it is discarded.
A transaction in Bitcoin has an input pointer to the spendable transaction it previously received. For spam transactions, these inputs are not spendable and are less likely to be mined, serving the objectives of the attacker who intends to broadcast spam transactions which eventually get rejected. Although the age factor is taken into account for transactions, it is not considered while broadcasting those transactions. As such, attackers may exploit this feature of the system by broadcasting spam transactions and flooding the mempools without losing bitcoins. In this design, we apply the check on the age of the incoming transactions. In the attack phase ( §5.2), the spam transactions will have input pointers of a parent transaction that will not be confirmed in any block. The age of of all those parent transactions, made in the distribution phase ( §5.1), will be 0.
Using this knowledge about the nature of spam transactions, we compute the average age of all the input pointers (parent transactions); minimum age value of 1 means that all transactions coming into the pool are confirmed in at least the most recent block of the blockchain. In Bitcoin, once the transaction is mined into a blockchain, its parent transaction is removed from the "UTXO" set and cannot be spent again. The transaction itself becomes the new spendable "UTXO." With these advantages, the age-based design can prevent the system from spam transactions and double-spending.
Once this design is implemented, if a user tries to spend his bitcoins, he needs to have at least one valid confirmation backing up his transaction. This gives advantage to the benign user who can make a normal transaction with confirmed parent transaction of significant age. On the other hand, most of the spam transactions of attacker will be rejected due to low confirmation factor despite paying high mining fee.

Analysis of Contra-A
In this section, we analyze the working of "Age-based Mempool Design" and how it can help in countering DoS attack. For this design, we have established that the attacker has the capability of circumventing the "Fee-based design" and is willing to pay the relay fee and the mining fee in all of his transactions. Also, the attacker knows that its transactions will not be verified, so it pays comparatively higher relay and mining fee than the benign users.
We carried out our second experiment to analyze the working of the age-based countermeasures. We set a minimum age limit and a maximum age limit as thresholds for the incoming transactions. For the attacker, the only set of transactions with age value greater than 1 are generated in the distribution phase. Child transactions made in the attack phase were assigned 0 age value due to unconfirmed parent transactions. To capture that, we normally distribute the average age value of all malicious transactions from 0 to the minimum age limit. The average age value of all benign transactions was set from 0 to the maximum age limit. A total of 2000 transactions were generated with half of them being malicious and half being benign. Then, we applied the age-based design on all the incoming transactions at the mempool. We increased the age requirement for the incoming transactions and evaluated the accuracy of detection and the state of mempool for each transaction.

Evaluation Results
Using the same confusion matrix in Table 1 and evaluation parameters in ( §6.2). The results in Figure 6 show that upon increasing the average age the malicious transac-

Analysis of Age-based Mempool Design
In this section, we analyze the working of "Age-based Mempool Design" and how it can help in countering DDoS attack. For this design, we have established that the attacker has the capability of circumventing the "Fee-based design" and is willing to pay the relay fee and the mining fee in all of his transactions. Also, the attacker knows that its transactions will not be verified, so it pays comparatively higher relay and mining fee than the legitimate users.
We carried out our second experiment to analyze the working of the age-based countermeasures. We set a minimum age limit and a maximum age limit as thresholds for the incoming transactions. For the attacker, the only set of transactions with age value greater than 1 are generated in the distribution phase. Child transactions made in the attack phase were assigned 0 age value due to unconfirmed parent transactions. To capture that, we normally distribute the average age value of all malicious transactions from 0 to the minimum age limit. The average age value of all legitimate transactions was set from 0 to the maximum age limit. A total of 2000 transactions were generated with half of them being malicious and half being legitimate. Then, we applied the age-based design on all the incoming transactions at the mempool. We increased the age requirement for the incoming transactions and evaluated the accuracy of detection and the state of mempool for each transaction.

Evaluation Results
Using the same confusion matrix in Table 1 and evaluation parameters in ( §7.1.2). The results in Figure 6 show that upon increasing the average age the malicious transactions (FP) decrease sharply. The mempool size decreases to a point where there are only legitimate transactions left in the mempool. Due to low (FP) and higher (TP), the precision reaches a close to 1 Figure 6(b). In Figure 6(c), it can be observed that at an average age value of 100 we achieve 60% accuracy, 80% size optimization and 80% precision. As we increase the age parameter to 200, the accuracy does not decrease like the fee-based design while the size ratio increases up to 90% and the precision increases up to 98%. This shows that the age-based prevents a majority of malicious transactions from entering into the pool and helps the legitimate users in getting their transactions accepted.
In these settings, if the attacker intends to spam the network, he needs to have majority of his transactions confirmed in the blockchain. However, in our attack model, we have described that confirmation is undesirable for the attacker since it results in losing bitcoins in mining and relay fee. In Bitcoin, recall that the average block mining time is 10 minutes. For a single confirmation of all of the transactions, the attacker has to wait on average for 10 minutes. Using the results from Figure 6(c), the attacker will have to wait a minimum of 100 blocks to relaunch the attack. With average block computation time of 10 minutes, 100 blocks lead to 16 hours of delay. Even if the attacker still plans to carry out the attack after waiting and paying all the fee, he will not be able to flood the mempool. The best the attacker might achieve will be occasional network stressing with series of transactions; higher attack cost and low incentive will discourage the attacker. Therefore, the age-based design offers more security against the DDoS attacks while ensuring regular service provision for the legitimate users.

Limitations of Age-based Countermeasures
Although the age-based countermeasures provide an effective defence in mitigating DDoS attack on Bitcoin, there are some limitations in this design. Primarily, it requires all the incoming transactions to have a confirmed parent transaction.The average mining time for a block in Bitcoin is 10 minutes [63]. Depending on the bottleneck and size of the mempool. Due to low (FP) and higher (TP), the precision reaches a close to 1 Figure 6(b). In Figure 6(c), it can be observed that at an average age value of 100 we achieve 60% accuracy, 80% size optimization and 80% precision. As we increase the age parameter to 200, the accuracy does not decrease like the fee-based design while the size ratio increases up to 90% and the precision increases up to 98%. This shows that the age-based prevents a majority of malicious transactions from entering into the pool and helps the benign users in getting their transactions accepted.
In these settings, if the attacker intends to spam the network, he needs to have majority of his transactions confirmed in the blockchain. However, in our attack model, we have described that confirmation is undesirable for the attacker since it results in losing bitcoins in mining and relay fee. In Bitcoin, recall that the average block mining time is 10 minutes. For a single confirmation of all of the transactions, the attacker has to wait on average for 10 minutes. Using the results from Figure 6(c), the attacker will have to wait a minimum of 100 blocks to relaunch the attack. With average block computation time of 10 minutes, 100 blocks lead to 16 hours of delay. Even if the attacker still plans to carry out the attack after waiting and paying all the fee, he will not be able to flood the mempool. The best the attacker might achieve will be occasional network stressing with series of transactions; higher attack cost and low incentive will discourage the attacker. Therefore, the age-based design offers more security against the DoS attacks while ensuring regular service provision for the benign users.

Shortcomings of Contra-A
Although the age-based countermeasures provide an effective defence in mitigating DoS attack on Bitcoin, there are some limitations in this design. Primarily, it requires all the incoming transactions to have a confirmed parent transaction.The average mining time for a block in Bitcoin is 10 minutes [72]. Depending on the bottleneck and size of the mempool, transaction verification can take even longer. In fast transactions where users cannot wait for verification, their transactions will be rejected by the mempool.An illustration of the fast transaction is bitcoin accepting vending machine [73]. However, we do not see Bitcoin evolving into such applications any soon, so we do not consider it as a significant problem.

Contra-S: Size-based Countermeasures
As discussed in section 1, the block size is a key bottleneck dictating the transaction throughput. The size limit of blocks enables the attacker to create a queue of pending transactions in the mempool. Ideally, if the block size is set equal to the mempool size, the mempool queue can be virtually eliminated. However, as discussed in [74], increasing the block size may have multiple drawbacks, including: 1 increasing the blockchain size overhead, 2 increase the transmission and propagation delays in the network, and 3 increase the processing overhead at the receiving node. Therefore, the block size cannot be set equal to the mempool size. However, we postulate that a calculated increase in the block size can prevent the mempool flooding without sacrificing the performance. Conti et al. [75] show that Bitcoin can process a block size of up to 8 MB with tolerable size overhead and delay. In response to that,  Figure 7: Difference between the Bitcoin block size and mempool size. The gap (shaded in blue color) provides advantage to the attacker to flood the mempool. Naturally, if the block size limit is increased, the gap can be reduced and the attack can be prevented.
the Bitcoin community experimented with two soft works called Segwit and Segwit2x, which allow the block size to exceed the standard threshold of 1 MB. Motivated by these changes, in this section we will investigate the usefulness of block size in countering the mempool flooding attack.
Before analyzing the size-based design in detail, with the results shown in Figure 7 we provide an intuitive overview of the gap between the block size and the mempool size. The blue region in Figure 7 shows the size of the pending transactions, and an attacker would ideally want to maintain the size in the blue zone to maintain the pressure on the mempool and avoid losing resources through transaction confirmation. In contrast, if the gap between block size and the mempool size is reduced, the transaction backlog will decrease, and the attacker will risk losing resources. Therefore, the block size variation can be modeled as a probability distribution that evaluates the chances of the attacker's transactions to be mined. The intuition behind this strategy is that if the mining probability is high, the attacker will be discouraged from launching the attack. Moreover, it will also reduce the gap between the block size and the mempool size, shown in Figure 7, thereby preventing the mempool flooding and the fee hike. Compared to the fee-based and age-based countermeasures, in this design we do not use transaction properties to isolate malicious transactions from benign transactions, and instead maximize the chances of transaction confirmation to raise the attack cost. In Figure 8, we illustrate the effect of increasing the block size (as proposed by SegWit and Segwit2x) on the mempool size. Note that the blue region shown in Figure 7 is significantly reduced in Figure 8. As a result, if the attacker has to flood the mempool he will have to generate transactions at a much higher rate with a high probability of losing balance. the mempool size Q, and the incoming transactions rate a[t]. Moreover, we define the block size as S, the set of transaction in the mempool as T , the attacker's transactions in T as I, the priority of a transaction t i ∈ T as P(i), the mining probability of a transaction as P (i), and the priority factor of a transaction as γ i . The mempool state is defined as: Next, we define the priority factor γ i for a transaction t i ∈ T . In cryptocurrencies, the priority is given to a transaction that pays a higher mining fee. Let f 1 , · · · , f v be the fee paid by each transaction, where v = |T | is the total number of transactions in T . We compute a normalized value for γ i and the priority factor P i as follows: , P(i) = S Q × γ i (11) From the transaction priority and the size difference between the block and the mempool, we compute the transaction confirmation probability P (i) as: Following from (12), we define the aggregate probability P (j) for all of the attacker's transaction in I as: From (11), we notice that if all transactions pay the same fee then the priority factor of any transaction will be 0. As a result, P (i) will be undefined. However, the likelihood of such an event is small, since we mention in subsection 3.2 that the attacker will try to pay less fee than the mining fee of the benign users, facilitated by the lack of standard fees in Bitcoin. With n users in Bitcoin, and assuming that each user generates one transaction, the probability that all users generate the same transaction fee is 1 n . Taking into account that there are more than 1 million Bitcoin users [76], the probability for such an event is quite negligible.
When the size-based design is applied, a miner first checks the mempool state, shown in (10). If the queue is empty, then the newly mined block size will be restricted to the standard block size. However, when a[t] > b[t], the miner would increase the block size. As a result, P r(i) for each transaction will also increase. Our goal is to evaluate the mining probability for an attacker when the block size is increased. Intuitively, if the block size is large, the attacker will be discouraged from launching the attack, fearing balance exhaustion. Additionally, we assume that attacker only pays the minimum relay fee to able to flood the mempool.

Evaluation Results
To evaluate the effect of Contra-S, we generate a series of transactions, each of which is with a size of 2 KB. Each transaction was assigned a fee, distributed normally between minimum and maximum fee threshold (subsection 7.1). The mempool size is then the sum of the size of all transactions. Next, we start with fixed transaction size for the attacker (10%), and sequentially increase the size to 90% of the total transactions. For each of the attacker's transaction, we randomly select the transaction fee between 0 and the minimum relay fee. We apply the size-based policy by setting the block size to 1 MB (current block size in Bitcoin), 4 MB (the segwit size), and 8 MB (segwit2x size). We use the same discrete-event simulation settings as used in the earlier experiments. In our simulations, we evaluate the effect of the block size on the probability of transaction confirmation and report the results in Figure 9. Our results show the effect of increasing the block size on the confirmation probability P (j) of the attacker's transactions in I ∈ T . The general trend indicates that when the block size increased, P (j) also increased, which would naturally affect the attacker's balance. Moreover, it is worth noting that when the attacker increases the rate of the incoming transactions, shown on the x-axis, P (j) increases exponentially. Therefore, the risk of balance exhaustion becomes more significant.
Apart from the promising results achieved by Contra-S, we believe that applying Contra-S in current Bitcoin protocol is relatively easier than Contra-F's and Contra-A's. The Contra-S will be applied on the block rather than the mempool. This would require minimal changes in the client software. Moreover, the size-based design specifies concrete parameters (4 MB or 8 MB), which prevent conflicting views. In the fee-based and age-based countermeasures, nodes can have different size of the mempool due to Confirmation Probability P(j) Standard Segwit Segwit2x Figure 9: Results obtained from the simulation of the size-based policy. The x-axis show the percentage of the attacker's transaction among the total transactions. The y-axis is the probability of acceptance of all of the attacker's transactions P (j). The results show that the increase in block size will increase the probability of transactions. Therefore, the attacker will risk losing his balance.
variance in the incoming transaction rate. As a result, they will apply different threshold parameters to control the size of the mempool, which can lead to conflicting states at each node. On the other hand, with concrete parameters for the block size, such a requirement to alter policies at the mempool will be alleviated. As part of our future work, we will analyze the asynchronous settings of Bitcoin network to understand the disagreements in the mempool view. Using that, we will derive bounds on the fee-based and age-based design to prevent the mempool attack while preserving the agreement on the mempool state.

Conclusion
In this paper, we identify a DoS attack on Bitcoin mempools that pushes the users into paying higher mining fees. Attacks on Bitcoin mempools have not been addressed previously, and we propose three countermeasures to the problem: fee-based, age-based, and size-based designs. Using simulations and various analyses, we conclude that when the attack is not severe, the fee-based design is more effective in mempool size optimization. However, the fee-based design does so by affecting both the attacker and the benign users. When the attack is severe, the age-based design is more useful in helping benign users while discarding maximum spam transactions. However, both designs use features from incoming transactions to distinguish between malicious and benign transaction. Our third design overcomes this shortcoming by simply increasing the block size and limiting the attacker's capabilities. The strength of the size-based design lies in concrete policy parameters that can be easily applied in the blockchain system, without any major protocol modifications.