Ethereum当前和Bitcoin一样，采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是，Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位，这个算法叫做Ethash。6 n/ D5 ~; [3 y: b  Q
为什么要反ASIC
/ \  L$ o# u7 B$ y4 O2 LPoW的的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。
* @* k! q6 R0 ]7 e2 K1 R+ j& g因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)
8 S5 d) M5 c/ CDagger-Hashimoto
1 ?/ w! i. @$ p9 P; OEthash是从Dagger-Hashimoto算法改动而来的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。
# s# O+ b' e# v传统的PoW的本质是不断尝试不同的nonce，计算HASH
# b" b3 L: r" g. ?1 T7 @, |6 uhash_output=HASH(prev_hash,merkleroot,nonce)
9 y6 ]5 R9 _! D# \/ ^) s* k- [如果计算结果满足$hash_output2 z# j: _9 L2 `9 r& A
而对于Hashimoto，HASH运算仅仅是第一步，其算法如下:
* j4 _1 ?7 ]& \! W$ T9 w4 ynonce:　64-bits.正在尝试的nonce值
9 D; l2 k- t* L( x- Nget_txid(T):历史区块上的交易T的hash" o# g2 J# J* W& D: q; b
total_transactions:　历史上的所有交易的个数
# B* F1 `; R: [8 _2 ihash_output_A = HASH(prev_hash,merkle_root,nonce)* C: [& D) ?5 v( O' \2 P  C" C
for i = 0 to 63 do , P! g6 K9 D% p3 V9 S3 Z! X$ G9 \
    shifted_A = hash_output_A >> i; R. D. F( n! |: |8 N8 r
    transaction = shifted_A mod total_transactions
% D1 Q$ H/ L8 B, ?7 W* |( b, T    txid = get_txit(transaction) 8 {0 L+ \  j, h
可以看出，在进行了HASH运算后，还需要进行64轮的混淆(mix)运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当　$final_output
* Y( y; d" ], o) g( Q: pDagger-Hashimoto相比于Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约1GB大小的数据集合(dataset)，矿工节点在挖矿时，需要将这1GB数据全部载入内存。
9 Q) n+ \! A! i9 JEthash算法概要
1 i7 l( V7 p4 k$ F; y矿工挖矿不再是仅仅将找到的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临时计算就行。
4 j. }5 s4 G$ O0 J7 @. g, k4 H6 S6 m9 E. t/ o
Ethash源码解析8 x% r2 A' o# t( _9 g
dataset生成
6 l( e3 j, {. {9 Rdataset通过generate()方法生成，首先是生成cache，再从cache生成dataset7 p9 C( h6 A1 l2 n/ A: M2 J& \8 F/ F
挖矿(Seal)$ r7 p( ^: A. N2 O2 ]+ q
在挖矿与共识中提到了，共识算法通过实现Engine.Seal接口，来实现挖矿,Ethash算法也不例外。) ?; V, M! B7 W+ ?- t9 m
其顶层流程如下:+ Q9 Z9 f; A  V8 N( s

( z* i. K4 x, T: l5 ^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()' S9 ~! `6 U% b. _. h$ f
& b1 }4 a0 G  m; n- W4 d
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
; L* \7 _; F: y: R0 ?* `. d    lookup := func(index uint32) []uint32 {
1 q; I6 C9 c. ?: w' }        offset := index * hashWords
* i, e( L) l; g8 D8 f- U        return dataset[offset : offset+hashWords]
. [0 f! |& |& f* s/ c; c  L    }
1 y9 _: A  e5 Q4 Z    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
# ^, V: q, ^0 R% S}% A9 L1 n, o5 L5 f
hashmotoFull()是运算的核心，内部调用hashmoto()，第三个参数为dataset的大小（即1GB）,第四个参数是一个lookup函数，它接收index参数，返回dataset中64字节的数据。
- H7 i- ~8 h/ rfunc hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {% _9 [0 e0 z( U+ ^1 A/ h# \
    // 将dataset划分为2维矩阵，每行mixBytes=128字节，共1073739904/128=8388593行
* [( N  N/ S+ n$ T( \    rows := uint32(size / mixBytes)
* r( Y4 b4 i9 e6 M    ' i2 z+ U: a7 c9 B) w7 M4 @6 H
    //　将hash与待尝试的nonce组合成64字节的seed
1 A2 e+ m; H* M; {2 {    seed := make([]byte, 40)+ m( M5 [7 W& E7 s
    copy(seed, hash)
0 {( `1 t* U* n5 R6 F$ x  D    binary.LittleEndian.PutUint64(seed[32:], nonce)
" x1 H: u5 _2 N5 j6 W0 Z6 j. F    seed = crypto.Keccak512(seed)1 e. `2 R+ F- a* P
    seedHead := binary.LittleEndian.Uint32(seed)
7 R" b( C4 u) k* a! Y& @! u    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)0 `$ Z# I& P: j/ H( F; x
    mix := make([]uint32, mixBytes/4)
3 N7 ?8 v" m" j7 o7 C* v    for i := 0; i
3 W' v& @5 [( f5 E  W/ F验证(Verify)' q' ^* D! M2 N+ @4 N. x: r
验证时VerifySeal()调用hashimotoLight()，Light表明验证者不需要完整的dataset，它需要用到的dataset中的数据都是临时从cache中计算。
2 j2 p# C& S6 ], A7 Kfunc hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {9 B2 |: ?7 n* C+ y- j' F8 k
    keccak512 := makeHasher(sha3.NewKeccak512())0 e' a- V8 Y) i
    //lookup函数和hashimotoFull中的不同，它调用generateDatasetItem从cache中临时计算& N* h  n' L$ R+ n+ G* h
    lookup := func(index uint32) []uint32 {( M$ l$ i5 w  u5 t8 ~6 e' X
        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte
, Q3 G1 M) K0 m* j        data := make([]uint32, len(rawData)/4) //  16 个　uint32
+ j" ^, {( r) Z/ d* p# B        for i := 0; i
- S7 v8 \% w( W2 `0 z, `除了lookup函数不同，其余部分hashimotoFull完全一样3 k* p4 T  X: m. A& d2 t" p# `
总结+ F) s" }& y6 n( F
Ethash相比与Bitcoin的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。0 E! S, P) L. p$ B

% c8 T9 h# E6 J7 N2 ~5 X0 ?