CryptoDB
On Graphs of Incremental Proofs of Sequential Work
| Authors: |
|
|---|---|
| Download: | |
| Conference: | PKC 2025 |
| Abstract: | In this work, we characterize graphs of \emph{(graph-labeling) incremental proofs of sequential work} (iPoSW). First, we define \emph{incremental} graphs and prove they are necessary for iPoSWs. Relying on space pebbling complexity of incremental graphs, we show that the depth-robust graphs underling the PoSW of Mahmoody et al., are not incremental, and hence, their PoSW cannot be transformed into an iPoSW. Second, and toward a generic iPoSW construction, we define graphs whose structure is compatible with the incremental sampling technique (Döttling et al.). These are \emph{dynamic} graphs. We observe that the graphs underlying all PoSWs, standalone or incremental, are dynamic. We then generalize current iPoSW schemes by giving a generic construction that transforms any PoSW whose underlying graph is incremental and dynamic into an iPoSW. As a corollary, we get a new iPoSW based on the modified Cohen-Pietrzak graph. When used in constructing blockchain light-client bootstrapping protocols (Abusalah et al.), such an iPoSW, results in the most efficient bootstrappers/provers, in terms of both proof size and space complexity. Along the way, we show that previous iPoSW definitions allow for trivial solutions. To overcome this, we provide a refined definition that captures the essence of iPoSWs and is satisfied by all known iPoSW constructions. |
BibTeX
@inproceedings{pkc-2025-35173,
title={On Graphs of Incremental Proofs of Sequential Work},
publisher={Springer-Verlag},
author={Hamza Abusalah},
year=2025
}