1.Ethash算法1.1EthashEthash是以太坊1.0中使用的PoW(工作量证明)算法,它是Hashimoto算法结合Dagger之后产生的一个变种。它的特点是计算的效率基本与CPU无关，却和内存大小和内存带宽正相关。因此通过共享内存的方式大规模部署的矿机芯片并不能在挖矿效率上有线性或者超线性的增长。该算法的一般流程如下：
$ t2 ^3 t- T# P" M) S5 D  G* |; G* N. U2 f5 y
    首先根据块信息计算一个种子(seed,c++代码中为seedhash)
5 z4 [! x2 Q: T8 W* L5 r1 N
! A; U  k' D9 h" W    使用这个种子，计算出一个16MB的cache数据。轻客户端需要存储这份cache.6 s  A( W. P4 H7 u% a
" C% y; p& e; z! A# u
    通过cache，计算出一个1GB(初始大小)的数据集(DAG)，DAG可以理解为是一个完整的搜索空间，全客户端和矿工需要存储完整的DAG，挖矿过程中需要从DAG中重复的随机抽取数据拿去和其他数据计算mixhash，DAG中每个元素的生成只依赖于cache中的少量数据。每到一个新的纪元DAG会完全不一样，并且它的大小也随时间线性增长。+ L1 }( A! V- n+ L3 t' c7 I  d

+ \( w# z" b* {  z( l; |8 u, h    由于仅根据cache就可以使用少量内存快速的计算出DAG中指定位置的数据，所以轻客户端只需要存储cache就可以高效的进行校验。1 S* m1 H9 O9 ~0 d( D( R& [
7 f( f2 t$ R% I/ ]
    1.2内存难解由于比特币将hash算法作为pow工作量证明的重要手段，后续的各种采用pow的数字货币也延续了这个设计，以SHA256、MD5（MD5后来被证明不具备强碰撞性数字货币一般不用）为代表算法。在设计之初都是算力敏感型，意味着计算资源是瓶颈，主频越高的CPU进行Hash的速度也越快。这个设计直接导致后来的矿机出现，采用ASIC芯片的矿机更是将这种运算能力成倍提升，更多矿场的出现使得当时的比特币面临算力中心化的威胁。为了限制计算能力的依赖，人们开始寻求新的算法，既然要限制CPU的能力，目光自然投向存储依赖，也就是内存依赖。Hashimoto算法采用IO饱和的策略来对抗ASIC，使内存读取成为采矿过程中的限制因素。Dagger算法使用DAG(directedacyclicgraphs有向无环图)来同时实现内存难解和内存易验证两个特点。主要原理是，计算每个nonce需要DAG中的一小部分，采矿过程需要存储完整的DAG，禁止每次计算DAG的相应子集，而验证过程是允许的。1.3参数定义WORD_BYTES4Word的字节数2 |2 J, G! `- p1 F4 P* O6 Z6 j
! @8 L3 Y5 s; P9 k
    DATASET_BYTES_INIT2**301GBDataset的初始大小|
0 S% m% z' O% Q/ s1 g" o* U6 k6 u3 L1 v" t  Z/ X+ l
    DATASET_BYTES_GROWTH2**238MB每个纪元dataset的增长量|
% `5 ]' X* }" Q( O+ C+ R' I) C' E
    CACHE_BYTES_INIT2**2416MBCache的初始大小|8 H' j7 Z4 ^  s/ N% e3 a
( K7 V# N0 y/ r4 |
    CHCHE_BYTES_GROWTH2**17128KB每个纪元cache的增长量|$ L/ }$ Q2 D6 S  m. F/ w

2 u0 @7 ^; M; y, i    CACHE_MULTIPLIER1024SizeoftheDAGrelativetothecache|
% t  J2 M4 b; a& K
! u; ?. Y) F# i3 |* L% A" L9 ?5 Y    EPOCH_LENGTH30000每个epoch的块数|
! c9 Q( }( r; |. t' c* x
" U( e4 ]# H0 ?/ |8 S* c    MIX_BYTES128Mix的宽度|
7 d+ m; @5 b9 P+ ?) n6 F
( W; Q* T; q1 o) h6 r8 r    HASH_BYTES64Hash的长度|* N  O! y- ?. P4 _/ U% Z9 I
3 g: z- i. p9 C& R8 I
    DATASET_PARENTS256每个数据集元素的parents数量|* }9 c. y6 |5 H8 s: L9 M

5 J$ \# _+ W. B& Y! \5 A, J' G    CACHE_ROUNDS3计算cache时的轮数|
; z' l# q6 o& ?8 r
( R9 x- U$ C! H4 C6 J4 e+ X- u    ACCESSES64Hashimoto循环的次数|2DAGDAG是ethash算法中需要频繁访问的数据集，这个为每个epoch生成的。DAG要花很长时间生成，如果客户端至少按照需要生成它，那么在找到新epoch第一个区块之前，每个epoch过渡都要等待很长时间。然而，DAG的生成只取决于区块数量，所以可以预先计算出DAG来避免在每个epoch过渡过长的等待时间。DAG的生成流程如下：2.1Dag_size和Cache_size每个epoch的dagsize和cachesize都不同，上面已经定义了创世时的初始值，以太坊还提供了一个表来存储接下来2048个纪元(大约20年)的各个值。
4 q: `: U* g% F! V) @; U. L
, \7 H7 ?7 ~' ?5 y    或源码cpp-ethereum/libethash/data_sizes.h.获取datasize和cachesize的方法如下:2.2Seedhash算法中需要一个seedhash，由下面程序生成，从程序可见每个epoch的seed是不变的。2.3Cache使用seedhash计算cache。
: V* k( d) b9 _4 i
0 i$ J1 j, k4 a5 H& f2.4DAG最后使用cache计算DAG，light参数中保存的是cache数据.2.5DAG文件DAG每次生成都需要很长时间，因此生成时候需要存在文件中，再使用mmap映射到内存中。DAG文件路径一般如下Mac/Linux:$HOME/.ethash/full-R–Windows:$HOME/Appdata/Local/Ethash/full-R–是ethash算法的版本号，在libethash/ethash.h中REVISION定义。
# v3 B" q2 \& a0 A# j
+ f; R* h2 Z$ F& i, q是上面计算出来的seedhash路径下可能会有多个DAG文件，这取决于用户或者客户端是否删除过时的DAG文件。格式：DAG文件以8字节的幻数开头，值为0xfee1deadbaddcafe,以小端格式写入。1 o4 |* ^  @/ Q1 N, n* O

  c$ q2 k0 w" R* o5 I. L/ i接下来是小端格式写入的dataset数据。3Ethash实现3.1Ethash图1算法流程图参数说明：Header_hash:是当前块头部数据的hash值，在矿机调用get_ethwork时从任务参数中获取。
" `- |* P4 P6 T+ s( e) ?$ ~6 B. l& j. A
Nonce:是每次计算ethash使用不同的数，不能重复。可以取时间戳或随机数作为起始值，然后递增。对于矿工来说，如果result的值小于或等于target，那么就完成了挖矿过程，将当前的nonce和mix_hash作为工作量证明提交工作；如果result的值大于target，那么就需要改变nonce的值，再次调用ethash算法.Ethash算法程序如下：从图中看，每次ethash从DAG随机取64128=8192Bytes,以GTX1070显卡为例，带宽为256GB/s,那么每秒能承受256*1024*1024*1024/8192=33554432次ethash运算，即33MH/s的算力。
0 K6 ]  b0 c" ?6 p9 n) p+ i& ?& p, G' f2 z: D3 W* d
可见，该算法对内存带宽的要求很高。3.2快速验证当验证一个工作提交是否有效时，速度很快。下面是快速验证程序：感谢HPB团队整理。