# Difference between revisions of "Equihash"

(→Resources) |
(→Full paper) |
||

Line 9: | Line 9: | ||

== Full paper == | == Full paper == | ||

− | [ | + | [http://orbilu.uni.lu/bitstream/10993/22277/2/946.pdf Equihash original paper]. |

== High Level View == | == High Level View == |

## Revision as of 15:31, 30 November 2017

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}, all smaller than 2^{n/(k+1)+1}, 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 order of i_{j}.

A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). 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.

## Equihash time-space tradeoffs

The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2^{n/(k+1)+1} entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q^{k/2}) times as much computation per solution if there are q times as few entries per list.

Thus we conjecture that Equihash is a memory-hard PoW because:

- The optimizations in the list entry size are limited and have been largely discovered by the Zcash Mining Contest;
- For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.

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

The reference implementation solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.

## Instances

Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.

n,k | Time | Source | Memory | Source |
---|---|---|---|---|

96,5 | 0.2 s | (3) | 2.5 MB | (1) |

102,5 | 0.5 s | (3) | 5 MB | (1) |

95,4 | 1 s | (3) | 13 MB | (1) |

100,4 | 4 s | (3) | 26 MB | (1) |

120,5 | 4 s | (3) | 42 MB | (1) |

144,5 | 15 s | (3) | 700 MB | (1) |

200,9 | 5 s | (3) | 500 MB | (1) |

200,9 | 0.1 s | (2) | 150 MB | (2) |

(1) Proposition 2 of the paper.

(2) Zcash Mining Contest.

(3) Reference implementation

## Resources

- NDSS'16 paper: PDF (please refer to this publication if you need to cite Equihash)
- Eprint version: PDF
- Presentation slides: PDF
- Reference implementation: at github.

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