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.