# Is there a hash algorithm that is slow to calculate but relatively fast to check?

Or more generally, is there a function or algorithm that is slow to calculate/execute, has a reliable execution time, and has a result that can be tested much more quickly than the calculation took?

-

It sounds like you're looking for a proof-of-work system.

One way to implement such a system would be, given a message $m$, to ask for a suffix $s$ such that the hash $H(m \operatorname{\|} s)$, where $H$ is some standard cryptographic hash function and $\|$ denotes concatenation, begins with a specific prefix (e.g. $n$ zero bits).

Of course, the execution time of such a scheme is not really deterministic; we can predict the expected time it will take, but the actual time will be geometrically distributed, and so will vary a lot. Also, the particular scheme I described is very easy to parallelize, so that using multiple processors (or parallel processors like GPGPUs) cuts down the expected solving time in inverse proportion to number of cores used. Depending on your application, this may or may not be an issue.

-
Yes, exactly what I was looking for; thanks. –  shino Apr 10 '12 at 3:01
This is precisely how Bitcoin mining works (except it's not a suffix, it's embedded in the block). It takes a lot of work to mine a block but very little work to confirm a validly-mined block. –  David Schwartz Apr 14 '12 at 4:07
We generally use these kinds of problems in cryptographic constructions such that the user with the message or key calculates the easy part and the hard part is published to the world. We choose the answer, from the answer derive the hard problem, then we publish the hard problem. But it sounds like you want the opposite of that, namely, a hard problem that we output the answer for, which others then verify. Ilmari's answer provided an example of that: If the hash used is a good one-way function, then it is exponential time to find the answer $s$, but it is polynomial time to verify that $s$ is correct.