Gaming Proof of Stake

While working on a draft for a paper for the upcoming Ledger academic journal I came across the concept of "stake grinding". After considering this problem for awhile, I think I came up with a neat solution to it under some specific conditions. Lets discuss...

Proof of Stake and Stake Grinding

Proof of Stake is an alternative block generation algorithm to Proof of Work. In it, blocks are not generated by mining pools roughly in proportion to the computing power they hold, but by block producers / minters / notaries or however you want to call them roughly in proportion to the amount of coins they own / stake.

In PoW, blocks are created at random whenever a solution is found, making the network block creation time somewhat random and unpredictable.

In PoS, the blocks can be generated on a more fixed schedule since once a block is created there is no randomness as to who should create the next block - the minter is picked using the randomness inherent in block creation and the balances in the network.

However, if we use a naive implementation of PoS, we open ourselves to the block minters grinding the block to ensure they are also the creators of the next block or some other block in the future (say, if you use a scheme where a block minter is selected by an entropy from 100 blocks back). If you have only one attacker grinding the blocks, they will eventually become the only entity creating the blocks no matter how small their balance is. Since honest minters would select them to mine the blocks every now and then and the attacker would make sure their blocks nominate them to be the minters with 100% certainty, they will be minting more and more blocks.

From what I could find (see section 6.4), stake grinding has been used on a few systems like NXT or Peercoin with success, forcing the networks to abandon the naive approach.

Potential solutions

There are a few solutions to stake grinding. Peercoin appears to have adopted a hybrid PoS-PoW model to make grinding less trivial. BitShares used a Delegated Proof of Stake where the block minters each get to create one block before the order is reshuffled and everyone gets another turn - an interesting approach, but it treats a minter with 50% of support the same as one with 10% of support.

Now, there might be a way to implement Proof of Stake in such a way as to avoid the grinding problem altogether and reward all minters in proportion to their stake / support. It is inspired by CGP Grey's video on Mixed-Member Proportional Representation voting system (a part of his very interesting series "Politics in the Animal Kingdom"):

In the new scheme, we would need to create a list of all minters that want to participate in the block creation process and figure out their weight based on the amount of stake / support / votes they represent. The list would have to be locked in for a certain minting period, similarly to BitShares' implementation. Given this information, we can start creating blocks in a deterministic fashion. Each block minter would be chosen based on who is the most underrepresented in a given minting period. They would be chosen to be the next block minter. After a new block is created, the representation is updated and the next minter is chosen in the same fashion. You could also deterministically break up large chains of blocks being created by the same minter to prevent 51% attacks, or implement a punishment algorithm for creating forks.

This approach would both eliminate grinding and give fairer rewards than DPoS.