浅析Ethash共识算法

上一期我们分享了在 Ethereum 平台上进行 Merkle Proof 问题分析的实践。本期我们主要讨论区块链爱好者们都非常关心的话题——共识算法。以 Ethereum 的 Ethash 为例,我们将从 Ethash 算法、DAG(有向无环图,Directed Acyclic Graph) 的生成几个方面逐一介绍。

Ethash 简介

Ethash是 Ethereum 1.0基于 POW(工作量证明)的共识引擎,也叫以太的挖矿算法。其前身是 Dagger 算法和 Hashimoto 算法。

其思想是通过 IO 的限制来抵制专用矿机,实现挖矿设备平等,达到去中心化的目的。符合区块链的去中心化精神。





Epoch 和 DAG

在 Ethereum 平台上,每30,000个区块为一个 epoch,对应一个 DAG,DAG 是一个大约1G 大小的数据块,需要几个小时的时间才能生成出来。

Ethash 算法需要区块头和 DAG,通过不停尝试不同的 nonce,来计算满足难度值要求的hash。

Ethash 算法

1. 算法流程

浅析Ethash共识算法

a)区块头和 nonce 的 hash 作为 seed;
b)按照公式计算一个 DAG 索引,根据索引从 DAG 中获取数据,将获得的数据和 seed 进行 fnv_hash 作为新的 seed;
c)将第2步重复64轮;
d)压缩计算的 seed 作为 digest;
e)将1步计算的 seed 和第四步计算的 digest 的 hash 作为该区块头的 hash;

将区块头的 hash 和目标 hash(2^256/difficulty)比较,如果小于目标 hash 则 nonce 值 ok,否则更新 nonce 值重新开始。

2. 算法代码

浅析Ethash共识算法

DAG 的生成

要生成 DAG 需要先生成一个 Cache,再基于 Cache 生成 DAG。

1. DAG Cache 的生成

浅析Ethash共识算法

a)根据当前 block 的 height 映射到对应的 epoch;

b)生成 epoch 的 seed;


c)将 seed 的 hash 为 cache 中第一个 hash,cache 中后续每个 hash 均为前一个 hash 的 hash;


d)将 cache 中的一个 hash 更新为其前一个 hash 和 cache 中伪随机索引的一个 hash 的 hash;


e)将第4步重复3轮。

2. DAG Cache 生成代码

浅析Ethash共识算法

3. DAG 生成

浅析Ethash共识算法

以计算 DAG 索引 x 处的 hash(记为 hashx)为例:

a)从 Cache 中取 x/rows(rows 为 Cache 中 hash 的总个数)的 hash 作为 seed,共16个 W(W 为一个 uint 32的整数);
b)取 seed hash 的 W0计算 W0^x(W0的 x 次方)作为 hashx 的 W0,将 seed hash 的其他 W 拷贝到 hashx 对应的 W;
c)计算 hashx 的 hash 作为新的 hashx;
d)根据公式在 Cache 中伪随机索引一个 hash 和 hashx 计算 fnv_hash 作为新的hashx,这步重复256轮;
e)将 hashx 进行 hash 得到新的 hashx 即为 DAG 索引 x 处的 hash。

按照上面的方法计算 DAG 所有索引位置的 hash。

4. DAG 生成代码

浅析Ethash共识算法

关键词: Ethash  共识算法  

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/28084

联系我们

aliyinhang@gmail.com