This spec is REVISION 23. Whenever you substantively (ie. not clarifications) update the algorithm, please update the revision number in this sentence. Also, in all implementations please include a spec revision number
Ethash is the planned PoW algorithm for Ethereum 1.0. It is the latest version of Dagger-Hashimoto, although it can no longer appropriately be called that since many of the original features of both algorithms have been drastically changed in the last month of research and development.
The general route that the algorithm takes is as follows:
- There exists a seed which can be computed for each block by scanning through the block headers up until that point.
- From the seed, one can compute a 16 MB pseudorandom cache. Light clients store the cache.
- From the cache, we can generate a 1 GB dataset, with the property that each item in the dataset depends on only a small number of items from the cache. Full clients and miners store the dataset. The dataset grows linearly with time.
- Mining involves grabbing random slices of the dataset and hashing them together. Verification can be done with low memory by using the cache to regenerate the specific pieces of the dataset that you need, so you only need to store the cache.
The large dataset is updated once every 30000 blocks, so the vast majority of a miner’s effort will be reading the dataset, not making changes to it.
Ethereum’s development coincided with the development of the SHA3 standard, and the
standards process made a late change in the padding of the finalized hash algorithm, so that Ethereum’s
“sha3_256” and “sha3_512” hashes are not standard sha3 hashes, but a variant often referred
to as “Keccak-256” and “Keccak-512” in other contexts.
The parameters for Ethash’s cache and dataset depend on the block number. The cache size and dataset size both grow linearly; however, we always take the highest prime below the linearly growing threshold in order to reduce the risk of accidental regularities leading to cyclic behavior.
The cache production process involves first sequentially filling up 32 MB of memory, then performing two passes of Sergio Demian Lerner’s RandMemoHash algorithm from Strict Memory Hard Hashing Functions.
We use an algorithm inspired by the FNV hash in some cases as a non-associative substitute for XOR. Note that we multiply the prime with the full 32-bit input, in contrast with the FNV-1 spec which multiplies the prime with one byte (octet) in turn.
Essentially, we combine data from 256 pseudorandomly selected cache nodes, and hash that to compute the dataset node.
Now, we specify the main “hashimoto”-like loop, where we aggregate data from the full dataset in order to produce our final value for a particular header and nonce. In the code below,
header represents the SHA3-256 hash of the RLP representation of a truncated block header, that is, of a header excluding the fields mixHash and nonce.
nonce is the eight bytes of a 64 bit unsigned integer in big-endian order.
Essentially, we maintain a “mix” 128 bytes wide, and repeatedly sequentially fetch 128 bytes from the full dataset and use the
fnv function to combine it with the mix. 128 bytes of sequential access are used so that each round of the algorithm always fetches a full page from RAM, minimizing translation lookaside buffer misses which ASICs would theoretically be able to avoid.
If the output of this algorithm is below the desired target, then the nonce is valid. Note that the extra application of
sha3_256 at the end ensures that there exists an intermediate nonce which can be provided to prove that at least a small amount of work was done; this quick outer PoW verification can be used for anti-DDoS purposes. It also serves to provide statistical assurance that the result is an unbiased, 256 bit number.