Cryptology ePrint Archive: Report 2014/059
Cuckoo Cycle: a graph-theoretic proof-of-work system
Abstract: We introduce the first graph-theoretic proof-of-work system,
based on finding cycles in large random graphs.
Such problems are arbitrarily scalable and trivially verifiable.
Our implementation uses 1 bit per edge, and up to 1 bit per node.
We hypothesize that using significantly less causes superlinear slowdown.
Category / Keywords: proof-of-work graph-theory
Date: received 27 Jan 2014, last revised 14 May 2014
Contact author: john tromp at gmail com
Available format(s): PDF | BibTeX Citation
Note: previous memory hardness claims invalidated and adjusted by new preprocessing step reducing memory 32-fold.
Version: 20140514:150658 (All versions of this report)
Short URL: ia.cr/2014/059
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]