conference paper
Simple proofs of sequential work
LNCS
published
yes
Bram
Cohen
author
Krzysztof Z
Pietrzak
author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654
KrPi
department
Eurocrypt: Advances in Cryptology
Teaching Old Crypto New Tricks
project
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” χ, 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 χ 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.
Springer2018Tel Aviv, Israel
eng
10.1007/978-3-319-78375-8_15
10821451 - 467
Cohen, Bram, and Krzysztof Z. Pietrzak. <i>Simple Proofs of Sequential Work</i>. Vol. 10821, Springer, 2018, pp. 451–67, doi:<a href="https://doi.org/10.1007/978-3-319-78375-8_15">10.1007/978-3-319-78375-8_15</a>.
B. Cohen, K.Z. Pietrzak, in:, Springer, 2018, pp. 451–467.
Cohen, B., & Pietrzak, K. Z. (2018). Simple proofs of sequential work (Vol. 10821, pp. 451–467). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. <a href="https://doi.org/10.1007/978-3-319-78375-8_15">https://doi.org/10.1007/978-3-319-78375-8_15</a>
Cohen, Bram, and Krzysztof Z Pietrzak. “Simple Proofs of Sequential Work,” 10821:451–67. Springer, 2018. <a href="https://doi.org/10.1007/978-3-319-78375-8_15">https://doi.org/10.1007/978-3-319-78375-8_15</a>.
B. Cohen and K. Z. Pietrzak, “Simple proofs of sequential work,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10821, pp. 451–467.
Cohen B, Pietrzak KZ. Simple proofs of sequential work. In: Vol 10821. Springer; 2018:451-467. doi:<a href="https://doi.org/10.1007/978-3-319-78375-8_15">10.1007/978-3-319-78375-8_15</a>
Cohen B, Pietrzak KZ. 2018. Simple proofs of sequential work. Eurocrypt: Advances in Cryptology, LNCS, vol. 10821, 451–467.
3022018-12-11T11:45:42Z2021-01-12T07:40:30Z