Cryptology ePrint Archive: Report 2014/059
Cuckoo Cycle: a memory bound graph-theoretic proof-of-work
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.
Category / Keywords: proof-of-work graph-theory
Date: received 27 Jan 2014, last revised 1 Jan 2015
Contact author: john tromp at gmail com
Available format(s): PDF | BibTeX Citation
Note: Final version submitted to Bitcoin 2015 workshop.
Version: 20150101:160919 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]