# Difference between revisions of "Equihash"

Line 19: | Line 19: | ||

The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below. | The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below. | ||

− | The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that | + | The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that |

− | H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the | + | H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>. |

− | A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem. Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work. | + | 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<sup>n/(k+1)</sup>) 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 as a Proof of Work == | ||

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

+ | |||

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

+ | |||

+ | == 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<sup>n/(k+1)+1</sup> 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<sup>k/2</sup>) 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 [https://zcashminers.org/submissions Zcash Mining Contest]; | ||

+ | * For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms. | ||

Line 36: | Line 45: | ||

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 | 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 [https://zcashminers.org/submissions Zcash Mining Contest]. | can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest]. | ||

+ | |||

+ | The [https://github.com/khovratovich/equihash 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 == | == Instances == | ||

− | Here, we list several Equihash instances with d=0, and provide | + | Here, we list several Equihash instances with d=0, and provide timing benchmarks 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. |

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

## Revision as of 18:10, 31 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}, 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. 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.