ETH-Pow算法分析
四道風喜
发表于 2022-12-3 13:09:36
157
0
0
' s1 f. l) ]+ p* K/ T2 r# N4 R
首先根据块信息计算一个种子(seed,c++代码中为seedhash)* U, P' H* Q* b0 @: \% V7 [2 O
* a2 M1 D) s' C4 C: d& i2 S& T8 N1 P
使用这个种子,计算出一个16MB的cache数据。轻客户端需要存储这份cache.
. Y* d$ O b; S- n/ [$ g
通过cache,计算出一个1GB(初始大小)的数据集(DAG),DAG可以理解为是一个完整的搜索空间,全客户端和矿工需要存储完整的DAG,挖矿过程中需要从DAG中重复的随机抽取数据拿去和其他数据计算mixhash,DAG中每个元素的生成只依赖于cache中的少量数据。每到一个新的纪元DAG会完全不一样,并且它的大小也随时间线性增长。: c! ^, m. O2 o2 m' h
由于仅根据cache就可以使用少量内存快速的计算出DAG中指定位置的数据,所以轻客户端只需要存储cache就可以高效的进行校验。
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的字节数* a+ \: V# x1 D" u3 L
DATASET_BYTES_INIT2**301GBDataset的初始大小|" q+ O- s7 O3 `' @- L* v
+ ]1 K6 B3 q1 A, P9 [+ _2 T5 z' k
DATASET_BYTES_GROWTH2**238MB每个纪元dataset的增长量|
, [2 c3 \; T4 ]: G# T
CACHE_BYTES_INIT2**2416MBCache的初始大小|0 g7 `. }5 p0 D" @" e
. f5 i; l* n6 B% c
CHCHE_BYTES_GROWTH2**17128KB每个纪元cache的增长量|3 S4 j6 N5 c7 N$ Q; c" ~
4 X1 g6 H" i+ O+ N
CACHE_MULTIPLIER1024SizeoftheDAGrelativetothecache|- ~# {1 c: V2 P6 G* c' M
EPOCH_LENGTH30000每个epoch的块数|
1 f7 Q: ^3 e8 e- H+ _/ O3 {+ v, J
MIX_BYTES128Mix的宽度| _& _; e2 R( w: X: Q* f
HASH_BYTES64Hash的长度|
DATASET_PARENTS256每个数据集元素的parents数量|
" `7 a% p$ _% Z$ H
CACHE_ROUNDS3计算cache时的轮数|
# _( R. l* I9 y
ACCESSES64Hashimoto循环的次数|2DAGDAG是ethash算法中需要频繁访问的数据集,这个为每个epoch生成的。DAG要花很长时间生成,如果客户端至少按照需要生成它,那么在找到新epoch第一个区块之前,每个epoch过渡都要等待很长时间。然而,DAG的生成只取决于区块数量,所以可以预先计算出DAG来避免在每个epoch过渡过长的等待时间。DAG的生成流程如下:2.1Dag_size和Cache_size每个epoch的dagsize和cachesize都不同,上面已经定义了创世时的初始值,以太坊还提供了一个表来存储接下来2048个纪元(大约20年)的各个值。
或源码cpp-ethereum/libethash/data_sizes.h.获取datasize和cachesize的方法如下:2.2Seedhash算法中需要一个seedhash,由下面程序生成,从程序可见每个epoch的seed是不变的。2.3Cache使用seedhash计算cache。, Y# q' Q$ T( M: [; P" o$ ^* t
2.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定义。
是上面计算出来的seedhash路径下可能会有多个DAG文件,这取决于用户或者客户端是否删除过时的DAG文件。格式:DAG文件以8字节的幻数开头,值为0xfee1deadbaddcafe,以小端格式写入。+ M8 m6 s0 r# g
4 a. W3 p5 v5 w( e* r
接下来是小端格式写入的dataset数据。3Ethash实现3.1Ethash图1算法流程图参数说明:Header_hash:是当前块头部数据的hash值,在矿机调用get_ethwork时从任务参数中获取。+ {, z) }/ R7 p3 A) V
: z: v4 w! _* J, E
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的算力。
可见,该算法对内存带宽的要求很高。3.2快速验证当验证一个工作提交是否有效时,速度很快。下面是快速验证程序:感谢HPB团队整理。
成为第一个吐槽的人