Ethereum当前和Bitcoin一样，采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是，Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位，这个算法叫做Ethash。
3 _) A4 n! Y3 I$ W) S为什么要反ASIC
8 Z% |, S$ a/ ~2 g8 g4 dPoW的的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。- Y" T1 I. q& Y' D9 n0 u* g
因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound), g1 q4 _$ @, b8 W: `  R, \+ f* z" t
Dagger-Hashimoto
- d, z, ?5 B9 K2 REthash是从Dagger-Hashimoto算法改动而来的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。5 G1 d4 f, i) n0 E0 |4 ]/ p
传统的PoW的本质是不断尝试不同的nonce，计算HASH
: g3 ]: ?% U" S- Q& ~+ a# v( d% ihash_output=HASH(prev_hash,merkleroot,nonce)( A  L* T. @  N4 G
如果计算结果满足$hash_output
# e/ i! [8 x4 t" i5 p) `而对于Hashimoto，HASH运算仅仅是第一步，其算法如下:
% ]$ F) E, K' f: G' Qnonce:　64-bits.正在尝试的nonce值
! y9 X% o; k3 q3 N4 A; E- g7 vget_txid(T):历史区块上的交易T的hash: C5 n. U( C' X3 W+ i$ F9 f) @, c
total_transactions:　历史上的所有交易的个数: z+ R: Q9 V: @& X$ \7 `7 E& V
hash_output_A = HASH(prev_hash,merkle_root,nonce)
& @2 g1 `8 \6 tfor i = 0 to 63 do
# B) y# V6 ^- Q4 t4 P    shifted_A = hash_output_A >> i
1 a! X+ q: F9 `7 B8 @* a    transaction = shifted_A mod total_transactions
- k& o9 @$ L- o    txid = get_txit(transaction)
! Q6 @+ I0 g% u% h9 ^$ @可以看出，在进行了HASH运算后，还需要进行64轮的混淆(mix)运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当　$final_output
/ I! c0 i' c* f5 v1 RDagger-Hashimoto相比于Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约1GB大小的数据集合(dataset)，矿工节点在挖矿时，需要将这1GB数据全部载入内存。4 l0 w. K: p, {; Q9 _
Ethash算法概要; l* C2 o4 `$ z# P) P2 v/ R
矿工挖矿不再是仅仅将找到的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临时计算就行。
. p- d4 r, f* X3 Z/ i& R) R) ~+ M& w+ w. t- l0 E  h5 |
Ethash源码解析( _6 ~8 R* M* ?- R+ L' a$ b
dataset生成
( P" w; K# a$ W8 e/ A* @+ j3 tdataset通过generate()方法生成，首先是生成cache，再从cache生成dataset# d, S& Q, }, D6 }+ @6 k2 \
挖矿(Seal)
- K9 U. w" \8 A% s在挖矿与共识中提到了，共识算法通过实现Engine.Seal接口，来实现挖矿,Ethash算法也不例外。% P+ G6 Q  `" b# M" R% Z
其顶层流程如下:
1 c% Z9 H  N; T$ H/ N; T1 d, j# {7 W8 H1 c
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()1 n' U" w2 T2 d9 B: ^7 Y3 N
& a8 h7 V" w* E: k
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
  e# k" L3 Q" a' t# J  j( [    lookup := func(index uint32) []uint32 {
" {, S, C$ p9 z8 z& J) I1 ~' t        offset := index * hashWords
5 {2 H6 R3 g1 ?  P) K        return dataset[offset : offset+hashWords]9 }7 I" A; D, n& t6 ]$ I; s$ v
    }; i1 ]- f0 G  c9 l3 \! K
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)( H4 B  k. T4 M- w! J/ ]
}
' `5 y) l; x% M( e4 u5 j) l. RhashmotoFull()是运算的核心，内部调用hashmoto()，第三个参数为dataset的大小（即1GB）,第四个参数是一个lookup函数，它接收index参数，返回dataset中64字节的数据。5 P: G5 f2 c! m8 b7 H
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
: a/ ~( l; n! P+ ~* _# y    // 将dataset划分为2维矩阵，每行mixBytes=128字节，共1073739904/128=8388593行
/ {4 f/ s& ]; u" B    rows := uint32(size / mixBytes)" q; e* ?3 I/ O
   
. a4 E5 n  x) R$ _/ `8 [    //　将hash与待尝试的nonce组合成64字节的seed
  L. v% F8 y* n    seed := make([]byte, 40)
+ y" e# ?5 \2 }9 x: g; p/ _5 e    copy(seed, hash)2 T# L0 m3 H) A% `/ J" ~$ P; F
    binary.LittleEndian.PutUint64(seed[32:], nonce)! u0 T1 i% G+ B2 n
    seed = crypto.Keccak512(seed)
8 u$ v! Y/ U1 F# F) z, L: I    seedHead := binary.LittleEndian.Uint32(seed)
7 \& Z8 y6 `/ \  P$ c) Y    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)% o: ]1 L4 Z8 m
    mix := make([]uint32, mixBytes/4)* Z! D6 }# j# Y
    for i := 0; i 0 Y% A: H9 J" Q/ c# B
验证(Verify)' e8 l5 h6 `! w2 I% Z/ C
验证时VerifySeal()调用hashimotoLight()，Light表明验证者不需要完整的dataset，它需要用到的dataset中的数据都是临时从cache中计算。
& k8 _, Y5 q  Z+ t0 q. \: a  ^; @func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {8 a$ W4 i# S% M0 [
    keccak512 := makeHasher(sha3.NewKeccak512()), n: m. o1 s. ?$ R6 E
    //lookup函数和hashimotoFull中的不同，它调用generateDatasetItem从cache中临时计算$ L! Y$ b+ J6 H8 P
    lookup := func(index uint32) []uint32 {, v2 x7 E4 @; H# E
        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte
% }4 G0 k, N2 e, v        data := make([]uint32, len(rawData)/4) //  16 个　uint32
7 ^' M+ h/ J" T" m  G" X" d        for i := 0; i
) |' g" V' K0 j- w' H除了lookup函数不同，其余部分hashimotoFull完全一样
" L8 u/ h" g/ {. y: O总结- a7 I' h- Y$ L5 M6 Z6 S
Ethash相比与Bitcoin的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。
4 `$ I+ d  W9 B+ E* Y3 g6 T/ Q0 n3 I1 ~