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 √
N memory and to run for N +
√
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).
History
Preferred Citation
Nico Döttling, Russell Lai and Giulio Malavolta. Incremental Proofs of Sequential Work. In: International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT). 2019.
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)
Legacy Posted Date
2019-04-18
Open Access Type
Unknown
BibTeX
@inproceedings{cispa_all_2879,
title = "Incremental Proofs of Sequential Work",
author = "Döttling, Nico and Lai, Russell and Malavolta, Giulio",
booktitle="{International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)}",
year="2019",
}