Stored Proofs Of Work

A thought experiment in consensus algorithms

There’s a distinct shortage of Nakamoto consensus algorithms. The ones which have been built and work are proofs of work and proofs of space and time. I’ll now explain a third option, proofs of stored work (and time). I’m not saying this is something which people should rush out and build, but it is something which would work, and is a novel idea, so is worth thinking about.

Like proofs of space, stored proofs of work make responses to a challenge which have some quality, and if that quality is high enough they sign a block which makes it into the blockchain. Also like proofs of work they have to be combined with proofs of time to function. It would be possible to take the Chia codebase change it to use stored proofs of work instead of proofs of space while leaving all the timelording and such alone and the result would be a working system.

A stored proof of work consists of three things: A public key, a quality multiplier, and a nonce. To check if it’s valid you hash the whole thing to a value between 0 and 1 and multiply by the quality multiplier. If the result is less than 1 it’s valid, otherwise it isn’t. The details of how the hashing is done have the same criteria as ordinary proof of work do. I’m not going to delve into a discussion of whether being asic-resistant or asic-friendly is the better approach here. To find the quality of the response of a valid stored proof of work to a challenge you hash them both together and multiply by the quality multiplier.

The theory behind this fairly trivial but slightly odd construction is that anyone making stored proofs of work gets rewards roughly proportional to the amount of work they’ve done in the past. There’s a very interesting question of whether you could have a good proof of work which accumulates work as it’s done but it’s much more expedient to reward it in constant units and let each miner decide what they want their granularity to be. If they get too few rewards their variance will be extremely high. If they get too many then they’ll have to do a nontrivial amount of compute in response to each challenge to see if they win. A miner sets it up so they get, say, 10 rewards per day then they’ll have low variance after just a few months and the amount of computer necessary to check all their rewards for each challenge will still be trivial even after many years.

There are interesting questions like how to make it possible for miners to sell their keys to other miners but this is meant as a thought experiment not a full blown proposal. I’m not terribly attached to the term ‘stored proof of work’. It’s not exactly right but it’s what my brain keeps referring to it as and I don’t have a better name yet.