Preventing Selfish Mining In The Blockchain

The principle of the blockchain is that a "miner" is rewarded for being the first to solve a mathematical problem.  If you're new to Bitcoin I suggest you spend some time watching this video. One of problems with the principle is that it assumes everyone who solves the problem first, actually provides the block that they have in order to continue to build the blockchain.  If a node in the network acts "selfishly" (ie it withholds the block) it can delay transactions and/or waste computing power elsewhere in the network.  It has been an open question as to how one prevents this.

Simply delaying a transaction or making the network work harder wouldn't seem to be much of an attack but it matters for several reasons:

1. The blockchain already has a relatively slow update frequency and so if it is to compete with other transaction systems it has to be sure of being as fast as it can be, and free from possible malicious slowing effects.
2. The problem in the protocol is designed to become progressively harder to solve as time progresses so anything that adds to the computational power required in the network can only make it less economically for people to act as miners.
3. If someone can disrupt your financial transaction engine, albeit just a delay, it will erode trust in the robustness of the system.

The incentives for conducting such attacks are not always that obvious but they are very real and make it an attractive endeavour.  It was laid out very nicely in this paper in 2014 entitled "Majority is not Enough: Bitcoin Mining is Vulnerable".

The problem was further discussed by Ittay Eyal at the IEEE Syposium on Privacy and Security in 2015.

which was accompanied by a paper entitled "The Miner's Dilemma". 

Several groups have been working on how to prevent these block withholding attacks, and in the last week one has produced a proposal called ZeroBlock.  It is described in a paper entitled "ZeroBlock: Preventing Selfish Mining In Bitcoin".

The algorithm they propose is best summed up in this diagram from the paper:

ZeroBlock generation has to be conducted by a node known to be honest to prevent block withholding . First assume B2: B2 are generated by a selfish node and kept until some delayed time ET2 and thus have expired as valid blocks. The Proof of Work of B2 includes only the hash of B1 and thus will be rejected by the honest node. As the honest node didn’t receive a new block until ET2 it generates a ZeroBlock. Now for Block 3 the Proof of Work will include the hash of (B1 + ZeroBlock) and will be accepted.

The "correctness" of the algorithms is proven and thereby develops 5 theorems which appear to be hold in the conditions discussed.

The million Bitcoin question is will this algorithm or a derivative make their way into the blockchain algorithm used in Bitcoin (or other cryptocurrencies)?  Given the problems in agreeing something as simple as changing the size of the blocks in order to speed up transactions, I fear it may be some time.