Ethash is the Proof of Work mining algorithm used by Ethereum and distributed ledgers based on Ethereum, such as Ethereum Classic. Ethash has gone through many iterations and evolved from the initial algorithm Dagger-Hashimoto after considerable research and development. Matthew Wompler-Doty AKA “xcthulhu” did most of the work on Ethash, with contributions from others as well.
As part of Proof of Work mining, miners must generate what is called a “nonce” which is then hashed produces an output value less than a pre-specified target threshold. Due to the hash function being a one-way function, it is impossible to reverse engineer a nonce value that satisfies the target threshold. Miners must keep guessing the nonce until it satisfies the target threshold.
Ethash was designed to be ASIC resistant with a property known as “memory hardness”, which means at least 1-2 GB of RAM is required for each GPU used and the memory required to mine ether is larger than other Proof of Work systems like Bitcoin. In other words, the system’s memory bandwidth limits the performance of a miner. With Bitcoin, the time taken to complete a computation is based on the speed of the computer's central processor and has no relation to memory requirements.
However, ASICs (Application Specific Integrated Circuits) eventually appeared for Ethereum. These machines that are more efficient but tend to centralise mining and make GPUs unprofitable - which acts to push out smaller players in the mining ecosystem. While the first wave of ASICs were only marginally better than GPU, newer ASICs are likely to be much more efficient and powerful in comparison.
The process behind Ethash is outlined below.
For each block, a seed can be computed by miners by scanning all block headers up until that point. From the seed, a 16MB pseudo-random cache is computed and in turn creates a 1GB dataset (known as a Directed Acyclic Graph or DAG for short). The DAG will grow linearly over time in line with Ethereum' blockchain. Each item in the dataset depends on only a small number of items from the cache.
The process of mining ether involves grabbing random slices from the dataset and hashing them together. Verification can be done with low memory by using the cache to re-calibrate the specific pieces of the dataset you need, so only the cache needs to be stored. The large dataset is updated once every 30,000 blocks such that the majority of the miner’s effort is directed toward reading the dataset rather than making changes to it.