Are there Guaranteed Proof-of-work Systems? 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?
You could use a challenge consisting of multiple subtasks.

For example, provide a unique random string of characters $R$ and ask for $n$ distinct strings that have $R$ as a prefix and whose SHA256 sum ends in $z$ zeros.

In a single hash calculation, the probability of a lucky guess is $2^{-4z}$, so the probability of multiple lucky guesses in one challenge is going to be very small if $z = 10$.

The number of SHA256 calculations needed to pass the challenge is of the order of $n \times 2^{4z}$, but only $n$ hash calculations are needed to check the results (plus a little extra to check that no two strings are the same).