Difference between revisions of "Equihash"

From CryptoLUX
Jump to: navigation, search
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.
  
  
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.

Equihash overview.

Full paper

Equihash original 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(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 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(qk/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 2k 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

  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.