Equihash

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.[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).

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 chosen hash 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.

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.

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

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

• Proof of stake