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

Ethereum當(dāng)前和Bitcoin一樣，采用基于工作量證明(Proof of Work,PoW)的共識(shí)算法來產(chǎn)生新的區(qū)塊。與Bitcoin不同的是，Ethereum采用的共識(shí)算法可以抵御ASIC礦機(jī)對(duì)挖礦工作的壟斷地位，這個(gè)算法叫做Ethash。

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

Ethash是從Dagger-Hashimoto算法改動(dòng)而來的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在傳統(tǒng)Bitcoin的工作量證明的基礎(chǔ)上增加了消耗內(nèi)存的步驟。

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

而對(duì)于Hashimoto，HASH運(yùn)算僅僅是第一步，其算法如下:

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

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)

可以看出，在進(jìn)行了HASH運(yùn)算后，還需要進(jìn)行64輪的混淆(mix)運(yùn)算，而混淆的源數(shù)據(jù)是區(qū)塊鏈上的歷史交易，礦工節(jié)點(diǎn)在運(yùn)行此算法時(shí)，需要訪問內(nèi)存中的歷史交易信息(這是內(nèi)存消耗的來源)，最終只有當(dāng)　$final\_output < target$　時(shí)，才算是找到了有效的nonce

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

礦工挖礦不再是僅僅將找到的nonce填入?yún)^(qū)塊頭，還需要填入一項(xiàng)MixDigest，這是在挖礦過程中計(jì)算出來的，它可以作為礦工的確在進(jìn)行消耗內(nèi)存挖礦工作量的證明。驗(yàn)證者在驗(yàn)證區(qū)塊時(shí)也會(huì)用到這一項(xiàng)。

先計(jì)算出約16MB大小的cache，約1GB的dataset由這約16MB的cache按特定算法生成，dataset中每一項(xiàng)數(shù)據(jù)都由cache中的256項(xiàng)數(shù)據(jù)參與生成，cache中的這256項(xiàng)數(shù)據(jù)可以看做是dataset中數(shù)據(jù)的parent。只所以是約，是因?yàn)槠湔嬲拇笮∈潜?6MB和1GB稍微小一點(diǎn)(為了好描述，以下將省略約)

cache和dataset的內(nèi)容并非不變，它每隔一個(gè)epoch(30000個(gè)區(qū)塊)就需要重新計(jì)算

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

全節(jié)點(diǎn)(比如礦工)會(huì)存儲(chǔ)整個(gè) cache和dataset，而輕客戶端只需要存儲(chǔ) cache。挖礦(seal)時(shí)需要dataset在內(nèi)存中便于隨時(shí)存取，而驗(yàn)證(verify)時(shí)，只需要有cache就行，需要的dataset臨時(shí)計(jì)算就行。

dataset生成

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

挖礦(Seal)

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

Seal調(diào)用中，啟動(dòng)一個(gè)go routine來調(diào)用ethash.mine()進(jìn)行實(shí)際的挖礦，參數(shù)中的block是待挖掘的區(qū)塊(已經(jīng)打包好了交易)，而nonce是一個(gè)隨機(jī)值，作為挖礦過程嘗試nonce的初始值。

mine()調(diào)用首先計(jì)算后續(xù)挖礦需要的一些變量。hash為區(qū)塊頭中除了nonce和mixdigest的Hash值，dataset為挖掘這個(gè)區(qū)塊時(shí)需要的混淆數(shù)據(jù)集合(占用1GB內(nèi)存),target是本區(qū)塊最終Hash需要達(dá)到的目標(biāo)，它與區(qū)塊難度成反比

對(duì)本次嘗試的nonce進(jìn)行hashmotoFull()函數(shù)計(jì)算最終result(最終Hash值)和digest，如果滿足target要求，則結(jié)束挖礦，否則增加nonce，再調(diào)用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()是運(yùn)算的核心，內(nèi)部調(diào)用hashmoto()，第三個(gè)參數(shù)為dataset的大?。?GB）,第四個(gè)參數(shù)是一個(gè)lookup函數(shù)，它接收index參數(shù)，返回dataset中64字節(jié)的數(shù)據(jù)。

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

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

    // 將64字節(jié)的seed轉(zhuǎn)化為32個(gè)uint32的mix數(shù)組(前后16個(gè)uint32內(nèi)容相同)
    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))

    //　進(jìn)行總共loopAccesses=64輪的混淆計(jì)算，每次計(jì)算會(huì)去dataset里查詢數(shù)據(jù)
    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個(gè)uint32的mix壓縮成8個(gè)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個(gè)uint32的mix填充32字節(jié)的digest
    digest := make([]byte, common.HashLength)
    for i, val := range mix {
        binary.LittleEndian.PutUint32(digest[i*4:], val)
    }
    //　對(duì)seed+digest計(jì)算hash，得到最終的hash值
    return digest, crypto.Keccak256(append(seed, digest...))
}

驗(yàn)證(Verify)

驗(yàn)證時(shí)VerifySeal()調(diào)用hashimotoLight()，Light表明驗(yàn)證者不需要完整的dataset，它需要用到的dataset中的數(shù)據(jù)都是臨時(shí)從cache中計(jì)算。

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

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

        data := make([]uint32, len(rawData)/4) //  16 個(gè)　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函數(shù)不同，其余部分hashimotoFull完全一樣

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

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