Ethereum当前和Bitcoin一样，采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是，Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位，这个算法叫做Ethash。
, [$ S) P7 ^: L9 }6 h为什么要反ASIC# i0 e4 q# \6 F' N
PoW的的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。
, ?8 e, J$ c1 K9 k9 U  I因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)4 F1 M* R2 `! y9 W5 I: D
Dagger-Hashimoto
& R* P3 [% k/ u/ C$ PEthash是从Dagger-Hashimoto算法改动而来的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。7 m7 z& Q4 ]) L3 Y6 r
传统的PoW的本质是不断尝试不同的nonce，计算HASH
& T: l) n/ z6 Z8 Z6 |; Dhash_output=HASH(prev_hash,merkleroot,nonce)
# @3 H; @* u$ Q/ ?# Y7 k7 N如果计算结果满足$hash_output
% j! C; _7 t: i9 E1 w" l而对于Hashimoto，HASH运算仅仅是第一步，其算法如下:
: C+ [. U) j; E* `nonce:　64-bits.正在尝试的nonce值* C' `8 c. r& F: m. K$ |
get_txid(T):历史区块上的交易T的hash
: E5 _: H7 x7 g5 |total_transactions:　历史上的所有交易的个数
4 U# d5 n! l7 ghash_output_A = HASH(prev_hash,merkle_root,nonce)  a& ?- f9 B, i
for i = 0 to 63 do ( \# g- [# x0 W) o. M, [6 H& e, l% ^; b4 D
    shifted_A = hash_output_A >> i
1 u2 G% H2 r( R    transaction = shifted_A mod total_transactions/ C: {' \+ _( U. ~" h% V8 l+ [* N
    txid = get_txit(transaction)
! s9 d1 z/ e( b4 L2 A可以看出，在进行了HASH运算后，还需要进行64轮的混淆(mix)运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当　$final_output
# p" Y. `. i' tDagger-Hashimoto相比于Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约1GB大小的数据集合(dataset)，矿工节点在挖矿时，需要将这1GB数据全部载入内存。
$ O1 Z" u  C9 mEthash算法概要
# V$ W0 r1 s5 R/ j$ R/ [3 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! q1 T  [1 n
7 h: H$ F$ ~# B
Ethash源码解析; L" P1 e( W3 k! G. ~' r
dataset生成! y4 ~. y7 [- ^! j+ u9 z
dataset通过generate()方法生成，首先是生成cache，再从cache生成dataset
& ~3 V. S! b$ [- s# E& O# l; b挖矿(Seal)$ F# l: D, k' e2 i5 F; w8 @
在挖矿与共识中提到了，共识算法通过实现Engine.Seal接口，来实现挖矿,Ethash算法也不例外。
: M3 S% q- y- E其顶层流程如下:6 K' Z; r7 A8 x5 |

" l5 P; y+ |$ S8 y$ `9 |7 i- `/ OSeal调用中，启动一个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& `0 C# n3 Z: P  y# i; z: X; m) V+ E, H5 b. z  H2 E# Z6 p
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {# ]" I) l) a- `
    lookup := func(index uint32) []uint32 {5 @1 }) ^5 c" O1 \3 k
        offset := index * hashWords4 V( `! V# Y- L$ I" m5 S, D* @6 p
        return dataset[offset : offset+hashWords]
7 H; o. y2 e7 \. f- k+ o    }. ?4 z. Q: s* D  {
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
& p2 f, `* E) t* Z! n}" d' Y5 u/ a: S, b8 @% r, K
hashmotoFull()是运算的核心，内部调用hashmoto()，第三个参数为dataset的大小（即1GB）,第四个参数是一个lookup函数，它接收index参数，返回dataset中64字节的数据。
: O; _6 y+ `$ E% Hfunc hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {; P) W% R2 R9 ~7 {' f2 w
    // 将dataset划分为2维矩阵，每行mixBytes=128字节，共1073739904/128=8388593行
. i# B& K& r$ y* U    rows := uint32(size / mixBytes)
8 i% [3 @3 w7 c& G6 E: S9 H! n2 Q   
. e4 ~) d9 o% s! ~    //　将hash与待尝试的nonce组合成64字节的seed; \& C; p' B7 @8 s) Y5 G
    seed := make([]byte, 40)/ h0 r  j" b# t" }
    copy(seed, hash)
! [$ U! [9 H6 O+ k# A    binary.LittleEndian.PutUint64(seed[32:], nonce)
0 r4 d/ N* R( w% Y- F    seed = crypto.Keccak512(seed)% g' t  C" t  |7 g0 h  s
    seedHead := binary.LittleEndian.Uint32(seed)9 D  _) V8 L" v6 ~' n2 B( i
    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)
2 v3 T% }0 L7 V) x* v0 l    mix := make([]uint32, mixBytes/4)
7 s8 Q+ m3 \: b0 [5 M9 k/ `9 r    for i := 0; i , ^3 q% ~4 C+ ^: a- m) b- K
验证(Verify)# P8 z# O: C: N& s) x
验证时VerifySeal()调用hashimotoLight()，Light表明验证者不需要完整的dataset，它需要用到的dataset中的数据都是临时从cache中计算。. }0 S7 F- i6 [% \
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
& y/ p* q4 ?; v    keccak512 := makeHasher(sha3.NewKeccak512())  W  {  G' n/ ~. m+ a
    //lookup函数和hashimotoFull中的不同，它调用generateDatasetItem从cache中临时计算
& G: `; c% A% e7 }1 d' \    lookup := func(index uint32) []uint32 {
+ V. p" O, S: f( l( Q        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte
# H" I/ L4 Q5 z4 {        data := make([]uint32, len(rawData)/4) //  16 个　uint32* \6 x* r: a% M1 ~: s
        for i := 0; i
: Y9 m9 o- i+ |+ m9 K) v除了lookup函数不同，其余部分hashimotoFull完全一样  z- w; k+ [8 g
总结1 y7 C+ [; `# h& ]1 c1 a8 J" t
Ethash相比与Bitcoin的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。
5 ^: g1 ~; d* o4 F+ d, T' r" k
% q" X- O2 W! Q& W& Q$ p0 m