Introduction

This is an very informal proof, because I wanted it to be as readable as possible for the majority of readers. I hope this will finally show why Proof of Stake (PoS) is not a viable consensus design.

This particular attack is called 'keys from the past', or the 'history attack' and is endemic to the design of PoS.

Recap of Proof of Stake

PoS requires bonded stake in order to generate a block. The more bonded stake, the higher the probability you can generate a block and this probability is linear in stake and is also a constant over any amount of time. It is possible for a majority stake holder to have a 100% probability of generating every block; this is something like 33% of all stake. The attack works like this:

The attack

1. The attacker simultaneously purchases a majority of old staking private keys, which were very recently used to stake with and are now empty and as such valueless to the seller(s)
2. He uses these historical keys to generate a new chain of history starting just before the keys were emptied and which is longer in cumulative difficulty than the canonical chain. He can do this first time with 100% probability since he has a majority of historical stake
3. He can then either steal the coins back to himself and carry on, or can bring the entire chain to a total halt by excluding all transactions.

Motivation

By taking out a massive short on an exchange before he carries out this attack, he can make it even more profitable. He can also hold the chain to ransom by excluding transactions at will, or by charging extra fees to include them.


Mitigations

It doesn't even matter if the chain itself has a re-org depth limit because it is quite possible that he can generate this new history in under the limit of the reorg depth. Even if he can't, it doesn't matter because all syncing nodes will be vulnerable to accepting his fake history as genuine and since impersonating a general network node has ~0 cost, he can impersonate a majority of nodes such that any syncing node querying at random will find his fake nodes with fake history. Given sufficient time, his history becomes canonical.

Checkpoints

The only mitigation for this attack is to enforce checkpoints from some trusted location. At this point, the currency has totally ceased to be decentralised, since the consensus result has been reduced to a consensus of one, which is the same as having no consensus at all. This is the antithesis of decentralisation.

Conclusion

The cost of this attack is very low since empty private keys have no value. All PoS chains are vulnerable to this attack because the cost of block production is close to zero, which is the chief reason this is possible. A reorg depth limit is ineffective at preventing this attack for the reasons described.
Checkpoints completely fail to be decentralised or trustless in any way; the network of nodes are reduced to simple database replication slaves in a system with far higher cost and inconvenience, lower performance and the same level of security as a centralised service.