Paper 2015/946

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

Alex Biryukov and Dmitry Khovratovich

Abstract

Proof-of-work is a central concept in modern cryptocurrencies and denial-of-service protection tools, but the requirement for fast verification so far 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 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.

Note: More material on parallel ASIC implementations added.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Equihashmemory-hardasymmetricproof-of-workclient puzzle
Contact author(s)
alex biryukov @ uni lu
khovratovich @ gmail com
History
2016-10-27: last of 3 revisions
2015-09-28: received
See all versions
Short URL
https://ia.cr/2015/946
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/946,
      author = {Alex Biryukov and Dmitry Khovratovich},
      title = {Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2015/946},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/946}},
      url = {https://eprint.iacr.org/2015/946}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.