“Fake Stake” attacks on chain-based Proof-of-Stake cryptocurrencies

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.

  1. “roll back” the current view (UTXO set) to the point before the fork begins, or
  2. store copies of the UTXO set for all the earlier blocks.

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.

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:

  1. Check if the output being spent exists in the main chain.
  2. Check if the PoS kernel hash meets the difficulty target.

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.

Stake Amplification and Spent Stake Attack

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.

Marketcap data from 9th August 2019

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.

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Decentralized Systems Lab

Decentralized Systems Lab

Decentralize Systems Lab, University of Illinois at Urbana Champaign