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 noninteractive timestamping 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 hashfunctions, 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 hashfunction $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 "depthrobust" 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)
 Category
 Cryptographic protocols
 Publication info
 Published by the IACR in EUROCRYPT 2018
 Keywords
 Proofs of Sequential WorkBlockchain
 Contact author(s)
 krzpie @ gmail com
 History
 20180214: received
 Short URL
 https://ia.cr/2018/183
 License

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}, url = {https://eprint.iacr.org/2018/183} }