Several cryptocurrencies have implemented proof-of-stake, but, as yet, the versions of it that they have implemented are subject to attacks based on what has been called the “nothing-at-stake” problem.

I outline the problem and a partial solution below.

In order to distinguish a “correct” blockchain from an orphan (or attacking) blockchain, proof-of-work relies on the provable expenditure of a finite resource – compute power. The nothing-at-stake problem arises when there is no ability to prove expenditure of a similarly finite resource to distinguish a correct from an orphan blockchain in a proof-of-stake cryptocurrency.

Proof-of-stake as implemented in existing cryptocurrencies treats “coin days” as the finite resource whose expenditure distinguishes correct from attack blockchains. The idea behind this is that when a txout is used in a transaction, the time since it was created is multiplied by the number of coins it represents to get a number of “coin days.” And the assumption is that whichever blockchain has created (or used up, depending on how you think of it) the greatest number of coin days is accepted as legitimate.

Nothing-at-stake arises because “coin days” are not a finite resource in the way we need a resource to be finite in order to resist attacks. When there is a fork, stake is duplicated on both sides of the fork. This leads to attacks based on the use of stake that the attacker has already spent in the other fork. Also, the same unspent txout can generate more or fewer “coin days” depending on when it is spent, so an attacker can spend coins on both sides of a fork while choosing which side to generate more “coin days” in.

Also, under proof-of-stake, there is no need for a miner to forsake one side of a fork in order to support another; The miner has the same stake on both sides of the fork, and would be an idiot to stop generating blocks supporting either side until he is absolutely certain which side which will be orphaned. That makes the support of miners effectively useless for deciding which side is to be orphaned.

Finally, new unspent txouts are generated by transactions, including coinbase transactions, on both sides of the fork, and expenditures of these txouts are ‘noise’ that an attacker (in an attack which gives the attacker control of a higher proportion of the coinbase txouts on one side of a fork) can take advantage of to generate more coin days in his attack chain than in the legitimate chain.

A partial solution to “nothing at stake” is to focus on a resource which really is finite in the way we need it to be: Uncontested expenditures of txouts that existed at the moment when the blockchains diverged.

When comparing two sides of a fork, instead of counting coin days, we should count the expenditure of txouts that existed at the moment of divergence. But we should count only those transactions that do not conflict with (do not use any of the same txouts as) transactions on the other fork. And we should count them strictly for the number of coins spent, rather than varying it by block height as in counting “coin days”.

This means it is transactions, and not mining, that supports the security of the blockchain. In order for transaction support to be finite (necessarily count for only one side of the fork) it is necessary for transactions to give a block hash from the blockchain they support. Any transaction that gives a pre-fork block hash can be replayed into either side of the fork, thus cancelling its support for the other side. Any transaction that gives a post-fork block hash can be counted as support only for the fork in which that block hash appears. Thus, transactions that name more recent block hashes (within the last 1-3 blocks) are more valuable for securing the chain than transactions that name earlier block hashes (within the last 4-7 blocks), and if compensated via proof-of-stake ‘interest’ payments for securing the chain, should be compensated more. Transactions giving block hashes older than 8 blocks are not terribly useful in securing the chain, and should not be accepted.

Because this solution is not subject to nothing-at-stake, at the very least attackers have to use real as opposed to already-spent stake to attack it, and cannot support their attacks by making transactions using the same coinbases they are trying to steal via their attacks.

But this is still a partial solution. There is still a flaw in that someone making a transaction can easily make it in both sides of a fork, therefore supporting neither. Further, there is some motive for them to do so, unless such transactions can be demonstrated based on information to be recorded in the main branch and their proof-of-stake payment for securing the chain withheld. I believe that this is possible, but complex and possibly unnecessary.