摘要：當前和一樣，采用基于工作量證明的共識算法來產生新的區塊。源碼解析生成通過方法生成，首先是生成，再從生成挖礦在挖礦與共識中提到了，共識算法通過實現接口，來實現挖礦算法也不例外。

Ethereum當前和Bitcoin一樣，采用基于工作量證明(Proof of Work,PoW)的共識算法來產生新的區塊。與Bitcoin不同的是，Ethereum采用的共識算法可以抵御ASIC礦機對挖礦工作的壟斷地位，這個算法叫做Ethash。

PoW的的核心是Hash運算，誰的Hash運算更快，誰就更有可能挖掘出新的區塊，獲得更多的經濟利益。在Bitcoin的發展過程中，挖礦設備經歷了(CPU=>GPU=>ASIC)的進化過程，其中的動機就是為了更快地進行Hash運算。隨著礦機門檻地提高，參與者久越來越少，這與區塊鏈的去中心化構想背道而馳。
因此，在共識算法設計時，為了減少ASIC礦機的優勢(專用并行計算)，Ethereum增加了對于內存的要求，即在進行挖礦的過程中，需要占用消耗大量的內存空間，而這是ASIC礦機不具備的(配置符合運算那能力的內存太貴了，即使配置，這也就等同于大量CPU了)。即將挖礦算法從CPU密集型(CPU bound)轉化為IO密集型(I/O bound)

Ethash是從Dagger-Hashimoto算法改動而來的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在傳統Bitcoin的工作量證明的基礎上增加了消耗內存的步驟。

傳統的PoW的本質是不斷嘗試不同的nonce，計算HASH
$$hash\_output=HASH(prev\_hash,merkle_root,nonce)$$
如果計算結果滿足$hash\_outputnonce是有效的

而對于Hashimoto，HASH運算僅僅是第一步，其算法如下:

nonce:　64-bits.正在嘗試的nonce值
get_txid(T):歷史區塊上的交易T的hash
total_transactions:　歷史上的所有交易的個數

hash_output_A = HASH(prev_hash,merkle_root,nonce)
for i = 0 to 63 do 
    shifted_A = hash_output_A >> i
    transaction = shifted_A mod total_transactions
    txid[i] = get_txit(transaction) << i
end of
txid_mix = txid[0]^txid[1]...txid[63]
final_output = txid_mix ^ （nonce<<192)

可以看出，在進行了HASH運算后，還需要進行64輪的混淆(mix)運算，而混淆的源數據是區塊鏈上的歷史交易，礦工節點在運行此算法時，需要訪問內存中的歷史交易信息(這是內存消耗的來源)，最終只有當　$final\_output < target$　時，才算是找到了有效的nonce

Dagger-Hashimoto相比于Hashimoto，不同點在于混淆運算的數據源不是區塊鏈上的歷史交易，而是以特定算法生成的約1GB大小的數據集合(dataset)，礦工節點在挖礦時，需要將這1GB數據全部載入內存。

礦工挖礦不再是僅僅將找到的nonce填入區塊頭，還需要填入一項MixDigest，這是在挖礦過程中計算出來的，它可以作為礦工的確在進行消耗內存挖礦工作量的證明。驗證者在驗證區塊時也會用到這一項。

先計算出約16MB大小的cache，約1GB的dataset由這約16MB的cache按特定算法生成，dataset中每一項數據都由cache中的256項數據參與生成，cache中的這256項數據可以看做是dataset中數據的parent。只所以是約，是因為其真正的大小是比16MB和1GB稍微小一點(為了好描述，以下將省略約)

cache和dataset的內容并非不變，它每隔一個epoch(30000個區塊)就需要重新計算

cache和dataset的大小并非一成不變，16MB和1GB只是初始值，這個大小在每年會增大73%,這是為了抵消掉摩爾定律下硬件性能的提升，即使硬件性能提升了，那么最終計算所代表的工作量不會變化很多。結合上一條，那么其實每經過30000個區塊，cache和dataset就會增大一點，并且重新計算

全節點(比如礦工)會存儲整個 cache和dataset，而輕客戶端只需要存儲 cache。挖礦(seal)時需要dataset在內存中便于隨時存取，而驗證(verify)時，只需要有cache就行，需要的dataset臨時計算就行。

dataset生成

dataset通過generate()方法生成，首先是生成cache，再從cache生成dataset

挖礦(Seal)

在挖礦與共識中提到了，共識算法通過實現Engine.Seal接口，來實現挖礦,Ethash算法也不例外。
其頂層流程如下:

Seal調用中，啟動一個go routine來調用ethash.mine()進行實際的挖礦，參數中的block是待挖掘的區塊(已經打包好了交易)，而nonce是一個隨機值，作為挖礦過程嘗試nonce的初始值。

mine()調用首先計算后續挖礦需要的一些變量。hash為區塊頭中除了nonce和mixdigest的Hash值，dataset為挖掘這個區塊時需要的混淆數據集合(占用1GB內存),target是本區塊最終Hash需要達到的目標，它與區塊難度成反比

對本次嘗試的nonce進行hashmotoFull()函數計算最終result(最終Hash值)和digest，如果滿足target要求，則結束挖礦，否則增加nonce，再調用hashmotoFull()

func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    lookup := func(index uint32) []uint32 {
        offset := index * hashWords
        return dataset[offset : offset+hashWords]
    }
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
}

hashmotoFull()是運算的核心，內部調用hashmoto()，第三個參數為dataset的大小（即1GB）,第四個參數是一個lookup函數，它接收index參數，返回dataset中64字節的數據。

func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
    // 將dataset劃分為2維矩陣，每行mixBytes=128字節，共1073739904/128=8388593行
    rows := uint32(size / mixBytes)
    
    //　將hash與待嘗試的nonce組合成64字節的seed
    seed := make([]byte, 40)
    copy(seed, hash)
    binary.LittleEndian.PutUint64(seed[32:], nonce)

    seed = crypto.Keccak512(seed)
    seedHead := binary.LittleEndian.Uint32(seed)

    // 將64字節的seed轉化為32個uint32的mix數組(前后16個uint32內容相同)
    mix := make([]uint32, mixBytes/4)
    for i := 0; i < len(mix); i++ {
        mix[i] = binary.LittleEndian.Uint32(seed[i%16*4:])
    }

    temp := make([]uint32, len(mix))

    //　進行總共loopAccesses=64輪的混淆計算，每次計算會去dataset里查詢數據
    for i := 0; i < loopAccesses; i++ {
        parent := fnv(uint32(i)^seedHead, mix[i%len(mix)]) % rows
        for j := uint32(0); j < mixBytes/hashBytes; j++ {
            copy(temp[j*hashWords:], lookup(2*parent+j))
        }
        fnvHash(mix, temp)
    }
    // 壓縮mix：將32個uint32的mix壓縮成8個uint32
    for i := 0; i < len(mix); i += 4 {
        mix[i/4] = fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3])
    }
    mix = mix[:len(mix)/4]

    // 用8個uint32的mix填充32字節的digest
    digest := make([]byte, common.HashLength)
    for i, val := range mix {
        binary.LittleEndian.PutUint32(digest[i*4:], val)
    }
    //　對seed+digest計算hash，得到最終的hash值
    return digest, crypto.Keccak256(append(seed, digest...))
}

驗證(Verify)

驗證時VerifySeal()調用hashimotoLight()，Light表明驗證者不需要完整的dataset，它需要用到的dataset中的數據都是臨時從cache中計算。

func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    keccak512 := makeHasher(sha3.NewKeccak512())

    //lookup函數和hashimotoFull中的不同，它調用generateDatasetItem從cache中臨時計算
    lookup := func(index uint32) []uint32 {
        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte

        data := make([]uint32, len(rawData)/4) //  16 個　uint32
        for i := 0; i < len(data); i++ {
            data[i] = binary.LittleEndian.Uint32(rawData[i*4:])
        }
        return data
    }

    return hashimoto(hash, nonce, size, lookup)
}

除了lookup函數不同，其余部分hashimotoFull完全一樣

Ethash相比與Bitcoin的挖礦算法，增加了對內存使用的要求，要求礦工提供在挖礦過程中使用了大量內存的工作量證明,最終達到抵抗ASIC礦機的目的。

1 Ethash-Design-Rationale
2 what-actually-is-a-dag
3 why-dagger-hashimoto-for-ethereum