Ensuring that an operation takes a relatively specific amount of time, but easily verify the result

Question

I want an algorithm of some sort that can ensure that an operation takes a fairly specific amount of time, but proof that this operation was done can be completed relatively inexpensively.

For instance, I can prove that an operation will probably take around 30 seconds by doing a cycle with a hashing algorithm such as SHA256 such that the output of the hash feeds directly back into the input. If I count how many hashes are computed within 30 seconds on a modern computer I can be relatively sure that it can't be significantly faster on better hardware.

So, you can ensure that another user waits for around 30 seconds by giving them the amount of rounds they must do of the hash.

And then, for the receiver to verify that they did the hash, they would calculate the given input X amount of rounds and verify that the result matches what they were given.

However, this is hard, because to verify they took that amount of time, the verifier must also take that amount of time.

Is there a way to do such a thing with the verification taking significantly less time than the actual computation?

For instance, one idea is to use asymmetric RSA encryption. Usually, signing a given input is slower than verifying the signature. So, you could possibly sign the input for X amount of rounds and then verifying X amount of rounds would be significantly faster. However the actual amount of data that would get signed would explode (because each round requires adding another signature) and I think RSA would not be secure to use in this manner.

Is there some way to do this securely and without exploding amounts of data for each required round?

Answer 1

Timelock puzzles solve this problem.

For instance, consider the function $f(x) = x^{2^t} \bmod n$, where $n$ is a RSA modulus and $t$ is large. For people who don't know the factorization of $n$, computing $f$ takes $t$ squarings modulo $n$. If you do know the factorization of $n$ (the private key), then computing $f$ can be done with $O(\lg n)$ squarings, regardless of how large $t$ is, by first reducing $t$ modulo $\varphi(n)$. This lets you create a puzzle that will take a controllable amount of time for someone else to solve, and where you can very efficiently verify the answer: e.g., choose $n$ to be a 2048-bit prime and $t$ to be a million, or whatever you want $t$ to be to make computing $f$ take exactly as long as you want for the other person.

See, e.g., Time Capsule cryptography? and Parallel-resistant proof-of-work scheme? and What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

---

If you want a proof of work puzzle that requires the other person to do 30 seconds of work, I don't see any practical reason to worry much about quantum computers. Right now there are no quantum computers that could pose a serious threat to this scheme. If they ever become possible, you can always change the scheme out. The scheme only needs to be secure for 30 seconds, not for 30 years....