Proof-of-Work systems such as hashcash, it seems to me, do not actually prove that a certain amount of work has been performed. For example, in the case of hashcan, could not the first random hash choice just get lucky? Thus almost no actual "work" was performed?
My question is on the existence (and practicality) of methods that guarantee, within a probability, that a given minimum amount of "work" has been performed in each and every case, without compromising the average or maximum amounts.
On hashcash then, the probability of failing to prove work is the chance of "getting lucky". So, with a 20 bit zero hash target, that's around a few in a million (the first few random attempts out of a 2^20 space). Therefore a few in a million hashcans won't really be doing any work. But if i wanted to reduce this proof-of-work fail to a lower probability, simply increasing the zero bit space does not work, since it also drastically increases the average work.
To compare this to, say, the workload of compressing a file (eg zip). That's a much more controllable amount of work, roughly proportional to the input length.
Say we manufacture an unpredictable text generator, fed into zip, fed into a hash function. The proof of work is the generator seed and the final hash value. the generator output length controls the amount of work and saying you could "guess" the final hash is virtually impossible (compared to say 1:2^20).
But this example is not practical because it is symmetric, requiring the same work to be performed for verification.
so, are there any guaranteed (within probability) asymmetric proof-of-work systems?