Written by L.M. Goodman. Hosted here as a courtesy.

a simple hack

edit: here’s a far more efficient way to do this Disincentive to pool mining with Fawke signatures (inspired by a post from @RKHilbertSpace)

It occurs to me that there is a simple hack which could prevent the concentration of bitcoin mining pools. It only requires a minimal change to the bitcoin protocol and, quite importantly, it does not penalize the existing investments in ASICs.

Instead of having the miner attempt to produce a block hash matching the difficulty, we have the miner generate Lamport signatures.

First, the miner forms a pair of public/private Lamport keys.

The miner then hashes the block header along with the signature and signs this hash, the hash of this signature must then meet the difficulty target.

• Lamport keys are S (secret) and P (public)
• B is the usual bitcoin block header (timestamp, merkle hash of transactions, etc)
• Sha is the SHA-256 hashing function
• Sign(S,Sha(M)) is the Lamport signature of the digest of message M using secret key S
• + is the xor function

We are computing

1
x = Sha(Sign(S, Sha(Sha(B)+Sha(P)))))))

x is the block hash and is the number that must meet the difficulty target. The miner can collect his reward at a later time, using the same key. Since the security parameter of a Lamport key halves after each signature on average, we use a signature of 512 x 256 bit hashes.

Some key properties:

• The miner cannot change the content of the block after he’s found a solution — this, of course, is essential.
• The miner cannot safely outsource the computation to a pool he does not control, not even the cloud: finding a solution involves knowledge of the private key.
• All the work consists in repeated applications of the SHA-256 function. Thus, this can be performed entirely using the existing ASICs (perhaps with very minor tweaks) and thus respects the value of the existing mining investment.
• No fancy mathematics (SNARKs, etc)
• The chain difficulty is still readable from the headers by an SPV client
• The main downside is the size of the Lamport signatures, adding an average 64kb to each block (which is 6.25% of the maximum block size)