Investigating Long Range Attack

Theoretical attack against proof of stake

For my dedicated readers, I guess you already know what I’m about to say about long-range attacks … but if you need more convincing, read on.

Long-range attacks are a popular reason to discredit proof of stake algorithms together with the concept of “Weak Subjectivity”. The idea is that at some point of time (most likely at the Genesis block), an attacker can use the existing state of the blockchain, together with a significant stake of the token balance, to create a chain that is indistinguishable from the real chain. The attacker then tricks users into using his malicious chain instead of the real one.

As I previously observed in my article about the “Nothing at Stake” attack, this seemingly simple attack has never been observed in practice. This is of course a strange oddity given what is at stake.

Our friend evil Bob, inspired by articles on the subject, decides to launch a long range attack against Nxt. Bob can easily reproduce the state of the chain at any given block height by simply downloading the blockchain up to this height. Now, he needs to get significant stake of the Nxt token at this block height to create a chain with a better difficulty than the real chain.

If Bob is a large stake holder and has more than 50% of the stake he can always attack Nxt using a normal 51% attack. So, let’s assume for a start that Bob has no significant Nxt balance at the moment.

Luckily for Bob, when Nxt was distributed back in 2013 it was distributed to only 72 lucky stake holders. All Bob has to do is track down these guys and get their account passphrase. In fact, Bob does not need to track all of them - he just needs to get a stake higher than the forging stake at the time of the Genesis block, which was only around 20% of the stake. Finding give or take 5 of the large genesis stake holders and getting their passphrase would be sufficient. Most of these stake holders already moved their funds to another account or sold it, so giving these old account passphrases to Bob would come with little risk. That said, Bob can’t brute force entry to these accounts. This entire attack could end right here if Bob fails to acquire the necessary passphrases to exceed the Genesis staking balance.

Consider that the Nxt distribution is a relatively simple case, most proof of stake tokens were distributed to many more accounts at the Genesis block. Ardor, for example, was distributed to more than 100,000 Nxt holders back in 2016. Still, I assume that getting a stake in the blockchain token larger than the forging power at the time of the Genesis block release is possible for a well-funded and powerful attacker like Bob against any proof of stake coin.

Equipped with the Genesis block that is available to anyone after installing the Nxt software, and 20% of the stake at the time of the genesis block, Bob starts to forge his own malicious chain. Alas, nothing happens, all other Nxt nodes blacklist his node and any other node already using Bob’s fork. New users never connect to Bob’s node.

It appears that the Nxt software implements several simple layers of protection against long-range attacks:

1. The software itself is distributed with a list of bootstrap nodes known to be on the right fork at the time of the release.
2. The Nxt software implements checkpoints of the state of the blockchain at given block heights. Any fork that does not reproduce this exact state is rejected.
3. Transactions use pointers to existing blocks when submitted to the blockchain. These pointers prevent multiple forks from including the same transaction with different block histories.
4. Nodes will never switch to another fork whose chain differs for more than 720 blocks. You can think of it as a rolling checkpoint.

As we will see, none of these features provide foolproof protection alone, but put together, they make it very difficult to implement a long-range attack.

In my previous article, I explained that it will be very difficult for Bob to create a new version of Nxt which does not implement these protections. Even if he does, other users are very unlikely to use his modified version of the software. Therefore, I conclude that Bob can use a modified version on his own nodes, but to effectively implement any attack against Nxt, he will need to cheat users using the official Nxt software without his modifications.

With some effort, Bob can circumvent protection #1 and get his nodes into the list of bootstrap nodes provided with the product. He will need to setup some central nodes and follow the normal chain for a while until some of his nodes make it into the bootstrap list. It would be even more difficult to prevent other nodes from blacklisting his nodes once he starts his attack. Perhaps he can maintain two forks, one honest fork he will show existing nodes connecting to his node, and one malicious fork he will show new users. Implementation of this will be very tricky but still possible.

This way, Bob can attract some new users to his malicious fork. Next, Bob will need to circumvent protection #2 - the built in checkpoints. This is impossible unless he can convince new users to use his version of the software, which we assume is unlikely. To workaround this, Bob can try to start his fork after the latest built-in checkpoint. Assuming the latest checkpoint is not too recent this might still be possible using some of the techniques above.

Another weakness of Bob’s fork is that it won’t be able to accept existing transactions due to protection #3, which means his fork history will differ significantly from the real chain and this will be simple to detect using any block explorer.

Finally, Bob won’t be able to trick existing nodes to move into his malicious fork due to protection #4, the rolling checkpoint.

The worst damage Bob can cause is if he is able to convince a large exchange or business to use his fork. But exchanges and businesses can easily protect against this by checking their fork against a well-known block explorer, which is guaranteed to be on the right fork.

Which brings up the question, can Bob implement a long-range attack in less than 720 blocks to override protection #4, the rolling checkpoint?

For Bob’s attack against the Genesis block or some very old block height, users did not lose much by revealing old account passphrases to Bob. The problem with the short-range attack on recent blocks is that Bob cannot expect anyone to give up their current passphrase without payment. To create the short-range version of the long-range attack, Bob will need to purchase more tokens than the current forging stake, but if he does this, he can just implement a simple 51% attack.

To summarize, long-range attack against proof of stake is a theoretical threat effectively mitigated using simple practical steps.

Postface

A common procedure for creating a private/public key pair is to base it on 12 words selected randomly from a dictionary of 1626 words. This is how the Nxt wallet generates a passphrase for a new account. There are roughly 3.41*10³⁸ combinations, slightly more than 2¹²⁸. In cryptographic terms, this provides 128 bits of security which is considered safe, even against quantum computers, forever.

However, if someone can create memory cells from all the 10⁴⁹ Silicon atoms on Earth and use them to store a pre-image of all possible word combinations and their hashes, they can crack every private key based on its public key in a split second. Still, it is considered safe to use 128 bit keys and rightly so. The point is, we tend to accept algorithms as secure even when theoretical attacks against them exist. The same goes for the Nxt’s proof of stake algorithm.