Equihash

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Equihash is a memory-hard Proof-of-work algorithm introduced by the University of Luxembourg's Interdisciplinary Centre for Security, Reliability and Trust (SnT) at the 2016 Network and Distributed System Security Symposium. 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. 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.

Equihash is a memory-hard Proof-of-work algorithm introduced by the University of Luxembourg's Interdisciplinary Centre for Security, Reliability and Trust (SnT) at the 2016 Network and Distributed System Security Symposium. 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. 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, BitcoinZ, Horizen, Aion, Hush, and Pirate Chain 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-200,9 with an ASIC. Equihash has three parameters – n , k , and d – which determine the algorithm's time and memory requirements. The time complexity is proportional to 2^{\frac{n}{k+1}+d} while the memory complexity is proportional to 2^{k+\frac{n}{k+1}} . The algorithm is often implemented with d = 0 (using an alternative method of controlling the effective difficulty). The problem in Equihash is to find distinct, n -bit values i_1, i_2, ..., i_{2^k} to satisfy H(i_1) \oplus H(i_2) \, \oplus \, ... \, \oplus \, H(i_{2^k}) = 0 such that H(i_1 \parallel i_2 \parallel \, ... \, \parallel i_{2^k} ) has d leading zeros, where H is a chosen hash function. In addition, there are "algorithm binding conditions" which are intended to reduce the risk of other algorithms developed to solve the underlying birthday problem being applicable. A memory-less verification requires 2^k hashes and XORs. The cryptocurrency Zcash implements Equihash with n=200 and k=9 . The cryptocurrency BitcoinGold implements Equihash with n=144 and k=5 .

See also

Proof of stake

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370681896 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

7 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.