PaperfootJoin free
arXiv

Encoded storage can cut memory costs in a graph model

The proof found a gap growing as a power of graph size between encoded storage and whole-value storage when answering random challenges.

Paper by Piotr Marszalik
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

The researchers proved a polynomial separation—a gap growing as a power of graph size—between pure and entangled pebbling on explicitly constructed graphs. These models of memory cost differ in what they can store: pure pebbling holds whole values, while entangled pebbling also permits encoded combinations.

The proof addressed a setting where stored information was prepared before a random challenge, with memory charged for as long as it was held. On the constructed graphs, strategies storing whole values could do no better, up to a constant factor, than storing every possible answer in advance. A strategy storing encoded combinations instead paid polynomially less.

Why it matters

Graph pebbling supports security arguments for computations designed to demand memory and for methods of proving access to storage. This proof ruled out treating whole-value pebbling as accurate up to small factors in the setting studied.

Caveats

The result concerns the constructed graphs and the stated challenge setting, not every graph or memory-based security construction. The paper is an arXiv preprint, not yet peer-reviewed.

In this paper

separation between pure and entangled pebbling

What it shows

Pure pebbling can be wrong by a polynomial factor because the representation of stored information can change the asymptotic memory cost.

Pure pebbling can be wrong by a polynomial factor: the way stored information is represented can change the asymptotic cost of memory, so a pure-pebbling lower bound needs an additional argument before it says anything about strategies that store encoded information.

7. Conclusion and open questions

On the constructed graphs, an adversary keeping XORs instead of whole labels pays polynomially less than a pure adversary.

Still, an adversary who keeps XORs instead of labels pays polynomially less.

Abstract

Every pure strategy in the memory game has a total memory cost of at least 2|E| = Kd.

Every pure strategy has \mathrm{TMC}≥ 2|E|=Kd, and this is attained (for example by storing nothing, or by storing all labels).

Theorem 3 (Pure lower bound in the game).

Every K-connector DAG is maximally ST-robust.

Every K -connector is maximally ST-robust.

Lemma 17.

The paper does not claim that any deployed memory-hard function or proof of space is broken, as its graphs are built specifically for the attack.

We do not claim that any deployed memory-hard function or proof of space is broken; our graphs are built for the attack.

Real constructions.

Quoted word for word from the full text on arXiv.

The paper

When Pebbles Are Not Atomic: A Polynomial Separation Between Pure and Entangled Pebbling

Piotr Marszalik

arXiv, Oct 19, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.27249

arXiv:2610.27249v1 in cs.CR

AbstractPDFHTML

Comments: 29 pages, 8 figures

Cite as BibTeX
@misc{marszalik2026when,
  title = {When Pebbles Are Not Atomic: A Polynomial Separation Between Pure and Entangled Pebbling},
  author = {Marszalik, Piotr},
  year = {2026},
  eprint = {2610.27249},
  archivePrefix = {arXiv},
  primaryClass = {cs.CR},
  doi = {10.48550/arxiv.2610.27249},
  url = {https://arxiv.org/abs/2610.27249}
}

Related