**Publicly Verifiable Proofs of Sequential Work**

*Mohammad Mahmoody and Tal Moran and Salil Vadhan*

**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 \gets D_n, where n is the security parameter and D_n 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 \Omega(N) \emph{sequential} evaluations of the hash function after receiving P. Thus, valid solutions constitute a ``proof'' that \Omega(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 (when the distribution over the possible documents corresponds to the puzzle distribution D_n) 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.

Our construction makes a novel use of ``depth-robust'' directed acyclic graphs---ones whose depth remains large even after removing a constant fraction of vertices---which were previously studied for the purpose of complexity lower bounds. The construction bypasses a recent negative result of Mahmoody, Moran, and Vadhan (CRYPTO `11) for time-lock puzzles in the random oracle model, which showed that it is impossible to have time-lock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.

**Category / Keywords: **cryptographic protocols /

**Publication Info: **combinatorial cryptography, hash functions, random oracles,

**Date: **received 6 Oct 2011, last revised 17 Mar 2013

**Contact author: **mahmoody at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **Polished the proofs a bit (with combining the two hash properties).

**Version: **20130318:035942 (All versions of this report)

**Short URL: **ia.cr/2011/553

[ Cryptology ePrint archive ]