《迅雷链精品课》第十二课：PoW 共识算法

上一节课我们了解了常用的几种共识算法，今天我们详细地分析PoW(Proof-of-Work，工作量证明)共识算法，了解其来源和优缺点。



在学习课程的时候，你也可以领取BaaS平台为期一个月的试用机会，免费使用高性能区块链服务（点击链接即可免费领取https://blockchain.xunlei.com/baas/try.html）。课程学习结合实践操作，让你迅速成为区块链大牛！

*以下为第十二课的内容~



第十二课 PoW共识算法



1. 概述



PoW(Proof-of-Work，工作量证明)是比特币采用的共识机制。由于比特币在加密货币中的重要地位，PoW也成为后续加密货币系统的主流共识机制之一。



PoW是一种针对拒绝服务攻击的应对方法，其要求客户端执行某些需要消耗资源的运算，而其答案能被服务方快速验算，以耗用的时间、设备与能源做为担保成本，以确保服务无法被恶意节点所滥用。



2.  PoW机制的来源



这个概念由Cynthia Dwork 和Moni Naor 1993年在学术论文《 Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology》中首次提出；而“Proof of Work”一词则是在1999年由Markus Jakobsson与Ari Juels发表的论文《Proofs of Work and Bread Pudding Protocols》中提出正式的定义；PoW技术最初在Hashcash中应用。Hashcash是Adam Back 在1997年提出的，作为一种遏制互联网系统资源被滥用的措施，例如反垃圾电子邮件应用。



Hashcash要求邮件客户端生成一个字符串，用SHA-1算法计算这个字符串得到的哈希值中，有特定数量的0前缀。SHA-1算法的碰撞非常困难，而且要求的哈希值的前缀0的数量越多，客户端要找到符合条件的字符串需要的计算量就越大。在电子邮件的应用中，为了给发出的消息加上戳记，只需要向电子邮件添加头部字段即可：用于电子邮件的每一个 To: 或 Cc: 接收者的 X-Hashcash 头。例如，某个想给adam@cypherspace.org这个邮箱发送消息的人可能会在消息中包含一个X-Hashcash消息头：

X-Hashcash:

1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi



服务端可以通过检查戳记的SHA-1散列来校验它，如下所示：



00000b7c65ac70650eb8d4f034e86d7d5cd1852f

可见，哈希结果有5个前缀字符是0，每个字符占4个比特，因此这个哈希值的前20个比特为零，即前缀0的比特数量为20。



Hashcash的头部格式为：1:bits:date:resource:ext:salt:suffix，包括 7 个域：

1) 版本号。

2) 前缀为0的比特数量。若其哈希值的0前缀数量少于此数，那么它就是非法的。

3) 生成戳记的日期。可以认为当前时间之后的戳记以及那些在很久以前的戳记是非法的。

4) 戳记为哪个资源而生成。可能是一个电子邮件地址，但是也可能是一个 URI 或者其他命名的资源。

5) 特定应用程序可能需要的扩展，通常为空。

6) 随机因子（salt）。用于将该戳记与其他人为相同的资源在同一日期生成的戳记区别开来。

7) 后缀字符串。是算法真正起作用的部分。由于在特定的时间，A给B发邮件，前 6 个域就已经是固定的，为了生成一个通过期望数目的前导零进行散列的的戳记，客户端必须尝试很多连续的后缀值。



通过让邮件客户端做这样的计算，能有效防止垃圾邮件的泛滥。生成一个 20比特0前缀哈希的字符串只需要几秒钟的时间，当你一天中只发送几十封电子邮件时，这个代价并不大。但是，对那些想要发送数百万消息的垃圾邮件制造者来说，这就是无法承受的消耗。



在比特币出现之前，Hashcash的PoW算法也被Hal Finney以可重复使用的工作量证明（RPOW）的形式用于一种比特币之前的加密货币实验中。另外，Wei Dai的B-money、Nick Szabo的Bit-Gold这些数字货币的先行者，都是基于Hashcash的PoW机制下进行挖矿的。



3. 比特币的PoW共识机制



比特币网络于2009年上线。比特币网络的PoW共识机制使用基于Hashcash的PoW来挖矿，挖矿节点发布自己的计算结果，由比特币P2P网络上的去中心化节点负责验证。比特币的PoW计算难度会被周期性的调整，以保证出块时间的稳定。



3.1. 哈希函数的选择



由于SHA-1已被证明不安全，比特币采用了SHA-2系列的SHA-256算法作为哈希函数。使用SHA-256作为哈希函数时，无论输入长度为多少，输出总有一个固定的256位（32字节）长度。



由于PoW严重依赖于哈希算法，因此哈希算法的安全性至关重要。若使用了不安全的哈希算法，则恶意节点能付出远小于其它诚实节点的计算量，就能找到符合要求的字符串，这样恶意节点就可能承包所有的出块，获得所有的奖励，并能随意篡改数据。



理论上进行暴力破解SHA-1至少需要2的80次方（哈希循环的一个周期）才能碰撞破解。但是在2005年，中国密码学家王小云院士提出哈希函数的碰撞攻击理论，只用了2的69次方次就完成了SHA-1的循环碰撞周期。 



不容忽视的是，SHA-1和SHA-2使用了相同的Merkle-Damgard引擎，这意味着对SHA-1的成功攻击行为会影响到SHA-2的安全，即使还没有宣布一个全轮回的SHA-2被成功攻破，但毫无疑问，攻击机制正被私下的研发。这也是NIST赞助SHA-3竞赛的一个原因，NIST感觉需要一个与之前算法不同的哈希算法。



NIST设置的筛选SHA-3的标准为：



l 候选散列函数必须好实现。它应该消耗最少的资源即使散列大量的消息文本。许多候选算法实际上无法达到这个要求。

l 候选算法在安全性方面必须是保守的。它应该抵御已知的攻击，同时保持一个大的安全系数。它应该同SHA-2相同的四个散列大小(224bit、256bit、384bit或512bit)，但如果需要能够支持更长的散列位宽。

l 候选算法必须接受密码分析。源代码和分析结果公开为感兴趣的第三方审查和评论。在分析过程中发现的任何缺陷都需要解决，通过调整或通过重新设计。

l 候选算法必须使代码多样性。它不能使用Merkle-Damgard引擎产生消息散列。



2012年10月2日，Keccak哈希算法被选为NIST散列函数竞赛的胜利者。Keccak算法（读作为“ket-chak”）是Guido Bertoni, Joan Daemen, Michael Peters, and Giles Van Assche的工作，在2008年10月被提交作为SHA-3的一个候选算法。



Keccak采用了创新的的“海绵引擎”散列消息文本，它抗碰撞性好、快速、设计简单、方便硬件实现。Keccak已可以抵御最少复杂度为2的n次方的攻击，其中N为散列的大小（比特位数），具有广泛的安全界限。至目前为止，第三方密码分析已经显示出Keccak没有严重的弱点。尽管如此，Keccak的创建者已经启动Crunchy加密比赛，挑战人们去发现和报告成功且可验证的对Keccak的攻击方法。



2015年， NIST 批准了SHA-3的标准草案，Keccak哈希算法正式成为SHA-3标准。根据wikipedia，SHA家族函数的比较情况如下：



图1. SHA家族函数对比(资料来自wikipedia.org)



3.2. 比特币的PoW



比特币的PoW共识机制也常被称为Nakamoto 共识或中本聪共识，以比特币的发明者中本聪Satoshi Nakamoto命名。



比特币用区块头部的其中6个字段作为工作量证明的输入字符串。参与PoW计算的6个字段总大小为80字节，由4字节的版本号、32字节的上一个区块的散列值、32字节的Merkle Root Hash、4字节的时间戳（当前时间）、4字节的当前难度值、4字节的随机数组成，如下表所示：



表1. 参与哈希计算的区块头



比特币的PoW，就是要求挖矿节点找到一个合适的 nonce, 即令nonce从0开始递增，直到使得这区块头部经过2次SHA-256计算（即SHA256(SHA256(BlockHeader))）的哈希值小于当前区块的目标阈值。比特币的nonce是一个4字节的无符号整数，若尝试完所有的4字节无符号整数还是没找到符合要求的值，则可以修改time，或修改coinbase交易以改变mrkl_root，然后再重新寻找满足条件的nonce值。



由于SHA-256的哈希值是256-bit的，因此目标阈值(target threshold)也是一个256-bit（32字节）的无符号整型，要求区块头的哈希值必须小于等于此值。



比特币的难度值是动态调整的。每出2016个区块就调整一次难度值，如果区块产生的速率比10分钟快则增加难度，比10分钟慢则降低难度。调整公式如下：



难度值 = 旧难度值 * ( 过去2016个区块花费时长 / 20160 分钟 )

而使用这个难度值来计算目标阈值的计算公式为：

目标阈值 = 最大目标值 / 难度值

其中最大目标值为一个恒定值：

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF



根据上述公式可知，目标值的大小与难度值成反比。难度值越大，则目标值越小，即符合要求的哈希值的前缀0的数量越多，导致查找随机数(nonce)的计算时间就越长。



比特币将这个32字节长度的目标阈值通过类似科学计数法的方法将其压缩为4字节的表示，结果即为区块头部的bits字段。比特币规定，bits编码由两个部分组成：bits值的最高位的1个字节为幂（exponent），接下来3个字节为系数(coefficient)，这样，计算目标阈值的公式为：

Target = coefficient * 256^(exponent – 3）



3.3. 区块头实例解析



下面以比特币的实际区块为例说明区块头部组成和目标阈值的计算方法。我们可以在 https://www.blockchain.com/explorer，查看区块数据，例如区块高度为552020的页面显示如下：



图2. 552020的区块头



在这个页面可以看到区块头的全部字段，例如区块生成时间是“2018-11-30 09:14:39”；区块的bits值为388648495；nonce值为2211011375；区块的hash值为：0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e。通过 https://blockchain.info/rawblock接口可查看包含所有交易数据在内的区块的全部内容：https://blockchain.info/rawblock/0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e



其中区块头如下：





接下来我们可以算下这个区块的目标阈值。从上图可以看到，这个区块的bits值为388648495，先将其转换成16进制表示为：0x172A4E2F，如前所述，这个值包含两个部分，最高位的1个字节为幂：exponent = 0x17



接下来3个字节为系数：coefficient = 0x2A4E2F



代入目标阈值的计算公式：

Target = coefficient * 256^(exponent – 3)= 0x2A4E2F * 256^(0x17– 3)= 0x2A4E2F0000000000000000000000000000000000000000



由于目标阈值是32字节的，这个值为23个字节，只要在高位补9个字节的0，即为目标阈值：0x0000000000000000002A4E2F0000000000000000000000000000000000000000



也就是说，552020这个区块的哈希值要小于等于这个目标值。区块的实际哈希值0x0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e，是满足条件的。而使哈希值满足条件而找到的nonce值为2211011375。



3.4. 交易确认



比特币系统在挖矿的过程中每10分钟生成一个区块，所有节点可以利用这10分钟的时间，来完成接收，打包，见证的工作，同时将产生的交易在整个网络里进行广播。PoW要面对的一个问题是区块分叉，为此比特币规定每个交易需要至少有5个验证过的区块在其后面得到验证才能算作确认，也就是说比特币的共识机制认为等待6个确认的情况下，分叉切换的概率就足够低了(例如按一个节点1%的算力来计算，6个区块后被长度被赶超的概率是100的6次方分之1)，因此，比特币的交易确认时间在1小时以上。



4. 以太坊的PoW共识机制



4.1. Ethash算法



以太坊设计了ethash作为工作量证明算法，包括找到算法的随机数输入以使结果低于特定的难度阈值。它的特点是计算的效率不仅与CPU相关，还与内存大小和内存带宽相关。该算法的一般流程如下：

1) 首先根据块信息计算一个种子。

2) 使用这个种子，计算出一个16MB的cache数据。

3) 通过cache，计算出一个1GB(初始大小)的数据集(DAG)。DAG可以理解为是一个完整的搜索空间，全客户端和矿工需要存储完整的DAG，挖矿过程中需要从DAG中重复的随机抽取数据拿去和其他数据计算哈希值（类似于比特币挖矿中查找合适Nonce）。

4) DAG中每个元素的生成只依赖于cache中的少量数据，验证者可以从Cache快速计算DAG指定位置的元素，以执行哈希验证。

5) 每3000个区块的DAG完全不同，并且它的大小也随时间线性增长，从1G开始，每年大约增长7G左右。

6) 由于仅根据cache就可以使用少量内存快速的计算出DAG中指定位置的数据，所以轻客户端只需要存储cache就可以高效的进行校验。



参与哈希计算的区块头内容，以太坊和比特币之间最主要的的区别是，以太坊区块不仅包含交易列表也包含最近状态（merkle patricia trie结构的根hash编码在状态中更精确）。除此之外，另外两个值，区块数和难度，也储存在区块中。



借助DAG结构，Ethash工作量证明是内存难解的，也就是需要大量的内存用于存储数据，并且计算过程需要频繁访问内存，占用大量的内存带宽，这使它能抵抗类似比特币那样的ASIC矿机 ，以支持矿工可以用电脑的CPU挖矿。但自从GPU矿工的效率高出两个数量级，CPU挖矿就不再盈利了。



4.2. 交易确认



与比特币类似，以太坊的交易同样需要等待6区块以确认交易。以太坊的难度调整的方式是每15秒整个网络会产生一个区块，这个"心跳"基本上主要强调系统状态同步，保证不可能维持一个分叉（允许double spend）或被恶意分子重写历史，除非攻击者有半数以上的网络挖矿能力（即所谓的 51% 攻击）。



5. 小结



目前业界普遍认为PoW是最适合公链的共识机制，优点是开放，任何人都可以参与进来；不需要任何权威机构的介入也能保证安全。



然而其缺点也同样明显，例如速度慢、能耗巨大、导致集中化的矿池等。而且从长远来看，随着技术的发展，依靠算力的机制也终会被算力打败，PoW共识机制将变得不再安全，例如，有人可能会制造一台量子计算机，算力可能比其他人快百亿倍，能够在一秒钟内破坏比特币或以太坊区块链。因此，人们也有充足的理由和动力去研发其它的共识机制。