《迅雷链精品课程》第12课：PoW共识算法
上节课我们学习了几种常用的共识算法。 今天我们就来详细分析一下PoW（Proof-of-Work）共识算法，了解它的来源和优缺点。
学习课程时，还可以获得为期一个月的BaaS平台试用机会，免费使用高性能区块链服务（点击链接免费领取）。 课程学习结合实操，让你快速成为区块链高手！
*以下是第12课的内容~
第十二课 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”一词是Markus Jakobsson和Ari于1999年在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-哈希现金：
1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi
服务器可以通过检查其 SHA-1 哈希来验证戳记，如下所示：
00000b7c65ac70650eb8d4f034e86d7d5cd1852f
可以看出，哈希结果有5个前缀字符为0，每个字符占4位，所以哈希值的前20位为0，即以0为前缀的位数为20。
Hashcash的头部格式为：1:bitsresource:ext:salt:suffix，包括7个字段：
版本号。
以 0 为前缀的位数。如果它的哈希值少于这个 0 前缀的数目，则它是非法的。
戳记的生成日期。 当前时间之后的邮票以及很久以前的邮票都可以被视为非法。
为其生成戳记的资源。 它可以是电子邮件地址，但也可以是 URI 或其他命名资源。
特定应用程序可能需要的扩展名，通常为空。
随机因素（盐）。 用于区分此戳记与其他在同一日期为同一资源人工生成的戳记。
后缀字符串。 是算法真正起作用的部分。 由于在任何给定时间，A 向 B 发送了一封电子邮件，前 6 个字段已经固定，并且为了生成一个带有所需数量的前导零的散列戳，客户端必须尝试许多连续的后缀值。
通过让邮件客户端进行这样的计算，可以有效地防止垃圾邮件的泛滥。 只需几秒钟即可生成一个带有 20 位 0 前缀哈希的字符串，当您每天只发送几十封电子邮件时，付出的代价并不大。 然而，对于想要发送数百万条消息的垃圾邮件发送者来说，这是一笔无法承受的费用。
在比特币之前，Hal Finney 还以 Reusable Proof of Work (RPOW) 的形式在前比特币加密货币实验中使用了 Hashcash 的 PoW 算法。 此外，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 尚未been announced -2被成功攻破，但毫无疑问，攻击机制正在私下开发。 这就是 NIST 赞助 SHA-3 竞赛的原因之一，并且 NIST 认为需要一种不同于以前的哈希算法。
NIST 设定的筛选 SHA-3 的标准是：
l 候选哈希函数必须易于实现。 即使在散列大消息文本时，它也应该消耗最少的资源。 许多候选算法实际上不能满足这个要求。
l 候选算法在安全性方面必须是保守的。 它应该抵抗已知的攻击，同时保持较大的安全边际。 它应具有与 SHA-2 相同的四种哈希大小（224 位、256 位、384 位或 512 位），但如果需要可以支持更长的哈希位宽。
l 候选算法必须经过密码分析。 公开源代码和分析结果以供感兴趣的第三方审查和评论。 在分析过程中发现的任何缺陷都需要通过调整或重新设计来解决。
l 候选算法必须使代码多样化。 它不能使用 Merkle-Damgard 引擎来生成消息哈希。
2012 年 10 月 2 日，Keccak 哈希算法被选为 NIST 哈希函数竞赛的获胜者。 Keccak 算法（发音为“ket-chak”）是 Guido Bertoni、Joan Daemen、Michael Peters 和 Giles Van Assche 的工作，并于 2008 年 10 月作为 SHA-3 的候选算法提交。
Keccak采用创新的“海绵引擎”对消息文本进行哈希处理，具有抗碰撞性好、速度快、设计简单、硬件实现方便等特点。 Keccak 已经能够抵抗最小复杂度为 2 的 n 次方的攻击，其中 N 是散列的大小（位数），并且具有广泛的安全限制。 到目前为止，第三方密码分析表明 Keccak 没有严重的弱点。 尽管如此，Keccak 的创建者发起了 Crunchy Crypto Competition，挑战人们发现并报告对 Keccak 的成功且可验证的攻击。
2015年，NIST通过了SHA-3标准草案，Keccak哈希算法正式成为SHA-3标准。 根据维基百科，SHA族函数的比较如下：
图 1. SHA 族函数比较（数据来自 wikipedia.org）
3.2. 比特币的PoW
比特币的PoW共识机制也常被称为Nakamoto consensus或Nakamoto consensus，以比特币的发明者中本聪命名。
比特币使用区块头中的 6 个字段作为工作量证明的输入字符串。 参与 PoW 计算的 6 个字段总大小为 80 字节，由 4 字节的版本号、32 字节的上一个区块哈希值、32 字节的 Merkle Root Hash 和 4 字节的时间戳组成（当前时间）、4字节当前难度值、4字节随机数，如下表所示：
表 1. 哈希计算涉及的区块头
比特币的PoW是要求挖矿节点找到合适的nonce，即nonce从0开始递增，直到区块头的hash通过SHA-256计算两次（即SHA256(SHA256(BlockHeader))） ) 该值小于当前块的目标阈值。 比特币的 nonce 是一个 4 字节的无符号整数。 如果尝试了所有4字节无符号整数，还是找不到满足要求的值，可以修改时间，或者修改coinbase事务，更改mrkl_root，然后重新搜索满足条件的nonce值.
由于SHA-256的哈希值为256位，目标阈值（target threshold）也是一个256位（32字节）的无符号整数，区块头的哈希值必须小于等于这个值.
比特币的难度值是动态调整的。 难度值每 2016 个区块调整一次。 如果出块速度快于 10 分钟，则增加难度，如果慢于 10 分钟比特币采用的共识机制是什么，则降低难度。 调整公式如下：
难度值=旧难度值*（过去2016个区块花费的时间/20160分钟）
使用该难度值计算目标阈值的计算公式为：
目标门槛=最大目标值/难度值
其中最大目标值是一个常数值：
0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
根据上面的公式可以看出，目标值的大小与难度值成反比。 难度值越大，目标值越小，即满足要求的哈希值的前缀0个数越多，找到nonce的计算时间就越长。
比特币通过类似科学计数法的方法将32字节的目标阈值压缩成4字节的表示，结果就是区块头中的bits字段。 比特币规定bits编码由两部分组成：bits值的最高字节是指数，接下来的3个字节是系数。 这样，目标阈值的计算公式为：
目标 = 系数 * 256^(指数 - 3)
3.3. 区块头实例分析
下面以比特币的实际区块为例，说明区块头组成和目标阈值的计算方法。 我们可以查看 中的区块数据，例如区块高度为552020的页面显示如下：
图 2. 552020 的区块头
在此页面上，您可以看到区块头的所有字段。 例如区块生成时间为“2018-11-30 09:14:39”； 该块的位值为388648495； nonce 值为 2211011375； 该块的哈希值为：0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e。 可以通过界面查看包括所有交易数据在内的区块的全部内容：
区块头如下：
接下来我们可以计算这个块的目标阈值。 从上图可以看出，这个block的bits值是388648495，先把它转化成16进制表示：0x172A4E2F，前面说了这个值包含两部分，最高字节是幂：exponent = 0x17
接下来的 3 个字节是系数：系数 = 0x2A4E2F
代入目标阈值的计算公式：
目标 = 系数 * 256^(指数 – 3)= 0x2A4E2F * 256^(0x17– 3)= 0x2A4E2F00000000000000000000000000000000000000000
由于目标阈值是32字节，所以这个值为23字节，只要在高位加上9字节的0，就是目标阈值：0x0000000000000000002A4E2F0000000000000000000000000000000000000000
换句话说，块552020的哈希值应该小于或等于目标值。 该区块的实际哈希值为0x0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e，满足条件。 并且找到使哈希满足条件的nonce值是2211011375。
3.4. 交易确认
比特币系统在挖矿过程中每 10 分钟产生一个区块，所有节点都可以利用这 10 分钟完成接收、打包和见证的工作，同时将产生的交易广播到全网。 PoW 不得不面对的问题之一就是区块分叉。 为此，比特币规定每笔交易至少需要经过5个验证区块的验证后才能算作确认。 也就是说，比特币的共识机制认为，在等待6次确认的情况下，分叉切换的概率足够低（例如比特币采用的共识机制是什么，基于节点1%的算力，被反超的概率6 个区块后的长度是 100 的 1/6 1)，因此比特币交易确认时间超过 1 小时。
4. 以太坊的 PoW 共识机制 4.1. Ethash算法
以太坊将 ethash 设计为工作量证明算法，其中涉及找到算法的随机数输入，使得结果低于某个难度阈值。 其特点是计算效率不仅与CPU有关，还与内存大小和内存带宽有关。 算法的大致流程如下：
首先根据块信息计算种子。
使用这个种子，计算出一个 16MB 的缓存数据。
通过缓存，计算出一个1GB（初始大小）的数据集（DAG）。 DAG可以理解为一个完备的搜索空间。 所有客户和矿工都需要存储完整的 DAG。 在挖矿过程中，需要反复从DAG中随机抽取数据，并与其他数据计算哈希值（类似于比特币挖矿，在矿场中寻找合适的Nonce）。
DAG中每个元素的生成只依赖于缓存中的少量数据，验证者可以快速从缓存中计算出DAG指定位置的元素进行哈希验证。
每3000个区块的DAG是完全不同的，其大小也随时间线性增长，从1G开始，每年增长7G左右。
由于基于缓存仅需少量内存即可快速计算出DAG中指定位置的数据，因此轻客户端只需要存储缓存即可高效进行验证。
以太坊和比特币的主要区别在于哈希计算中涉及的区块头内容，以太坊区块不仅包含交易列表，还包含最近的状态（merkle patricia trie结构的根哈希码在州）。 除此之外，另外两个值，块号和难度，也存储在块中。
借助DAG结构，Ethash工作量证明是内存难处理的，即需要大量内存存储数据，计算过程需要频繁访问内存，占用大量内存带宽，使其像比特币矿机一样抵抗ASIC，支持矿工可以使用计算机的CPU进行挖矿。 但由于 GPU 矿工的效率提高了两个数量级，CPU 挖矿不再有利可图。
4.2. 交易确认
与比特币类似，以太坊交易也需要等待6个区块才能确认交易。 以太坊的难度调整方式是全网每15秒产生一个区块。 这个“心跳”基本上是强调系统状态的同步，确保不可能维持分叉（允许双花）或被恶意分子改写。 ，除非攻击者拥有超过一半的网络挖矿算力（即所谓的 51% 攻击）。
5.总结
目前业界普遍认为，PoW是最适合公链的共识机制。 优点是公开，任何人都可以参与； 它不需要任何当局的干预来确保安全。
但它的缺点也很明显，比如速度慢、能耗大、矿池导致中心化等。 而且从长远来看，随着技术的发展，依赖算力的机制最终会被算力打败，PoW共识机制将变得不再安全。 其他的则快数百亿倍，能够在不到一秒的时间内破坏比特币或以太坊区块链。 因此，人们也有充分的理由和动力去发展其他的共识机制。
