Paper 2018/183

Simple Proofs of Sequential Work

Bram Cohen and Krzysztof Pietrzak


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.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2018
Proofs of Sequential WorkBlockchain
Contact author(s)
krzpie @ gmail com
2018-02-14: received
Short URL
Creative Commons Attribution


      author = {Bram Cohen and Krzysztof Pietrzak},
      title = {Simple Proofs of Sequential Work},
      howpublished = {Cryptology ePrint Archive, Paper 2018/183},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.