How does it depend on the choice of hash function?
I guess this is something purely theoretical, right?
It's not related to hash functions, it's a generic proof of computation.
Not purely theoretical, there's a compiler in relatively early stages that's already working. For computation of a specific hash function, major optimizations could be done.
But let's not hijack this thread with unrelated matters, please PM me if you'd like.