基于区块链的共识算法（一）——权威解析PoW

悄悄地告诉你，文章末尾有惊喜！

自2008年以来，比特币被认为是所有密码货币（cryptocurrency）中最为流行的密码货币。最为吸引人的地方是共识机制（也称Nakamoto共识），它能使P2P网络中的所有节点对一个分布式的公共账本（区块链）达成共识。

当前已存在的共识算法分为两大类型。第一种类型是基于证明（proof-based）的共识算法，它要求加入网络中的节点去证明自己比其他节点更有资格添加一个区块到链上。第二种类型是基于投票（voting-based）的共识，它要求网络中的节点交换当前新区块或者交易的验证结果，然后做出最终的决定。

在Back最初提出的工作量证明（Poorf of Work，PoW）概念后，第一种基于证明的变种共识算法是由Nakamoto提出的工作量证明算法。在这种共识算法中，节点只有通过硬件设备(如，CPU)做大量的计算才有机会将区块添加到区块链上。也就是说，在整个P2P网络中，为了对某个时间段内的数据达成一致性共识，如果哪个节点最先解决这个PoW谜题，那么这个网络中的所有节点就对这个节点提交的数据达成共识。然而，由于PoW共识算法造成能源浪费等缺点，研究者们提出了许多改进的共识算法。权益证明（Proof of Stake，PoS）共识算法就是其中一种。权益证明运用了每个节点的权益（如，代币）并通过一个幸运因子来选择哪个矿工有权利添加区块到链上，这样就降低了挖矿过程中能源的消耗。当前基于PoW和PoS的共识算法是研究和应用中最常用的算法。

基于PoW的共识算法

在区块链网络中，如果每一个节点都广播包含着许多已验证交易的区块，那么势必增加网络负载。比如，一笔合法交易，这笔交易需要网络中的节点验证，这些节点将会把这笔交易打包进自己构造的区块中并且广播给网络中的其他节点。如果广播操作不受限制，那么该笔交易很有可能被不同的节点打包进区块，并出现在不同的区块中。这样网络中记账的账本就变得没有意义了。即，造成了双重花费。为了让网络中的所有节点对最新产生的区块达成共识，PoW要求网络中的所有节点去解决一个难度可调的谜题（puzzle），目的就是获得一次在该时间段（epoch）将自己构造的打包区块添加到当前区块链上。在这个时间段最先解决这个谜题的节点将获得这个权利并得到报酬。

PoW共识算法就是在解决一个不等式问题。通过不断的尝试一个随机数nonce，使得不等式左边的值小于不等式右边的难度值。如，PoW(s,nonce)

在比特币网络中，运行PoW共识算法的节点称为矿工。找随机数nonce的过程称为挖矿。矿工们通过运行PoW算法相互竞争解决每一个时间段中的PoW谜题。如果一个矿工解决了该谜题，表示这个矿工找到了一个有效的随机数nonce使得不等式成立。也就是说，该矿工挖到一个区块。

然而，挖矿是有竞争的。在某个时间段中，可能存在多个矿工同时挖到一个包含有效随机数nonce的区块。这个时候，这些矿工将自己挖到的区块广播到网络中。在比特币的协议中，节点收到一个有效区块后，将会忽略后到的区块。这样就会导致分叉问题：网络中出现两条不同且长度一样的区块链。Nakamoto表示，矿工将会在各自的分叉链上挖矿，直到其中一条链的长度超过另外一条链的长度。此时，网络中所有的矿工都将选择在最长链上继续挖矿。

区块链分叉及解决示意图

基于PoW算法上的变种算法

不幸的是，很多其他研究成果表明了PoW算法存在很多缺陷。比如能量浪费和安全问题。因此，很多研究者针对这些缺陷提出了许多其他的共识算法。

最初Nakamoto设计的PoW算法是通过普通计算机来挖矿的。也就是说，通过普通计算机的硬件来解决PoW谜题的。随着比特币的流行及经济因素，大量的矿工通过硬件的升级来扩大自己挖到区块的概率。从一开始使用CPUs挖矿到GPUs、FPGAs(field-programmable gate array)，最后到ASICs(application-apecific integrated circuit)。写作到此，比特币网络中的每秒哈希算力达到了45，709，343，00TH/S。Philip Daian表示，这些巨大的算力除了用于保护比特币网络安全外，并没有对社会产生其他作用。因此，造成了极大的资源浪费。

在以太坊中，为了抵制ASIC矿池，使用了一种称为Ethash的共识算法。Ethash是以太坊1.0的PoW算法，是由Buterin和Dryja推出的Dagger-Hashimoto最新版本。Ethash算法的设计使得挖矿过程更多的依赖于内存和带宽，以此来弱化具有大算力矿工的优势。Ethash算法每猜测一次随机数，都需要循环的从内存中的DAG随机地抽取一段数据用于计算。因此，挖矿依赖于内存和带宽。

2015年John Tromp引入了另外一个PoW算法，主要思想就是将挖矿依赖于算力转移到挖矿依赖于内存。值得注意的是，如上的Ethash算法也是依赖于内存的。这个算法采用了Cuckoo哈希函数来代替PoW算法。Cuckoo哈希函数允许矿工付出更少的努力，且赋予矿工更容易挖到区块的权利。

为了将网络中的算力利用起来，King提出了一种思想：利用网络中的算力来寻找最长的素数链。谁找的素数链最长，谁就挖矿成功。要想挖到一个区块，或者说要想找到一条长而有效的素数链，必须要满足一些要求。第一个要求就是素数链的长度必须大于给定值（难度值）。第二个要求就是素数链必须是Cunningham链的形式。找Cunningham链的PoW算法除了将算力用于挖矿之中，还产生了一些有助于数学研究的素数。因此，将挖矿使用的算力利用起来了。

双重花费攻击问题

许多研究提出，PoW的缺点之一就是一个双重花费攻击问题。简而言之，攻击者试图通过分叉并在其中一条分叉链上发起一笔交易（Tx2），以达到撤销一笔刚刚上链（另外一条分叉链）的交易（Tx1）。接着，攻击者将会努力使得有交易Tx2的分叉链长度超过另外一条分叉链的长度（即，交易Tx1无效）。为了达到这样的目的，攻击者需要拥有全网51%的算力。因此，双重花费攻击也被称为51%攻击。对于单个用户来说，拥有全网51%的算力是件极其困难的事情。

双重花费攻击

然而，随着所谓的矿池出现，攻击者们容易发起51%攻击。在矿池挖矿的过程中，不是单个矿工试图猜测一个谜题的随机数nonce，而是所有的矿工聚集在一起，对谜题进行拆分，每一个矿工完成其中一小部分任务。因此，解决一个谜题的工作变得容易。当矿池挖到一个区块时，每个矿工都将获得一定比例（相同或者根据矿工完成的任务难易比例）的奖励。因此，在规模经济的影响下，大量的矿工不断地加入矿池。

为了阻止大型矿池的产生，Miller等人提出一种新的机制：将PoW谜题设计成不可外包的谜题（non-outsourceable puzzles）。在不可外包谜题的设计中，使用了谜题外包者的私钥。大致工作原理就是每尝试解决一次谜题（每猜测一次随机数），都需要外包者对区块信息签名一次。如果外包者想加快解决谜题的速度，则会把谜题外包给其他矿工一起合作挖矿。同时，为了帮助外包者挖矿，其他矿工在每尝试解决一次谜题时，都需要外包者的私钥对消息进行签名。因此，外包者必然将自己的私钥告诉他们。一旦外包者将自己的私钥告诉跟他有合作的矿工，那么区块奖励除了外包者自己能获得以外，其他任何跟他有合作的矿工（都有外包者的私钥）都能轻松获取整个区块的报酬。对于外包者来说，并不愿意其他矿工能够获得该区块所有的报酬。因此这种不可外包的谜题能够有效的阻止矿工们合作起来，形成大型矿池进行挖矿。

其他问题

PoW算法除了安全性问题以外，Eyal等人提出了另外一个问题：应用PoW算法的支付系统不适合做实时支付。这里先考虑一个例子。当Alice下班去商店购买一杯咖啡且出块时间在10分钟左右，Alice需要等待大约十分钟时间才能被允许离开商店。这是因为店主需要十分钟时间确认刚刚产生的这笔交易是否上链了。因此，减少交易延时的需求是必要的。在这之前，已经有两种可能解决方法。第一种就是增加区块的大小；第二种就是减小谜题的难度。由于前者增加了区块在网络里传播的时间（因为区块数据增多，在网络中传播的速度变慢），后者缩短了区块生成的时间（难度值变小，使得矿工容易挖到区块），使得网络中容易出现区块链分叉和双重花费的攻击。Eyal等人提出了一种新的共识模式，称为Bitcoin-NG。Bitcoin-NG将传统的区块数据结构分成了两种类型，分别是主区块（key block）和小区块（micro block）。当一个矿工在一个时间段内最先找到一个谜题的有效随机数Nonce后，他将广播主区块给网络中的其他矿工，直到另外一个矿工找到另外一个随机数Nonce。随后，这个矿工广播包含了一些交易信息的小区块（所对应的主区块）到网络中。然而，矿工利用主区块的信息能够快速的验证小区块中的交易。因此加快了确认交易的时间。

Sompolinsky和Zolar提出了一种策略，用来减少区块产生的时间。这种策略能够处理分叉和阻止双重花费攻击的问题。这种策略称为GHOST策略，它能维持那些没有被选作为主链上的区块状态。

GHOST策略并不是将最长链作为主链，而是将对主链贡献最多的区块所形成的链作为主链，即该主链上的区块最多。

GHOST策略中的主链

Liu等人基于PoW上，提出了一种一般化的工作量证明共识。该机制中的难度比最初的PoW挖矿算法难度要低一些，这样能够使得网络中的节点运用自己的算力可能找到许多有效的随机数Nonce。在这种共识下，将一个区块添加到区块链上不是由单独一个矿工来完成，而是由矿工中一些幸运的委员会来完成。大致工作原理如下：在每一轮中（一个时间段），每一个矿工必须为他们创建的区块找到有效的随机数Nonce。矿工找到随机数之后，将包含该有效随机数的区块广播给委员会（是一些幸运的矿工，主要负责验证接收到的区块）。然后，委员会将这些有效区块（通过验证的区块）放在一个临时的数组里（注意每一个区块都有一索引号）。到了该轮的最后环节时，随机的选择一个随机数。这个随机数如果就是某个区块的索引号，那么该区块被添加到区块链上，并且该区块的主人成为一名新的委员会成员。在该轮后，委员会中的成员会被轮换，这是为了保证成员数量不会过大以及成员及时更新。在每一轮中，区块的报酬将均等的分给委员会中的所有成员。

PoW被认为挖矿不公平：一些拥有现代化且先进设备的矿工非常容易找到有效随机数，而拥有相对低级设备的矿工找到一个有效随机数非常难。

PoS的提出就是用于解决这个不公平。

（文章来源：科银研究院）

关注公众号，回复“1”，惊喜红包等你拿！