Incremental Proofs of Sequential Work

Nico Döttling, Russell W. F. Lai, and Giulio Malavolta

Abstract

A proof of sequential work allows a prover to convince a verifier that a certain amount of sequential steps have been computed. In this work we introduce the notion of incremental proofs of sequential work where a prover can carry on the computation done by the previous prover incrementally, without affecting the resources of the individual provers or the size of the proofs. To date, the most efficient instance of proofs of sequential work [Cohen and Pietrzak, Eurocrypt 2018] for $N$ steps require the prover to have $\sqrt{N}$ memory and to run for $N + \sqrt{N}$ steps. Using incremental proofs of sequential work we can bring down the prover's storage complexity to $\log N$ and its running time to $N$. We propose two different constructions of incremental proofs of sequential work: Our first scheme requires a single processor and introduces a poly-logarithmic factor in the proof size when compared with the proposals of Cohen and Pietrzak. Our second scheme assumes $\log N$ parallel processors but brings down the overhead of the proof size to a factor of $9$. Both schemes are simple to implement and only rely on hash functions (modelled as random oracles).

Available format(s)
Publication info
Contact author(s)
nico doettling @ gmail com
russell lai @ cs fau de
giulio malavolta @ hotmail it
History
Short URL
https://ia.cr/2019/650

CC BY

BibTeX

@misc{cryptoeprint:2019/650,
author = {Nico Döttling and Russell W.  F.  Lai and Giulio Malavolta},
title = {Incremental Proofs of Sequential Work},
howpublished = {Cryptology ePrint Archive, Paper 2019/650},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/650}},
url = {https://eprint.iacr.org/2019/650}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.