Equihash is a memory-hardProof-of-work algorithm introduced by theUniversity 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 theBirthday problem which finds colliding hash values. It has severe time-space trade-offs but concedes vulnerability to unforeseen parallel optimizations.^[1] 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 customASIC 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.^{[citation needed]}

Equihash was proposed byAlex Biryukov andDmitry Khovratovich as part of the University of Luxembourg research group CryptoLUX. It was introduced at the Network and Distributed System Security Symposium 2016 inSan Diego. Notableblockchain-based projects such asZCash, BitcoinZ, Horizen, Aion, Hush, andPirate Chain have integrated Equihash for reasons such as security, privacy, andASIC miner resistance.^{[citation needed]}

The manufacturerBitmain has succeeded in optimizing the processing of Zcash's Equihash-200,9 with an ASIC.^[2]

Equihash has three parameters –${\displaystyle n}$,${\displaystyle k}$, and${\displaystyle d}$ – which determine the algorithm's time and memory requirements. The time complexity is proportional to${\displaystyle 2^{\frac{n}{k+1}+d}}$while the memory complexity is proportional to${\displaystyle 2^{k+\frac{n}{k+1}}}$. The algorithm is often implemented with${\displaystyle d=0}$ (using an alternative method of controlling the effective difficulty).^[1]

The problem in Equihash is to find distinct,${\displaystyle n}$-bit values${\displaystyle i_1,i_2,...,i_{2^k}}$ to satisfy${\displaystyle H(i_1)\oplus H(i_2)\oplus ...\oplus H(i_{2^k})=0}$ such that${\displaystyle H(i_1\parallel i_2\parallel ...\parallel i_{2^k})}$ has${\displaystyle d}$ leading zeros, where${\displaystyle H}$ is a chosenhash function.^[1] 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${\displaystyle 2^k}$hashes and XORs.^[1]

It is proposed that the puzzle in Equihash be solved by a variation of Wagner's algorithm for the generalized birthday problem. (Note that the underlying problem is not exactly the Generalized Birthday Problem as defined by Wagner, since it uses a single list rather than multiple lists.) The proposed algorithm makes${\displaystyle k}$ iterations over a large list.^[1][3] For every factor of${\displaystyle \frac{1}{q}}$ fewer entries per list, computational complexity of the algorithm scales proportional to${\displaystyle q^{\frac{k}{2}}}$ for memory-efficient implementations. Alcock and Ren^[4]refute Equihash’s security claims, concluding that no tradeoff-resistance bound is in fact known for Equihash.

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(February 2021) (Learn how and when to remove this message)

The cryptocurrencyZcash implements Equihash with${\displaystyle n=200}$ and${\displaystyle k=9}$.

The cryptocurrencyBitcoinGold implements Equihash with${\displaystyle n=144}$ and${\displaystyle k=5}$.

• Proof of stake

• Cryptocurrencies
• Cryptographic algorithms

• CS1 German-language sources (de)
• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from December 2022
• Articles with unsourced statements from October 2022
• Articles needing additional references from February 2021
• All articles needing additional references