This page uses content from Wikipedia and is licensed under CC BY-SA.

Equihash

Equihash is a memory-hard Proof-of-Work introduced by the University of Luxembourg's Interdisciplinary Centre for Security, Reliability and Trust (SnT) at the 2016 Network and Distributed System Security Symposium.[1] The algorithm is based on a generalization of the Birthday problem which finds colliding hash values. It has severe time-space trade-offs but concedes vulnerability to unforeseen parallel optimizations.[2] It was designed such that parallel implementations are bottle-necked by memory bandwidth in an attempt to worsen the cost-performance trade-offs of designing custom ASIC implementations. ASIC resistance in Equihash is based on the assumption that commercially-sold hardware already has quite high memory bandwidth, so improvements made by custom hardware may not be worth the development cost.

General

Equihash was proposed by Alex Biryukov and Dmitry Khovratovich as part of the University of Luxembourg research group CryptoLUX. It was introduced at the Network and Distributed System Security Symposium 2016 in San Diego. Notable blockchain-based projects such as ZCash and Aion have integrated Equihash for reasons such as security, privacy, and ASIC miner resistance.

The manufacturer Bitmain has succeeded in optimizing the processing of Zcash's Equihash-210/9 with an ASIC.[3]

Specification

Equihash has three parameters – n, k, and d – which determine the algorithm's time and memory requirements. The time complexity is proportional to while the memory complexity is proportional to . The algorithm is often implemented with .

The problem in Equihash is to find to satisfy such that has leading zeros.[2] A memory-less verification requires hashes and XORs.

Memory-hardness and time-space tradeoffs

It is proposed that the puzzle in Equihash be solved by Wagner's algorithm for the generalized birthday problem, which makes iterations over a large list.[2][4] For every factor of fewer entries per list, computational complexity of the algorithm scales proportional to for memory-efficient implementations. The authors of the original Equihash proposal claim Equihash to be memory-hard because for a given number of list entries, the fastest implementations are Wagner's algorithms, whereas optimizations in the size of list entries have already been proven.[2]

Usage

The cryptocurrency Zcash implements Equihash with and .

The blockchain-based project Aion implements Equihash with and .

See also

References

  1. ^ Prisco, Giullio (February 16, 2017). "How the Equihash Algorithm Could Democratize Zcash Mining". NASDAQ. Retrieved 6 Oct 2018.
  2. ^ a b c d Biryukov, Alex; Khovratovich, Dmitry (2017). "Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem: Open Review". 2. ISSN 2379-5980. Retrieved 7 October 2018.
  3. ^ Dölle, Mirko (June 26, 2018). "End of the graphics card era: 8000 ASIC Miners for Zcash, Bitcoin Gold & Co". Heise (in German). Retrieved 6 Oct 2018.
  4. ^ Wagner, David (2002), "A Generalized Birthday Problem", Advances in Cryptology — CRYPTO 2002, Springer Berlin Heidelberg, pp. 288–304, doi:10.1007/3-540-45708-9_19, ISBN 9783540440505, retrieved 2018-11-30