Difference between revisions of "Equihash"

From CryptoLUX
Jump to: navigation, search
(High Level View)
Line 18: Line 18:
 
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 length and order of i<sub>j</sub>.
 
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 length and order of i<sub>j</sub>.
  
== Properties ==
+
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.
 +
 
 +
Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.
 +
 
 +
== Implementation ==
 +
 
 +
 
  
 
== Instances ==
 
== 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
+
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"
Line 46: Line 52:
  
 
* NDSS'16 paper: To appear
 
* NDSS'16 paper: To appear
* Eprint version: To appear
+
* Eprint version: To appear  
*
 
 
* Bibtex entry: To appear
 
* Bibtex entry: To appear
 
* Presentation slides:  
 
* Presentation slides:  
* Reference implementation:  
+
* Reference implementation: [https://github.com/khovratovich/equihash at github]
 
* Optimized implementations: .
 
* Optimized implementations: .
  

Revision as of 22:00, 16 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.

Equihash overview.

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

Implementation

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
|

Resources

  • NDSS'16 paper: To appear
  • Eprint version: To appear
  • Bibtex entry: To appear
  • Presentation slides:
  • Reference implementation: at github
  • Optimized implementations: .

References

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