@conference {634284,
	title = {Publicly verifiable proofs of sequential work},
	booktitle = {Innovations in Theoretical Computer Science (ITCS {\textquoteleft}13)},
	year = {2013},
	pages = {373-388},
	publisher = {ACM},
	organization = {ACM},
	abstract = {
	Version History:\&nbsp;Preliminary version posted as Cryptology ePrint Archive Report 2011/553, under title {\textquotedblleft}Non-Interactive Time-Stamping and Proofs of Work in the Random Oracle Model{\textquotedblright}.



	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 {\textquotedblleft}inherently sequential{\textquotedblright} hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled {\textquotedblleft}puzzle{\textquotedblright}\&nbsp;\(\mathcal{P} \overset{$}\gets \mathbf{D}_n\), where\&nbsp;\(n\)\&nbsp;is the security parameter and\&nbsp;\(\mathbf{D}_n\)\&nbsp;is the distribution of the puzzles, a corresponding {\textquotedblleft}solution{\textquotedblright} can be generated using\&nbsp;\(N\)\&nbsp;evaluations of the sequential hash function, where\&nbsp;\(N \&gt; n\)\&nbsp;is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as \(\Omega(N)\)\&nbsp;sequential evaluations of the hash function after receiving\&nbsp;\(\mathcal{P}\). Thus, valid solutions constitute a {\textquotedblleft}proof{\textquotedblright} that \(\Omega(N)\) parallel time elapsed since\&nbsp;\(\mathcal{P}\)\&nbsp;was received. Solutions can be publicly and efficiently verified in time \(\mathrm{poly}(n) \cdot \mathrm{polylog}(N)\). Applications of these {\textquotedblleft}time-lock puzzles{\textquotedblright} include noninteractive timestamping of documents (when the distribution over the possible documents corresponds to the puzzle distribution\&nbsp;\(\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 {\textquotedblleft}depth-robust{\textquotedblright} directed acyclic graphs{\textemdash}ones whose depth remains large even after removing a constant fraction of vertices{\textemdash}which were previously studied for the purpose of complexity lower bounds. The construction bypasses a recent negative result of Mahmoody, Moran, and Vadhan (CRYPTO {\textquoteleft}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.

},
	url = {https://dl.acm.org/citation.cfm?id=2422479},
	author = {Mohammad Mahmoody and Tal Moran and Salil Vadhan}
}
