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 26 Oct 2014

Contact author: john tromp at gmail com

Available format(s): PDF | BibTeX Citation

Note: added time-memory tradeoff algorithms and more benchmark results

Version: 20141027:033038 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]