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 lot of memory to generate a proof (called "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 the factor of 1000 if memory is halved, and presents a proof of just 120 bytes long.
Category / Keywords: Equihash, memory-hard, asymmetric, proof-of-work, client puzzle Date: received 28 Sep 2015, last revised 27 Oct 2016 Contact author: alex biryukov at uni lu;khovratovich@gmail com Available format(s): PDF | BibTeX Citation Note: More material on parallel ASIC implementations added. Version: 20161027:073154 (All versions of this report) Short URL: ia.cr/2015/946 Discussion forum: Show discussion | Start new discussion