Portal de Periódicos da CAPES

Simple Proofs of Sequential Work

2018; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-319-78375-8_15

1611-3349

Bram Cohen, Krzysztof Pietrzak,

Cryptographic Implementations and Security

At ITCS 2013, Mahmoody, Moran and Vadhan [MMV13] 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 [MMV13] 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 $$\mathsf{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 $$\mathsf{H}$$ , while soundness requires that any prover who makes the verifier accept must have made (almost) N sequential queries to $$\mathsf{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 [MMV13] 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 [MMV13] 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.