Difference between revisions of "Equihash"

From CryptoLUX
Jump to: navigation, search
(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.
  
== Strengths ==
+
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>
  
== Cryptanalysis ==
+
== Properties ==
  
Here, we list the different cryptanalyses against the SPARX ciphers we are aware of, including those by its designers.
+
== 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"
! Instance || Rounds || Attack || Authors
+
! n,k|| Time || Memory || Minimum memory
 
|-
 
|-
! rowspan="1" | SPARX-64/128
+
! rowspan="1" | 144,5
| rowspan="1" | 24
+
| rowspan="1" | 15 sec
| 15 rounds (Integral)
+
| 2 GB
| Designers<ref name=DPUVGB16></ref>
+
| 500 MB
 
|-
 
|-
! rowspan="1" | SPARX-128/128
+
! rowspan="1" | 200,9
| rowspan="1" | 32
+
| rowspan="1" | 5 sec
| 22 rounds (Integral)
+
|  
| Designers<ref name=DPUVGB16></ref>
+
|  
 
|-
 
|-
! rowspan="1" | SPARX-128/256
+
! rowspan="1" |
| rowspan="1" | 40
+
| rowspan="1" ||  
| 24 rounds (Integral)
+
|
| Designers<ref name=DPUVGB16></ref>
 
 
|-
 
|-
 
|}
 
|}

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.

SPECKEY, denoted Ak.
Round function of SPARX-64/128

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

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

  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.