Paper 2018/183

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2018
Keywords
Proofs of Sequential WorkBlockchain
Contact author(s)
krzpie @ gmail com
History
2018-02-14: received
Short URL
https://ia.cr/2018/183
License
Creative Commons Attribution
CC BY

BibTeX

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