Proof that Proof of Stake is either extremely vulnerable or totally centralised

[monsterer]

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.

[jl777]

Where can I buy these keys? I am interested to buy up any PoS using this method and then short sell it

Theoretical vs Practical issues.

Also, what if the PoS chain utilized a PoW chain, like BTC? By effectively using BTC blockhashes directly in a PoS, you can get at least a backstop level of protection. By putting in a moving checkpoint onto the BTC blockchain, then you can create a decentralized and verifiable PoS chain.

Use BTC at the trusted party. Now maybe that changes it from a pure PoS, but maybe you can see a way to attack that too? The assumption is that all nodes are directly monitoring the BTC blockchain and the PoS staking node also puts data into the BTC blockchain, maybe once per hour or so.

James

[monsterer]

Where can I buy these keys? I am interested to buy up any PoS using this method and then short sell it

Theoretical vs Practical issues.

Also, what if the PoS chain utilized a PoW chain, like BTC? By effectively using BTC blockhashes directly in a PoS, you can get at least a backstop level of protection. By putting in a moving checkpoint onto the BTC blockchain, then you can create a decentralized and verifiable PoS chain.

Use BTC at the trusted party. Now maybe that changes it from a pure PoS, but maybe you can see a way to attack that too? The assumption is that all nodes are directly monitoring the BTC blockchain and the PoS staking node also puts data into the BTC blockchain, maybe once per hour or so.

James

Imagine the temptation for any stakeholder being presented with an offer to buy his empty private key for $1000? It has no value to him, he gets 'free' money and is unaware of the risks.

Using BTC as a provider of sidechains for PoS candidates has been discussed before, of course. I haven't studied it well enough to form any conclusions on the viability of combined consensus techniques.

[jl777]

Where can I buy these keys? I am interested to buy up any PoS using this method and then short sell it

Theoretical vs Practical issues.

Also, what if the PoS chain utilized a PoW chain, like BTC? By effectively using BTC blockhashes directly in a PoS, you can get at least a backstop level of protection. By putting in a moving checkpoint onto the BTC blockchain, then you can create a decentralized and verifiable PoS chain.

Use BTC at the trusted party. Now maybe that changes it from a pure PoS, but maybe you can see a way to attack that too? The assumption is that all nodes are directly monitoring the BTC blockchain and the PoS staking node also puts data into the BTC blockchain, maybe once per hour or so.

James

Imagine the temptation for any stakeholder being presented with an offer to buy his empty private key for $1000? It has no value to him, he gets 'free' money and is unaware of the risks.

Using BTC as a provider of sidechains for PoS candidates has been discussed before, of course. I haven't studied it well enough to form any conclusions on the viability of combined consensus techniques.

Imagine the difficulty of contacting enough such stakeholders. So with a very long term horizon and actively targeting a coin and aggressively buying keys (has anyone every actually done even a single sale) from ex-whales, then at some point you have enough keys, but you cant go back in time with a one day moving checkpoint. So now you need to setup a zillion nodes to sucker in newbies and exchanges?

also the lack of any large short selling market. My estimate is the manual labor cost to do this makes it have a negative expected return and as such is in the same category of economically nonviable endeavors.

Anyway, my interest on this topic is not about pure PoS, but a way to allow all of crypto to benefit from the electricity BTC is using.

I wrote up a little bit on how to use BTC as a unversal sequence server, like a clock for all of crypto.
https://bitcointalk.org/index.php?topic=1372879.msg14034846#msg14034846

It came out of a post  made the other day, so I am sure it is not perfect, but I am pretty sure that weak PoS chains can be made a lot more secure by utilizing BTC. It would make BTC the heart of all these hybrid BTC/PoS and should appeal to the BTC maximalists.

As always, I am agnostic. I just seek the truth to find the best solution for each specific case

James

[monsterer]

Imagine the difficulty of contacting enough such stakeholders. So with a very long term horizon and actively targeting a coin and aggressively buying keys (has anyone every actually done even a single sale) from ex-whales, then at some point you have enough keys, but you cant go back in time with a one day moving checkpoint. So now you need to setup a zillion nodes to sucker in newbies and exchanges?

I just imagine setting up a forum post to get the key stake holders together with a trusted escrow to action it in one go. Can't see that being difficult, or expensive.

Remember, these are not ex-whales, these are current whales and they're not selling their stake, they're selling old private keys which are now empty and thus valueless.

In addition, the one day moving checkpoint you're describing is a reorg-depth limit, not a checkpoint. A checkpoint is a block hash and a height.

[jl777]

Imagine the difficulty of contacting enough such stakeholders. So with a very long term horizon and actively targeting a coin and aggressively buying keys (has anyone every actually done even a single sale) from ex-whales, then at some point you have enough keys, but you cant go back in time with a one day moving checkpoint. So now you need to setup a zillion nodes to sucker in newbies and exchanges?

I just imagine setting up a forum post to get the key stake holders together with a trusted escrow to action it in one go. Can't see that being difficult, or expensive.

Remember, these are not ex-whales, these are current whales and they're not selling their stake, they're selling old private keys which are now empty and thus valueless.

In addition, the one day moving checkpoint you're describing is a reorg-depth limit, not a checkpoint. A checkpoint is a block hash and a height.

what I suggest is a moving checkpoint, utilizing BTC blockhashes

[stdset]

This attack is known for years, just the first link from google: https://bitcointalk.org/index.php?topic=1019320.0
It's not easy to carry it out though.
Imagine you bought a key k1. In order to keep it's balance, the latest point where you can start building you fork is right before the key was emptied. Now you can buy another empty (on the main chain) key k2, but what state the key k2 is on your fork? Your history is different (on your branch you must exclude all transactions that depend on transaction that spends k1), maybe k2 was never funded on your fork, if it was, OK you buy it, but your history inevitably drifts away from the main history more and more and it becomes more and more difficult to find suitable keys from the main chain to buy.
Also I can't agree, that setting a limit on the reorg depth doesn't help. In the case of such a major attack node owners will have to manually choose what branch they want to stay on, and likely it will be easy to see which branch is a legit one.

[monsterer]

This attack is known for years, just the first link from google: https://bitcointalk.org/index.php?topic=1019320.0
It's not easy to carry it out though.
Imagine you bought a key k1. In order to keep it's balance, the latest point where you can start building you fork is right before the key was emptied.
Now you can buy another empty (on the main chain) key k2, but what state the key k2 is on your fork? Your history is different, maybe k2 was never

The attacker buys all keys at once, or very close together as stated in the description.

Also I can't agree, that setting a limit on the reorg depth doesn't help. In the case of such a major attack node owners will have to manually choose what branch they want to stay on, and likely it will be easy to see which branch is a legit one.

How can they be sure which branch is legitimate? If the re-org depth is very small, it will be indistinguishable from a regular re-org. In any case, such manual intervention is equivalent to centralised control, and we're back to the same conclusion again.

[jl777]

This attack is known for years, just the first link from google: https://bitcointalk.org/index.php?topic=1019320.0
It's not easy to carry it out though.
Imagine you bought a key k1. In order to keep it's balance, the latest point where you can start building you fork is right before the key was emptied. Now you can buy another empty (on the main chain) key k2, but what state the key k2 is on your fork? Your history is different, maybe k2 was never funded on your fork, if it was, OK you buy it, but your history inevitably drifts away from the main history more and more and it becomes more and more difficult to find suitable keys from the main chain to buy.
Also I can't agree, that setting a limit on the reorg depth doesn't help. In the case of such a major attack node owners will have to manually choose what branch they want to stay on, and likely it will be easy to see which branch is a legit one.

I have a use case of needing to have many weak chains all be able to do atomic swaps between each other and to be as secure as possible. The problem is that there probably will only be a dozen nodes per chain and PoS is the only practical way to secure these chains. While it would be great to have an unlimited electricity budget, these nodes wont, especially the ones running off of batteries.

So, while the ultimate super duper security is by doing a zillion hashes and PoW, I dont think anybody debates this. The issue is that not all networks can afford this, so the choice is not between PoW and PoS, the choice is between PoS and no network at all.

My idea is to infuse these weak chains with BTC's security. Not for every tx of course, but certainly a backstop from reorgs that go too deep is one protection. Just knowing that after X amount of time, it cant be changed, regardless of how smart/powerful an attacker comes around.

The other thing that BTC can provide via a few consensus rules is a common clock. By segmenting time periods to match the BTC blocktimes (probably grouped into batches of 10 or so), then all the different chains can have a verifiable common reference. The mere presence of a BTC blockhash proves an "after" time relationship.

To get the "before", the weak chains will need a consensus rule to either reject or add any later BTC blockhash that is available. Only "permanent" BTC blockhashes are used, ie 10+ blocks to avoid confusions from small reorgs. maybe it needs to be 30 blocks, but some amount where we can be pretty certain that it will never get reorged.

With a leeway of one to account for lag time that happens when a new block arrives, all chains can have at least a +/- 1 btc block resolution. The consensus rules still need to be completely worked out, but so far, nobody has found a fatal flaw. Which means even the weakest chain with enough confirmations will be able to trade with other weak chains and still with enough confirms (past the max reorg allowed), all can pretend they have BTC level security. Of course prior to reaching the permanent point, any weak chain is subject to all the usual suspects of attacks

including the fantasy one of buying old keys for $5 or $500 or whatever token amount is supposed to be possible. It just isnt so easy to buy something at significantly less than what they are worth from rich crypto traders. Arguably, anybody with a privkey that used to be a large enough stake you want to obtain it, is smart enough to ask for market value. So the cost of the private keys will trade at the expected value for them, with a bit of a discount. And it would not be a contingent payment as once the privkey is delivered there is no way to collect. So now we are looking at not $5 for "worthless" keys, but $X upfront, where X is some discount from the expected value, ie chance of success * size of successful attack. So this goes from a riskless attack to one that rapidly approaches some sort of breakeven level, but uncertain proposition.

The bigger attack that any coin PoW or PoS has is the hardfork attack. This attack is when the parties that control the hardfork version can transfer value from one part of the system to themselves. Their self interest assures they will do this if such a hardfork is available. What this means is that ALL derived cryptos are totally insecure from the hardfork attack.

James

[Come-from-Beyond]

"It was a bright cold day in April, and the clocks were striking thirteen."

Use this secret phrase to get access to Nxt account holding all the coins. Now you have all the keys you were looking for, what's next?

[monsterer]

"It was a bright cold day in April, and the clocks were striking thirteen."

Use this secret phrase to get access to Nxt account holding all the coins. Now you have all the keys you were looking for, what's next?

Sorry, I don't follow you?

[jl777]

"It was a bright cold day in April, and the clocks were striking thirteen."

Use this secret phrase to get access to Nxt account holding all the coins. Now you have all the keys you were looking for, what's next?

you could have gotten a BTC for it!

now the history attack is all but completed. Just need to run 1000 nodes with a fake (but somewhat believable history), then make all new accounts use the fake chain, and please ignore the long running nodes on the mainchain, that chain is not relevant anymore. Only the attacker's chain matters, so all the exchanges and blockexplorers will simply move to the attackers chain.

Happens all the time. Wont cost anything at all for this free attack.

James

[Come-from-Beyond]

"It was a bright cold day in April, and the clocks were striking thirteen."

Use this secret phrase to get access to Nxt account holding all the coins. Now you have all the keys you were looking for, what's next?

Sorry, I don't follow you?

In the very beginning Nxt had all the coins kept on a single account that is accessible through that phrase.

[jl777]

"It was a bright cold day in April, and the clocks were striking thirteen."

Use this secret phrase to get access to Nxt account holding all the coins. Now you have all the keys you were looking for, what's next?

Sorry, I don't follow you?

He saved you thousands of dollars for the privkey. that privkey is the one for the original genesis account. with it you can make any new chain you want

[jl777]

I look forward to the proof of the OP's conclusion "The cost of this attack is very low"

[monsterer]

"It was a bright cold day in April, and the clocks were striking thirteen."

Use this secret phrase to get access to Nxt account holding all the coins. Now you have all the keys you were looking for, what's next?

Sorry, I don't follow you?

In the very beginning Nxt had all the coins kept on a single account that is accessible through that phrase.

This attack doesn't work that way. It relies on contemporary private keys, from very recent history.

[Come-from-Beyond]

He saved you thousands of dollars for the privkey. that privkey is the one for the original genesis account. with it you can make any new chain you want

Yes, but the point is that I'd like to know what next steps are. I suspect that security is not broken completely once someone has the keys, some other factors should be taken into account, but the corresponding analysis is not presented in the OP.

[Come-from-Beyond]

This attack doesn't work that way. It relies on contemporary private keys, from very recent history.

I still don't agree with "totally centralised" part. I feel something lacks in the analysis.

[Coryvmcs1]

How does this affect PoW/ Pos Systems. Or is this just PoS only chains?

[monsterer]

He saved you thousands of dollars for the privkey. that privkey is the one for the original genesis account. with it you can make any new chain you want

Yes, but the point is that I'd like to know what next steps are. I suspect that security is not broken completely once someone has the keys, some other factors should be taken into account, but the corresponding analysis is not presented in the OP.

What would you like more detail on?