Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem
Open accessThe DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Parallel Collision Search with Cryptanalytic Applications
van Oorschot, P. C., & Wiener, M. J. (1999) · Journal of Cryptology · doi:10.1007/pl00003816 · Cited by 639
Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
Becker, A., Joux, A., May, A., & Meurer, A. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_31 · Cited by 398 · cited 1×
“Many algorithms were proposed for this problem [11], and many were implemented so we expect them to be well scrutinized.”
BackgroundDziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-48000-7_29 · Cited by 294
Hopcroft, J., Paul, W., & Valiant, L. (1977) · Journal of the ACM · doi:10.1145/322003.322015 · Cited by 253
Dwork, C., Naor, M., & Wee, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535218_3 · Cited by 95
Cited by
A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks
Wang, W., Hoang, D. T., Hu, P., Xiong, Z., Niyato, D., Wang, P., Wen, Y., & Kim, D. I. (2019) · IEEE Access · doi:10.1109/access.2019.2896108 · Cited by 995
Blockchain technology, bitcoin, and Ethereum: A brief overview
Vujicic, D., Jagodic, D., & Randic, S. (2018) · 2018 17th International Symposium INFOTEH-JAHORINA (INFOTEH) · doi:10.1109/infoteh.2018.8345547 · Cited by 589
A Comprehensive Survey of Blockchain: From Theory to IoT Applications and Beyond
Wu, M., Wang, K., Cai, X., Guo, S., Guo, M., & Rong, C. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2922538 · Cited by 285
Sanka, A. I., Irfan, M., Huang, I., & Cheung, R. C. C. (2021) · Computer Communications · doi:10.1016/j.comcom.2020.12.028 · Cited by 265
Quantum Attacks on Bitcoin, and How to Protect Against Them
Aggarwal, D., Brennen, G., Lee, T., Santha, M., & Tomamichel, M. (2018) · Ledger · doi:10.5195/ledger.2018.127 · Cited by 231
Metadata
- Authors
- Biryukov, A., & Khovratovich, D.
- Venue
- Ledger
- Published
- 2017-04-28
- Volume
- 2
- Pages
- 1-30
- ISSN
- 2379-5980 (ISSN-L)
- OpenAlex
- W2430860929
- Cited by
- 98
- References
- 5
- FWCI
- 6.40
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.