[Cryptography] Preventing proof-of-work outsourcing in bitcoin with Lamport signatures

[L. M. Goodman]

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.

I'm not 100% sure it is correct. I may have missed a gaping flaw, if so please point it out!

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

First, the miner forms two pairs of public/private Lamport keys. 

The miner then hashes the block header along with both signatures, signs this hash with the first signature, combines the result with a transaction to the coinbase, and then signs with the second Lamport private key. The overall hash must then meet the difficulty target.

- Lamport keys are (S1,P1) and (S2,P2) 
- B is the usual bitcoin block header (timestamp, merkle hash of transactions, etc) is B
- Sha is the SHA-256 hashing function
- Sign(S,Sha(M)) the Lamport signature of the digest of message M using secret key S
- + the xor function
- ct the coinbase transaction

We are computing

x = Sha(Sign(S2, Sha(ct+Sha(Sign(S1, Sha(B+P1+P2))))))

x is the the block hash and is the number that must meet the difficulty target.

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 perfomed 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 48kb to each block (which is still less than 5% of the maximum block size)