# Difference between revisions of "Equihash"

(Created page with "Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources. {| class="floa...") |
|||

Line 15: | Line 15: | ||

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

− | == | + | == Properties == |

− | Here, we list | + | == 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 | ||

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

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

|- | |- | ||

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

− | | rowspan="1" | | + | | rowspan="1" | 15 sec |

− | | | + | | 2 GB |

− | | | + | | 500 MB |

|- | |- | ||

− | ! rowspan="1" | | + | ! rowspan="1" | 200,9 |

− | | rowspan="1" | | + | | rowspan="1" | 5 sec |

− | | | + | | |

− | | | + | | |

|- | |- | ||

− | ! rowspan="1" | | + | ! rowspan="1" | |

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

− | | | + | | |

− | | | ||

|- | |- | ||

|} | |} |

## Revision as of 16:00, 15 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*^{[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}

## Properties

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

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

200,9 | 5 sec | ||

rowspan="1" |

## Resources

- NDSS'16 paper: To appear
- Eprint version: To appear
- Bibtex entry: To appear
- Presentation slides:
- Reference implementation:
- 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.