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.