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 \(\varOmega (k)\). The constant implied in \(\varOmega ()\) 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
or, less accurately, results in many leading zeroes.
- 2.
Preferably less than the roughly 50 nanosecond row activation delay for switching rows on a memory bank.
- 3.
Rather arbitrarily defined as incurring an order of magnitude increase in time \(\times \) memory used per expected solution.
- 4.
Hash functions generally have arbitrary length inputs, but here we fix the input width at \(W_i\) bits.
- 5.
These micro nonces should be distinguished from the macro nonce used to generate key k.
- 6.
excluding the very least significant bit distinguishing even from odd nodes.
References
Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system. Technical Report, May 2009. http://www.bitcoin.org/bitcoin.pdf
Back, A.: Hashcash - a denial of service counter-measure. Technical Report, August 2002. (implementation released in Mar 1997)
Lolcust: [announce] tenebrix, a cpu-friendly, gpu-hostile cryptocurrency, September 2011. https://bitcointalk.org/index.php?topic=45667.0
Coblee: [ann] litecoin - a lite version of bitcoin. launched! October 2011. https://bitcointalk.org/index.php?topic=47417.0
King, S.: Primecoin: Cryptocurrency with prime number proof-of-work. Technical Report, July 2013. http://primecoin.org/static/primecoin-paper.pdf
Larimer, D.: Momentum - a memory-hard proof-of-work via finding birthday collisions. Technical Report, October 2013. www.hashcash.org/papers/momentum.pdf
Back, A.: Hashcash.org, February 2014. http://www.hashcash.org/papers/
Poelstra, A.: Asics and decentralization faq (2014). https://download.wpsoftware.net/bitcoin/asic-faq.pdf
Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122–144 (2004). doi:10.1016/j.jalgor.2003.12.002
Wikipedia, Disjoint-set data structure – wikipedia, the free encyclopedia (2014). Accessed from 23-March-2014. http://en.wikipedia.org/w/index.php?title=Disjoint-set_data_structure
Andersen, D.: A public review of cuckoo cycle, April 2014. http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html
Preshing, J.: The world’s simplest lock-free hash table, June 2013. http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/
Brent, R.P.: An improved Monte Carlo factorization algorithm. BIT 20, 176–184 (1980)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Financial Cryptography Association
About this paper
Cite this paper
Tromp, J. (2015). Cuckoo Cycle: A Memory Bound Graph-Theoretic Proof-of-Work. In: Brenner, M., Christin, N., Johnson, B., Rohloff, K. (eds) Financial Cryptography and Data Security. FC 2015. Lecture Notes in Computer Science(), vol 8976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48051-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-662-48051-9_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48050-2
Online ISBN: 978-3-662-48051-9
eBook Packages: Computer ScienceComputer Science (R0)