「索引」浅析Ethash共识算法

原创 寻欢人  |  文章来源:币圈达人发布时间:2020-05-24 02:09  阅读 224 次 评论 0 条
众人帮 趣闲赚 牛帮
摘要:

上一期我们分享了在 Ethereum 平台上进行 Merkle Proof 问题分析的实践。本期我们主要讨论区块链爱好者们都非常关心的话题——共识算法。以 Ethereum 的 Ethash 为例,我们将从 Ethash 算法、DAG(有向

上一期我们分享了在 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. 算法流程

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. 算法代码

DAG 的生成

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

1. DAG Cache 的生成

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 生成代码

3. DAG 生成

以计算 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 生成代码

历史上的今天:

本文地址:https://www.u5881.com/8879.html
版权声明:本站推荐的部分活动具有时效性,老淘本人并不能保证当您看到本文时,该项活动是否仍在继续。

发表评论


表情