Ethereum当前和Bitcoin一样，采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是，Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位，这个算法叫做Ethash。; @5 H/ U' s' z" e# R$ i8 h" e
为什么要反ASIC
$ f2 Z+ t- e1 M' LPoW的的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。0 |2 i7 p  }( i
因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)
  n! M# q3 |# ?- bDagger-Hashimoto/ r2 q. D8 h3 N! _/ s
Ethash是从Dagger-Hashimoto算法改动而来的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。
! w) l: l* r4 Y/ ^传统的PoW的本质是不断尝试不同的nonce，计算HASH
  @; ]6 L4 V& o+ q3 j2 C0 Ehash_output=HASH(prev_hash,merkleroot,nonce)
. ~5 i. v% m. y& O  L/ I' p* [如果计算结果满足$hash_output
+ n" f4 ?7 Z+ E- \9 U而对于Hashimoto，HASH运算仅仅是第一步，其算法如下:
6 c4 F' y- ]3 H$ _0 T0 R4 Knonce:　64-bits.正在尝试的nonce值
5 I* @$ L. `8 h' u1 }0 cget_txid(T):历史区块上的交易T的hash
. B6 N$ i- b) ?9 S7 _8 ?1 A  \7 ttotal_transactions:　历史上的所有交易的个数
7 J1 u* @3 l/ n' O7 }/ ahash_output_A = HASH(prev_hash,merkle_root,nonce)) W, h- E, }% [. }3 o8 i, [
for i = 0 to 63 do
* g# f4 Y+ o4 ?    shifted_A = hash_output_A >> i
, W) g7 l$ q( C0 f5 K    transaction = shifted_A mod total_transactions
  o! f4 o1 ?) w9 W9 @    txid = get_txit(transaction) ! j& T  A8 k5 J# k; D
可以看出，在进行了HASH运算后，还需要进行64轮的混淆(mix)运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当　$final_output # W' X: s) k- b$ O
Dagger-Hashimoto相比于Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约1GB大小的数据集合(dataset)，矿工节点在挖矿时，需要将这1GB数据全部载入内存。
; I( c; h8 p% W+ ]6 ?6 s1 z' CEthash算法概要
' O2 W2 ?: Q' {! N4 y0 d$ n0 C矿工挖矿不再是仅仅将找到的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临时计算就行。
  a4 P+ T: ]9 U' p5 [; Y9 Z
3 `+ [: I$ M2 g& vEthash源码解析
! W. |" \+ ]5 F/ h! m% `* sdataset生成
8 g7 ?6 P- d7 s- N$ odataset通过generate()方法生成，首先是生成cache，再从cache生成dataset
; F" b2 g$ R5 U挖矿(Seal)+ b& P" [" \. f. l
在挖矿与共识中提到了，共识算法通过实现Engine.Seal接口，来实现挖矿,Ethash算法也不例外。
8 j+ L2 O- J# U1 r其顶层流程如下:) J) U5 X9 v2 T5 U* @/ U- ^

0 u4 X1 G# i: i5 i7 QSeal调用中，启动一个go routine来调用ethash.mine()进行实际的挖矿，参数中的block是待挖掘的区块(已经打包好了交易)，而nonce是一个随机值，作为挖矿过程尝试nonce的初始值。mine()调用首先计算后续挖矿需要的一些变量。hash为区块头中除了nonce和mixdigest的Hash值，dataset为挖掘这个区块时需要的混淆数据集合(占用1GB内存),target是本区块最终Hash需要达到的目标，它与区块难度成反比对本次尝试的nonce进行hashmotoFull()函数计算最终result(最终Hash值)和digest，如果满足target要求，则结束挖矿，否则增加nonce，再调用hashmotoFull()  P. j. |% Z: l3 W. ]5 ^0 M
& C$ P4 V$ a3 t
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {3 X" h. Y8 p" |" h
    lookup := func(index uint32) []uint32 {  a( N+ l4 R; D+ Q5 e
        offset := index * hashWords
( h( V( e5 t' ~' i0 ?        return dataset[offset : offset+hashWords]! p' I& R+ v" z) B! L
    }
" P$ ^* Z4 N4 l( u# D    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)9 c# }0 W, R$ g9 x
}2 {: X) u+ P' i9 J$ d( ?
hashmotoFull()是运算的核心，内部调用hashmoto()，第三个参数为dataset的大小（即1GB）,第四个参数是一个lookup函数，它接收index参数，返回dataset中64字节的数据。
2 d0 V0 }4 C" ]; f0 D, xfunc hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {$ f" p: q2 i/ X% s1 P; n: I
    // 将dataset划分为2维矩阵，每行mixBytes=128字节，共1073739904/128=8388593行) V% ]" l% e3 l
    rows := uint32(size / mixBytes)
! }9 R* U# T8 S& }! t" N   
3 ]5 ?9 @6 r+ S. Q% S2 P    //　将hash与待尝试的nonce组合成64字节的seed- [, o2 K8 ^3 A+ r3 y
    seed := make([]byte, 40)
; E$ ]$ A( x. v4 A. X  @6 M* Z    copy(seed, hash); [( n/ e2 ]3 q) F
    binary.LittleEndian.PutUint64(seed[32:], nonce)
, B0 D7 t; V2 y% |4 E& B$ G    seed = crypto.Keccak512(seed)  l7 s! ]8 w' h: F" ?
    seedHead := binary.LittleEndian.Uint32(seed)
( g. a+ x" p! Z  Z9 k0 {6 G    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)) D7 Q* q4 Y$ v
    mix := make([]uint32, mixBytes/4)6 {+ p3 {9 K0 T
    for i := 0; i
8 u% O- L3 _. B  |" A验证(Verify)
7 G. f" s& e# w7 h- y. l  |验证时VerifySeal()调用hashimotoLight()，Light表明验证者不需要完整的dataset，它需要用到的dataset中的数据都是临时从cache中计算。5 e  M# \) P! G) E# ~( R( W4 _
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
. h: W" R2 U6 {" V$ \% G    keccak512 := makeHasher(sha3.NewKeccak512())0 ~# [& t+ G3 h5 S
    //lookup函数和hashimotoFull中的不同，它调用generateDatasetItem从cache中临时计算
2 t- S( D% k2 P6 Q" |- H$ ^1 F& m    lookup := func(index uint32) []uint32 {! ^% }7 Y7 h8 R$ J2 G! g. F3 b/ A
        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte
, e/ y; t: ~' v- K7 ~        data := make([]uint32, len(rawData)/4) //  16 个　uint32
( ^* J2 Q- |) a1 R* c        for i := 0; i + ?/ U, ?( X& `! [5 d6 p
除了lookup函数不同，其余部分hashimotoFull完全一样1 O5 i3 G8 b+ }7 E9 l9 U* i
总结
8 e2 Q  ^! T) V* oEthash相比与Bitcoin的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。
! b! e  o' N4 u7 \/ T. {
1 W1 ?, K) N1 D& n