理解Bitcoin的挖矿难度调整算法

显示全部楼层 · 发表于 2019-1-28 00:07:32

「在Bitcoin的设计中，PoW共识算法是极其精彩的一部分，矿工需按照全网络当前挖矿难度，耗费一定量的算力构造出合法的区块头部，才有可能让全网络接受这个区块并将其添加到账本中，进而获得区块奖励。挖矿难度是一个可变参数，为了出块均速控制在10分钟/个，每隔2016个区块，全网络中的节点会按照统一的算法重新计算并设定全网一致的新难度值。理解难度调整算法之前，需先熟悉区块与账本的生成过程、以及区块头部的数据结构，已经熟悉这些知识的读者可直接跳到第三部分。」
区块与账本生成流程
1）交易广播：用户签名发送交易到任意一个或多个网络节点，若交易是正确的，通过节点验证后，节点会继续向其他节点广播，最终传递到了大部分进行挖矿的节点中；
2）区块生产：矿工节点收到交易后，将交易打包成区块，并计算交易对应的Merkle Tree的树根哈希值，通过挖矿运算构造区块头部，直到区块头部的哈希值满足挖矿难度要求；
3）区块广播：任意矿工节点成功挖出区块之后，立即将区块广播到全网，和交易广播类似，全网络的其他节点会验证区块的合法性；
4）账本接纳：若同一时段只有一个合法区块被生产出来，而没有与之竞争的其他合法区块，该区块将会被纳入账本，若存在竞争区块，则取决于全网络的多数算力意志会选择继承并扩展哪一个区块路径分支，累计难度最大且最长的链最终会胜出，没有被纳入账本的合法区块则成为孤块，被淘汰出局。
「多数算力意志选择的路径」：可以将区块链的矿工集体看成是一支行军打仗的部队，这个部队在边打仗、边推进的过程中，经常会有人掉队或者走入歧路，那么如何区分歧路和主路呢？当然是拥有主要军力的主流部队选择的前进路线才是主路径。

（图1，难度累计最大且最长的链为主链，来自《Bitcoin Developer Reference》）
区块与头部数据结构
区块头部数据仅占80字节的存储空间，由于引入了交易Merkle Tree Root，区块头部可代表整个区块、可被独立传输与处理。在图2与图3的简单示意中，没有完整给出所有字段。真正的区块头部数据结构包含6个字段：
版本（Version）：4字节，Bitcoin协议的版本，矿工可以设置4字节中的空闲比特位进行算力投票；
前一区块头部的哈希（Previous Block Hash）：32字节，前一区块头部数据的哈希值（双重SHA256）,通过该字段将各个区块依次链接起来形成区块链账本；
交易梅克尔树根哈希（Merkle Root）：32字节，由本区块内的交易构成的Merkle Tree Root哈希值（双重SHA256）；
区块生成时间（Time ）：4字节，采用UNIX纪元时间，必须大于前面11个区块的中位数时间值，但不能超过当前时间2小时；
挖矿难度阀值（nBits，或记为Bits）：4字节，对挖矿难度的目标阀值的简化编码，当前区块的哈希值（双重SHA256）必须小于或等于这个阀值；
随机数（Nonce）：4字节，通过多次调整这个值对当前区块头部数据进行双重SHA256哈希运算，以满足挖矿难度阀值的要求。

q0afqo1qvjo.jpg

（图2，区块的结构，来自《Bitcoin: A Peer-to-Peer Electronic Cash System》）

1caxemth3nj.jpg

（图3，链式结构的账本，来自《Bitcoin: A Peer-to-Peer Electronic Cash System》）
出块速度与挖矿难度调整
区块头部哈希值占32字节（265个比特位），若定义MAX=2**256，则区块头部哈希的取值范围为0～MAX-1，对区块头部做双重SHA256哈希运算的结果一定位于0～MAX区间。在该区间内取一个阀值TT（Target_Threshold），并规定区块头部哈希值必须位于0～TT区间才算合法。因此挖矿运算就是不断调整区块头部中的3个字段：Nonce、Time、Merkle Root，尝试计算出位于0～TT区间的哈希值（位于TT～MAX区间则无效），得到合法的区块头部。
由于哈希函数的设计特性，其输出结果在值域区间基本上是均匀分布的，若TT越大，哈希运算结果落在0～TT区间的概率就越大，挖矿难度就低，反之，若TT越小，挖矿难度就大。这就像是在射箭，目标体积大，就容易命中，目标体积小，就很难命中。调整TT的值，也就调整了挖矿的难度。由于TT需要占用256位，为了缩短区块头部的总尺寸，对TT进行简化编码就得到了区块头部的Bits字段。
在Bitcoin网络中，随时可能有挖矿节点加入，也随时可能有挖矿节点退出，因此全网络的哈希算力经常会变化。假设挖矿难度不变，若全网算力增大，出块速度就会变快，平均少于10分钟就能产出1个区块，反之若全网算力减少，出块速度就会变慢，平均多于10分钟才能产出1个区块。若需维持平均10分钟产生1个区块，就得随着全网的算力变化而动态调整挖矿难度（也就是Bits字段的值）。
之所以采用「每生产2016个区块进行一次难度调整」的算法，而不是每次区块生产过程中都进行调整，可能是由于中本聪在设计Bitcoin之初，未能预见到矿机、矿场、矿池的出现，也未能预见到大量算力可以在比特币、比特现金、以及其他采用了同样哈希算法系统之间随意切换，并引起全网算力大幅度颠簸抖动。毕竟Bitcoin是破天荒的发明，很难做到完美，人们对区块链技术的探索与改进必然是持续迭代发展的。
假设当前正在生产的区块的高度为2016的整数倍（区块高度是从0开始计数的），这时就应该调整TT的值。若将最近2016个区块的预期产出时间记为S（2016*10*60秒），实际产出时间记为R，那么S/R则反应了出块的实际速度与预期速度的倍数关系。将TT的值调整为TT*S/R，也就是根据S/R的值放大或缩小哈希值的目标范围，则区块产出均速将贴近预期10分钟/个。
再换个角度来看，先定义一个公式DIFF=MAX/TT，相当于将0～MAX区间划分为DIFF个子区间，0～TT则为第1个区间，从概率上看，尝试DIFF次哈希运算，可以命中1次0～TT区间，可以认为这个DIFF就是难度值。当TT和MAX相等时，DIFF值为1，也就是执行1次哈希运算就能命中。但是普遍采用的难度值计算方法并不是这样的。在Bitcoin刚上线时，可能是中本聪根据当时的挖矿算力条件，设定了一个TT初始值，记为BMAX：
0x00000000FFFF0000000000000000000000000000000000000000000000000000，再定义公式BDIFF=BMAX/TT，可得出初始的基准难度值BDIFF为1（也就是最小难度值）。后来在某些矿池中，设定了一个PMAX：0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF，并按照PDIFF=PMAX/TT的公式计算难度值。BDIFF、PDIFF、DIFF都是用来表达难度的，只是分别对应的基准最大值（BMAX、PMAX、MAX）有所不同。BDIFF被使用的更普遍一些，其直观涵义为：和起初的最低难度值1相比，现在的难度增长到了BDIFF倍。
举例：通过区块浏览器https://www.blockchain.com/zh/btc/block-height/481824，可以查询到Block#481,824（2016*239）的头部哈希值为0000000000000000001c8018d9cb3b742ef25114f27563e3fc4a1902167f9893，其头部各个字段内容为：
Version：
0x20000002（以十六进制显示，矿工利用了其中的一个比特位进行了投票，表示支持Segwit）
Previous Block Hash：
0x000000000000000000cbeff0b533f8e1189cf09dfbebf57a8ebe349362811b80（以十六进制显示）
Merkle Root：
0x6438250cad442b982801ae6994edb8a9ec63c0a0ba117779fbe7ef7f07cad140（以十六进制显示）
Time：24 Aug 2017, 01:57:37（以日期时间的形式显示）
Bits：0x18013ce9（以十六进制显示）
Nonce：575,995,682（以十进制数显示）
查询前一区块Block#481,823，可以得到Bits为0x180130e0，而Block#481,824调整了挖矿难度，采用了新值0x18013ce9。最高位字节18（十进制的24）表示TT数值的字节长度，而013ce9表示TT最高位3个字节的数值，由此得出TT的值为0x013ce9000000000000000000000000000000000000000000，补满前导0扩展到256位（32字节），则为0x0000000000000000013ce9000000000000000000000000000000000000000000，计算0x00000000FFFF0000000000000000000000000000000000000000000000000000 / 0x0000000000000000013ce9000000000000000000000000000000000000000000，结果（BDIFF）为：888,171,856,257.32，意味着生产Block#481,823时的挖矿难度是初期最低难度（为1）的888,171,856,257.32倍、全网算力增幅惊人。

[挖矿综合] 理解Bitcoin的挖矿难度调整算法

相关帖子