Ethereum当前和Bitcoin一样，采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是，Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位，这个算法叫做Ethash。) B& e! a+ m8 O& J- z6 n+ y  O
为什么要反ASIC
0 n" u( Z8 u9 o6 a3 L4 qPoW的的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。
# J" G1 p7 R% f) V$ a! A9 o/ S因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)7 V- [+ t* u8 ^% \1 W# T: D
Dagger-Hashimoto
; j. X& _9 ?. Y& G7 ]  LEthash是从Dagger-Hashimoto算法改动而来的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。9 m' t* h7 |3 P  w+ H1 i
传统的PoW的本质是不断尝试不同的nonce，计算HASH' d' S! X+ O9 D9 q
hash_output=HASH(prev_hash,merkleroot,nonce)
8 }  ^' N+ g: Z' x! t: h如果计算结果满足$hash_output. o- O3 [  V& n: C, |( [
而对于Hashimoto，HASH运算仅仅是第一步，其算法如下:
- p3 Z3 F+ \3 hnonce:　64-bits.正在尝试的nonce值. Z: i( O* Q+ D7 r4 p* n
get_txid(T):历史区块上的交易T的hash8 V7 Z7 c( a/ O- P
total_transactions:　历史上的所有交易的个数4 l8 ^1 [0 J; I5 m
hash_output_A = HASH(prev_hash,merkle_root,nonce)  l& a) ^: [- n/ b8 H
for i = 0 to 63 do   o6 A8 ^5 {! @, c( K9 I
    shifted_A = hash_output_A >> i
# I2 Q9 F" j3 c2 {9 O  b    transaction = shifted_A mod total_transactions$ b* U6 f/ z+ F1 v1 W# i
    txid = get_txit(transaction)
5 B$ B# u6 S/ j+ M8 n可以看出，在进行了HASH运算后，还需要进行64轮的混淆(mix)运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当　$final_output
6 v9 ]' p1 c2 [+ WDagger-Hashimoto相比于Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约1GB大小的数据集合(dataset)，矿工节点在挖矿时，需要将这1GB数据全部载入内存。
  _5 y0 g: R& o2 T4 gEthash算法概要
- S! B  W  z  x0 T5 a7 U: U' B矿工挖矿不再是仅仅将找到的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临时计算就行。& r% `+ z4 f& D# l& E

% t+ O& G5 i3 }+ o5 b  y  ]% \Ethash源码解析
' J! F$ o' S. y9 o! ?dataset生成/ V. M  G8 }' I' {/ i
dataset通过generate()方法生成，首先是生成cache，再从cache生成dataset
0 H3 @! ^7 ?& q5 Z挖矿(Seal)
+ H$ r/ x1 p( ]" r. {# y, v在挖矿与共识中提到了，共识算法通过实现Engine.Seal接口，来实现挖矿,Ethash算法也不例外。7 L' F% a5 c  ^' p8 n5 g
其顶层流程如下:
4 N3 K/ I7 l2 S3 b1 b  p9 ~/ P9 p: d! [4 b  i% c/ |- M3 F
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()
# U, ?5 M# p+ q; Y2 |! X" p/ s
3 b8 L% Z4 w" k0 ufunc hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {" t; Q4 Z/ ?' d: l
    lookup := func(index uint32) []uint32 {
' x$ U1 f, H' @6 X- ?6 @        offset := index * hashWords$ w3 w# ^* H! V, [3 W# P
        return dataset[offset : offset+hashWords]
8 ~! F' Y. |7 t6 {    }
( @+ ?" g+ j6 m; }* `, [) B# ]* l/ Z; c    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
: F1 y# Y( U4 \; S}9 i5 q+ F$ l! [+ g5 I
hashmotoFull()是运算的核心，内部调用hashmoto()，第三个参数为dataset的大小（即1GB）,第四个参数是一个lookup函数，它接收index参数，返回dataset中64字节的数据。. X2 {3 ~% G5 I' I" i
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
. \5 f' `/ Q( h4 N2 S( G# U0 `+ q    // 将dataset划分为2维矩阵，每行mixBytes=128字节，共1073739904/128=8388593行1 {; W: W* s2 k  ^, q
    rows := uint32(size / mixBytes)6 r7 U( W) i. q  O5 s% S5 w
   
5 K3 ?: b1 X* k. ~: ^( {" J    //　将hash与待尝试的nonce组合成64字节的seed, {9 k0 c, k+ o; l6 k
    seed := make([]byte, 40)9 M2 l0 H, j2 y
    copy(seed, hash)
  W: |/ _" r# I# _" k" t3 C! s6 o9 O    binary.LittleEndian.PutUint64(seed[32:], nonce)( I! B4 L- h: x
    seed = crypto.Keccak512(seed)
( v7 ~* C: ?/ C' Z: U    seedHead := binary.LittleEndian.Uint32(seed)) {- a- H7 r% G
    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)
1 k, |1 p# S7 z- N* O0 b    mix := make([]uint32, mixBytes/4)
/ I6 x0 i$ N1 J) `    for i := 0; i 6 I* x  }) @( Y+ y9 q4 M7 T1 V# F" V
验证(Verify)
9 f: _5 f3 E7 O+ C  N: k, {8 ?验证时VerifySeal()调用hashimotoLight()，Light表明验证者不需要完整的dataset，它需要用到的dataset中的数据都是临时从cache中计算。
5 J0 U8 {7 ?7 d/ S5 u2 Z$ [. [func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {  L2 `- U5 F/ P5 [6 t# W5 n. f. z
    keccak512 := makeHasher(sha3.NewKeccak512())
! c" o' N7 f( p/ h, Y    //lookup函数和hashimotoFull中的不同，它调用generateDatasetItem从cache中临时计算
* r' N9 A1 y9 ?3 z    lookup := func(index uint32) []uint32 {
4 d3 \0 c( S3 b+ J8 ?        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte2 [- c2 S) W4 T
        data := make([]uint32, len(rawData)/4) //  16 个　uint32
7 `: x% `/ X$ B7 m        for i := 0; i - A0 ]* ~) M: w9 u
除了lookup函数不同，其余部分hashimotoFull完全一样1 h" K: }) T/ u
总结
9 h0 ?( R) c7 x( T# p* uEthash相比与Bitcoin的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。* s0 Y' i& B- t( N

0 z% s7 v: \& s, S2 k