2.2　常见共识算法

在前述诸多原理的指引下，人们对分布式系统中的一致性算法（即共识算法）进行了很多探索。比较常见的算法有PBFT、Paxos、Raft、PoW、PoS和DPoS等。这些算法的应用场景有所区别。PBFT、Paxos和Raft等算法侧重于强一致性，它们在包含节点准入和控制的私有链或联盟链系统中比较常用。PoW、PoS和DPoS等算法侧重于可用性，在公有链系统中比较常用。下面对以上算法进行逐一介绍。

2.2.1　PBFT算法

1999年Miguel Castro等学者提出了PBFT（Practical Byzantine Fault Tolerance）算法，该算法的主要过程如图2-3所示。

算法中将节点划分为两类：主节点和其他节点。每一次请求要经历五个步骤：发起（Request）、预准备（Pre-prepare）、准备（Prepare）、确认（Commit）和响应（Reply）。对这些步骤简述如下。

首先，从全网节点选举出一个主节点（Leader），新区块由主节点负责生成。主节点的选择方法是类轮询的方式。假设Node0是主节点，当客户端向它发起请求后，就从发起阶段进入了预准备阶段。

在预准备阶段，主节点把该请求广播到所有节点。为了确保请求的时间顺序不错乱，主节点会给当前的请求分配一个编号p。所有节点收到这个请求信息后，都会各自对该消息进行校验，当确认时序正确、校验信息无误后，该节点会进入下一阶段。

在准备阶段，每个节点将收到的请求信息存入消息队列，在请求信息中嵌入其自身编号i，并继续向所有其他节点广播处理后的请求信息（即Prepare消息），完成后进入下一阶段。

在确认阶段，如果某个节点收到了来自其他2f个节点（f代表PBFT最大容错节点数量，算法中假设f不大于总节点数的1/3）的Prepare消息，并确认这些消息和自己之前收到的一致，就可以执行Commit操作，即向所有其他节点发送一条Commit确认消息，这条消息中包含消息编号n和节点编号i。

最后是响应阶段。在该阶段中，如果一个节点收到来自2f+1个不同节点的Commit消息，则确认成功，并向最初发起请求的客户端发送响应信息。请求的发起者会等待，直到收到f+1个响应，才接受这个结论。至此，整个算法流程结束。

简而言之，PBFT算法通过两种手段实现拜占庭容错：以类似轮询的方式选择主节点；每一次请求都要在主节点和其他节点之间互相验证，只有足够多的节点确认后才达成共识。PBFT比经典拜占庭协议的复杂度低，应用性更强。

2.2.2　Raft算法

在了解Raft算法前，先简述Paxos算法。Paxos算法最早于1989年提出，在20世纪八九十年代被广泛讨论。该算法强调一致性，将节点分为Client、Voters、Proposer、Learner和Leader等多种角色，对应于不同的职责权限。从步骤上来说，算法包含Prepare、Promise、Accept和Accepted等多个步骤。通过这些角色和步骤的定义，在节点中反复确认并达成一致性决策。经过理论证明，Paxos是可以满足一致性和分区容错的。谷歌公司曾在分布式数据库Chubby系统中应用Paxos算法，微软公司在搜索引擎Bing的并行计算系统中也尝试运用了Paxos算法。Paxos被诟病的原因是其逻辑过于复杂，难于理解，因此在教学和工程实践中，人们运用Paxos算法的困难较大。

Raft（Reliable、Replicated、Redundant和Fault-Tolerant）是Paxos的一种简化变种，同样追求的是分布式系统中的强一致性。假设节点的总数为n，Raft的最大容错节点数量为(n-1)/2。Raft算法主要分为两个基本步骤：Leader的选举以及Log同步。算法将节点分为两类：Leader和Follower。Raft算法中将时间划分为若干个分块（term），在每一个term中Leader不变，分块结束后，发起新的Leader选举。该算法也定义了一些机制以允许Follower在一些情况下发起Leader选举，例如长时间未收到任何请求时。

在每个term中，所有节点在唯一Leader的管理下执行Log同步的过程。当Leader收到来自客户端的新请求时，便将该新请求指令增补到日志中，并向所有节点发送日志刷新消息。日志中的指令按时间顺序排列编号，Log序列中每一个输入都包含其所对应的term编号以及指令本身。Follower收到日志刷新消息后，会向Leader发回响应信息。基于这些响应信息，Leader可以判定某个新的指令是否获得了超过半数的节点响应，如果是，则这条指令被认为成功地同步了。Leader会执行成功同步过的指令，并将执行结果返回到最初发起请求的客户端。由于Leader会持续刷新最新的Log同步信息，其中包含最新成功同步的指令序号，各个Follower可以将其和自己所存的Log序列进行比对，以判断自己是否曾错过了之前的消息指令，从而确保系统中的一致性。

2.2.3　PoW算法

PoW（Proof-of-Work）算法最早于20世纪90年代被提出，它的基本思路是，用“工作量证明”的方式来避免类似于DoS的攻击。其基本原理是用高“工作量”提高作恶的成本，从而达到规避恶意节点破坏的目的。PoW算法的一般过程如图2-4所示。首先客户端要进行复杂运算完成“解题”，然后把计算结果连同指令请求一起发送给服务器，在服务器端对计算结果进行验证，如果验证通过，则服务器接受指令请求，否则拒绝。为了便于实现，这类算法都有一个显著特点：“工作量证明”的计算过程很复杂，但是校验过程非常简单快速。例如，我们假设要求是“对信息序列增补随机数后再进行哈希函数运算，其输出结果以特定字符串开头”。该题目的结果是很容易检验的，只需要用序列计算哈希，验证是否以特定字符串开头即可。但是从函数的输入端来说，需要大量地尝试可能的随机数序列，才能得到满足题目要求的结果，这意味着很大的工作量。

PoW共识机制的一个例子是HashCash系统，该系统可以用来防止互联网上的恶意DoS和垃圾信息攻击。简言之，HashCash要求在电子邮件的消息头中增加一个哈希戳（HashCash stamp）。PoW算法的另一个典型应用是比特币区块链系统。在比特币区块链系统中，得出“工作量证明”的过程通常被称为“挖矿”，后续章节将会详细介绍这一过程。

2.2.4　PoS算法

PoS（Proof-of-Stake）的特点是将所持有“权益”作为选择下一个区块记账节点的标准。在加密数字货币系统中，权益一般对应的就是数字货币本身。PoS机制最早在2012年运用于Peercoin系统，后来该机制的各种演化版本也应用于BlackCoin、Nxt和以太坊等区块链系统中。形象地说，哪个节点拥有的数字货币更多或持有时间更长，就提高它的优先级，让它能更容易地成为记账节点。

在不同的系统中，PoS的具体形式可能不一样。例如，前面提到的Peercoin系统基本是在比特币区块链的PoW基础上做了改变，在每个节点求解复杂数据运算时引入不同的权值（有关比特币区块链的具体原理，可参见后续章节），使得特定节点的计算复杂度与它持有的虚拟货币数量和时间成反比。以太坊中的Casper共识机制也基于PoS原理。和前文中的PoW相比，PoS计算量较小。但也有观点认为，PoS算法中节点的作恶成本过低，不能够像PoW那样完全基于计算复杂度这种更绝对的指标来执行共识决策。在以太坊区块链系统中采用的PoS引入了“保证金”的概念。首先，所有验证者节点要锁定其拥有的一部分以太坊虚拟货币作为保证金，付出保证金后才有资格做新区块验证和投票。然后，验证者节点都可以验证节点，当发现新区块并验证其合法后，可以投票。如果所投票的区块被选中添加到区块链，验证者可以获得和投票成比例的奖励。该机制也规定，如果验证者向错误的分支投票，保证金将会被罚没。

在PoS的基础上，又进一步演化出了DPoS算法。其基本思路是，从所有网络节点中预先选择固定数量的节点来构成区块链验证者节点子集，仅在这个子集中选择验证节点对新区块进行验证。本质上，DPoS进一步向CAP原理描述的“可用性”进行了倾斜。DPoS还有助于缓解PoW和PoS中固有的“算力”或“财力”过于集中而导致权力集中的问题。