Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem

Authors

  • Alex Biryukov University of Luxembourg
  • Dmitry Khovratovich University of Luxembourg

DOI:

https://doi.org/10.5195/ledger.2017.48

Keywords:

Equihash, memory-hard, asymmetric, proof-of-work, client puzzle

Abstract

Proof-of-work is a central concept in modern cryptocurrencies and denial-ofservice protection tools, but the requirement for fast verification so far has made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on memory-intensive computations in order to remedy the disparity between architectures have resulted in slow or broken schemes. In this paper we solve this open problem and show how to construct an asymmetric proof-of-work (PoW) based on a computationally-hard problem, which requires a great deal of memory to generate a proof (called a ”memory-hardness” feature) but is instant to verify. Our primary proposal, Equihash, is a PoW based on the generalized birthday problem and enhanced Wagner’s algorithm for it. We introduce the new technique of algorithm binding to prevent cost amortization and demonstrate that possible parallel implementations are constrained by memory bandwidth. Our scheme has tunable and steep time-space tradeoffs, which impose large computational penalties if less memory is used. Our solution is practical and ready to deploy: a reference implementation of a proof-of-work requiring 700 MB of RAM runs in 15 seconds on a 2.1 GHz CPU, increases the computations by a factor of 1000 if memory is halved, and presents a proof of just 120 bytes long.

References

Abadi, M., Burrows, M., Wobber, T. “Moderately Hard, Memory-Bound Functions.” (2003) http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/2.pdf

Alwen, J., Blocki, J. “Efficiently Computing Data-Independent Memory-Hard Functions.” Lecture Notes in Computer Science 9815 (2016) 241–271

Alwen, J., et al. “On the Memory-Hardness of Data-Independent Password-Hashing Functions.” Cryptology ePrint Archive, Report 2016/783 (2016) (Accessed 29 January 2017) http://eprint.iacr.org/2016/783

Andersen, D. “A Public Review of Cuckoo Cycle.” (2014) (Accessed 29 January 2017) http://www.cs.cmu.edu/~dga/crypto/cuckoo/analysis.pdf

Avior, A., Calamoneri, T., Even, S., Litman, A., Rosenberg, A. L. “A Tight Layout of the Butterfly Network.” Theory Comput. Syst. 31.4 (1998) 475–488

Back, A. “Hashcash – A Denial of Service Counter-Measure.” (2002) (accessed 29 January 2017) http://www.hashcash.org/papers/hashcash.pdf

Beame, P., Borodin, A., Raghavan, P., Ruzzo, W. L., Tompa, M. “Time-Space Tradeoffs for Undirected Graph Traversal.” (1990) 429–438 doi:10.1109/FSCS.1990.89563

Becker, A., Coron, J., Joux, A. “Improved Generic Algorithms for Hard Knapsacks.” Lecture Notes in Computer Science 6632 (2011) 364–385

Becker, A., Joux, A., May, A., Meurer, A. “Decoding Random Binary Linear Codes in 2n/20: How 1+1 = 0 Improves Information Set Decoding.” Lecture Notes in Computer Science 7237 (2012) 520–536 doi:10.1007/978-3-642-29011-4 31

Bellare, M., Micciancio, D. “A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost.” Lecture Notes in Computer Science 1233 (1997) 163–192 doi:10.1007/3-540-69053-0 13

Bernstein, D. J. Circuits for integer factorization: a proposal. Technical report (2001) https://cr.yp.

to/papers/nfscircuit.pdf

Bernstein, D. J. “Better Price-Performance Ratios for Generalized Birthday Attacks.” 7 (2007) 160

Bernstein, D. J., Lange, T., Niederhagen, R., Peters, C., Schwabe, P. “FSBday.” Lecture Notes in Computer Science 5922 (2009) 18–38 doi:10.1007/978-3-642-10628-6 2

Biryukov, A., Khovratovich, D. “Tradeoff Cryptanalysis of Memory-Hard Functions.” (2015) http://

eprint.iacr.org/2015/227

Biryukov, A., Khovratovich, D. “Argon2: new generation of memory-hard functions for password hashing and other applications.” (2016) (Accessed 29 Janaury 2017) https://www.cryptolux.org/images/0/0d/Argon2.pdf

Bonneau, J., Miller, A., Clark, J., Narayanan, A., Kroll, J. A., Felten, E. W. “SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies.” (2015) 104–121

Cawrey, D. “Avalon ASIC’s 40nm Chip to Bring Hashing Boost for Less Power.” (2014) (Accessed 29 January 2017) http://www.coindesk.com/avalon-asics-40nm-chip-bring-hashing-boost-less-power/

Crosby, S. A., Wallach, D. S. “Denial of Service via Algorithmic Complexity Attacks.” 2 (2003)

Dean, D., Stubblefield, A. “Using Client Puzzles to Protect TLS.” 42 (2001)

Denneman, F. “Memory Deep Dive: Memory Subsystem Bandwidth.” (2015) (Accessed 29 January 2017)

http://frankdenneman.nl/2015/02/19/memory-deep-dive-memory-subsystem-bandwidth/

Dinur, I., Dunkelman, O., Keller, N., Shamir, A. “Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems.” Lecture Notes in Computer Science 7417 (2012) 719–740 doi:10.1007/978-3-642-32009-5 42

Dwork, C., Goldberg, A., Naor, M. “On Memory-Bound Functions for Fighting Spam.” Lecture Notes in Computer Science 2729 (2003) 426–444

Dwork, C., Naor, M. “Pricing via Processing or Combatting Junk Mail.” Lecture Notes in Computer Science 740 (1992) 139–147

Dwork, C., Naor, M., Wee, H. “Pebbling and Proofs of Work.” Lecture Notes in Computer Science 3621 (2005) 37–54

Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K. “Proofs of Space.” Lecture Notes in Computer Science 9216 (2015) 585–605 doi:10.1007/978-3-662-48000-7 29

Fortnow, L. “Time-Space Tradeoffs for Satisfiability.” J. Comput. Syst. Sci. 60.2 (2000) 337–353 doi:10.1006/jcss.1999.1671

Geiselmann, W., Steinwandt, R. “A Dedicated Sieving Hardware.” Lecture Notes in Computer Science 2567 (2003) 254–266

Giridhar, B., et al. “Exploring DRAM Organizations for Energy-efficient and Resilient Exascale Memories.” (2013) 23–35

Helman, D. R., Bader, D. A., JaJ´ a, J. “A Randomized Parallel Sorting Algorithm with an Experimental Study.” J. Parallel Distrib. Comput. 52.1 (1998) 1–23 doi:10.1006/jpdc.1998.1462

Hopcroft, J. E., Paul, W. J., Valiant, L. G. “On Time Versus Space.” J. ACM 24.2 (1977) 332–337

Howgrave-Graham, N., Joux, A. “New Generic Algorithms for Hard Knapsacks.” Lecture Notes in Computer Science 6110 (2010) 235–256

Huang, D. Y., et al. “Botcoin: Monetizing Stolen Cycles.” (2014)

Jakobsson, M., Juels, A. “Proofs of Work and Bread Pudding Protocols.” IFIP Conference Proceedings 152 (1999) 258–272

Kirchner, P. “Improved Generalized Birthday Attack.” IACR Cryptology ePrint Archive 2011 (2011) 377

Lakshmanan, K. B., Ravikumar, B., Ganesan, K. “Coping with Erroneous Information while Sorting.” IEEE Trans. Computers 40.9 (1991) 1081–1084

Lang, H., Schimmler, M., Schmeck, H., Schroder, H. “Systolic Sorting on a Mesh-Connected Network.” IEEE Trans. Computers 34.7 (1985) 652–658

Lenstra, A. K., Shamir, A., Tomlinson, J., Tromer, E. “Analysis of Bernstein’s Factorization Circuit.” Lecture Notes in Computer Science 2501 (2002) 1–26

“Litecoin: Mining hardware comparison.” (2015) (Accessed 29 January 2017) https://litecoin.info/

Mining_hardware_comparison

Lorimer, D. “Momentum – A Memory-Hard Proof-of-Work via Finding Birthday Collisions.” (2014) (Accessed 29 January 2017) http://www.hashcash.org/papers/momentum.pdf

Merrill, D., Grimshaw, A. “High Performance and Scalable Radix Sorting: A case study of implementing dynamic parallelism for GPU computing.” Parallel Processing Letters 21.02 (2011) 245–272 doi:10.1142/S0129626411000187

Minder, L., Sinclair, A. “The extended k-tree algorithm.” (2009) 586–595

Nikolic, I., Sasaki, Y. “Refinements of the k-tree Algorithm for the Generalized Birthday Problem.” Lecture Notes in Computer Science 9453 (2015) 683–703

Nivasch, G. “Cycle Detection Using a Stack.” Inf. Process. Lett. 90.3 (2004) 135–140 doi:10.1016/j.ipl.2004.01.016

Park, S., Pietrzak, K., Alwen, J., Fuchsbauer, G., Gazi, P. “Spacecoin: A Cryptocurrency Based on Proofs of Space.” IACR Cryptology ePrint Archive 2015 (2015) 528 http://eprint.iacr.org/2015/528

Percival, C. “Stronger Key Derivation Via Sequential Memory-Hard Functions.” (2009) (Accessed 29 January 2017) http://www.tarsnap.com/scrypt/scrypt.pdf

Pippenger, N. “Superconcentrators.” SIAM J. Comput. 6.2 (1977) 298–304 doi:10.1137/0206022

Rajasekaran, S., Reif, J. H. “Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms.” SIAM J. Comput. 18.3 (1989) 594–607

Satish, N., et al. “Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort.” SIGMOD’10 (2010) 351–362

Schroeppel, R., Shamir, A. “A T = O(2n/2),S = O(2n/4) Algorithm for Certain NP-Complete Problems.” SIAM J. Comput. 10.3 (1981) 456–464 doi:10.1137/0210033

Shamir, A. “On the Cryptocomplexity of Knapsack Systems.” (1979) 118–129 doi:10.1145/800135.804405

Tromp, J. “Cuckoo Cycle: a memory bound graph-theoretic proof-of-work.” (2014) Cryptology ePrint Archive, Report 2014/059 (Accessed 29 January 2017) http://eprint.iacr.org/2014/059, project webpage https://github.com/tromp/cuckoo

van Oorschot, P. C., Wiener, M. J. “Parallel Collision Search with Cryptanalytic Applications.” J. Cryptology 12.1 (1999) 1–28 doi:10.1007/PL00003816

Wagner, D. “A Generalized Birthday Problem.” Lecture Notes in Computer Science 2442 (2002) 288–303 doi:10.1007/3-540-45708-9 19

Ye, X., Fan, D., Lin, W., Yuan, N., Ienne, P. “High Performance Comparison-Based Sorting Algorithm on Many-Core GPUs.” (2010) 1–10 doi:10.1109/IPDPS.2010.5470445

Downloads

Published

2017-04-28

How to Cite

Biryukov, A., & Khovratovich, D. (2017). Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem. Ledger, 2, 1–30. https://doi.org/10.5195/ledger.2017.48

Issue

Vol. 2 (2017)

Section

Research Articles

License

Authors who publish with this journal agree to the following terms:

  1. The Author retains copyright in the Work, where the term “Work” shall include all digital objects that may result in subsequent electronic publication or distribution.
  2. Upon acceptance of the Work, the author shall grant to the Publisher the right of first publication of the Work.
  3. The Author shall grant to the Publisher and its agents the nonexclusive perpetual right and license to publish, archive, and make accessible the Work in whole or in part in all forms of media now or hereafter known under a Creative Commons Attribution 4.0 International License or its equivalent, which, for the avoidance of doubt, allows others to copy, distribute, and transmit the Work under the following conditions:
    1. Attribution—other users must attribute the Work in the manner specified by the author as indicated on the journal Web site;
    with the understanding that the above condition can be waived with permission from the Author and that where the Work or any of its elements is in the public domain under applicable law, that status is in no way affected by the license.
  4. The Author is able to enter into separate, additional contractual arrangements for the nonexclusive distribution of the journal's published version of the Work (e.g., post it to an institutional repository or publish it in a book), as long as there is provided in the document an acknowledgement of its initial publication in this journal.
  5. Authors are permitted and encouraged to post online a prepublication manuscript (but not the Publisher’s final formatted PDF version of the Work) in institutional repositories or on their Websites prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work. Any such posting made before acceptance and publication of the Work shall be updated upon publication to include a reference to the Publisher-assigned DOI (Digital Object Identifier) and a link to the online abstract for the final published Work in the Journal.
  6. Upon Publisher’s request, the Author agrees to furnish promptly to Publisher, at the Author’s own expense, written evidence of the permissions, licenses, and consents for use of third-party material included within the Work, except as determined by Publisher to be covered by the principles of Fair Use.
  7. The Author represents and warrants that:
    1. the Work is the Author’s original work;
    2. the Author has not transferred, and will not transfer, exclusive rights in the Work to any third party;
    3. the Work is not pending review or under consideration by another publisher;
    4. the Work has not previously been published;
    5. the Work contains no misrepresentation or infringement of the Work or property of other authors or third parties; and
    6. the Work contains no libel, invasion of privacy, or other unlawful matter.
  8. The Author agrees to indemnify and hold Publisher harmless from Author’s breach of the representations and warranties contained in Paragraph 6 above, as well as any claim or proceeding relating to Publisher’s use and publication of any content contained in the Work, including third-party content.
  9. The Author agrees to digitally sign the Publisher’s final formatted PDF version of the Work.

Revised 7/16/2018. Revision Description: Removed outdated link.