Publicly verifiable proofs of sequential work

Abstract

We construct a publicly verifiable protocol for proving computational work based on collision-resistant hash functions and a new plausible complexity assumption regarding the existence of "inherently sequential" hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled "puzzle" P getsr Dn, where $n$ is the security parameter and Dn is the distribution of the puzzles, a corresponding "solution" can be generated using N evaluations of the sequential hash function, where N>n is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as Ω(N) serial evaluations of the hash function after receiving $P$. Thus, valid solutions constitute a "proof" that Ω(N) parallel time elapsed since p was received. Solutions can be publicly and efficiently verified in time poly(n) ⋅ polylog(N). Applications of these "time-lock puzzles" include noninteractive timestamping of documents (where the distribution over the possible documents corresponds to the puzzle distribution Dn) and universally verifiable CPU benchmarks. Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic.