王晓明对区块链和以太坊的思考

HPB47：ETH-Pow算法分析

2018 年 6 月 26 日

1. Ethash算法

1.1 以太坊

Ethash是以太坊1.0使用的PoW（Proof of Work）算法，是Hashimoto算法结合Dagger的变种。 其特点是计算效率基本与CPU无关，与内存大小和内存带宽正相关。 因此，通过共享内存大规模部署的矿机芯片，无法实现挖矿效率的线性或超线性提升。

算法的大致流程如下：

1.2 记忆困难

由于比特币使用哈希算法作为POW工作量证明的重要手段，后续各种使用POW的数字货币也延续了这种设计，以SHA256和MD5（MD5后来被证明没有强碰撞的数字货币一般不使用）作为代表一种算法。 在设计之初，它们都是计算能力敏感的，也就是说计算资源是瓶颈，主频越高的CPU进行Hash的速度越快。 这种设计直接导致了后来矿机的出现。 使用ASIC芯片的矿机使算力翻倍。 更多矿场的出现让当时的比特币面临着算力中心化的威胁。 为了限制对计算能力的依赖，人们开始寻求新的算法。 既然要限制CPU的算力，自然就把目光转向了存储依赖，也就是内存依赖。

桥本算法使用 IO 饱和策略来对抗 ASIC，使得内存读取成为挖矿过程中的限制因素。

Dagger算法利用DAG（directed acyclic graphs directed acyclic graph）同时实现了记忆困难和记忆容易验证的两大特点。 主要原则是计算每个nonce需要DAG的一小部分，挖矿过程需要存储完整的DAG，禁止每次计算DAG对应的子集，而验证过程是允许的。

1.3 参数定义

WORD_BYTES 4 Word的字节数

DATASET_BYTES_INIT

2**301GB

数据集的初始大小|

DATASET_BYTES_GROWTH

2**238MB

每个epoch数据集的增长量|

CACHE_BYTES_INIT

2**2416MB

缓存的初始大小|

CCHCHE_BYTES_GROWTH

2**17128KB

每个时期的缓存增长量|

CACHE_MULTIPLIER 缓存乘数

1024

DAG 相对于缓存的大小|

EPOCH_LENGTH

30000

每个时期的块数|

混合字节

128

混合宽度|

HASH_BYTES

64

哈希长度|

数据集_父母

256

每个数据集元素的父母数量|

CACHE_ROUNDS 轮次

3个

计算缓存时的轮数 |

访问权限

64

桥本循环次数 |

2 个 DAG

DAG是ethash算法中访问频率较高的数据集，每个epoch产生一次。 DAG 的生成时间很长，如果客户端至少按需生成，那么每次 epoch 转换都会等待很长时间才能找到新 epoch 的第一个区块。 然而，DAG 的生成只依赖于块的数量，因此可以预先计算 DAG，以避免在每个 epoch 转换时等待时间过长。

DAG生成过程如下：

2.1 Dag_size和Cache_size

每个epoch的dagsize和cachesize都不一样。 上面已经定义了创建时的初始值。 以太坊还提供了一个表来存储接下来 2048 个纪元（大约 20 年）的值。 有关详细信息，请参阅或源代码 cpp-ethereum/libethash/data_sizes.h。

datasize和cachesize的获取方法如下：

2.2 种子哈希

该算法需要一个种子哈希以太坊创世区块不能挖矿了，它由以下程序生成。 从程序中可以看出，每个epoch的seed是不变的。

2.3 缓存

使用 seedhash 计算缓存。

2.4 DAGs

最后使用缓存计算DAG，缓存数据保存在light参数中。

2.5 DAG文件

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，以little-endian格式写入。 接下来是以little-endian格式编写的数据集数据。

3Ethash实现

3.1 以太坊

图1 算法流程图

参数说明：

Header_hash：为当前区块头数据的哈希值，矿工调用get_ethwork时从任务参数中获取。

Nonce：每次计算ethash使用不同的数字，不能重复。 可以将时间戳或随机数作为起始值和增量。

对于矿工来说，如果result的值小于等于target，则挖矿过程结束，提交当前的nonce和mix_hash作为工作量证明； 如果result的值大于target，则需要改变nonce的值。 再次调用ethash算法。

Ethash算法流程如下：

从图中可以看出，每个ethash从DAG中随机取64128=8192Bytes。 以GTX1070显卡为例，带宽为256GB/s，所以每秒可以承受256102410241024/8192=33554432次ethash操作，即33MH/s的算力。 可见该算法对内存带宽要求较高。

3.2 快速验证

快速验证工作提交是否有效。

这是一个快速验证程序：

感谢 HPB 团队的整理。

关于我

蓝莲花（王晓明）：HPB核心链（hpb.io）创始人，巴比特专栏作家。 十余年金融大数据和区块链技术开发经验，参与创建银联大数据。 创作区块链教学视频节目《名说》30余集，编写《以太坊官网文档中文版》，作为主要作者编写《区块链开发指南》，中国区块链社区ID“蓝莲花” ”著名。2018年6月9日，HPB芯链荣登《2018胡润区块链企业排行榜》区块链创新企业TOP50。

公众

发布者 Bob WangJun 26th, 2018HPB

« HPB46: Solidity编译器和简单调试 HPB48: P2P网络数据处理流程 »