Proof-of-capacity whitepaper

Perhaps this should be moved to NebulousLabs/Experimental? Or maybe we should just have a Papers repository...
I don't think it'd be reliably detectable, but I could be wrong.

How to execute a non-optimal attack: for each challenge, you look at the 10 or 100 closest responses. You can get all of these in a single generation of the data. Then, for the 10-100 responses, you see which next-challenge is most favorable.

So, each of the 10-100 potential responses will be suboptimal by some distance. If they produce a target that improves your potential best answer by more than that distance, then you pick the non-greedy response and improve your overall score.

A live-compute attacker still only needs to compute the whole data set a single time per sequential choice, they just store the 100 potential responses and the 100 potential responses resulting from each. This in total is 10,000 indices. Once they know the single potential response that is best of the space they have searched, they throw away the other 99 and their potential responses, bringing the memory footprint back down to 100 indices.

This wouldn't search the whole tree of potential answers, but it would search enough of it to get an improvment over the greedy solution.