This article comes fromMediumTranslator | Moni

Translator | Moni

Editor | Lu Xiaoming

Editor | Lu Xiaoming

Editor's note: This article is a research report on "resource exhaustion vulnerabilities" written by the research team of the Decentralized Systems Lab (Decentralized Systems Lab) under the University of Illinois at Urbana-Champaign (UIUC). Members of the team Including Sanket Kanjalkar, Yunqi Li, Yuguang Chen, Joseph Kuo, and consultant Andrew Miller. It is reported that these vulnerabilities have affected more than 26 cryptocurrencies based on proof-of-stake in total, and cyber attackers only need to use a very small "stake" (stake) to crash any network node running the corresponding software. The research team began disclosing the investigation in October 2018 with the aim of making the matter known to developers of potentially affected cryptocurrencies, most of which have now deployed mitigations.

Proof-of-Stake (PoS) cryptocurrencies, especially those PoSv3 (Proof-of-Stake version 3: Proof-of-Stake version 3) cryptocurrencies similar to Bitcoin, basically use UTXO (Unspent Transaction Output: Unspent Transaction Output) Model and longest chain consensus rule. The so-called UTXO refers to the collection of bitcoin amounts associated with bitcoin addresses. Since there is no concept of accounts in the bitcoin system, there are only unconsumed transaction outputs all over the blockchain of the entire network, which is essentially a data containing data and executable code. structure. The basic unit of UTXO is "Satoshi", "Satoshi" is the smallest unit of measurement of Bitcoin, and one Bitcoin is equal to 10^8 Satoshi. Once a UTXO is created, it cannot be divided. It can only be spent as the input of the transaction. After spending, a new UTXO will be generated, so that the value transfer of the currency can be realized repeatedly. Therefore, the account balance we see in the Bitcoin wallet is actually the result of aggregate calculation of unconsumed transaction outputs.

Compared with "proof of work", proof of stake does have some potential advantages, such as less energy consumption and no impact on the environment, and better security against 51% attacks. In fact, many cryptocurrencies on the market today are forks of the Bitcoin codebase (or derivatives of Bitcoin) and then grafted with the proof-of-stake consensus mechanism, but some design concepts have not been copied safely, resulting in Fixed some new bugs that were not in the original codebase.

Also in the rest of this article, we will explain the vulnerabilities and attacks in detail, and what kind of subtle consequences they can have. While the vulnerability itself may not seem complicated in hindsight, it is tricky to fully address, and the mitigations currently in place risk causing blockchain forks (more on that later).

secondary title

Before diving into the details of the “False Stake” vulnerability, let’s cover how Proof-of-Stake works.

secondary title

Proof of Stake Mining:

Similar to proof-of-work mining, proof-of-stake mining includes a block header hash value and a difficulty target (note: the difficulty target is the difficulty value required to enable the computing power of the entire network to generate a block approximately every 10 minutes). The high-level goal of Proof-of-Stake is to ensure that each stakeholder has a chance of mining the next block proportional to the amount of cryptocurrency they hold control. To achieve this, in a proof-of-stake consensus mechanism, the hash value depends not only on the block header, but also on the number of coins included in a special "coinstake" transaction inserted in the block by the stakeholder.

• "Coinstake" is a special transaction specially designed by Sunny King, the founder of proof of rights and interests. It draws on the Coinbase design of Bitcoin founder "Satoshi Nakamoto". There are some hard limits on input and output:

• The Coinbase structure requires that the input quantity must be equal to 1, and the input Prevout field (specifying the output of the previous transaction) must be empty, and the output quantity must be greater than or equal to 1;

The Coinstake structure requires that the number of inputs is greater than or equal to 1, and the Prevout field of the first input cannot be empty, that is, the Kernel must exist, the number of outputs is greater than or equal to 2, and the first output must be empty.

In addition, these two special transactions also have special requirements for storage locations in the blockchain. Satoshi Nakamoto stipulates that the first transaction of each block must be placed in Coinbase, which also means that Coinbase cannot appear in other locations in the block. . Sunny King obviously didn't want to break this rule, but he added a rule that for the second transaction of the "Proof of Stake" block, Coinstake must be placed, which also means that Coinstake cannot appear elsewhere on the blockchain. In other words, as long as the second transaction is Coinstake, then this block needs to be treated as a proof-of-stake block.

Proof-of-stake mining involves a lot of details, so I won’t go into details here. For the time being, we will focus on the following two aspects:

2. UTXO (unconsumed transaction output) spent in Coinstake transactions.

secondary title

The Role of Proof-of-Work in Securing Block Validation Resources

As we all know, although proof of work has played a vital role in Bitcoin consensus, a series of problems related to disk, bandwidth, memory and CPU have also made it not very popular. In a decentralized cryptocurrency network, the premise of transactions is not actually based on trust, so in order to prevent resource exhaustion attacks (resource exhaustion attacks), Bitcoin nodes submit more resources (such as storing blocks in RAM) or on disk) before first checking all transaction receipt blocks with a proof-of-work mechanism. However, it turns out that using Proof of Stake to check blocks is much more complicated than Proof of Work, and this consensus mechanism is context-sensitive (or context-sensitive), so many Proofs of Stake are actually very difficult to verify when implementing verification. "Stingy".

Before we can understand how a resource exhaustion vulnerability can be caused, we must first explain in detail how blocks are stored before they are validated. In fact, blockchain nodes not only need to track the longest chain at the current moment, but also a whole tree of fork chains, because any of them may become the longest chain, and the time zone Blockchain nodes need to "reorganize" to switch to the longest chain, such as in the event of an unprepared upgrade, a double-spend attack (such as the 51% attack on Ethereum Classic), or a temporary network partition. Reorganization" is possible.

In this case, it is very difficult to verify the blocks on these "off-main chains". If you want to fully verify a block, you need to get the collection of all unspent transaction outputs (UTXO) at the current point in time of the previous block. Bitcoin will keep the set of unspent transaction outputs at the current tip of the best chain, but blocks on forked blockchains may not follow Bitcoin's approach. There are two main ways for a block on a fork to be fully validated:

1. "Rollback" the current view (set of unconsumed transaction outputs) to the point before the fork; or,

2. Store copies of unconsumed transaction data collections of all early blocks.

The Bitcoin codebase does not support the second approach, and even if it could, it would add additional storage costs (Bitcoin node performance relies on constant "prune" of unneeded data). The first way is exactly how the Bitcoin codebase currently handles reorganization, but it can be very expensive, so when the amount of proof-of-work in the forked chain is greater than the current main blockchain, rollback and Full validation is deferred until the last moment. So, the first time a node receives a block or header that is not part of the longest chain, it skips full validation and saves the block to local storage.

In Proof of Stake, a similar initial check is validating the coinstake transaction and checking that it passed the previous block kernel's difficulty target. It is easy to calculate the computing power of the coinstake transaction, but it is really difficult to check whether the unconsumed transaction data entered in the coinstake transaction is valid and has not been consumed. As mentioned earlier, since this operation needs to check the collection of unconsumed transaction data, it does not apply to previous blocks. Because of the difficulty of fully verifying coinstake transactions, most proof-of-stake-based blockchains use only "heuristic" or "approximate" checks, which, it turns out, are often inadequate and can be exploited .

secondary title

Loophole #1: "I don't believe it's not an equity"

When we first investigated this issue, five cryptocurrencies—Qtum, Particl, Navcoin, HTMLcoin, and Emercoin—were found to have fairly simple forms of vulnerability—that is, before blocks were committed to RAM or disk, these encrypted Most likely the currency is not checking for any coinstake transactions at all. What these five cryptocurrencies have in common is that they employ Bitcoin's "headers first" feature, where block propagation is split into two separate messages, one for the block and the other for the zone. bulk. After the block header has passed the proof-of-work, the node only asks whether the block is the longest chain. Since coinstake transactions only appear in blocks, not block headers, nodes cannot verify block headers on their own. Instead, it stores a block header in an in-memory data structure (mapBlockIndex). Therefore, any network attacker, even one without any stake, can fill up the RAM of a potential victim node.

The second variant of this attack targets the code base, although it does it in a slightly different way and targets a different resource, the target is not RAM but disk. Arguably, an attack involving a disk is more harmful to a victim node, requiring a simple reboot if the RAM fills up and crashes the node; however, if the disk is full, manual intervention is required, such as running an external script to Clear obsolete blocks from disk.

Exploitation of any of these vulnerabilities can affect cryptocurrencies without any stake. In contrast, an attack on RAM may be less impactful, while an attack on disk requires a little more care from a technical standpoint, and neither has any stake requirement.

secondary title

Vulnerability 2: Spent Stake Attack

By tracing the lineage of these codebases, we noticed that bug one was originally merging the Bitcoin "header first" functionality into the PoSv3 codebase. However, the attack does not work on earlier versions (such as Peercoin), so two additional preliminary checks are required before storing blocks on disk:

1. Check whether all outputs exist in the main chain;

2. Check whether the Proof of Stake Kernel Hash meets the difficulty target requirements.

• The first check is done with a lookup in the transaction database (TxDB), which tracks all transactions so far in the current main chain. In other words, preliminary verification is better than no verification at all, but full verification is still not possible, only "heuristic" and "approximate" verification can be done. If we continue to explain this way of thinking, two other questions may arise:

• Concern A: The first check ensures that tokens exist, but cannot determine if they are unspent. This situation immediately leads to another vulnerability discussed next;

Based on concern A, we found a way to cheat these checks using a more subtle attack that we call a "spent stake attack". To bypass the first check, we make the node see an output that has already been spent; and to bypass the second check, we need to first mine a valid block that passes the difficulty target, Doing so may require you to own a significant amount of equity. It turns out, however, that we can take a few incompletely validated transactions and generate any amount of apparent stake using a technique called "stake amplification."

secondary title

Equity amplification

You'll find that even if you only have 0.01% stake in the system, an attacker only needs 5000 transactions to mine a 50% obvious stake block. After the attacker has collected a large amount of apparent stake, they start mining proof-of-stake blocks using the newly collected apparent stake output. Finally, the attacker fills the disk of the victim node with invalid blocks, as shown on the right in the figure above. In fact, an attacker can buy some tokens from a cryptocurrency exchange, expand their interests through the above methods, then sell these tokens back to the exchange, and execute the attack afterwards, the only cost they bear is a small transaction Fees only.

secondary title

Coordinated Vulnerability Disclosure

We first investigated whether two cryptocurrencies, Particl and Qtum, had "vulnerability one", that is, whether these cryptocurrencies check any coinstake transactions before blocks are committed to RAM or disk. To determine the magnitude of the vulnerability, we collected a list of known cryptocurrencies by market capitalization from CoinMarketCap.com on August 9, 2018, and filtered them by blockchain-based proof-of-stake consensus type. It should be noted that we only studied the cryptocurrencies whose code base was forked from Bitcoin. We checked a total of 26 cryptocurrencies and found that five cryptocurrencies were affected by the vulnerability, namely Qtum, Navcoin, HTMLcoin, and Emercoin. and Partickl, but our attack does not seem to apply to other cryptocurrencies.

To further confirm the vulnerability, we implemented the attack in five additional affected codebases. We leverage the existing test suite in the Bitcoin software - specifically the "regtest" mode, which supports simulated timestamps and easy block creation. In addition, we also build a test node based on the Python development language based on Bitcoin TestFramework and allow it to be extended by attacker behavior. We used Docker containers for testing, and also packaged the dependencies and affected specific commit hashes into a reusable toolkit as part of the vulnerability disclosure, which we can easily Share this information with all five affected development teams.

secondary title

Mitigation

Mitigation

Already, we have seen some cryptocurrency development teams implement a series of mitigations for the vulnerabilities disclosed in this article. Those cryptocurrencies that have implemented mitigations can not only detect exploits, but also disconnect offending forks. In simple terms, nodes can monitor abnormal behavior, such as a large number of block headers being sent on a forked chain.

However, there is still a difficult problem here, namely how to distinguish the "false stake" of the actual attack from the honest node of legal reorganization, because some mitigation measures may risk incorrectly banning the honest node. Some of the mitigations we've seen so far have been implemented reasonably well, but this requires further investigation and analysis to see the follow-up effects.

There are also mitigations for some cryptocurrencies that partially validate functionality within a certain length. If a forked block is received that exceeds the specified length on the main chain, then the block will be discarded. For example, the Bitcoin Cash ABC codebase takes this approach, where they set rolling checkpoints every tenth block. But this approach also has other disadvantages, namely the possibility of "blockchain splits". Because when more and more honest nodes appear on different forks of the blockchain, blockchain splits will occur. Especially when poor network connectivity causes nodes to get out of sync and not long enough to create conflicting checkpoints, it can also lead to "blockchain splits". Even if nodes regain connection, they cannot reach a common view of the chain.

But critically, we note that even with this mitigation in place there is a risk of a "blockchain split", as a node temporarily finds itself on a fork if the coinstake transaction is validated using the transaction outputs in the current chain. On the chain, it may not be possible to switch to the real main chain.

The "blockchain split" risk also introduces new attack vectors for adversarial miners, who may try to secretly mine long chains and then publish them to a subset of the nodes to cause a chain split. Nodes in the initial block download (Initial Block Download) and nodes that have been offline for a long time and have just restarted are particularly vulnerable to this type of attack, and this attack can also be combined with eclipse attacks to "introduce" honest nodes into the attacker's control on the blockchain.

So you'll find that all these mitigations just make the attack harder to execute, but they're not really a replacement for full authentication. It is reported that some cryptocurrencies, including Qtum, are planning to fully verify blocks on non-main blockchains in future versions.

secondary title

final thoughts

final thoughts

Although the "false stake" attack is theoretically simple, it reveals a possible problem with the design of proof-of-stake cryptocurrencies: some ideas that make sense in proof-of-work have not been safely converted to proof-of-stake. Given that Bitcoin Core codeshare is highly "upstream" of PoSv3 cryptocurrencies, we believe these proof-of-stake cryptocurrencies should receive more scrutiny. While investigating these vulnerabilities, we also found several examples in the work done on different code bases and in commented out code. To us, this shows that some proof-of-stake cryptocurrency developers don't fully understand this consensus mechanism when they design their cryptocurrencies.

On the one hand, we hope to reject invalid blocks as soon as possible to improve the processing efficiency of the blockchain; but on the other hand, we do not want to encounter blockages on the forked blockchain, which will affect and delay the actual transactions on the main chain, processing A systematic solution to this problem remains an open question in the current working group.

While we've seen this vulnerability affect at least two codebases recently (such as CVE 2018-17144 in Bitcoin), to the best of our knowledge there were more than 20 cryptocurrencies were affected, which is not a lot. Given the prevalence of duplication of design ideas and code reuse in cryptocurrencies, we expect more such vulnerabilities in the future.