1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ No cryptographic solution can protect you against an adversary making a lucky guess, you can merely make it "highly improbable". For example: I could get lucky guessing a private key of an Bitcoin address which has a positive balance, but my chances are roughly $1$ to $2^{256}-1$ (ignoring the birthday problem et al) $\endgroup$
    – e-sushi
    Apr 26, 2018 at 10:51

2 Answers 2

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Isn't the probability of generating a specific n*B-bit string, equal to that of generating n specific B-bit strings? With that in mind, I don't think this changes anything other than requiring more calculations to verify the answers. $\endgroup$
    – cutsoy
    Feb 24, 2018 at 17:53
  • $\begingroup$ @squeamish. thanks for your answer. I think this is the right direction. Im currently working on a version of poncho's answer here. $\endgroup$
    – jkj yuio
    Feb 24, 2018 at 20:22
0
$\begingroup$

It's impossible, because if the solution is efficiently verifiable, it's always possible (even though it happens with negligible probability) to guess it and verify that it works efficiently

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.