区块链时代的拜占庭将军们（中）

区块链时代的拜占庭将军们（上） 区块链时代的拜占庭将军们（中） 区块链时代的拜占庭将军们（下）

在继续关于BFT的讨论之前，我们先来说说计算机科学。很多人会把计算机科学误解成关于计算机的科学，是一门应用学科。但实际上并不是，计算机科学的广度远超于此——如果把计算机比作一个独立的个体，例如人类，那么计算机科学就涵盖了社会学（人机交互），教育学（人工智能），艺术（图像处理），传播学（互联网）等等范畴。但问题是，计算机并不是一个单独存在的个体，而是人类的造物，所以实际上，计算机科学其实包含了计算机是如何成为计算机的科学，例如生物学（硬件），医学和各种人体机能的开发和使用（算法，软件）。

以上这些，也许是更容易理解的部分，甚至说，也许对于大部分人来说，以上的这些就代表了计算机科学，计算机科学的定义和IT行业覆盖的范围是重合的。

但其实，计算机科学的内涵，也许是很多理工科学生甚至IT行业从业者都不甚了然的——

计算机科学更核心的部分，实际上是一个甚至有些哲学意味的问题：

“我们为什么需要计算机？”

整个信息时代和计算机科学的起源，需要追溯到两个人：香农和图灵，以及他们的信息论和图灵机。前者定义了信息与交流，后者定义了思考与计算。

而两者的出发点也类似，香农在战时火控系统的研究中，发现想要解决噪声问题，先要定义什么是“噪声”，或者说，什么是有效的信息，什么是无效的信息，那么，他首先要定义什么是信息。图灵也类似，图灵机的提出是他采用一种新的思路来解决希尔伯特提出的可判定问题，而这个时候，他需要考虑什么是计算，人类是如何实现计算的，于是，他用一个虚拟的机器的形式，模拟了什么是“计算”。

两人如果放在现在，也许都会被称为计算机科学家，但是在当时，他们只有一个共同的身份——数学家，或者说，应用数学家。因为他们从现实中提取数学问题，然后用数学的方式定义，然后解决。

他们提取的问题就是人类的基本问题——当我们现有的技术已经无法满足我们对于思考与交流的需求的时候，我们需要想一种办法来提高人类思考与交流的效率，而想要达到这一点，对于数学家而言，需要首先定义什么是思考，什么是交流。然后，他们发现信息量是对于交流这种活动最合适的定义，而图灵机是对于人类所有逻辑思考过程最合适的模拟。

于是才有了计算机，信息技术和计算机科学——它们实际上不是关于计算机的学科，它们实际上还是关于人的学科——是关于如何用数学的方式来定义人类的关于交流与思考的需求，然后通过机器的方式来实现它们的学科。我们甚至可以说，即便有外星人，只要他们还需要思考与交流，只要他们的身体不具备无限的思考与交流能力，那么那个星球也一定会诞生一门学科叫做计算机科学，尽管他们计算机也许看起来和我们完全不同。而这就是之前问题的答案——

我们需要计算机，是因为我们需要更高的效率来进行思考与交流。而计算机，是根据这个需求，用数学的方式推导得出的结果。

所以，以上这一大段的内容，我在强调的是一个观点：

计算机科学，实际上的核心和基础，是数学。

计算机科学的本质和源起，是从现实中发现关于交流与思考的数学问题，然后用数学的方法来解决这个问题。

至于解决问题的方法，是否会启发其他人，或者是直接被其他的人拿来作为工具来解决实际中的问题，则是另一个层面的事情了。

——————————————————————————————————

之所以在开篇写这些，是因为拜占庭将军问题，拜占庭容错，乃至数字签名，哈希函数，零知识证明这些密码学的基本组成部分，都属于此类问题——的确，他们是从应用中提取出的问题。但是，计算机科学家们的研究方向，应用只是其中的一个方面，而另外很大的一个方面，是问题本身。

只有当你了解了这些，你才能更好的理解区块链和拜占庭容错的关系——

拜占庭容错是个数学问题，他源自普通容错问题，然后Leslie Lamport发现一般容错算法没法很好地解决有恶意节点的情况，所以，需要定义一个新问题。

而拜占庭容错的应用是另一个问题，而且是个很大的问题——没有应用场景的理论，除非这理论真的很有趣，否则很多连诞生都不会诞生出来。但是，应用场景很有限的话，就代表没经费，没关注，于是就没人愿意来，这就是标准的冷门领域，拜占庭容错和密码学其实都是。密码学我们以后再说，拜占庭容错，别看是图灵奖获得者Leslie Lamport提出的，然后还吸引了另一位图灵奖获得者Barbara Liskov写了PBFT，但是它本身在区块链诞生之前，是毫无疑问的冷门领域。原因一个是因为它比较难，另一个就是，相比于一般容错有分布式数据库这样的随着互联网发展有着广泛应用和性能需求的领域，拜占庭容错的应用场景非常非常少。

而没有需求，自然就没有明确的发展方向，同时也没有足够的成果。如果没有区块链的出现，BFT只是在分布式系统这个方向上分布式容错算法这个子类中比较偏门艰涩的一类而已。这真的不是贬低——实际上随着互联网的普及，现在我们的生活中分布式系统已经无处不在，你所用的所有的设备和应用都可以认为处于一个分布式系统之中。而有分布式系统，就需要采用某些容错算法来达成共识，这所有的共识算法之中之中，采用BFT的少之又少。

我管拜占庭容错诞生直到比特币诞生这段时间内的所有BFT算法，包括像是后来诞生的但是还未受到比特币和区块链影响的BFT算法叫做传统BFT算法。这类算法包括著名的PBFT，也包括之前的不那么practical的BFT，和后PBFT时代中提出了“投机型”BFT的Zyzzyva。

这类BFT算法的最大特点，就是他们并没有把区块链当做主要的应用场景（废话）。

然后这类BFT算法我们又可以拿PBFT和Zyzzyva分成三个阶段。

第一阶段——从拜占庭将军问题的提出到PBFT的提出。

这个时候，正如我之前所说，是BFT作为一个数学问题的时期。人们关注的不是解决一个“一群拜占庭将军如何围攻地方城市的问题“，学者们既不关心这些将军也不关心地方城市的命运，学者们关注的是作为一个数学问题，如何解决它。

上一篇中我已经解释了这个问题为什么无解，即便是在有签名的情形下——最重要的原因实际上是异步系统共识固有的问题，即FLP不可能。

但是，数学家们显然不会就此止步——他们要探索这个问题的边界。而对于数学家，他们最喜欢使用的工具就是——无穷小。

所以，最终他们得出来的结论很简单——如果确定性的算法无法解决拜占庭容错问题，那么我们引入一些随机因素。简单地解释起来是这样——根据FLP不可能，如果要保持一致，总会出现那么一种特别恰巧的情况：每个节点的判断，延迟，消息接受的先后等等恰好都满足了某个条件，于是，恰好某些诚实节点需要等待某个失效节点的回复才能决定自己是“进攻”还是“撤退”，而他们的决定恰好会决定整个系统最终的判断，于是，系统卡在这了——如果选择中止，那么达不成一致，如果选择一致——那么就一直卡下去吧……

那么，在这个时候，当节点判断出这种情况出现，我们让这些节点掷个硬币，根据硬币的结果随机选择“进攻”和“撤退”，并且广播自己的决定再次执行一遍之前的共识算法……当然，更极端的情况是又出现了恰巧的情况，那么，我们就再掷一次硬币……最终，网络达不成共识的可能会越来越低。

最终，这个问题在数学层面得到了解决——任意给定一个不成功的概率，例如0.00001%，我们都能证明只要我们执行很多轮，例如100轮，这个算法失效的概率小于这个概率。

这种算法一点也没有考虑过实用，主要是它可能会需要很多轮才会中止，而且这个轮是异步系统的轮，是没有时间限制的，也就是说，每一轮我们保证会终止，但是我们不知道什么时候中止。

不过正如之前所说，计算机科学不是应用科学，这里，人们的目标是解决拜占庭容错这个数学问题。而这个工作是非常重要的，因为它为以后的拜占庭容错研究提供了两个很重要的东西：

1. 我们在上文中讲过的，弱终止条件下的拜占庭将军问题的解法，又被称为可靠广播——即，当指挥官的活性可以保证的情况下，这个算法可以保证一致性。我们把这个算法简单记为A。这个算法就是这个时期提出的。
2. 这个阶段给出了一个解决异步（拜占庭）容错问题的范式：先做出某个假设S1，采用某个基于A的拜占庭容错算法F(A)来试图达到共识，然后，如果不成功，即满足某个退出条件T，则改变S1为S2，然后再采用F(A)。

这里之所以不是直接用A，是因为A是异步拜占庭将军问题的算法，并不直接等价于异步拜占庭容错，两者的区别如下：

拜占庭将军：一个指挥官发令，剩下的所有将军需要听他的。

拜占庭容错：每个将军目前都有不同的判断，需要达成一致。

可以说，如果能够预设一个将军，并且这个将军不会不响应，那么可靠广播就能够解决拜占庭容错问题，这就是一种基于拜占庭将军算法的拜占庭容错算法，也即F(A)的一种。

对于这种范式，我们简单概括为S1:F(A):T -> S2:F(A):T -> S3:F(A):T.......，即，在S1状态下，执行某个基于可靠广播A算法的拜占庭容错算法，如果检测到共识无法达成的退出条件T成立，则改变初始状态以及假设至S2，再执行F(A)…… 掷硬币相当于改变初始状态

而在之前我们说的引入随机因素解决异步拜占庭容错的算法中，T就是检测到出现了“收到了所有能收到的消息，但是还是无法做出判断的情况”，例如，有f个恶意节点的情况，就是恰好收到各(n-f)/2条不一致的消息。S1->S2的方法就是所有无法做决定的节点随机掷硬币。注意这里退出条件是每个节点自行需不需要掷硬币，因为整个系统是无法确定地判断是不是达到了退出条件的——因为这就又回到FLP不可能了。

第二阶段——实用拜占庭容错（PBFT）

1999年，Castro和Liskov提出了PBFT。PBFT是一个非常重要的算法，同时也可以说是第一个“实用”的拜占庭容错算法。PBFT中的很多机制受到Paxos的影响。但是最核心的部分，实际上还是我们之前提到过的范式：

这里面，F(A)是这样一个机制——将所有节点排上号，然后轮流来做首领（指挥官），然后进行可靠广播即算法A来达成共识。

然后，S1就是前篇中提过的弱终止假设，即，假设选出来的首领（指挥官）不会不响应，S1就是编号1的指挥官发起共识，S2就是第二个，以此类推，而退出机制T也相对应的，是达到某个时间阈值t。

但是，如果仅仅是这样，这个拜占庭容错在异步系统中是无效的——因为这个算法会在延迟超过阈值t的时候失效，而异步系统的定义就是找不到这样一个阈值t。

所以，PBFT采用的方法是：在S1的时候，把阈值设为t1，然后如果超时，则增加这个阈值。这样保证无论这个系统的延迟有多大，只要延迟不会无限增长，PBFT都能保证最终达成共识。

所以，最终的PBFT，可以表示成：

S1:F(A):T1 -> S2:F(A):T2 -> S3:F(A):T3.......

注意，这个时候，我们仍旧没有严格地达成异步系统的拜占庭容错，因为如果这个异步网络的延迟会一直增长的话，这个算法也会失效。但是通常情况，我们认为这种情况不会发生，所以PBFT，正如它们名字一样，人们认为它已经够实用了。

至于PBFT的性能，比较重要并且经常造成瓶颈的两个指标是输出和延迟，而在对于一般分布式文件储存系统的测试中，PBFT都已经接近于传统的一般容错系统。于是，大家就认为PBFT已经足够实用，整个BFT的发展，似乎已经到了终点——大家觉得，似乎没有什么BFT问题是PBFT解决不了的了，又或者说，PBFT解决不了的BFT问题，似乎也只是那些只存在于理论上的情形，不太可能在实际中出现。

第三阶段——Zyzzyva

如果从现在的眼光看，以上那种想法显然过于乐观了。例如，比特币就解决了一个PBFT解决不了的拜占庭容错问题，但是，在比特币出现之前，没人想过这个问题是有解的，又或者说，压根就没人觉得这个问题存在。然后，比特币以及区块链给BFT问题打开了一扇新世界的大门，导致了BFT算法在近几年又有了许多发展。

尽管这些都是后话，这里我们想说的是，即便PBFT顶着实用拜占庭容错的名字，在接下来的许多年里，人们还是不知道它能用在哪。甚至，也许在PBFT提出的时候，作者也不知道它能用在哪，只是一般性地说“这东西是个更安全的分布式容错算法，能容下更恶意的错误的同时速度也没慢多少”。在论文中，它所有的机制，功能和性能都对标分布式文件储存系统，或者说，分布式数据库。于是，它做了很多相应的假设，例如：节点数量在10个左右，其中有不超过1/3的拜占庭节点；考虑的场景主要是一个外部的用户希望通过这个分步式系统将文件写入数据库，或者读取某个文件；每一步操作必须被严格排序再执行；优化是针对大文件的写入和读取，性能也是与传统的分布式文件存储系统对比，主要考虑延迟和输出。

而在这种场景下，PBFT的确已经相当优秀了。

可是在实际应用的时候，我们发现了PBFT的一个问题：

这里是PBFT的范式：

S1:F(A):T1 -> S2:F(A):T2 -> S3:F(A):T3.......

实际上翻译过来是这样：

先让节点1当首领，如果节点出了问题，有恶意，或者网络出了问题，导致规定时间没有完成任务，换节点2，提高规定时间的值，然后循环往复……

于是，出现了一个叫Zyzzyva的算法——这个奇怪的名字是英文词典的最后一个单词。大约，在提出的时候，作者认为这个是BFT问题的最终解决方案吧。

这个叫Zyzzyva的算法说，等等听起来好麻烦——难道实际上不是只会出现以下三种情况吗？

1. 轮到的首领是好人，同时网络状况好，于是顺利达成共识。
2. 轮到的首领是好人，但是网络状况极端，例如延迟超过t1，于是触发终止条件T1进入第二轮……直至最终达成共识。
3. 轮到的首领是坏人，用某些方法造成共识无法达成，但其实最简单的方法就是不响应。于是，触发T1进入第二轮……直至最终共识达成。

更简单地说，只有两种情况：1，正常情况（首领是好人，网络正常），执行F(A)，共识达成；2，特殊情况（首领恶意或者网络延迟高，但这两者其实通常区别不大），然后触发几次终止条件之后再执行F(A)共识达成。

但是，对于这两种情况，PBFT是不区分的。

换句话说，PBFT对于首领是不是好人都是一视同仁的，统统采用基于可靠广播这种绝对保证一致性同时需要O(N^2)消息复杂度的算法F(A)来达成共识。

Zyzzyva觉得这种方法不善良，说，我们要善良一些——如果首领是可信的，那么用不着那么复杂的算法啊，直接做一轮O(N)消息复杂度的普通广播就好了嘛。然后，如果大家发现首领有问题，再退回BFT的那种算法。

于是，Zyzzyva相对于PBFT的特性就是：“当首领是诚实的并且网络状况好的话，共识更快，然而，如果状况很糟糕的话，那么共识就会比PBFT慢，因为需要先等‘基于假设的’的算法跑完才能进入正题”。

然后，两者在实际应用中哪个更好呢？

……

不好说，因为BFT哪来的实际应用……

……

但没有实际应用也不能抹杀Zyzzyva的价值，因为它激发了以后的一系列的BFT算法。这类算法共同的范式变为：

正常状态:快速算法:终止条件 -> 不正常状态:F(A):终止条件 -> 下一个节点正常状态:快速算法:终止条件.......

然后，每个算法的区别就在于，什么才是它们认定的“正常状态”。换言之，就是这个BFT应用场景的特性，例如：网络状况如何，恶意节点数量多少，恶意节点会进行什么样的行为……等等等等。然后，每个这一类“投机BFT”都会在某种场景下更好用一些，因为“正常状况”的出现可能更大，而算法特意对这种状况进行了优化。

而这类算法的终极形态，就是被称为链式BFT的一类算法，最标志性的就是Azyzzyva，简单说就是既然有这么多BFT，大家都定义不同的正常状态，那么，我们干脆就把它们都串起来好了：

理想状态:快速算法:终止条件 -> 一般正常状态:一般快速算法:终止条件 -> 不那么正常的状态:不那么快速的算法:终止条件 -> 特别不正常的状态:PBFT……

一个链式BFT的示例

总之，无论是哪一种，基本思路就是，在理想状态下采用类似一般广播的O(N)的快速算法，最后消息复杂度O(N^2)的PBFT保底。然后，根据各种状况在这个应用场景中可能出现的比例和每个算法所需要的时间，我们只要进行优化就可以得出最适合这个场景的BFT算法了。

比特币的启示

而比特币基本上也在和链式BFT出现几乎同样的时间，独立地出现了。

当然，其实说BFT算法完全没有应用也是不公允的——随着硬件的发展和对于信息安全的重视，很多分布式系统也开始考虑拜占庭容错。但是比特币的出现，对于BFT的发展，很显然是一个重大的里程碑。一方面，它提供了一个新思路，而更重要的是，它终于给拜占庭容错提出了一个有用武之地的场景。在下一篇，我们会更加详细地叙述这个场景以及针对于区块链应用诞生的新BFT类算法。

在这里，我们先来谈谈思路。

在我之前介绍比特币的文章里已经讲过，比特币的POW算法提出的最重要的思路，就是引入了博弈论的机制，以算力的方式给每条消息加上了成本，然后采用激励的方式来激励诚实节点，同时惩罚恶意节点。

在大部分人，甚至很多区块链的研究者们看来，这个算法都是和传统BFT八竿子打不着的东西，甚至，很多研究共识算法的人都不清楚传统BFT算法的原理，认为传统BFT算法例如PBFT是一个纯粹的黑盒子（这很大程度上也是因为他们只知道PBFT），只能应用于联盟链或者是根本不能用于区块链。更有甚者，将POW这种共识算法当做是密码学而不是分布式系统的问题来看。

这很难说是他们的问题——因为从起源上，中本聪的论文并没有和分布式系统扯上关系，从描述上，比特币也更像是密码学而不是分布式系统的东西，而从整个东西的原理上，又和BFT算法，例如PBFT看起来相差甚远，两者似乎完全不在一个位面上，例如许可和非许可的问题，例如所谓3f+1的节点限制，例如关于理性节点和诚实节点的假设，PBFT和POW在这里看起来似乎没有任何一点重合的地方。

然而，回到我们开篇所说的：计算机科学是数学，拜占庭容错是数学问题，我们只是想要知道，如何在有恶意节点的情况下达成共识，这和应用，与场景，与方法都无关。而之前PBFT一类的一切传统BFT算法，无非都是试图解决这个问题的方法，而POW以及之后的共识算法，也是试图解决这个问题的方法。两者看起来似乎天壤之别，无非是因为两者提出的背景不同，描述的问题不同，同时叙述的规范不同而已。而实际上，两者无论从原理上，思路上，还是实现方式上，都有千丝万缕的联系——

PBFT看起来似乎和POW很不一样，但是Zyzzyva呢？还有衍生出的链式BFT呢？

Zyzzyva先于比特币，而也没有证据显示中本聪受到过链式BFT的影响，两者完全是独立诞生的两种算法，但是如果沿着Zyzzyva的路线往下看，你会发现比特币的想法其实和链式BFT不谋而合，而且，引入了激励正是神来之笔。比特币其实解决的问题是——

如果只有“理想状态”呢？

如果我们可以用激励和惩罚的方式，约束所有节点的行为，让大部分乃至所有节点都不去做恶意行为，并且尽最大努力保持网络同步呢？这不就正是投机BFT中假设的“理想状态”嘛？

那根据投机BFT和链式BFT的思路发展下去，当一个网络大部分时间都处于理想状态的时候，我们应该怎么优化呢？

我们是不是可以直接采用O(N)消息复杂度的，最最简单的直接广播就可以让全网达成共识了呢？然后，是不是我们也永远不需要再退回消息复杂度O(N^2)的PBFT了呢？然后，我们是不是其实连节点数量也就都不需要知道了呢？

应该说，关于这个的认识也不是一蹴而就的——区块链的研究者们，许多现在还没有接受这个问题，而BFT的研究者们，也是逐渐地才开始意识到BFT和POW其实没有那么不同。归根结底，无论是PBFT还是POW，都不是不可拆分的黑盒子，都是一个个思路和机制结合起来的。

而区块链这个场景带来的新问题就是——面对区块链这个全新的场景，而我们手边则有了许多工具，例如传统的BFT，例如激励，例如防止女巫攻击的方法，例如链式的思想……那么，如何从这其中选取合适的工具，来解决区块链的问题。

这个，我们下篇继续。

——————————————————————————————————

备注：

看过PBFT或者Zyzzyva的人可能会觉得我这里写的和他们看的大不相同，但这就是我在开篇时候说的——我会从区块链的视角写BFT。因为我知道大部分专栏的读者是从区块链的视角来看的，甚至说，现在世界上大部分想要了解BFT的人，都是从区块链过来的。于是，其实BFT类算法很重要的一个门槛，就是整个描述的范式，和描述的场景，都迥异于区块链，这导致了我上述的情况——很多人看不懂BFT的论文，即便看懂了，也看不出它和区块链的关系。

于是，我特地将里面的算法搬到区块链的语境下来叙述。

反映在PBFT和Zyzzyva里就是——

1. 这两个算法考虑的场景是有一个外部的用户如何像操作一台中心化系统一样来操作这个系统，因此算法里有一个重要的角色叫用户——用户负责给命令让节点达成共识。而在区块链里，我们关心的是节点（矿工）如何对于他们提交的区块达成共识，因此，实际上将PBFT和Zyzzyva应用于这种采用矿工模式的区块链时，用户就是首领，而发布的指令，就是区块。
2. 区块链中我们考虑的是区块顺序上链，所以一个后面的区块在前面的区块之前就达成了共识默认是不可接受的（因为有链式结构也是不可能的）。但是在传统BFT算法中这是可以的，只要最终顺序是对的就行。所以，传统BFT中有个很重要的部分是定序，因为节点可能会先对后面的区块达成共识。例如，PBFT中的prepare和commit的过程，就是通过两轮可靠广播先定序，再对内容达成共识。在这里我省去了，因为在区块链的语境下我们不考虑定序的问题。