Is discrete logarithm good approach for a time-bounded proof of work?

Question

I'm writing a system where a client needs to show via proof of work that it's really intending to consume CPU resources on the server, and not just bombing the server with denial of service queries. At first, I considered hashcash-style proof of work where the client needs to find a hash prefix that results in the hash having e.g. a prefix of 16 zeroes.

A benefit of hashcash is that it can be used to authenticate the message, so that if an attacker can capture a message and send it again after modifications, the attacker would need to re-calculate the hashcash. However, this attack requires so much resources (after all, the attacker needs to capture, drop and inject traffic) that I don't consider it unlikely that if an attacker goes to such great lengths, the attacker would just recalculate the hashcash.

Quickly I found that although the hashcash is often very fast, sometimes it takes a lot of time on the client. So it isn't time-bounded.

If I need 16 zeroes in the hash, and want 50% probability of finding a solution, the number of hashes needed is 45426:

$$ \left(1-\frac{1}{2^{16}}\right)^{45426} \approx 0.5 $$

However, this is not the expectation value for the number of hashes needed. For 16 zeroes, the expectation value is actually

$$ \sum_{k=1}^{\infty} k\frac{1}{2^{16}}\left(1-\frac{1}{2^{16}}\right)^k = \frac{1}{2^{16}}\frac{1-\frac{1}{2^{16}}}{\left(\frac{1}{2^{16}}\right)^2} = 65535$$

Not troubling so far, but since the distribution has a long tail, it isn't improbable that for example 262140 hashes would be needed, four times as much as the expectation value.

So I would like to have a proof of work system that is time-bounded, so that the server that creates a challenge can ensure that the time needed for the client to complete that challenge has an upper bound.

One possibility I considered is discrete logarithms. If the server chooses a prime $p$ and a base $b$ (primitive root modulo $p$), maybe those being even constants, then it can:

1. Choose exponent $x$ to have a reasonable value, between $[1, x_\mathrm{max}]$
2. Calculate $a = b^x \mod p$
3. Send $p$, $b$ and $a$ to client while storing them on the server as well for checking that the client used the same values
4. Wait for client to send $p$, $b$, $a$ and $x$ after the client has tested every possible value of $x$ and found the right value
5. Check that indeed $a = b^x \mod p$ for the $x$ the client sent to the server
6. Mark $a$ used so that it can no longer be reused

Is this a good approach for a time-bounded proof of work? Are there any weaknesses, so that the client could with some optimizations complete the puzzle orders of magnitude faster than using a simple for loop, checking every possible value of $x$? Of course the standard exponentiation by squaring would obviously be used on the genuine implementation, so an attacker inventing exponentiation by squaring wouldn't be considered a weakness.

Answer 1

There will still be variability around the mean for using DL. More importantly, the strength you get by choosing $x$ in $[1,x_{max}]$ is of the order $\log(\sqrt{x_{max}})=\frac{1}{2} \log x_{max}$ (halving the bitstrength) due to baby-step giant step and pollard rho algorithms. However, worst case time can be bounded a bit better here.

And if $x_{max}$ is not large enough you'll run out of $a'$s quite quickly. The $2^{16}$ you gave as an example is way too small.