Disincentive to pool mining with Fawke signatures
(inspired by improvements from @RKHilbertSpace to my original Lamport scheme)
It’s not clear that preventing mining pool from forming at all is a good idea to begin with — see “Why mining variance matters” . That said, if such a goal needed to be achieved, here’s one way to do it relying only on SHA-256 operations.
First the miner builds a block and hashes the block header, yielding B. He also picks a secret key S. Let H be the SHA-256 digest of a message.
The miner then looks for a number X for which H(H(S+B+X)+X+B) < difficulty. He cannot outsource this task to other miners without revealing S, nor can he just hold X constant, publish H(S+B+X) and outsource the finding of a block header that solves the equation. If a solution is found, the miner publishes the block (H(S+B+X),B,X)
After the block has been accepted, the miner follows a two step process. Fist, he submits a special transaction publishing H(S+B) and an bitcoin address A. Then, at a later time, he publishes S. This proves that he had knowledge of S and the mining reward is payed to address A. The two-stage reveal needs to happen over enough block so that a block chain reorganisation does not allow the coins to be stolen. However, this security requirement already exists for newly mined coins, which are also vulnerable to reorganisations.
This only adds a few bytes to every block and requires only a trivial change to the protocol.