Paper 2014/059

Cuckoo Cycle: a memory bound graph-theoretic proof-of-work

John Tromp

Abstract

We introduce the first graph-theoretic proof-of-work system, based on finding small cycles or other structures in large random graphs. Such problems are trivially verifiable and arbitrarily scalable, presumably requiring memory linear in graph size to solve efficiently. Our cycle finding algorithm uses one bit per edge, and up to one bit per node. Runtime is linear in graph size and dominated by random access latency, ideal properties for a memory bound proof-of-work. We exhibit two alternative algorithms that allow for a memory-time trade-off (TMTO)---decreased memory usage, by a factor $k$, coupled with increased runtime, by a factor $\Omega(k)$. The constant implied in $\Omega()$ gives a notion of memory-hardness, which is shown to be dependent on cycle length, guiding the latter's choice. Our algorithms are shown to parallelize reasonably well.

Note: Final version submitted to Bitcoin 2015 workshop.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
proof-of-work graph-theory
Contact author(s)
john tromp @ gmail com
History
2015-01-01: last of 6 revisions
2014-01-28: received
See all versions
Short URL
https://ia.cr/2014/059
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/059,
      author = {John Tromp},
      title = {Cuckoo Cycle: a memory bound graph-theoretic proof-of-work},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/059},
      year = {2014},
      url = {https://eprint.iacr.org/2014/059}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.