专栏首页本体研究院本体技术视点 | 浅析Ethash共识算法

本体技术视点 | 浅析Ethash共识算法

上一期我们分享了在 Ethereu

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

欢迎与我们就共识算法等话题进行深入讨论

本文分享自微信公众号 - 本体研究院(ontologyresearch),作者:egaotan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 本体技术视点 | 可以把工作邮箱作为公钥吗?

    在正式介绍 Celo 的基于地址加密方法前,让我们回想一下从用户角度来看 BTC 或者 ONT 等如何进行转账。假设 Alice 向本体新用户 Bob 转移1 ...

    本体Ontology
  • 本体技术视点 | 如何在区块链上实现数据等资源的交换?(二)

    上一期我们讲到建立于本体主链基础设施上的去中心化资源交换协议通用资源交易协议(Generic Resources Exchange Protocol,GREP)...

    本体Ontology
  • 本体研究院院长:区块链的内在精神是开放开源

    我觉得要回答这个问题,首先要了解区块链的核心价值。只有利用区块链核心价值的场景和应用才能解决真正问题、发挥区块链作用。在我看来,目前区块链的核心价值还主要在价值...

    本体Ontology
  • 面试题,如何在千万级的数据中判断一个值是否存在?

    当你看到这个标题的时候,你也许会想我可以使用hashmap之类的来存储值,然后get就是了。又或者把数据存在数据库里然后去判断就可以了。

    ImportSource
  • 纸上谈兵: 哈希表 (hash table)

    HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素...

    Vamei
  • djb2 hash算法

    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就...

    李小白是一只喵
  • hash散列 introduction

    hash散列是在记录的存储位置与他的关键字之间建立的对应关系f, 使得每个key都对应一个存储位置, 查找时根据key的hash去查找.

    CoffeeLand
  • Hash模板 个人模板

    owent
  • 散列表(二):冲突处理的方法之链地址法的实现(哈希查找)

    首先需要澄清的一点是,这里讲的是hash table/hash map ,即数据项所存储的表要用数组来实现。 一、链地址法 这种基本思想:将所有哈希地址为i 的...

    s1mba
  • 自己动手写区块链(Java版)

    2018年开始区块链真是火啊。一夜暴富的例子一直在传说。今天我们就自己动手写一个基本的区块链。 先简单的说一下区块链是个什么(相信你早就知道了)。 区块链就是一...

    ImportSource

扫码关注云+社区

领取腾讯云代金券