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" $$, a time parameter $$ and access to a hash-function $$, which for the security proof is modelled as a random oracle. Correctness requires that an honest prover can make a verifier accept making only $$ queries to $$, while soundness requires that any prover who makes the verifier accept must have made (almost) $$ sequential queries to $$. Thus a solution constitutes a proof that $$ time passed since $$ was received. Solutions must be publicly verifiable in time at most polylogarithmic in $$. 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 $$ time, but also $$ 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 $$ (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.