Ethereum当前和Bitcoin一样，采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是，Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位，这个算法叫做Ethash。
& b1 y1 V+ A' b9 `/ E% J为什么要反ASIC* w) f9 y/ }: x
PoW的的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。
6 g# s/ L! y/ {  [$ i; `( C* ~7 K因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)  ?' d  y$ U; Z7 G0 q! i# q
Dagger-Hashimoto) U! s( O# t% X+ K
Ethash是从Dagger-Hashimoto算法改动而来的，而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法，它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。
$ {( X0 A/ I- P; l9 a传统的PoW的本质是不断尝试不同的nonce，计算HASH9 K& [, k8 j0 s* z5 Q) F- `0 ^
hash_output=HASH(prev_hash,merkleroot,nonce)
  O6 h& [6 {; k+ C1 B1 E如果计算结果满足$hash_output
3 S# ]* z: v% N. @" O8 G而对于Hashimoto，HASH运算仅仅是第一步，其算法如下:* X( \1 l2 c4 u" h# ?% g
nonce:　64-bits.正在尝试的nonce值
5 s/ h' ?" h/ M- B9 P+ v, Uget_txid(T):历史区块上的交易T的hash( \4 p+ g- [+ l& T/ e/ O$ I
total_transactions:　历史上的所有交易的个数
) v. X) Z1 `2 Fhash_output_A = HASH(prev_hash,merkle_root,nonce)
1 O. o4 c9 ?, ofor i = 0 to 63 do - c  Y' k" Y! }7 }! y: t6 n
    shifted_A = hash_output_A >> i& Y6 d" w4 ]$ E- V" v
    transaction = shifted_A mod total_transactions
- Y) q3 t  K5 V4 ^" y- `  f% I5 R    txid = get_txit(transaction) , Y+ z: j6 k0 K+ o4 P, o" b
可以看出，在进行了HASH运算后，还需要进行64轮的混淆(mix)运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当　$final_output
8 Q& P! J# U- ^# U2 c- p) [/ rDagger-Hashimoto相比于Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约1GB大小的数据集合(dataset)，矿工节点在挖矿时，需要将这1GB数据全部载入内存。0 h" d, m* _' I7 V- e
Ethash算法概要
3 X) s4 P# D7 ]6 J: x2 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临时计算就行。
/ a0 G1 J% c# ]8 G1 e' N% u
* I2 J) y8 s/ nEthash源码解析3 J* E9 Z0 x! j4 P: V' l$ X- ~# Z
dataset生成
' c0 S/ F. ^  R$ @dataset通过generate()方法生成，首先是生成cache，再从cache生成dataset/ P+ b2 H( R; F/ P1 l* e% g
挖矿(Seal)
' O8 X8 w9 a: E% i6 k) i( L& i在挖矿与共识中提到了，共识算法通过实现Engine.Seal接口，来实现挖矿,Ethash算法也不例外。+ }8 ?0 s6 f  Z1 B: Z$ O, Y6 s  t
其顶层流程如下:
" s0 b8 N6 @3 \# r. w
1 x0 E  d+ m  q/ C/ v* A& v/ TSeal调用中，启动一个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 G8 f# ^/ s( ?) B

$ v. F* U  Z. Afunc hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
' w' M# p! V. o" w0 x% ^3 j% v    lookup := func(index uint32) []uint32 {7 U" x- e- f  p) M
        offset := index * hashWords' ?2 g, {7 q  ?" u! c
        return dataset[offset : offset+hashWords]
9 ?4 O, k4 s7 B& N8 |    }
7 X% s7 `; M7 x1 U8 }    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)8 m* y9 x' Z4 U  a% }- v$ {5 Y
}- D1 a% H2 a8 i6 M% U6 a- e. o8 W
hashmotoFull()是运算的核心，内部调用hashmoto()，第三个参数为dataset的大小（即1GB）,第四个参数是一个lookup函数，它接收index参数，返回dataset中64字节的数据。% w* A5 ~3 F1 c
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
( `1 z0 l8 a- S, h    // 将dataset划分为2维矩阵，每行mixBytes=128字节，共1073739904/128=8388593行2 D, i+ U7 Y- ?# D  o- i
    rows := uint32(size / mixBytes)
/ d# \* F! E/ V  D6 Z  g    3 W' S; S' Y) Q. P
    //　将hash与待尝试的nonce组合成64字节的seed
/ c- m! L( x, j* O. S8 C  U, P    seed := make([]byte, 40)+ N+ C3 m0 V- a3 u5 b" A# G' r
    copy(seed, hash)
' D. ~. d) X& W; R: o    binary.LittleEndian.PutUint64(seed[32:], nonce). ~. W2 X  E4 r& [
    seed = crypto.Keccak512(seed)
: z( a, S! t  I0 O    seedHead := binary.LittleEndian.Uint32(seed)
& }) b& n0 o& W4 E* C" U    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)
1 @8 ^  F9 s) z  k$ o: w    mix := make([]uint32, mixBytes/4)% Y/ ]4 Z* `% u. p6 \$ l+ a4 K; P
    for i := 0; i
# b+ d: r9 Z" U$ ]验证(Verify)
3 Q. W8 O* n* i5 n验证时VerifySeal()调用hashimotoLight()，Light表明验证者不需要完整的dataset，它需要用到的dataset中的数据都是临时从cache中计算。
# n" N  t; o( c& wfunc hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
7 }8 k) d7 t- x/ n4 @    keccak512 := makeHasher(sha3.NewKeccak512())$ }- ?( ?+ f; N5 H1 S0 [
    //lookup函数和hashimotoFull中的不同，它调用generateDatasetItem从cache中临时计算
& p; d% t; l# k    lookup := func(index uint32) []uint32 {
1 O  p* U3 h$ [        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte
9 G  S& @+ n# K        data := make([]uint32, len(rawData)/4) //  16 个　uint32" x& I5 {7 `( E- D4 z
        for i := 0; i   l2 g/ X4 c: @) K! I# M$ r$ I0 @
除了lookup函数不同，其余部分hashimotoFull完全一样! M& J0 k- A' [& p
总结1 G! v2 B% @. a& @2 ^+ a
Ethash相比与Bitcoin的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。" x0 ]) i% a/ e8 W* j
4 P8 g. S3 |+ D