高丽芬，胡全贵

（1.中国矿业大学（北京），北京 100000；2.北京国网信通埃森哲信息技术有限公司，北京 100000）

共识机制是区块链技术的核心，那什么是“共识”呢？对于现实世界，共识就是一群人对一件或者多件事情达成一致的看法或者协议。在计算机世界当中，共识包含两个层面，第一个层面是点的层面，即多个节点对某个数据达成一致共识。第二个层面是线的问题，即多个节点对多个数据的顺序达成一致共识。这里的节点可以是任意的计算机设备，比如PC电脑，笔记本，手机，路由器等，这里的数据可以是交易数据、状态数据等。

现阶段的共识算法分类如下图所示：

共识机制来源于著名的“拜占庭将军问题”，拜占庭将军问题是由莱斯利·兰伯特提出的点对点通信的基本问题，主要是用于分析在分布式节点传输信息时如何保持数据的一致。

Pbft算法的提出主要是为了解决拜占庭将军问题。那什么是拜占庭将军问题呢？

拜占庭位于如今的土耳其的伊斯坦布尔，是古代东罗马帝国的首都。拜占庭罗马帝国国土辽阔，为了达到防御目的，每块封底都驻扎着一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。在战争的时候，拜占庭军队内所有将军必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成一致的共识。在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致协议的问题，这就是拜占庭将军问题。

应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传递信息等问题，即消息传递的信道绝无问题。

如果信道不能保证可靠，那么拜占庭问题无解。关于信道可靠问题，会引出两军问题。

如上图所示，白军驻扎在沟渠里，蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大，但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通，只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议，这就是两军问题。看到这里你可能发现两军问题和拜占庭将军问题有一定的相似性，但是我们必须注意到是，通信兵得经过敌人的沟渠，在这个过程中他可能被捕，也就是说，两军问题中信道是不可靠的，并且其中没有叛徒之说，这就是两军问题和拜占庭将军问题的根本性不同。

拜占庭将军问题最早是由 Leslie Lamport 与另外两人在 1982年发表的论文《The Byzantine Generals Problem 》提出的，他证明了在将军总数大于3f，背叛者为f或者更少时，忠诚的将军可以达成命令上的一致，即 3f+1＜=n。算法复杂度为 o（n^（f+1））。而 Miguel Castro（卡斯特罗）和 Barbara Liskov（利斯科夫）在1999年发表的论文《 Practical Byzantine Fault Tolerance 》中首次提出pbft算法，该算法容错数量也满足3f+1＜=n，算法复杂度为o（n^2）。

对于 pbft 算法，因为 pbft 算法的除了需要支持容错故障节点之外，还需要支持容错作恶节点。假设集群节点数为n，有问题的节点为f。有问题的节点中，可以既是故障节点，也可以是作恶节点，或者只是故障节点或者只是作恶节点。那么会产生以下两种情况：

第一种情况，f个有问题节点既是故障节点，又是作恶节点，那么根据少数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即 f+1 个节点，正确节点的数量就会比故障节点数量多，那么集群就能达成共识。也就是说这种情况支持的最大容错节点数量是（n-1）/2。

第二种情况，故障节点和作恶节点都是不同的节点。那么就会有 f 个故障节点和 f 个作恶节点，当发现节点是故障节点后，会被集群排除在外，剩下 f 个作恶节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即f+1 个节点，正确节点的数量就会比作恶节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是 f+1 个正确节点，f个故障节点和f个作恶节点，即 3f+1=n，f=（n-1）/3。

举个例子，我是一个愚昧的国王，没有自己的判断力，我不知道应该对敌国进攻还是投降好。我有一些大臣，我希望听从他们的意见做出决定，但是他们现在都离我很远，我只能通过飞鸽传书的方式告知他们目前的问题，得到他们的选择。然而，可能出现大臣叛变，故意提出相反的观点（作恶节点），也可能出现鸽子在传输过程中飞错了，我没有得到该大臣的选择（网络堵塞）。PBFT可以保证如果我有3f+1的大臣的话，即使其中有f个大臣叛变或者没有响应，我依然可以得出共识的正确结果。

这里一个核心问题就是，为什么有f个节点未响应或出错时，为了保证系统的正常，需要总共有3f+1个节点进行投票。

同样用国王的例子，假设除了我（国王）一共有n个大臣，我知道其中有f个大臣是叛徒或者未响应，所以我一定要能从n-f个大臣的回应中进行判断。然而由于是飞鸽传书，所以当我陆续收到n-f个传来的消息后，我并不知道之后是否还会有新的消息传来。因为如果f个有问题的大臣都是未响应，那么我将不会收到新的消息，如果其中有大臣是叛徒，我之后还会收到消息，但作为国王的现在不知道是哪种情况，却需要立刻作出进攻还是投降的判断。

最坏的情况下，剩下的f个大臣都是好人，只是鸽子飞得慢我还没收到消息，也就是说我收到消息的n-f的大臣中有f个大臣都是叛徒，即f个叛徒和n-2f个好人。由于多数者胜，所以只有当n-2f＞f的情况下，作为国王的我会做出正确的决定，即n＞3f，n最小需要取3f+1。

pbft 算法的基本流程主要有以下四步：

（1）客户端发送请求给主节点

（2）主节点广播请求给其它节点，节点执行pbft 算法的三阶段共识流程。

（3）节点处理完三阶段流程后，返回消息给客户端。

（4）客户端收到来自 f+1 个节点的相同消息后，代表共识已经正确完成。为什么收到 f+1 个节点的相同消息后就代表共识已经正确完成？

从上面的介绍里可知，无论是最好的情况还是最坏的情况，如果客户端收到 f+1 个节点的相同消息，那么就代表有足够多的正确节点已全部达成共识并处理完毕了。

算法的核心三个阶段分别是 pre-prepare 阶段（预准备阶段），prepare 阶段（准备阶段），commit 阶段（提交阶段）。图中的C代表客户端，0，1，2，3 代表节点的编号，打叉的3代表可能是故障节点或者是问题节点，这里表现的行为就是对其它节点的请求无响应。0 是主节点。

Pre-prepare 阶段：节点收到 pre-prepare 消息后，会有两种选择，一种是接受，一种是不接受。什么时候才不接受主节点发来的 pre-prepare 消息呢？一种典型的情况就是如果一个节点接受到了一条 pre-pre 消息，消息里的 v 和 n 在之前收到里的消息是曾经出现过的，但是 d 和 m 却和之前的消息不一致，或者请求编号不在高低水位之间（高低水位的概念在下面会进行解释），这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的 v 和 n，但 d 和 m 却不同的消息。

Prepare 阶段：节点同意请求后会向其它节点发送 prepare 消息。这里要注意一点，同一时刻不是只有一个节点在进行这个过程，可能有 n 个节点也在进行这个过程。因此节点是有可能收到其它节点发送的 prepare 消息的。在一定时间范围内，一个节点如果收到 2f 个不同节点的 prepare 消息，就代表prepare 阶段已经完成。

Commit 阶段：于是进入 commit 阶段。向其它节点广播 commit 消息，同理，这个过程可能是有 n 个节点也在进行的。因此可能会收到其它节点发过来的 commit 消息，当收到 2f+1 条 commit消息后（包括该节点本身），代表大多数节点已经进入 commit 阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据。

图中A节点的当前请求编号是 1039，即checkpoint为1039，B节点的 checkpoint 为1133。当前系统 stable checkpoint 为 1034。那么1034这个编号就是低水位，而高水位 H=低水位 h+L，其中L是可以设定的数值。因此图中系统的高水位为 1034+100=1134。举个例子：如果 B 当前的 checkpoint 已经为 1134，而A的 checkpoint 还是 1039，假如有新请求给 B 处理时，B会选择等待，等到 A 节点也处理到和 B 差不多的请求编号时，比如 A 也处理到1112 了，这时会有一个机制更新所有节点的 stabel checkpoint，比如可以把 stabel checkpoint 设置成 1100，于是 B 又可以处理新的请求了，如果 L 保持100 不变，这时的高水位就会变成 1100+100=1200 了。

对于 pbft 算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人（2f+1）都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。

对于 pbft 算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人（2f+1）都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。

NEO 代币的持有者通过投票，可以选出其所支持的记账人。随后由被选出的记账人团体通过 BFT 算法，来达成共识并生成新的区块。投票在 NEO 网络持续实时进行，而非按照固定任期。

DBFT 对由 n 个共识节点组成的共识系统，提供 f=（n-1）/3的容错能力，这种容错能力同时包含安全性和可用性，可以抵抗一般性故障和拜占庭故障，并适用于任何网络环境。DBFT 具有良好的最终性，一个确认即最终确认，区块无法被分叉，交易也不会发生撤销或回滚。

NEO在 DBFT 共识机制下，每 15～20 秒生成一个区块，交易吞吐量实测可达到约 1000TPS，在公有链中性能优秀。通过适当优化，有能力到达 10000TPS，可以支持大规模的商业化应用。