**Simple Proofs of Sequential Work**

*Bram Cohen and Krzysztof Pietrzak*

**Abstract: **At ITCS 2013, Mahmoody, Moran and Vadhan [MMV'13] introduce and construct publicly verifiable proofs of sequential work, which is a protocol for proving that one spent sequential computational work related to some statement.
The original motivation for such proofs included non-interactive time-stamping and universally verifiable CPU benchmarks. A more recent application, and our main motivation, are blockchain designs, where proofs of sequential work can be used -- in combination with proofs of space -- as a more ecological and economical substitute for proofs of work which are currently used to secure Bitcoin and other cryptocurrencies.

The construction proposed by [MMV'13] is based on a hash function and can be proven secure in the random oracle model, or assuming inherently sequential hash-functions, which is a new standard model assumption introduced in their work.

In a proof of sequential work, a prover gets a "statement" $\chi$, a time parameter $N$ and access to a hash-function $H$, which for the security proof is modelled as a random oracle. Correctness requires that an honest prover can make a verifier accept making only $N$ queries to $H$, while soundness requires that any prover who makes the verifier accept must have made (almost) $N$ sequential queries to $H$. Thus a solution constitutes a proof that $N$ time passed since $\chi$ was received. Solutions must be publicly verifiable in time at most polylogarithmic in $N$.

The construction of [MMV'13] is based on "depth-robust" graphs, and as a consequence has rather poor concrete parameters. But the major drawback is that the prover needs not just $N$ time, but also $N$ space to compute a proof.

In this work we propose a proof of sequential work which is much simpler, more efficient and achieves much better concrete bounds. Most importantly, the space required can be as small as $\log(N)$ (but we get better soundness using slightly more memory than that).

An open problem stated by [MMV'13] that our construction does not solve either is achieving a "unique" proof, where even a cheating prover can only generate a single accepting proof. This property would be extremely useful for applications to blockchains.

**Category / Keywords: **cryptographic protocols / Proofs of Sequential Work, Blockchain

**Original Publication**** (in the same form): **IACR-EUROCRYPT-2018

**Date: **received 9 Feb 2018, last revised 14 Feb 2018

**Contact author: **krzpie at gmail com

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

**Version: **20180214:182912 (All versions of this report)

**Short URL: **ia.cr/2018/183

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]