Paper 2011/553
Publicly Verifiable Proofs of Sequential Work
Mohammad Mahmoody, Tal Moran, and Salil Vadhan
Abstract
We construct a publicly verifiable protocol for proving computational work based on collisionresistant 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 timelock 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)$ *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) \cdot \polylog(N)$. Applications of these "timelock 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 (collisionresistant hash functions and inherently sequential hash functions), and makes blackbox use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a publiccoin protocol, it can be made noninteractive in the random oracle model using the FiatShamir Heuristic. Our construction makes a novel use of ``depthrobust'' directed acyclic graphsones whose depth remains large even after removing a constant fraction of verticeswhich 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 timelock puzzles in the random oracle model, which showed that it is impossible to have timelock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.
Note: Polished the proofs a bit (with combining the two hash properties).
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Minor revision.Innovations in Theoretical Computer Science (ITCS) 2013.
 Contact author(s)
 mohammad @ virginia edu
 History
 20190331: last of 5 revisions
 20111011: received
 See all versions
 Short URL
 https://ia.cr/2011/553
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/553, author = {Mohammad Mahmoody and Tal Moran and Salil Vadhan}, title = {Publicly Verifiable Proofs of Sequential Work}, howpublished = {Cryptology ePrint Archive, Paper 2011/553}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/553}}, url = {https://eprint.iacr.org/2011/553} }