What ever happened to Non-Outsourceable Puzzles? Now that big miners have consolidated power over Bitcoin, maybe it's time to take another look at non-outsourceable puzzles. (link to PDF inside)

https://cs.umd.edu/~amiller/nonoutsourceable_full.pdf

Abstract:

An implicit goal of Bitcoin’s reward structure is to diffuse network influence over a diverse, decentralized population of individual participants. Indeed, Bitcoin’s security claims rely on no single entity wielding a sufficiently large portion of the network’s overall computational power.

Unfortunately, rather than participating independently, most Bitcoin miners join coalitions called mining pools in which a central pool administrator largely directs the pool’s activity, leading to a consolidation of power.

...

We argue that the prevalence of mining coalitions is due to a limitation of the Bitcoin proof-of-work puzzle – specifically, that it affords an effective mechanism for enforcing cooperation in a coalition.

We present several definitions and constructions for “nonoutsourceable” puzzles that thwart such enforcement mechanisms, thereby deterring coalitions. We also provide an implementation and benchmark results for our schemes to show they are practical.