背景

        对于基于PoW机制的区块链系统来说,其安全性要靠挖矿来保证。而在比特币的设计理念中,中本聪曾这样说过:“One CPU, one vote”。这样的设计初衷是好的,因为,如果所有人都可以参与挖矿,就会使得总算力分布很平均,提升恶意节点造假的难度,从而提高比特币系统内的安全性。
        在比特币系统发布之初,人们都使用普通CPU来挖矿。但后来人们发现,用GPU挖矿的效率更高。因为,比特币系统中的挖矿算法对内存要求不高,而对并行计算能力要求较高,这样一来,擅长并行计算的GPU就脱颖而出。后来,又出现了ASIC挖矿机,其价格较低,且并行计算能力很强。
        而随着ASIC挖矿机的出现,挖矿设备越来越专业化,普通用户用CPU很难再挖矿成功。不仅如此,目前还出现了很多超级矿池,有些矿池甚至可以占全网总算力的20%以上。很多人认为,这就与比特币当初所设计的“去中心化”理念背道而驰,使得比特币系统的安全性开始被担忧。

挖矿算法

        以太坊为了实现“扼制ASIC挖矿机(ASIC resistance)”,采用了“对内存要求较高的挖矿(memory hard mining)”的思想来设计计算难题(puzzle)。具体来说,其使用了两个数据集,小的数据集是一个16M的Cache,大的数据集是一个1G的DAG。轻节点使用Cache,全节点使用DAG。

        其中Cache的设计和莱特币中的puzzle设计所采用的一样。取一个很大的数组,数组中的每个位置都存储伪随机数,这些伪随机数的生成方法如下

        1、取一个伪随机数种子seed;
        2、对该seed取hash存入数组第一个位置;
        3、此后依次将数组第i个位置所存元素取hash,存入第i+1个位置,直至填满数组。

        而DAG是由Cache生成的,其生成过程如下:
        1、根据一个伪随机数读取数组中的一个元素,根据其取值进行运算;
        2、算出下一次要读取的位置,读出对应位置的元素;
        3、再根据其取值进行迭代更新;
        4、将步骤2、3共重复256次,结果存入DAG的第i个位置(i从0开始自增);
        5、重复步骤1、2、3、4,直至填满整个DAG。

        求解puzzle需要用到DAG中的数据,其过程入下:
        1、根据区块头(nonce值一直变化)生成hash,映射到DAG中的一个元素;
        2、将该元素和其一个相邻元素读取出来进行运算,计算出下一个要读取的位置;
        3、将步骤2重复64次,也就意味着一共读取了128个元素;
        4、将这128个元素进行hash运算,将hash结果与当前难度值进行比较,若符合难度要求,则求解puzzle成功,否则改变nonce值,并重复步骤1、2、3、4。

        轻节点验证“区块是否合法”的过程只需要使用Cache,其具体过程如下:
        1、根据header和nonce生成hash,映射到DAG的一个元素;
        2、根据Cache计算出DAG中相应位置及其相邻位置的元素;
        3、对2中计算出的元素进行运算,得到下一个DAG中的元素的位置;
        4、将步骤2、3重复64次,也就意味着一共读取了128个元素;
        5、将这128个元素进行hash运算,将hash结果与当前难度值进行比较,若符合难度要求,则该区块合法;否则不合法。
        上述过程也就解释了,为什么轻节点只需要保存Cache。

        注:每隔30000个区块,seed的值会发生改变,Cache的大小会增加128K,DAG的大小会增加8M。

难度调整

        以太坊中的难度调整公式如下

难度调整

  • 其中,𝐷(𝐻)是本区块的难度,由基础部分 𝑃(H)𝐻𝑑 + x×𝜍2 和难度炸弹部分 𝜖 相加得到。

        • 𝑃(𝐻)𝐻𝑑 为父区块的难度,每个区块的难度都是在父区块难度的基础上进行调整。
        • x × 𝜍2 用于自适应调节出块难度,维持稳定的出块速度。
        • 𝜖 表示设定的难度炸弹。

  • 基础部分有下界,为最小值 𝐷0 = 131072。

下面是自适应难度调整 x × 𝜍2 的详解:

难度调整

  • 其中,x 是调整的单位,𝜍2 为调整的系数。
  • y和父区块的uncle数有关。如果父区块中包括了uncle ,则y为2,否则为1。

        • 父块包含uncle时难度会大一个单位,因为包含uncle时新发行的货币量大,需要适当提高难度以保持货币发行量稳定。

  • 难度降低的上界设置为−99 ,主要是应对被黑客攻击或其他意想不到的黑天鹅事件。

难度调整

  • 𝐻𝑠 是本区块的时间戳,𝑃(H)𝐻s是父区块的时间戳,均以秒为单位,并规定 Hs > 𝑃(H)𝐻s。

        • 该部分是稳定出块速度的最重要部分:出块时间过短则调大难度,出块时间过长则调小难度。

  • 以父块不带 uncle 的情况(y = 1)为例:

        出块时间在 [1,8] 之间,出块时间过短,难度调大一个单位。
        出块时间在 [9,17] 之间,出块时间可以接受,难度保持不变。
        相差时间在 [18,26] 之间,出块时间过长,难度调小一个单位。
        。。。


下面是难度炸弹 𝜖 的计算方法:

难度调整

  • 𝜖 每十万个块扩大一倍,是2的指数函数,到了后期增长非常快,这就是难度“炸弹”的由来。
  • 设置难度炸弹的原因是要降低迁移到PoS协议时发生区块链分叉的风险。因为,当以太坊由 PoW 协议迁移到 PoS 协议时,可能有很多花了大价钱买矿机的矿池不愿意迁移,从而导致以太坊永久分叉。而通过难度炸弹,迁移到 PoS 协议时挖矿难度非常大,挖矿已变得非常困难,所以矿工有意愿迁移到 PoS 协议。
  • 𝐻′𝑖 称为伪区块号(fake block number),由真正的区块号 𝐻𝑖 减少三百万得到。这样做的原因是低估了 PoS 协议的开发难度,需要延长大概一年半的时间。

本文参考:

https://www.youtube.com/watch?v=RADwCuRRoFs&list=PLnTPdMjBRmAYehJkVbAXqxO-0cc9ALC6V&index=19

https://www.youtube.com/watch?v=RADwCuRRoFs&list=PLnTPdMjBRmAYehJkVbAXqxO-0cc9ALC6V&index=20

最后更新: 2019年03月26日 21:52

原始链接: http://yoursite.com/2019/03/26/以太坊中的挖矿算法与难度调整/