# Publicly verifiable proofs of sequential work

### Citation:

Mahmoody, Mohammad, Tal Moran, and Salil Vadhan. “Publicly verifiable proofs of sequential work.” In Innovations in Theoretical Computer Science (ITCS ‘13), 373-388. ACM, 2013.
 IACR2013.pdf 433 KB ITCS2013.pdf 524 KB

### Abstract:

Version HistoryPreliminary version posted as Cryptology ePrint Archive Report 2011/553, under title “Non-Interactive Time-Stamping and Proofs of Work in the Random Oracle Model”.

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” $$\mathcal{P} \overset{}\gets \mathbf{D}_n$$, where $$n$$ is the security parameter and $$\mathbf{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 $$\mathcal{P}$$. Thus, valid solutions constitute a “proof” that $$\Omega(N)$$ parallel time elapsed since $$\mathcal{P}$$ was received. Solutions can be publicly and efficiently verified in time $$\mathrm{poly}(n) \cdot \mathrm{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 $$\mathbf{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.

Publisher's Version

Last updated on 06/30/2020