Equihash Algorithm Explained
Last Updated: 1st November 2018
Developed by Alex Biryukov and Dmitry Khovratovich at the University of Luxembourg, the Equihash algorithm is an asymmetric memory-orientated proof-of-work system that is based on the generalized birthday problem. Equihash is memory-orientated in that it is ‘memory-hard’, meaning that the amount of proof-of-work mining that can be done is predominantly determined by how much memory i.e. RAM that one possesses. In other words, memory-hard refers to a situation in which the time taken to complete a given computational problem is primarily decided by the amount of memory required to hold data.
The current state of proof-of-work mining is such that mining in cryptocurrency systems such as Bitcoin has become a centralized activity. One reason for this is the emergence of mining specific hardware such as the application-specific integrated circuit (ASIC). An ASIC is an integrated circuit that has been custom designed for a particular use, which in this case is cryptocurrency mining. Because ASICs are especially designed for mining, they are extremely powerful and efficient in computing proofs, giving ASIC miners an advantage in the mining landscape. Thus, cryptocurrency mining has increasingly become centralized toward entities that can afford ASIC hardware in large numbers, leading to the emergence of large-scale cryptocurrency mining farms. Bitmain, the largest manufacturer of ASIC hardware, is approaching a hash rate on the Bitcoin network of 51%. If a network hash rate of over 51% is achieved, then this results in the possibility of a 51% attack. Such an attack could cause significant disruption to the network, including the reversal of transactions and also double-spends.
Equihash Algorithm and ASIC Resistance
The Equihash algorithm can be viewed as an attempt to curb ASIC mining centralization, which is why the Equihash algorithm is often referred to as being ASIC-resistant. The algorithm prevents ASIC centralization by ensuring that the generation of a proof is memory-intensive. Because memory is an expensive resource in computing, optimizing for memory on an ASIC chip will come at a large computational cost to the user. For example, as Biryukov and Khovratovich noted, the majority of desktops and laptops at market can handle 1GB of RAM, whereas 1GB of memory on a chip is expensive. Thus, the use of ASIC chips on the Equihash algorithm is intended to be less efficient and powerful when compared to mining on memoryless algorithms.
Equihash is also described as being asymmetric. This is significant because, a key feature of existing proof-of-work systems such as Bitcoin is that the proofs that are computed are difficult to prove but easy to verify. Most memory-hard schemes do not offer memory asymmetry (they are memory symmetrical), which means that a verifier must use the same amount of memory as the prover in order to validate a proof. Effectively, the verifier would have to be almost as powerful as the prover.
Biryukov and Khovratovich posit the Equihash algorithm has possessing the following properties:
Progress-free process: In order to avoid the centralization of mining, mining must be a stochastic process, where the probability of generating a proof at any given time is independent of previous events.
Large AT cost: By requiring the computation of proofs to be memory-intensive optimizing ASIC chips for memory should come at a large cost.
Small proof size and instant verification: Proof sizes are small and verified quickly enough such that minimal memory is used on part of the verifier.
Tradeoffs: Memory requirements imposed by the Equihash algorithm are worthwhile as long as attempts to optimize for memory disproportionately penalizes the user.
Flexbility: To account for future algorithmic improvements and architecture changes, variables such as the memory must be tuneable.
Limitation of the Equihash Algorithm
Zcash, a privacy-orientated and well-known cryptocurrency in the market place, adopted Equihash for their underlying algorithm, citing its ASIC resistance as the reason for its adoption. However, after adopting the algorithm in 2016, Bitmain announced in 2018 the creation of a piece of hardware, known as the Antminer Z9 mini, that has been especially designed to mine on the Equihash algorithm. This particular example highlights the difficulty of producing an algorithm that is capable of being ASIC resistant over the long run.
Other cryptocurrencies that make use of the Equihash algorithm include:
- Bitcoin Gold
- Bitcoin Private
- Komodo
- ZenCash
- ZClassic
Further information about Biryukov and Khovratovich’s Equihash algorithm can be found in their research paper: ‘Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem’.
