Cryptology ePrint Archive: Report 2014/059

Cuckoo Cycle: a graph-theoretic proof-of-work system

John Tromp

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)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]