Slasher: A Punitive Proof-of-Stake Algorithm

The purpose of this post is not to say that Ethereum will be using Slasher in place of Dagger as its main mining function. Rather, Slasher is a useful construct to have in our war chest in case proof of stake mining becomes substantially more popular or a compelling reason is provided to switch. Slasher may also benefit other cryptocurrencies that wish to exist independently of Ethereum. Special thanks to tacotime for some inspiration, and for Jack Walker for improvement suggestions.

Proof of stake mining has for a long time been a large area of interest to the cryptocurrency community. The first proof-of-stake based coin, PPCoin, was releasd by Sunny King in 2012, and has consistently remained among the top five alternative currencies by monetary base since then. And for good reason; proof of stake has a number of advantages over proof of work as a mining method. First of all, proof of stake is much more environmentally friendly; while proof of work requires miners to effectively burn computational power on useless calculations to secure the network, proof of stake effectively simulates the burning, so no real-world energy or resources are ever actually wasted. Second, there are centralization concerns. With proof of work, mining has been essentially dominated by specialized hardware (“application-specific integrated circuits” / ASICs), and there is a large risk that a single large player such as Intel or a major bank will take over and de-facto monopolize the market. Memory-hard mining algorithms like Scrypt and now Dagger mitigate this to a large extent, but even still not perfectly. Once again, proof of stake, if it can be made to work, is essentially a perfect solution.

However, proof of stake, as implemented in nearly every currency so far, has one fundamental flaw: as one prominent Bitcoin developer put it, “there’s nothing at stake”. The meaning of the statement becomes clear when we attempt to analyze what exactly is going on in the event of an attempted 51% attack, the situation that any kind of proof-of-work like mechanism is intended to prevent. In a 51% attack, an attacker A sends a transaction from A to B, waits for the transaction to be confirmed in block K1 (with parent K), collects a product from B, and then immediately creates another block K2 on top of K – with a transaction sending the same bitcoins but this time from A to A. At that point, there are two blockchains, one from block K1 and another from block K2. If B can add blocks on top of K2 faster than the entire legitimate network can create blocks on top of K1, the K2 blockchain will win – and it will be as if the payment from A to B had never happened. The point of proof of work is to make it take a certain amount of computational power to create a block, so that in order for K2 to outrace K1 B would have to have more computational power than the entire legitimate network combined.

In the case of proof of stake, it doesn’t take computational power to create a work – instead, it takes money. In PPCoin, every “coin” has a chance per second of becoming the lucky coin that has the right to create a new valid block, so the more coins you have the faster you can create new blocks in the long run. Thus, a successful 51% attack, in theory, requires not having more computing power than the legitimate network, but more money than the legitimate network. But here we see the difference between proof of work and proof of stake: in proof of work, a miner can only mine on one fork at a time, so the legitimate network will support the legitimate blockchain and not an attacker’s blockchain. In proof of stake, however, as soon as a fork happens miners will have money in both forks at the same time, and so miners will be able to mine on both forks. In fact, if there is even the slightest chance that the attack will succeed, miners have the incentive to mine on both. If a miner has a large number of coins, the miner will want to oppose attacks to preserve the value of their own coins; in an ecosystem with small miners, however, network security potentially falls apart in a classic public goods problem as no single miner has substantial impact on the result and so every miner will act purely “selfishly”.

The Solution

Some have theorized that the above argument is a deathblow to all proof of stake, at least without a proof of work component assisting it. And in a context where every chain is only aware of itself, this is indeed provably true. However, there is actually one clever way to get around the issue, and one which has so far been underexplored: make the chain aware of other chains. Then, if a miner is caught mining on two chains at the same time, that miner can be penalized. However, it is not at all obvious how to do this with a PPCoin-like design. The reason is this: mining is a random process. That is to say, a miner with 0.1% of the stake has a 0.1% chance of mining a valid block on block K1, and a 0.1% chance of mining a valid block on block K2, but only a 0.0001% chance of mining a valid block on both. And in that case, the miner can simply hold back the second block – because mining is probabilistic, the miner can still gain 99.9% of the benefit of mining on the second chain.

The following proposal, however, outlines an algorithm, which we are calling Slasher to express its harshly punitive nature, for avoiding this proposal. The design description given here uses address balances for clarity, but can easily be used to work with “unspent transaction outputs”, or any other similar abstraction that other currencies may use.

1. Blocks are mined with proof of work. However, we make one modification. When creating a block K, a miner must include the value H(n) for some random n generated by the miner. The miner must claim the reward by releasing a transaction uncovering n between block K+100 and K+900. The proof of work reward is very low, ideally encouraging energy usage equal to about 1% of that of Bitcoin. The target block time is 30 seconds.
2. Suppose the total money supply is M, and n[i] is the n value at block i. At block K+1000, an address A with balance B gains a “signing privilege” if sha256(n[K] + n[K+1] + … + n[K+99] + A) < 2^256 * 64 * B / M. Essentially, an address has a chance of gaining a signing privilege proportional to the amount of money that it has, and on average 64 signing privileges will be assigned each block.
3. At block K+2000, miners with signing privileges from block K have the opportunity to sign the block. The number of signatures is what determines the total length of one blockchain versus another. A signature awards the signer a reward that is substantially larger than the proof of work reward, and this reward will unlock by block K+3000.
4. Suppose that a user detects two signatures made by address A on two distinct blocks with height K+2000. That node can then publish a transaction containing those two signatures, and if that transaction is included before block K+3000 it destroys the reward for that signature and sends 33% to the user that ratted the cheater out.

The key to this design is how the signing privileges are distributed: instead of the signing privilege being randomly based on the previous block, the signing privilege is based on the block two thousand blocks ago. Thus, in the event of a fork, a miner that gets lucky in one chain will also get lucky in the other, completely eliminating the probabilistic dual-mining attack that is possible with PPCoin. Another way of looking at it is that because Slasher uses proof-of-stake-2000-blocks-ago instead of proof-of-stake now, and forks will almost certainly not last 2000 blocks, there is only one currency supply to mine with, so there is indeed “something at stake”. The penalty of block reward loss ensures that every node will take care to sign only one block at each block number.

The use of 100 pre-committed random numbers is an idea taken from provably fair gambling protocols; the idea is that powerful miners have no way of attempting to create many blocks and publishing only those that assign their own stake a signing privilege, since they do not know what any of the other random data used to determine the stakeholder is when they create their blocks.

The system is not purely proof-of-stake; some minimal proof-of-work will be required to maintain a time interval between blocks. However, a 51% attack on the proof of work would be essentially inconsequential, as proof of stake signing is the sole deciding factor in which blockchain wins. Furthermore, the energy usage from proof of work can be made to be 95-99% lower, resolving the environmental concern with proof of work.