Ethereum当前和Bitcoin一样，采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是，Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位，这个算法叫做Ethash。0 I* m- P$ q# `- q- n* ~7 t" j
为什么要反ASIC; }- O( F1 v% r. K  ~. O
PoW的的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。
, p1 }" F' W8 @8 i% _因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)
5 i4 C. b! F3 K; L! X, sDagger-Hashimoto
/ Z% m/ U5 z/ x8 y. H0 `( a& ]Ethash是从Dagger-Hashimoto算法改动而来的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。4 f0 S- A; f$ i
传统的PoW的本质是不断尝试不同的nonce，计算HASH5 R5 z! ~0 N% s
hash_output=HASH(prev_hash,merkleroot,nonce)# }- c/ X0 G& m' n9 ]: K' N
如果计算结果满足$hash_output0 _, ?% Z3 H. ]  F; a3 V! U( v
而对于Hashimoto，HASH运算仅仅是第一步，其算法如下:
+ d2 j+ e( k- D: a; i& dnonce:　64-bits.正在尝试的nonce值
$ ?2 U8 Q: I. ?! Pget_txid(T):历史区块上的交易T的hash; b  C/ f2 Z: N# B  [5 Z1 Y
total_transactions:　历史上的所有交易的个数! b' Q' W5 [4 e" Z- F5 D
hash_output_A = HASH(prev_hash,merkle_root,nonce)
5 M7 g" [9 ^1 A5 T  wfor i = 0 to 63 do
; j' G9 _" k( X7 P6 T    shifted_A = hash_output_A >> i
5 x; v3 U1 G3 Z+ Y; g9 i    transaction = shifted_A mod total_transactions. T" ^3 U" l+ o0 W1 f
    txid = get_txit(transaction)
+ O9 W9 b* v* N$ I  X9 \  l- h可以看出，在进行了HASH运算后，还需要进行64轮的混淆(mix)运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当　$final_output + q1 {1 E: a/ f' ?' ^
Dagger-Hashimoto相比于Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约1GB大小的数据集合(dataset)，矿工节点在挖矿时，需要将这1GB数据全部载入内存。
! R& @! o* E; ^# R8 G% Q0 r  }  M; _Ethash算法概要
$ b/ r* ?) g' J矿工挖矿不再是仅仅将找到的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临时计算就行。9 P9 K4 A+ c. m, }) w* t+ C
: ]9 p  R8 f2 K1 Y8 V
Ethash源码解析+ Q* f! y3 K: h( v) V% E
dataset生成1 \2 o* ^0 i9 x3 {0 \+ ?3 R
dataset通过generate()方法生成，首先是生成cache，再从cache生成dataset
, m  Q8 \- B# p挖矿(Seal)* n4 G0 s: W& k2 U% K# f
在挖矿与共识中提到了，共识算法通过实现Engine.Seal接口，来实现挖矿,Ethash算法也不例外。
  t1 `5 H6 f; ]! U2 N6 @* J其顶层流程如下:5 q! O! x  r' l: W" s
3 |+ n8 U# U7 [- b2 q# Y% y
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()
7 v' X& A0 ^4 H( Q2 `
9 ?% L$ j) t# t7 ?9 b) dfunc hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
. M' E3 V0 n+ j! i( }    lookup := func(index uint32) []uint32 {1 ?9 l7 O- g6 P  z
        offset := index * hashWords
1 M: o! U. g. Y; |6 T/ G; b0 T        return dataset[offset : offset+hashWords]3 b! h0 G. m( h" U
    }' c$ X; K4 t' V3 u/ E: Y" g7 D/ o- D
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)' Z! Y" E' t: g/ u) {- S, X% K
}- q/ c5 _( u6 q% ^2 _/ Y
hashmotoFull()是运算的核心，内部调用hashmoto()，第三个参数为dataset的大小（即1GB）,第四个参数是一个lookup函数，它接收index参数，返回dataset中64字节的数据。
4 ~" q: D5 S% n" Vfunc hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {' ^0 [5 ~! S! Z  s3 L+ p
    // 将dataset划分为2维矩阵，每行mixBytes=128字节，共1073739904/128=8388593行
) l7 z! M) F+ u    rows := uint32(size / mixBytes)
0 V/ T: b' r% n& a# Y! ^6 a; O$ ]   
" B+ Y. V9 J9 q+ @9 R# ~    //　将hash与待尝试的nonce组合成64字节的seed
# @$ h5 e1 ^, z    seed := make([]byte, 40)
* n# f& I. W4 a" D. H5 k    copy(seed, hash)
' k8 q, a. W  l" d. L    binary.LittleEndian.PutUint64(seed[32:], nonce)
3 z* f( O  ]/ [( N  E& y7 x& `# f    seed = crypto.Keccak512(seed)
/ ^+ U" W1 }, Q$ Z; S( F" Y2 b    seedHead := binary.LittleEndian.Uint32(seed)
9 j8 J( X" Y. B7 A2 i. k; }    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)
9 E  N/ s1 s; I0 d    mix := make([]uint32, mixBytes/4)
$ I4 Y; F" u: F# h! U: d    for i := 0; i
: q% |7 G# ^/ t- \% f验证(Verify)
1 M6 x7 O* c  F8 P2 d验证时VerifySeal()调用hashimotoLight()，Light表明验证者不需要完整的dataset，它需要用到的dataset中的数据都是临时从cache中计算。4 @1 m9 k$ \( ^7 R% i& K& l
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
& H; {2 c+ G  V0 P3 c; v8 {    keccak512 := makeHasher(sha3.NewKeccak512())1 s9 T. W7 h( @3 m; h
    //lookup函数和hashimotoFull中的不同，它调用generateDatasetItem从cache中临时计算
6 U1 d4 P1 J; _! U) f8 ^8 t1 @    lookup := func(index uint32) []uint32 {6 n* S  f- L4 D; L( \" I
        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte, X- w: ]0 ?( E4 O
        data := make([]uint32, len(rawData)/4) //  16 个　uint32  |5 g& f$ t: r: [
        for i := 0; i
# B( O* E; v* T/ s- [除了lookup函数不同，其余部分hashimotoFull完全一样2 t: V  E& u# f, O1 ]0 J( Y1 `$ J
总结
( R% q2 J. U9 DEthash相比与Bitcoin的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。. C/ X4 I* a' Z* A
) Y; K/ ~* t- c$ }# w" ?: ]