Bit-strength of discrete logarithm for a group of integers modulo a safe prime
For a proof of work scheme, you're probably better off making $p$ large enough that you don't have to worry about NFS (e.g. 2048 bits or more), or alternatively, using an elliptic curve group (e.g. P256 or Curve25519).

Instead, you'd tune things so that the generic attacks (e.g. Big-Step-Little-Step) are the optimal attacks, and use that to select the difficultly (range of $k$); if the solver knows that $0 &lt; k \le M$, then these generic searches will take circa $\sqrt{M}$ group operations (modular multiplications, elliptic curve additions), and that's the best the searcher can do (assuming that he doesn't have any further insight into the group structure - that's what we're trying to ensure by making NFS infeasible).

Now, while this would work as a 'proof-of-total-work', I'm not sure if it really meets your requirements, because someone with significant amount of parallelism (e.g a botnet farm) may be able to accelerate this computation significantly.

A better approach might be to have the serve publish integer $g$, $k$ and a composite $n$, and ask the client to compute $g^{2^k} \bmod n$; this type of operation isn't greatly parallizable (because each squaring operation must be done sequentially), and the server (who knows the factorization of $n = pq$) can verify this by checking a claimed answer $A$ by the relation $A \equiv g^{2^k \bmod p-1} \pmod p$