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?