[数据结构与算法]PoW共识算法

PoW共识算法

Proof of Work（工作量证明）：PoW

PoW历史进程

PoW的学术研究早在1993年就开始了。1993年，美国计算机科学家、哈佛大学教授辛西娅 · 德沃克(Cynthia Dwork)首次提出了工作量证明思想，用来解决垃圾邮件问题。该机制要求邮件发送者必须算出某个数学难题的答案来证明其确实执行了一定程度的计算工作，从而提高垃圾邮件发送者的成本。1997年，英国密码学家亚当 · 伯克(Adam Back)也独立地提出、并于2002年正式发表了用于哈希现金(Hash cash)的工作量证明机制。哈希现金也是致力于解决垃圾邮件问题，其数学难题是寻找包含邮件接受者地址和当前日期在内的特定数据的SHA-1哈希值，使其至少包含20个前导零。1999 年, 马库斯 · 雅各布松(Markus Jakobsson)正式提出了 “工作量证明” 概念。这些工作为后来中本聪设计比特币的共识机制奠定了基础。

区块链的PoW

2008年，中本聪发布比特币创世论文，将工作量证明思想应用于区块链共识过程中，设计了区块链的PoW共识算法。

SHA256

SHA256是一个哈希函数，是SHA-2细分的一种算法。哈希函数，又称为散列算法，散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（或哈希值）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。

SHA256算法，对于任意长度的消息，都会产生一个256bit的哈希值，也被称为消息摘要。这个摘要相当于是个长度为32个字节的数组，通常用一个长度为64的十六进制字符串来表示

例如：blockchain经过SHA256得到

ef7797e13d3a75526946a3bcf00daec9fc9c9c4d51ddc7cc5df888f74dd434d1

想继续了解SHA256哈希函数原理的可以点击这里SHA256算法原理详解

工作量证明

首先，PoW直译就是工作量证明，简单直白理解就是通过工作证明来决定挖矿的收益。挖矿就是产出比特币的途径，参与者通过参与挖矿这一过程，来获取挖矿的收益，也就是获取对应的奖励——比特币，参与者也被称为矿工。挖矿通常采用的是矿机，矿机性能越好，收益也就越多，就是根据工作证明来执行比特币的分配方式。

PoW也是通过计算一个数值（nonce），用这个nonce加上交易数据再进行hash后得到的hash值比目标值小，再得到这个结果后会马上对全网进行广播打包区块，网络中的节点收到广播打包区块，会对结果进行验证，如果验证通过，证明这个结果是正确的，接受这个正确的结果并记录到自己的账本中，这个过程就是工作量证明。

对工作量证明简单地举个例子：我们对blockchain字符串加随机数进行SHA256运算

"blockchain0" => bd4824d8ee63fc82392a6441444166d22ed84eaa6dab11d4923075975acab938
"blockchain1" => db0b9c1cb5e9c680dfff7482f1a8efad0e786f41b6b89a758fb26d9e223e0a10
"blockchain2" => 8f0532cd22055fb7599aa48f38501dcd46e61712ab49a02f840f5545830e9260
...
"blockchain400" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"blockchain401" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"blockchain402" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

在经过403次计算后，才能恰好找到前4位为0的哈希散列。为了实现工作量证明的目标，不停的递增nonce的值并对新的字符串进行哈希运算，才得到的最后的结果。（blockchain402）SHA256的结果前四位不为0，只是举例用。

nonce值

从上面blockchain字符串的例子就可以看出来，如果要把字符串+nonce在进行SHA256运算在得出前N位为0的难度很大，要经过不断的递增测试才能得到对应的结果。

nonce可以理解为一个随机数，nonce是从0开始一直递增，直到出现的hash值满足前N位为0，就是代表挖矿成功。难度系数为多少，hash最前面就需要满足多少个0。

举个简单的例子：

投掷一枚骰子，第一次要求总点数小于12才能赢，这很简单；第二次总结数小于11才能赢，赢得概率也很大，以此类推，当总点数小于3的时候，只有两次都是1点才能赢，赢得概率只有2%。目标越小，难度也越大。

挖矿的随机数也是类似，随着前N位的0增加，难度也越来越大。

难度值

难度值就是对挖矿难度程度的度量。

也就是计算一个给定目标的hash值的困难程度。

难度值计算公式

difficulty=difficulty_1_target / current_target

difficulty_1_target的长度为256bit，前32为0，后面全为1，一般显示为hash值：

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

difficulty_1_target表示比特币网络最初的目标hash。

current_target是当前块的目标hash，先经过压缩然后存储在区块中，区块的hash值必须小于给定的目标hash，区块才成立。

例如：如果区块中存储的压缩目标HASH为 0x1b0404cb , 那么未经压缩的十六进制HASH为

0x0404cb * 2 ^ (8 * (0x1b - 3)) = 0x00000000000404CB000000000000000000000000000000000000000000000000

所以，目标HASH为0x1b0404cb时， 难度为：

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF / 0x00000000000404CB000000000000000000000000000000000000000000000000 = 16307.67 pdiff

PoW的优缺点

优点

1. 完全去中心化，节点自由进出；
2. 全网算力强，篡改成本高，难以实现

缺点

1. 共识达成时间长，长达10分钟的交易确认时间
2. 强大的算力造成电力资源的浪费

参考文献

[1]袁勇, 倪晓春, 曾帅,等. 区块链共识算法的发展现状与展望[J]. 自动化学报, 2018, 044(011):2011-2022.

[2]Dwork C, Naor M. Pricing via processing or combatting junk mail. In: Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology. Santa Barbara, California, USA: Springer-Verlag, 1992. 139?147

[3]Back A. Hashcash — a denial of service counter-measure[Online], available: http://www.hashcash.org/papers/hashcash.pdf, April 10, 2018.

[4]Jakobsson M, Juels A. Proofs of work and bread pudding protocols (extended abstract). Secure Information Networks. Boston, MA, Germany: Springer, 1999. 258?272