Preventing mining pool concentration with Lamport signatures

a simple hack

edit: here’s a far more efficient way to do this https://medium.com/@lmgoodman/7c7ba2d6a1b (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

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

x is the 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

1. The miner cannot change the content of the block after he’s found a solution — this, of course, is essential.
2. 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.
3. 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.
4. No fancy mathematics (SNARKs, etc)
5. The chain difficulty is still readable from the headers by a SVC
6. 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)