# Difference between revisions of "Equihash"

Line 28: | Line 28: | ||

Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in | Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in | ||

Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>). | Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>). | ||

− | + | ||

− | Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H. | + | It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H. |

Line 43: | Line 43: | ||

{| border="1" class="wikitable" | {| border="1" class="wikitable" | ||

! n,k|| Time || Memory || Minimum memory | ! n,k|| Time || Memory || Minimum memory | ||

+ | |- | ||

+ | ! rowspan="1" | 96,5 | ||

+ | | rowspan="1" | | ||

+ | | 10 MB | ||

+ | | 2.5 MB | ||

+ | |- | ||

+ | ! rowspan="1" | 72,4 | ||

+ | | rowspan="1" | | ||

+ | | 16 MB | ||

+ | | 4 MB | ||

|- | |- | ||

! rowspan="1" | 144,5 | ! rowspan="1" | 144,5 |

## Revision as of 11:49, 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.

## Contents

## Full paper

## High Level View

- Article:
*"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem*^{[1]} - 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(2^{n/(k+1)+d}) time and O(2^{n/(k+1)}) memory, though implementations of this algorithms differ in both metrics, see below.

The puzzle for Equihash-n/k/d is to find i_{1}, i_{2}, ..., i_{2k} such that
H(i_{1}) xor H(i_{2}) xor ...xor H( i_{2k}) = 0 and H(i_{1}|| i_{2}|| ...|| i_{2k}) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of i_{j}.

A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem. Wagner's algorithm requires O(2^{n/(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 as a Proof of Work

Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in
Wagner's algorithm by the factor of q increases the computational complexity by O(q^{k/2}).

It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is *asymmetric* as a solution can be verified memoryless in only 2^{k} calls to H.

## Implementation

Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at Zcash Mining Contest.

## Instances

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.

n,k | Time | Memory | Minimum memory |
---|---|---|---|

96,5 | 10 MB | 2.5 MB | |

72,4 | 16 MB | 4 MB | |

144,5 | 15 sec | 2 GB | 500 MB |

200,9 | 5 sec | ||

| |

## Resources

- NDSS'16 paper: To appear
- Eprint version: PDF
- Presentation slides:
- Reference implementation: at github
- Optimized implementations: .

## References

- ↑ 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.