Difference between revisions of "Equihash"
|Line 6:||Line 6:|
== High Level View ==
== High Level View ==
Revision as of 09:35, 27 October 2016
Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.
High Level View
- Article: "Equihash: asymmetric proof-of-work based on the Generalized Birthday problem
- Authors: Alex Biryukov and Dmitry Khovratovich
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. The best algorithms for Equihash-n/k/d require O(2n/(k+1)+d) time and O(2n/(k+1)) memory, though implementations of this algorithms differ in both metrics, see below.
The puzzle for Equihash-n/k/d is to find i1, i2, ..., i2k such that H(i1) xor H(i2) xor ...xor H( i2k) = 0 and H(i1|| i2|| ...|| i2k) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of ij.
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem. Wagner's algorithm requires O(2n/(k+1)) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a memory-hard proof-of-work.
Equihash is asymmetric as a solution can be verified memoryless in only 2k calls to H.
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty.
|144,5||15 sec||2 GB||500 MB|
- NDSS'16 paper: To appear
- Eprint version: To appear
- Bibtex entry: To appear
- Presentation slides:
- Reference implementation: at github
- Optimized implementations: .
- Biryukov, A. and Khovratovich, D. (2016). Equihash: asymmetric proof-of-work based on the Generalized Birthday problem. In Network and Distributed System Security Symposium (NDSS) 2016.