“Fake Stake” attacks on chain-based Proof-of-Stake cryptocurrencies
This article is the public disclosure of a series of resource exhaustion vulnerabilities investigated by a team of students consisting of Sanket Kanjalkar (sanket1729, smk7@illinois.edu), Yunqi Li, Yuguang Chen, Joseph Kuo, and our adviser Andrew Miller(socrates1024) in the Decentralized Systems Lab @ UIUC. These vulnerabilities have affected 26+ Proof-of-Stake cryptocurrencies in total and would allow a network attacker with a very small amount of stake to crash any of the network nodes running the corresponding software. We began a coordinated disclosure in October 2018 to notify development teams of affected cryptocurrencies ahead of this public release. The majority of them (weighted by marketcap) have already deployed mitigations.
Proof-of-Stake (PoS) cryptocurrencies, particularly those based on chain-based PoSv3 (Proof-of-Stake version 3), are similar to Bitcoin in that they use the UTXO model and longest chain consensus rules. The key difference is that they replace the Proof-of-Work with proof-of-ownership of coins. Potential benefits of the PoS approach range from reducing environmental impact to better security against 51% attacks. Many cryptocurrencies are in fact forks (or at least descendants) of Bitcoin’s codebase, with the PoS functionality grafted in. However, some design ideas are copied over insecurely, leading to new vulnerabilities that did not exist in the parent codebase.
We call the vulnerabilities we found “Fake Stake” attacks. Essentially, they work because PoSv3 implementations do not adequately validate network data before committing precious resources (disk and RAM). The consequence is that an attacker without much stake (in some cases none at all) can cause a victim node to crash by filling up its disk or RAM with bogus data. We believe that all currencies based on the UTXO and longest chain Proof-of-Stake model are vulnerable to these “Fake Stake” attacks. A list of the cryptocurrencies we investigated and believe to be affected are shown towards the end of the article.
In the rest of this post, we’ll explain the vulnerabilities and attacks in detail, because they have some subtle consequences. While the flaw itself is simple in hindsight, solving the problem completely is tricky and the mitigations employed so far come at the cost of a chain split risk (more on this later).
Background:
Before going into the details of the vulnerabilities, we give some background on the relevant parts of how chain-based proof-of-stake works.
Proof-of-Stake Mining:
Similar to Proof-of-Work mining, mining in PoS consists of comparing the hash of a block header to a difficulty target. The high-level goal of PoS is to ensure that each stakeholder’s chance of mining the next block is proportional to the number of coins they control. To achieve this, in chain-based PoS the hash depends on not just the block header, but also the quantity of coins included in a special “coinstake” transaction inserted in the block by the stakeholder. The exact details of PoS mining can be a bit involved, and a thorough explanation can be found in earlz’s blog post. For this post, what matters is that checking the PoS depends on 1) the coinstake transaction and 2) the UTXO being spent by the coinstake transaction.
The role of Proof-of-Work in guarding block validation resources:
It’s well understood that Proof-of-Work (PoW) plays an essential role in Bitcoin consensus. But Proof-of-Work also plays a second, somewhat less appreciated role, which is guarding access to a node’s limited resources, such as disk, bandwidth, memory, and CPU. In a permissionless cryptocurrency network, peers must not be trusted. So, to prevent against resource exhaustion attacks, Bitcoin nodes first check the PoW for any received blocks before committing more resources, such as storing the block in RAM or on disk. However, it turns out that checking a Proof-of-Stake is a lot more complicated and context-sensitive than validating a Proof-of-Work. As a result, many chain-based PoS implementations have skimped on the appropriate validation.
To understand how this leads to a resource exhaustion vulnerability, we have to give a bit of detail on how blocks are stored before being validated. A node must not only keep track of the longest chain at the current instant, but also a tree of fork chains (any of them may turn out to be the longest chain, in which case the node needs to “reorg” to switch to it). This can happen, for example, during a botched upgrade, a double spend attack (ETC under 51% attack), or a temporary network partition.
Validating these off-the-main-chain blocks is difficult. To fully validate the block, you need the set of unspent coins (UTXOs) at the time of the previous block. Bitcoin keeps the UTXO set for the current tip of the best chain, but not for all the other past blocks a fork could start from. There are two main approaches for full validation of blocks on a fork:
- “roll back” the current view (UTXO set) to the point before the fork begins, or
- store copies of the UTXO set for all the earlier blocks.
Bitcoin’s codebase doesn’t support Option 2, and even if it did this would impose an additional storage cost (Bitcoin node performance relies on aggressively pruning unneeded data). Option 1 is exactly how the Bitcoin codebase currently handles a reorg. However, this can be very expensive, so the roll back and full validation are deferred to the last possible moment when the Proof-of-Work in the fork is already greater than the current main chain. So instead, when a peer first receives a block or header that is not part of the longest chain, full validation is skipped and the block is saved to local storage.
Before storing the block to disk, the Bitcoin codebase performs some preliminary validation based on the PoW (but ignoring the transactions). This preliminary check only depends on previous block header and current header, so a node can do this very quickly. And it’s an effective defense because generating a valid PoW that passes it is very expensive. For example, although it’s possible to trick a Bitcoin node into storing an invalid block on disk, it’s prohibitively expensive to mount a resource exhaustion attack this way.
The analogous preliminary check in PoS is to validate the coinstake transaction and check that it passes the difficulty target when hashed with the kernel of the previous block. Computing the hash of the coinstake transaction is easy, but the hard part is checking whether the input UTXO to the coinstake transaction is valid and unspent, since this requires checking the UTXO set, which as mentioned earlier, is not available for past blocks. Because fully validating the coinstake transaction is difficult, most chain-based PoS implementations provide a heuristic or approximate check instead. It turns out that these approximations are often inadequate and can be exploited.
Vulnerability #1: “I Can’t Believe it’s not Stake”
When we first investigated this problem, we found that five cryptocurrencies, Qtum, Particl, Navcoin, HTMLcoin, and Emercoin, exhibited a fairly trivial form of this vulnerability: namely, they fail to check any coinstake transaction at all before committing a block to RAM or disk. What these five cryptocurrencies have in common is that they have adopted Bitcoin’s “headers first” feature, in which block propagation was split into two separate messages, Block and Header. Nodes only ask for Block after Header passes the PoW checks AND it is a longest (or longer) chain. Since the coinstake transaction is present only in Block but not the Header, a node cannot validate the Header on its own. Instead, it directly stores the header to an in-memory data structure (mapBlockIndex). As a result, any network attacker, even with no stake whatsoever, can fill up a victim node’s RAM.
The second variation of this attack can be carried out against the same codebases, although it works in a slightly different manner and targets a different resource, the victim’s disk rather than RAM. Arguably an attack involving disk is more harmful to the victim: If RAM is filled up and the node crashes, it can simply be restarted. However, if the disk is full, manual intervention would be required (for example, to run an external script to clean up stale blocks from disk).
Different preliminary checks are performed when receiving a block rather than receiving a header. Ideally, since the block does contain the coinstake transaction, the node software should check the coinstake transaction before committing the block to disk. However, as mentioned, if the block is on a fork, there is no easy way for a node to access the UTXO spent by the coinstake transaction. Perhaps for this reason, these codebases do not validate the coinstake transaction.
Exploiting either of these vulnerabilities can be carried out without having any stake in the affected cryptocurrency at all. The RAM version of the attack is particularly trivial, but for technical reasons, the disk version of the attack requires slightly more care (though still no stake is required). The details are explained in a short paper to be presented at Financial Cryptography 2019.
Vulnerability #2 and the Spent Stake attack
By tracing the lineage of these codebases, we noticed that vulnerability #1 was originally introduced when merging Bitcoin’s “header-first” feature into the PoSv3 codebase. The attack does not work on earlier versions (for example, Peercoin) because there are two additional preliminary checks prior to storing blocks on disk:
- Check if the output being spent exists in the main chain.
- Check if the PoS kernel hash meets the difficulty target.
Check 1 is accomplished by a lookup in the transaction database (TxDB), which keeps track of all the transactions in the current main chain so far. In other words, the preliminary validation is better than no validation, but still a heuristic and incomplete approximation of full validation. If you’re following the explanation up to this point, two concerns may jump right out at you:
Concern A: Check 1 ensures that the coin exists, but NOT that it is unspent. This insight immediately leads to the vulnerability we discuss next.
Concern B: Even if we’re validating a block on a fork of the main chain, the coinstake transaction is validated against the TxDB for the main chain itself.
Based on Concern A, we found a way to fool these checks as well, using a more subtle attack we call the “spent stake attack.” To get around Check 1, we use an output that is seen by the node but is already spent. Typically, in order to get around Check 2, we would need to mine a valid block that passes the difficulty target, which in turn would require a large amount of stake. As it turns out, however, we can abuse the incomplete validation to generate an arbitrary amount of apparent stake using a technique we call “stake amplification.”
Stake Amplification
To carry out the attack starting from a small amount of stake, the attacker must amplify their amount of apparent stake. Apparent stake refers to the total candidate stake outputs, even the ones that are already spent. If an attacker starts with a UTXO of amount k, then the attacker can create multiple transactions spending the coins back to the attacker as shown in the figure below. Only UTXO(n+1) should be allowed for staking, but because of Check 2 above we are able to stake with all UTXO from 1 through n+1, thereby increasing the apparent stake by n*k. This increases the chances of finding a PoS block since the attacker can keep on doing this to increase his apparent stake. This is illustrated as “stake amplification step” on the left side of the illustration below.
For example, even with 0.01% stake in the system, the attacker only needs 5000 transactions to mine blocks with 50% apparent stake power. After the attacker has collected a large amount of apparent stake, he then proceeds to mine PoS blocks at a past time using the freshly collected apparent stake outputs. Finally, the attacker fills the disk of the victim peer with the invalid blocks as shown on the right part of the illustration above. An attacker could, for example, buy some coins from an exchange, amplify the stake through self-spends as we described, and then sell those coins back to the exchange, performing the attack at any later date. The only cost incurred to the attacker would be the transaction fees.
Coordinated Vulnerability Disclosure
We first investigated Vulnerability #1 in the context of Particl and Qtum cryptocurrencies.¹ To determine the extent of this vulnerability, we collected a list of known cryptocurrencies from coinmarketcap.com (on Aug. 9th, 2018), sorted by market cap, and filtered by chain-based PoS consensus type. We only looked at cryptocurrencies whose codebase was forked from (a descendant of) Bitcoin, i.e. in C++. In total, we examined 26 cryptocurrencies and found that only five cryptocurrencies (Qtum, Navcoin, HTMLcoin, Emercoin, and Particl) were affected, but our attack did not seem to work on the rest. To confirm the vulnerability, we implemented the attacks in each of the five affected codebases. We made use of existing test suites in Bitcoin software, specifically the regtest mode, which enables simulated timestamps and easy-to-create blocks, and a Python-based test node (based on bitcoin TestFramework), which can be extended with attacker behavior. We used Docker containers to package these tests, their dependencies, and the specific commit hash affected into a reproducibility kit that we could easily share with all five affected developer teams as part of our vulnerability disclosure.
We then dug deeper to understand why the unaffected cryptocurrencies were not susceptible to the first attack and realized that vulnerability #2 was nearly as severe (requiring minimal amount of stake), but far more pervasive. In planning a coordinated responsible disclosure, we considered that it might be counterproductive to disclose to cryptocurrencies with low economic activity and inactive developer teams (the risk, for example, is that if the vulnerability was leaked, it could affect others before they’d have time to deploy a mitigation). Ultimately, we decided to focus our attention on communicating with the fifteen developer teams associated with cryptocurrencies that were most likely to be attacked (among the top 200 cryptocurrencies) and to be responsive (some commit activity during 2018).
One complicating factor is that most of these codebases did not come with regtest mode, so we could not easily demonstrate the attack or provide a reproducibility kit for each one. We therefore only provided a demonstration on the C++ codebase of stratisX. Based on the similarity in the codebases, we informed all fifteen teams that we believed would be affected. Five teams acknowledged the vulnerability, three are still investigating, three rebutted it (pointed out implementation changes that had a mitigating effect), and four teams gave no response. For the four teams that did not respond, we contacted them through channels we could find from their websites.⁵ ⁶ Our Github reproducibility kit for both vulnerabilities can be found here and our short paper on vulnerability #1 can be found here. We have also reserved CVEs for the vulnerabilities, which should be public soon.
Mitigations
We saw a range of mitigations implemented by teams in response to our disclosure. Some cryptocurrencies implemented mitigations that detect attacks and disconnect from the offending peers.² In simple terms, a node monitors its peers for abnormal behavior (e.g., sending many headers on forks). The challenge with such heuristics is that it’s difficult to distinguish an actual attack from an honest node experiencing a legitimate reorg — there is a risk of mistakenly banning honest nodes. The mitigations we have seen so far look reasonable, but this is an area worth further investigation.
Some other cryptocurrencies added partial validation up to a fixed length.³ If a peer receives a block that forks from the main chain past that length, then the block is simply discarded. This approach is also taken, for example, in the ABC codebase of BCH (Bitcoin Cash), which uses a 10-block rolling checkpoint. The drawback of this approach is that it introduces the possibility of a “chain split.” A chain split occurs when honest nodes end up on different diverging forks of the blockchain. This can occur, for example, if poor network connectivity causes nodes to be out of sync with each other for a long enough time to create conflicting checkpoints. Even if the nodes regain connection, they would be unable to reach a common view of the chain. We note that a chain split risk is present even without this mitigation. Recalling Concern B from earlier, since the coinstake transaction is validated using the transaction outputs in the current chain, it is possible that a node would be unable to switch to the actual main chain if it temporarily found itself on a fork.
The chain split risk also introduces new attack vectors for hostile miners. An attacker could attempt to mine a long chain in secret and then publish it to a subset of the nodes in order to cause a chain split. Nodes in IBD (Initial Block Download) or nodes that have just restarted after a long offline period are particularly vulnerable to this attack. Such attacks can be combined with eclipse attacks to lead honest nodes into an attacker controlled chain.
All these mitigations make the attack difficult to carry out but are still no substitute for full validation. Some cryptocurrencies, such as Qtum, plan to move to full validation of off-main-chain-blocks in future releases.
Users of the following affected cryptocurrencies should be advised to update their nodes to the latest patched software and to be aware that in unpatched nodes this vulnerability can be exploited to result in increased RAM or disk consumption and an eventual crash.
The table below shows the currencies which we believe are affected by one of the above two described vulnerabilities. We have not yet validated the vulnerabilities for all currencies, and we have not yet examined why the currencies who rebutted our claims were not affected.
Final Thoughts
While the “fake stake” attacks are simple in principle, they underscore a difficult design challenge: some ideas that make sense in Proof-of-Work do not translate over securely to Proof-of-Stake. Given the high degree of code sharing from Bitcoin Core as “upstream” among PoSv3 cryptocurrencies, we think this deserves even more scrutiny. While investigating these vulnerabilities, we found several examples across different codebases of works-in-progress⁴ (or commented out code) that aim for various mitigations and ad hoc defenses. To us, this suggests an awareness among PoS developers that the trade-offs and requirements in this design space are not yet fully understood. The challenge is that on one hand, we want to reject invalid blocks as soon as possible, but on the other hand, we don’t want to get stuck on a chain split or get delayed in processing what’s actually the main chain. A systematic way to deal with this remains an open problem for future work.
Although we have seen recent examples (e.g., CVE 2018–17144 in BTC) affecting at least two codebases, to our knowledge this is the first coordinated security vulnerability disclosure across such a large number (20+) of independent cryptocurrencies. Given the amount of cross-pollination of ideas and code reuse across cryptocurrencies, we anticipate more vulnerabilities like this in the future. We found there was little uniformity in the security process among these codebases. For example, there was no dedicated security contact for most of them. Establishing best practices for coordinated disclosures could benefit the overall ecosystem.
[1] The idea for this vulnerability originated in Summer 2018 while Andrew Miller was working with Unit-E developers. We thank Matteo Sumberaz and Gil Danziger for the helpful discussions and the DTR Foundation (https://dtr.org/) for a research grant.
[2] A Heuristic for peer detection was implemented by Emercoin. https://github.com/emercoin/emercoin/commit/ec32762b99cc68fb9abb2909dda96bc7a13bd819
[3] Rolling checkpoints in Qtum https://github.com/qtumproject/qtum/commit/8d208d0bee8449c1e4a3904ff3fc97ed26156648
[4]Examples of ad-hoc checks for PoS can be found here: https://github.com/peercoin/peercoin/blob/ebb4003ce8367501020181f7e734d52c4b1ab5ea/src/main.cpp#L2564
[5] We reached out to some coins via email listed their webpage or “send note” feature
[6, *] We tried contacted PIVX multiple times starting in November via the [contact form on their website]. Only while writing this post did we come to realize that [PIVX also launched a hackerone project]. We note that even as of today, the [bug bounty page on the PIVX website itself] does not mention the hackerone project at all.
[**]StratisX has shifted to a C# implementation from their vulnerable C++ codebase.
[***] Edit: 26th Jan, 2019: Updated the table with new responses from developers. PivX, LuXcoin, NoLimitCoin, HTMLcoin, DeepOnion.
Edit: Feb 7th, 2019: Added Linda rebuttal.
