Cryptology ePrint Archive: Report 2019/252

Reversible Proofs of Sequential Work

Hamza Abusalah and Chethan Kamath and Karen Klein and Krzysztof Pietrzak and Michael Walter

Abstract: Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement $\chi$ and a time parameter $T$ computes a proof $\phi(\chi,T)$ which is efficiently and publicly verifiable. The proof can be computed in $T$ sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that $T$ units of time have passed since $\chi$ was received.

PoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18].

In this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different.

Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation.

The fact that the construction is reversible can potentially be used for new applications like constructing \emph{proofs of replication}. We also show how to ``embed" the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of ``verifiable delay functions" subsume most of the applications this construction was aiming at).

Category / Keywords: Proof of work, Proof of sequential work

Original Publication (in the same form): IACR-EUROCRYPT-2019

Date: received 28 Feb 2019

Contact author: hamzaabusalah at gmail com,ckamath@ist ac at,karen klein@ist ac at,krzpie@gmail com,michael walter@ist ac at

Available format(s): PDF | BibTeX Citation

Version: 20190228:191916 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]