fake-stake-1924x800.jpg

Feb 20, 2019“Fake Stake” Official PIVX Report

Based on the “Fake Stake” DoS attack presented by Andrew Miller et al., the PIVX core team has expanded upon the original problem, discovering, recreating and patching several other possible attack vectors.

The report describes the vulnerability as follows:

“An attacker that connects to a victim node as a peer can send invalid blocks and/or headers, which are stored in RAM or on disk without being validated. The consequence is that an attacker can connect to a victim node and fill its disk or RAM, until the node crashes or slows.”

The vulnerability arises in most PoS blockchains due to the absence of validation of the coinstake input on header wise valid blocks before storing them on disk. Exploiting this results in a possible DoS attack due to resource exhaustion of the receiver’s node.

However, there are no consensus/theft attacks related to the current vulnerabilities. No risk of connecting invalid blocks to the main chain. Invalid blocks are discarded during the main chain connection process.

To better detail the presented vulnerability, it is helpful to first highlight the differences between PoW and PoS block generation and validation.

PoW vs PoS

PoW

To be able to generate valid blocks in a proof of work system, miners need to hash the block’s header, iterating the nonce field until the hash meets the difficulty target. As simple as this sounds, finding the valid hash is computationally expensive. As soon as a node finds the hash, it broadcasts the block to the network, making every node that receives it validate it and store it on disk. Block validation under PoW is quite cheap, merely requiring check that the block header is well formed and the hash meets the target. Every Bitcoin-style blockchain stores valid headers on disk, because this represents a considerable resource and energy consumption for the node that crafted it.

PoS

In proof of stake, unlike PoW, blocks are not mined but rather minted. The consensus model is not about who has more electricity and computer power. It is an environmentally friendly alternative that distributes block generation amongst every actor in the network, incentivizing everyone with tokens to be part of the block validation, offering the chance to win a block based on their “staking power”. In this way, overall network security is increased. Staking power is defined by the amount of tokens the user owns in the network.

PoS is a more complex protocol. Instead of having machines look for the block hash iterating over the nonce field inside the header, they instead need to look for the “kernel hash”.

The kernel hash is composed of several pieces that cannot be modified in the block that is being produced. For example, the stake transaction information (input) that represent the actor’s staking power and form part of the difficulty target calculation; another is the stake modifier, which based on previous block’s stake modifier, height and time; then there is a coinstake signature, which must be a valid signature of the stake input public key, among other data and restrictions.

Summary

As good as PoS is, like every protocol, it has some drawbacks. One of these is how cheap it is to provide a fake block and how much information is needed to be able to properly verify it. For this reason, PIVX developed several mitigations that are part of the following PR [https://github.com/PIVX-Project/PIVX/pull/803]

Mitigations

Block spam filter

A new structure called CNodeBlocksFilter was created, which checks for peers exceeding the maximum occurrences of the same block height and the maximum average of repeated block heights in different chains continuously. If any peer surpass such limits, it gets banned.

  • Receive main chain block with an invalid stake input validation.
    Involves the detection of a double-spent stake input before storing the block on disk. This check is performed during the block acceptance process, preventing the storage of blocks that appear valid from the header but are actually invalid due to the coinstake transaction input.
  • Receive main chain block with an invalid zPoS input validation.
    This detects and deletes any invalid Zerocoin proof of stake block that contains a double-spent serial on the zc_spend script that was used as the coinstake input. This check is performed during the block acceptance process, preventing the storage of such bad zPoS blocks.
  • Forked chain state validation (PoS and zPoS).
    This is a more complex detection process, as peers do not store forked chains states. In essence, when the node receives a block that is part of a fork, it walks backward along the forked chain up to the chain split (up to a maximum of 100 blocks) and verifies the chain status.

The block data is only stored on disk if the (forked) chain state is valid. If it is invalid, the peer broadcasting this block is banned.

Forked chains TTL on disk.

Every valid block from a forked chain is stored along with a flag that represents whether it is part of the main chain or not. A background thread is triggered that checks every forked chain on disk and verifies that the maximum reorganization height limits have not been reached. When the limits are reached, the forked chain will be removed from disk, thus keeping disk storage as clean as possible.

Reproduction Test Suite

The test suite published in the article did not cover the full complexity of our system. For that reason, a new test suite was created covering the full specs of how our PoS/zPoS protocol works.

PIVX test suite https://github.com/PIVX-Project/PIVX/pull/812.

We need first to detail the problems in the reproduction kit provided by the report which not only required changes to the python script itself, but also to the underlying consensus code.

The following exceptions were needed:

  1. The python test script required further adaptation to function on pre-existing regtest mode. This was largely expected.
  2. Kernel solving within the script was unreliable, with a very high chance that a kernel would not be found whose hash was below the target. To overcome this, the solving of a kernel was put through a loop that increments `nTime` after each iteration.
    • This, in turn, caused a situation where the crafted block’s coinstake transaction was outside the allowable drift time.
    • Modification of the block consensus code was needed to, again, explicitly allow for an infinite drift time in coinstake transactions.
    • a `stake amplification` method has been added to get a more realistic scenario and having more chances at finding a valid stake kernel hash.
  3. Script generated PoS blocks failed the pre-existing check in `AcceptBlock()` which calls `CheckProofOfStake()`. This was, once again, modified to explicitly pass for the sake of the test.

After replicating the reported issue, we decided to create our own full test suite to be able to resolve a more extensive coverage of all of the possible attacks.

PIVX Test Suite & Results

The suite is contained in the folder test/functional/fake_stake.

There are x test cases covered by the present suite, named Test_01, ... , Test_x (extending the base class PIVX_FakeStakeTest) which are run from the main script pivx_fake_stake.py

Test_00

The first test simply benchmarks the disk size allocation and verifies that the proposed fix does not filter out valid proof of stake blocks.

The node generates the first 250 proof of work blocks and then uses the collected rewards to stake the successive 15 blocks which are then relayed to the network.

RESULTS: OK

– The disk size increase due to the storage of the 15 PoS blocks, 44 kb each, a total of 660 kb.

Test_01

Covers a naive scenario representing the basic attack described in the article: “forked” blocks with a valid proof of stake but with an invalid (already spent on mainchain before the split) coinstake input, are spammed to the network.

Specifically, here, a node mines 150 blocks, then spends the mined coinbase outputs performing the “stake amplification” step of the attack. (other blocks are mined to confirm the spending transactions).

All the outputs are then used as coinstake inputs to create 15 spam blocks at a random heights in the range (N-20, N) where N is the current block height and those blocks are then sent from a node to his peers.

RESULTS: OK

Spamming 15 blocks of 1703 Kbytes each resulted in a disk size increase of:

– [w/o patch] increase of 16424 kbytes (64% of the projected increase of 25545)

– [patched] increase of 40 kbytes (0.15% of the projected increase of 25545)

Test_02

Verifies that the proposed fix doesn’t block “valid” forked chains.

What might happen, in fact, is that some coins could be spent on main chain in a block which is higher than the “forked” one that contains a coinstake transaction using the same coins as inputs.

The test node mines 150 blocks collecting the rewards and then mines 50 more blocks. Then spends the coins mined in the first 150 blocks. Then mines 10 more blocks to include the transactions in the chain.

The same outputs mined in blocks 1-150 (and spent from block 201 onward) are used to create 15 spam blocks at a depth between 151 and 200.

RESULTS: OK

– [w/o patch] valid blocks from a forked chain accepted.

– [patched] valid blocks from a forked chain accepted.

Test_03

Covers the following attack: “forked” blocks with a valid zPoS but with an invalid (already spent on mainchain before the split) coinstake input that actually is a zerocoin spend, serial double-spent.

In other words, performs the same attack described in Test_01 but using already spent zerocoins to create fake zPoS stakes.

RESULTS: OK

Spamming a block of 22.4 Kbytes each resulted in a disk size increase of:

– [w/o patch] increase of 22.4 kbytes (invalid block accepted).

– [patched] increase of 0 kbytes (invalid block rejected).

Test_04

Performs the same check as in Test_02 verifying that zPoS forked blocks that stake a zerocoin which is spent on mainchain on a higher block are still accepted.

RESULTS: OK

– [w/o patch] valid zPoS blocks from a forked chain accepted.

– [patched] valid zPoS blocks from a forked chain accepted.

Test_05

Covers the scenario of a valid PoS block with a valid coinstake input that double spent the coinstake input in one of the transactions in the same block.

RESULTS: OK

  • Received block on main chain containing double spent coinstake input on the same block.

– [w/o patch] blocks stored on disk

– [patched] block rejected.

  • Received block on forked chain containing double spent coinstake input on the same block.

– [w/o patch] blocks stored on disk

– [patched] block rejected.

announcementTechUpdates