Paper 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.

Note: previous memory hardness claims invalidated and adjusted by new preprocessing step reducing memory 32-fold.