【Byzantine Generals Problem】深度了解区块链——拜占庭将军问题深入探讨（二）

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？

了解过比特币和区块链的人，多少都听说过拜占庭将军问题，或听说过比特币（或区块链）的一个重要成就正是解决了拜占庭将军问题。但真正明白这个问题的人并不多，甚至知道这个问题实质的人都很罕见。本文是一篇技术科普，将重点提供了拜占庭将军问题本身对本质及经典算法的解析，并探讨与之相关的一些问题。笔者参考了不少文献，夹杂了大量私货，但并没有提出解决该问题的新算法，这也不是本文的目的。

Part1：拜占庭将军问题是什么

拜占庭将军问题是一个共识问题: 首先由Leslie Lamport与另外两人在1982年提出，被称为The Byzantine Generals Problem或者Byzantine Failure。核心描述是军中可能有叛徒，却要保证进攻一致，由此引申到计算领域，发展成了一种容错理论。随着比特币的出现和兴起，这个著名问题又重入大众视野。

1.1. 拜占庭将军问题场景

关于拜占庭将军问题，一个简易的非正式描述如下：

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。

应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，我们已经假定了信道是没有问题的，并在这个前提下，去做一致性和容错性相关研究。如果需要考虑信道是有问题的，这涉及到了另一个相关问题：两军问题。

1.2.与拜占庭将军相关问题：两军问题

正如前文所说，拜占庭将军问题和两军问题实质是不一样的。国内大量解释拜占庭将军问题的文章将两者混为一谈，其实是混淆了两个问题的实质，由此造成了许多误解。这两个问题看起来的确有点相似，但是问题的前提和研究方向都截然不同。

（图1：两军问题图示）

如图1所示，白军驻扎在沟渠里，蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大，但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通，只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议，这就是两军问题。

看到这里您可能发现两军问题和拜占庭将军问题有一定的相似性，但我们必须注意的是，通信兵得经过敌人的沟渠，在这过程中他可能被捕，也就是说，两军问题中信道是不可靠的，并且其中没有叛徒之说，这就是两军问题和拜占庭将军问题的根本性不同。由此可见，大量混淆了拜占庭将军问题和两军问题的文章并没有充分理解两者。

两军问题的根本问题在于信道的不可靠，反过来说，如果传递消息的信道是可靠的，两军问题可解。然而，并不存在这样一种信道，所以两军问题在经典情境下是不可解的，为什么呢？

倘若1号蓝军（简称1）向2号蓝军（简称2）派出了通信兵，若1要知道2是否收到了自己的信息，1必须要求2给自己传输一个回执，说“你的信息我已经收到了，我同意你提议的明天早上10点9分准时进攻”。

然而，就算2已经送出了这条信息，2也不能确定1就一定会在这个时间进攻，因为2发出的回执1并不一定能够收到。所以，1必须再给2发出一个回执说“我收到了”，但是1也不会知道2是否收到了这样一个回执，所以1还会期待一个2的回执。

虽然看似很可笑，但在这个系统中永远需要存在一个回执，这对于两方来说都并不一定能够达成十足的确信。更要命的是，我们还没有考虑，通信兵的信息还有可能被篡改。由此可见，经典情形下两军问题是不可解的，并不存在一个能使蓝军一定胜利的通信协议。

不幸的是，两军问题作为现代通信系统中必须解决的问题，我们尚不能将之完全解决，这意味着你我传输信息时仍然可能出现丢失、监听或篡改的情况。但我们能不能通过一种相对可靠的方式来解决大部分情形呢？这需要谈到TCP协议。事实上，搜索“两军问题与三次握手”，您一定可以找到大量与TCP协议相关的内容。若您是通信方面的专家，权当笔者是班门弄斧，这里仅用最浅显易懂的方式科普TCP协议的原理和局限，可能存在一些毛刺，请多包涵。

                                                                                                                                                                                              （图2：TCP协议的基本原理）

TCP协议中，A先向B发出一个随机数x，B收到x了以后，发给A另一个随机数y以及x+1作为答复，这样A就知道B已经收到了，因为要破解随机数x可能性并不大；然后A再发回y+1给B，这样B就知道A已经收到了。这样，A和B之间就建立一个可靠的连接，彼此相信对方已经收到并确认了信息。

而事实上，A并不会知道B是否收到了y+1；并且，由于信道的不可靠性，x或者y都是可能被截获的，这些问题说明了即使是三次握手，也并不能够彻底解决两军问题，只是在现实成本可控的条件下，我们把TCP协议当作了两军问题的现实可解方法。

                                                                                                                                                                                  （图3：量子隐形传态的原理图）

那么，是否能够找到一个理论方法来真正的破解两军问题呢？

答案是有的，量子通讯协议，笔者并没有能力弄清这个颇为高深的问题。据我的理解，处于量子纠缠态的两个粒子，无论相隔多远都能够彼此同步，光是直观的来看，这个效应可以用来实现保密通讯。

但是由于测不准原理，一测量粒子状态就会改变其状态，所以通讯时还必须通过不可靠信道发送另一条信息。尽管这个“另一条信息”是不可靠的，但是由于已经存在了一条绝对可靠的信道（量子纠缠），保证了另一条信道即使不可靠也能保证消息是可靠的，否则至少被窃取了一定能够被发现。

因此我们可以相信，至少理论上两军问题是可解的，即存在一种方法，即使利用了不可靠的信道，也能保证信息传递的可靠性。所以，在确保了信道可靠的基础上，我们可以回到拜占庭将军问题上继续讨论。

Part2：问题实质及形式化

我们已经了解了拜占庭将军问题的场景，并且明确了这个问题的解决是建立在通信兵可以正确的传达信息的基础上的，即信道绝对可信。同时，通过前文对于两军问题的探讨，我们明白了理论上可信的信道也是可以实现的。接下来，我们将探讨拜占庭将军问题的实质。

2.1. 拜占庭将军问题实质

回顾问题，一群将军想要实现某一个目标（一致进攻或者一致撤退），但是单独行动行不通，必须合作， 达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。注意，这里“一致性”才是拜占庭将军问题探讨的内容，如果本来叛徒数量就已经多到了问题不可解的地步，这个就是“反叛”的问题了；同时，我们的目标是忠诚的将军能够达成一致，对于这些忠诚的将军来说，进攻或者撤退都是可以的，只要他们能够达成一致就行。

但是，光靠“一致”就可以解决问题吗？考虑一下，如果万事俱备，客观上每个忠诚的将军只要进攻了就一定能够胜利，但是却因为叛徒的存在他们都“一致的”没有进攻；反之，条件不利，将军们不应该进攻，但是却因为叛徒的存在所有人都“一致的”进攻了。

可以发现，只有“一致性”是不足以解决拜占庭将军问题的，我们还需要提出一个“正确性”要求。这个要求是值得斟酌的，因为如果客观来看或许会有“绝对正确的”判断，但是针对每一个将军，大家的判断或许都不相同，我们如何定义“正确”呢？我们或许可以简单地说，正确就是每个忠诚的将军都正确的表达了自己的意思，不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。

至此，我们将拜占庭将军问题简化成了，所有忠诚的将军都能够让别的将军接收到自己的真实意图，并最终一致行动；而形式化的要求就是，“一致性”与“正确性”。

如果将问题推广开来，可以发现针对一致性和正确性的算法并不要求命令必须是“进攻/撤退”或是“1/0”，而可以是“发送消息1/发送消息2/待机”或“x/y/z/w”，这意味着拜占庭将军问题算法可以为多种分布式系统提供启发，比如电力系统或网络系统。

由此可见，这个问题说到底是一个关于一致性和正确性的算法问题，这个算法是针对的是忠诚的将军，因为叛徒可以做出任何超出约定的判断。我们就是要在有叛徒的干扰下，找到一个抗干扰的算法。要解决这个算法问题，我们需要将形式化要求具体化。

2.2.形式化条件的推演

定义一个变量vi（为不失一般性，并不要求vi是布尔值），作为其他将军收到的第i个将军的命令值；i将军会将把自己的判断作为vi。可以想象，由于叛徒的存在，各个将军收到的vi值不一定是相同的。之后，定义一个函数来处理向量(v1,v2,…,vn)，代表了多数人的意见，各将军用这个函数的结果作为自己最终采用的命令。至此，我们可以利用这些定义来形式化这个问题，用以匹配一致性和正确性。

1）一致性

条件1：每一个忠诚的将军必须得到相同的(v1,v2,…,vn)指令向量或者指令集合。

这意味着，忠诚的将军并不一定使用i将军送来的信息作为vi，i将军也可能是叛徒。但是仅靠这个条件，忠诚的将军的信息送来的信息也可能被修改，这将影响到正确性。

2）正确性

条件2：若i将军是忠诚的，其他忠诚的将军必须以他送出的值作为vi。

如此，我们得到了一致性和正确性的形式化条件（条件1和条件2），这个条件是充分条件。考虑到正确性条件是针对单个将军，而一致性条件是针对所有将军的，为方便我们重写一致性条件为

条件1′：无论i将军是忠诚或是叛徒，任何两个忠诚的将军都使用相同的vi。

条件1和条件1′是完全等价的。这是很巧妙的一步转换，如此一致性条件（条件1′）和正确性条件（条件2）都只涉及一个将军i如何帮别的将军接受自己送出的值vi，所以可以将问题改为司令-副官模式来简化问题，即一个司令把自己的命令传递给n-1个副官，使得：

IC1：所有忠诚的副官遵守一个命令，即一致性。

IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令，即正确性。

IC1和IC2分别由条件1′和条件2演化得来。司令-副官模式只要将司令遍历各个将军，就可以变成完整问题，而他们采用的算法可以是完全一致的。IC1和IC2构成了解决拜占庭将军问题的充分条件，在这种模式下，司令副官的形式下达成的一致意味着司令的命令得到了有效传达，若出现了异议，有异议的将军会作为司令发起新的司令副官模式寻求自己的观点表达，以协商达成一致。

接下来，我们可以讨论拜占庭将军问题的算法了，这个算法只要能够满足IC1和IC2，就代表这个算法可以切实有效的解决拜占庭将军问题。

在经典的情形下，我们可以找到两种办法，口头协议和书面协议。笔者将会逐一探讨两种算法的推演和证明，其中证明部分并不会采用纯推理，而以介绍证明思路为主。

事实上，若完整进行了算法推演，对算法已经能够有一个大致的了解。口头协议和书面协议会有很多不同的启发，口头协议的实现起来简单，但是算法复杂，同时需要克服的困难更多；书面协议的算法本身很简单，却能够克服很多问题，但是实现算法并不容易。这些不同让两者有了不同的使用场景和具体实现。

Part3：口头协议

首先，我们明确什么是口头协议。我们将满足以下三个条件的方式称为口头协议：

A1：每个被发送的消息都能够被正确的投递

A2：信息接收者知道是谁发送的消息

A3：能够知道缺少的消息

简而言之，信道绝对可信，且消息来源可知。但要注意的是，口头协议并不会告知消息的上一个来源是谁。

先告知结论：采用口头协议，若叛徒数少于1/3，则拜占庭将军问题可解。也就是说，若叛徒数为m，当将军总数n至少为3m+1时，问题可解（即满足了IC1和IC2）。

这个结论说明了，一个三模冗余的系统只能容故障冻结类型的错误，即一个元件故障以后就卡住不动了（也即已知错误后会出现的结果），那么三模冗余是足够的。

但是对于拜占庭将军问题，由于叛徒可以做出各种各样的判断，就必须四模冗余系统才足够容错。口头协议算法就是把自己的命令告诉其他人，并利用对其他人的命令取多数的方法来得到自己的结论。但要注意的是，别的将军传来的命令是通过算法递归的方法来确定的。利用这个方法，可以保证在叛徒数量少于1/3的情况下，忠诚的将军可以实现一致性和正确性要求，即问题可解。

那么，口头协议算法又是怎么实现叛徒数少于1/3即可容错的呢？下面，笔者将介绍Lamport在其论文中提出的口头协议OM(m)算法。笔者将会逐一介绍口头协议算法的详细内容、实例推演及证明，这一部分将会需要您花一些时间来思考。

3.1.口头协议算法OM(m)

OM(0)算法

（1）司令将他的命令发送给每个副官。

（2）每个副官采用从司令发来的命令；如果没有收到命令，则默认为撤退命令。

OM(m)算法

（1）司令将他的命令发送给每个副官。

（2）对于每个i，vi是每个副官i从司令收到的命令，如果没有收到命令，则默认为撤退命令。副官i在OM(m-1) 中作为发令者将之发送给另外n-2 个副官。

（3）对于每个i，和每个j ≠ i，vj 是副官i 从第2步中的副官j （使用OM(m-1)算法）发送过来的命令，如果没有收到第2步中副官j 的命令，则默认为撤退命令。最后副官i 使用majority(v1,…,vn-1)得到命令。

其中，majority(v1,…,vn-1)代表了大多数人的命令，若不存在则默认为撤退命令。

要一遍读懂这个算法并不容易，笔者也是花了不少时间研究这一小段文字才弄明白的。不过您不用担心，笔者将会解释几个值得注意的点，并利用一个不难的实例来帮助您理解这个算法。

（1）算法始终保证了一个更加安全的默认值，这意味着若信息没有传到是可知的，并且传输时间不在考虑范围内。

（2）这个算法是一个递归算法，在OM(m)中需要采用OM(m-1)得到相关结果。m代表的是叛徒数量，从m到0，意味着对于每个将军，需要m+1轮的算法才能完成。

（3）该算法是关于m的，意味着使用该算法必须知道有多少个叛徒。或者说，利用该算法，可以保证叛徒数量在某一个最大值（即总将军数量的1/3）之下时，拜占庭将军问题可解。

（4）对于任意k<m，在第m-k+1步中OM(k)的vi，都是利用OM(k-1)得来的，即每个将军将会在OM(k-1)中询问其他人，i将军传给他们的是什么，而其他人传递回来的信息则是利用OM(k-2)得到。

这个就是递归的意义，若您觉得笔者表达得不甚清楚，不用担心，您只用记住每一步都会牵涉到下面很多步骤就可以了，之后将在实例推演中明白算法的核心思路。

3.2.口头协议实例推演

首先，笔者将先举一个m=1，n=3的例子来说明三模冗余的问题所在，并介绍m=1，n=4的时候系统是怎么容错的，这样您就可以明白算法是运行的。但由于m=1的时候并没有体现递归的过程（因为m-1就变成了0），笔者将再举一个m=2，n=7的例子来说明算法递推的过程。 （1）m=1，n=3的情形 n=3，意味着一个司令发送命令给两个副官，m=1意味着他们中有一个叛徒。 首先考虑司令忠诚而副官2是叛徒的情况。

（图4：m=1，n=3中司令忠诚而副官2是叛徒的情形）

司令把进攻命令传给了两个副官1和副官2，但是由于副官2为了不让他们达成一致，将司令的命令改成了撤退。那对于副官1来说，他应该如何判断？他无法知道是司令是叛徒还是副官2是叛徒，从而无法判断。

                                                                                                                                                                         （图5：m=1，n=3中司令是是叛徒的情形）

而如果司令是叛徒，两个副官忠诚，司令会发送两个不同的命令。当两个副官对照命令时，他们又凌乱了，无法判断司令是叛徒或者对方是叛徒，从而又无法判断。这个情形非常简易的说明了三模冗余是无法动态容错的。（2）m=1，n=4的情形 n=4，意味着一个司令发送命令给三个副官，m=1意味着他们中有一个叛徒。 首先考虑司令忠诚而副官3是叛徒的情况。

（图6：m=1，n=4中司令忠诚而副官3是叛徒的情形）

倘若司令在OM(1)中给各副官发送的消息都是进攻（A），之后OM(0)时，叛徒副官3给副官1和副官2说他收到的消息是撤退（R）。那么对于副官1（或副官2）来说，他综合司令、副官3和副官2（或副官1）后得到的消息向量都将会是(A,A,R)，利用majority函数之后，将会采用A，满足了IC1和IC2（回顾IC1：所有忠诚的副官遵守一个命令，IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令）。

（图7：m=1，n=4中司令是是叛徒的情形）

倘若司令是叛徒，那么我们已经不需要满足IC2。为方便，我们假设叛徒司令在OM(1)会给三个副官发送的信息是(x,y,z)，其中x，y，z都可以是A或R的任意一种。之后，三位忠诚的副官将会按照OM(0)要求的那样，交换他们收到的信息。

对于副官1，他综合司令、副官2和副官3后得到的消息向量将会是(x,y,z)，可以发现对于其他两个忠实的副官，他们得到的消息向量也将是(x,y,z)。不管x，y，z如何变化，majority(x,y,z)对于三人来说都是一样的，所以三个副官将会采用一致的行动。

（3）m=2，n=7的情形 接下来，我们将讨论m=2，n=7的情形，虽然只是多了一个叛徒，但是这里会出现递归过程，所以会复杂很多。

首先，我们先讨论司令忠诚的情形，假设叛徒为副官5和副官6。

（图8：m=2，n=7中司令忠诚而副官5和副官6是叛徒的情形）

在OM(2)中，司令将攻击命令（A）传给各个副官。在OM(1)中，忠诚的副官们将会发送他们收到的消息（A），但由于副官5和副官6是叛徒，他们将会发送别的信息（比如R）。这时，忠诚的副官们将会采用使用OM(1)中的方法来确定各个v1~v6。例如，对于副官1，他收到了司令传来的命令，他会直接采用majority函数综合司令和其他将军传来的信息吗？他不会，因为这还在OM(1)中，他并不知道司令是不是叛徒，他会利用询问别人的方式来确认将军的命令，但是按照算法他会把司令的命令作为v1（即v1=A）并传给其他人。

接下来他会努力取得其他的v2~v6的值，这时已经在OM(1)中了，副官1绝不会轻易相信别人传来的消息，比如副官2给他传来了命令A，但是他会怀疑副官2传来的消息，所以他用OM(1)大法，问其他人副官2传给了他们什么，副官3和副官4诚实的告诉副官1，副官2给他们传的是A，而这时副官5和副官6又要撒谎了，他们又乱说，我们姑且假定他们传来的是x’和y’吧。这样，终于进入到了OM(0)，这时副官1将会综合其他副官对于v2的反馈，得到向量(A,A,A,x’,y’)，再利用majority函数，得到了v2=A。如下图，这是副官1在OM(1)中得到的信息（x，y等表示了不确定的命令）。

                                                                                                                                                                                 （图9：司令忠诚时副官1在OM(1)中得到的信息）

我们就可以得到副官1的v1~v6向量为(A,A,A,A,x,y)，利用majority函数，副官1最终采用的行动会是A。 类似的，我们可以发现，其他几个忠诚的副官得到的命令向量都会是(A,A,A,A,x,y)，利用majority函数后采用的行动都会是A。所以，我们可以发现忠诚的副官采用的命令都是A（满足IC1），并且和忠诚的将军的命令一致（满足IC2）。至此，您应该已经明白了这个算法是怎么递归的，不管m等于多少，都只是一个算法步骤多寡的问题。 至于司令是叛徒的情形，其实是相似的，这里简单的再提一下便于理解。若您已经明白了算法过程，完全可以跳过。

                                                                                                                                                            （图10：m=2，n=7中司令和副官6是叛徒的情形）

为方便，我们假定了副官6是叛徒。司令在OM(2)中就很鸡贼的给副官1~副官6发送了不同的命令(A,R,A,R,A,x)。在OM(1)中，各副官把自己收到的命令传出去，而（为方便，假定）副官6则给其他副官分别发送了(A,R,A,R,A)。类似于前文推演的那样，考虑副官1，他将司令传来的命令A作为v1后，还会询问其他人传来的命令，由此去确认v2~v6，类似的，我们将之表达为下图：

                                                                                                                                                               （图11：司令反叛时副官1在OM(1)中得到的信息）

如图，我们就可以得到副官1的v1~v6向量为(A,R,A,R,A,A)，利用majority函数，副官1最终采用的行动会是A。类似的，我们可以发现忠诚的副官1~副官5得到的消息向量都是(A,R,A,R,A,A)，最终他们采用的行动都会是A（满足了IC1），而司令是叛徒不需要满足IC2。值得提醒的是，若副官6传递的是(R,A,R,A,R)，那么他们所有人得到的消息向量都是(A,R,A,R,A,R)，此时A和R数量一样多，这并不代表majority不起作用了，他将采用默认值R（回顾前文：majority(v1,…,vn-1)代表了大多数人的命令，若不存在则默认为撤退命令），所有人的行动都会采用R，这同样是满足的。

到此为止，我们已经将口头算法的实例推演进行的很彻底了，若您还有兴趣，可以试一试当n=7，m=3的时候为什么就不能达成一致了，操作是类似的。 3.3.口头协议算法证明 算法的证明思路其实并不复杂，简单的来说，对于一个递归算法，我们使用数学归纳法来证明是最直观而又有效的方法了。我们回顾一下命题：将军总数为n，叛徒数量为m，OM(m)可以实现，在n>3m的情况下，使得：

IC1：所有忠诚的副官遵守一个命令。

IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令。

为了证明整个命题，我们先引入一个针对IC2的引理：

引理：对于任意m和k，如果有超过2k+m 个将军和最多k 个背叛者，那么算法OM(m)满足IC2。

证明：

（1）m=0，而将军是忠诚的，直接满足IC2；

（2）m>0，此时假定OM(m-1)是有效的，那么只需要考虑OM(m)这一轮即可。

n>2k+m，意味着n-1>2k，n-1是除了司令以外的所有副官，而所有副官的数量比叛徒的两倍还多，那他们直接利用majority函数的时候，就可以直接正确得到司令的命令。
可以发现，这个引理说明了如果只需要考虑IC2，将军总数是不需要3倍背叛者之多的，接下来我们回归命题。

证明：

首先考虑司令是忠诚的，令引理中的k=m，直接得到OM(m)可以满足IC2。

这时，我们只用考虑司令是叛徒的状况。同样利用数学归纳法。

（1）m=1，之前我们已经推演过OM(1)可以满足1个叛徒司令，3个忠诚副官的情况；

（2）m>1，那么假设n’>3m’的情况下，OM(m-1)能够满足IC1和IC2。

由于司令是叛徒，在OM(m)中司令会把命令发给各个副官，而这些副官中会有m-1个叛徒。在下一轮中，副官的数量至少有3m个，叛徒数为m-1，很显然3m>3(m-1)，也就是说n’>3m’，根据假设，OM(m-1)可以满足IC1和IC2，尽管司令是叛徒，由于OM(m-1)是有效的，OM(m)这一轮中忠诚的副官可以得到相同的(v1,…,vn-1)向量，所以忠诚的副官将会利用majority函数采用相同的命令，得证。

总结一下，口头协议中，我们始终要求的是相同的(v1,…,vn-1)向量，只要这个向量是相同的我们怎么处理都可以。又由于算法是递归的，所以我们一定需要把这个处理方法变得通用而逻辑有效才行，所以我们才选用了majority函数这个算法。这一点至关重要却又没有这么直观，因为我们的第一反应是要得到相同的majority函数值。但是反过来一想，既然算法是递归的，majority函数值相同不就意味着(v1,…,vn-1)向量相同吗？正确理解递归的思想是使用该算法和利用数学归纳法证明该算法的关键点。

至此，我们已经大致明确了口头协议是怎么回事，可以做到什么不能做到什么，以及这个算法的推演和证明。很多系统都会出现口头协议的情况，即各个系统节点可以把自己的消息准确的发送出去，同时可以知道消息的来源于何处。但是，这个方法的消息并不能追本溯源，这使得在口头协议中至少得四模冗余，我们可以试图找到一个方法，让消息能够追本溯源，可以想象这能够拓宽使用条件，这个方法可以是书面协议。

Part4：书面协议

口头协议中我们讨论了很多，揭示了口头协议的缺点是消息不能追本溯源，这使得口头协议必须在四模冗余的情况下才能保证正确。但是，若能引入一种方法让消息能够追本溯源，情况会不会有所改变呢？这就是书面协议引入的灵感。

除了A1，A2和A3以外，我们在口头协议之上添加一个条件A4，使之成为书面协议

A4：（a）签名不可伪造，一旦被篡改即可发现，而叛徒的签名可被其他叛徒伪造；（b）任何人都可以验证签名的可靠性。

那么，我们先说结论：对于任意m，最多只有m个背叛者情况下，算法SM(m)能解决拜占庭将军问题。也就是说，在使用签名的情况下，书面协议可以打破三模冗余的僵局，使用了签名的情况下，只要知道了叛徒数量，我们就可以利用SM(m)算法解决拜占庭将军问题。

4.1.书面协议算法SM(m)

口头协议算法我们已经讨论过很多了，所以笔者对书面协议尽量简短的介绍。回顾

IC1：所有忠诚的副官遵守一个命令，即一致性。

IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令，即正确性。

我们要找到一个算法SM(m)，不管将军总数n和叛徒数量m，只要采用该算法，忠诚的将军总能达到一致（满足IC1和IC2）。我们用集合Vi来表示i副官收到的命令集，这是一个集合，也就是满足互异性（没有重复的元素）等集合的条件。类似的，我们定义choice(V)函数来决定各个副官的选择，这个函数可以有非常多种形式，他只要满足了以下两个条件：

（1）如果集合V只包含了一个元素v，那么choice(V)=v

（2）choice(o)=RETREAT，其中o是空集

任何满足了这两个条件的函数都可以作为choice()，例如取平均值就可以。我们只需要根据具体情形定义choice()即可，这个非重点，笔者并不加以讨论，您可以自行思考。之后我们会发现SM(m)算法并不是一个递归算法，我们只要让各个副官收到的V集相同，choice(V)也一定能够得到相同的值。

简单解释该算法如下：

初始化Vi=空集合。

（1）将军签署命令并发给每个副官；

（2）对于每个副官i：

（A）如果副官i从发令者收到v:0的消息，且还没有收到其他命令序列，那么他

（i）使Vi为{v}；

（ii）发送v:0:i给其他所有副官。

（B）如果副官i收到了形如v:0:j1:…:jk的消息且v不在集合Vi中，那么他

（i）添加v到Vi；

（ii）如果k<m，那么发送v:0:j1:…:jk:i 给每个不在j1,..,jk 中的副官。

（3）对于每个副官i，当他不再收到任何消息，则遵守命令choive(Vi)。

值得注意的是，如果司令忠诚，由于其签名不可伪造，所有忠诚的副官都将得到一个单点集{v}，他们采用的命令集Vi相同，得到的choive(Vi)也为v，满足了IC1和IC2。

如果司令并非忠诚，只需要满足IC1，但是算法SM(m)使得所有忠诚的副官得到相同的Vi，使用choice()函数后采用的命令也就一定相同。

4.2.书面协议实例推演

司令是叛徒的状况稍难想象，举个例子，n=3，m=1，其中司令是叛徒，这是口头协议不能解决的状况。

                                                                                                                                                                         （图12：m=1，n=3中司令是叛徒的情形）

很显然，副官1得到的V1={A,R}，副官2得到相同的V2={A,R}。他们采用choice函数后得到的命令一定相同。

相似的，n=4，m=2，其中司令是叛徒，这同样是口头协议不能解决的状况。

（图13：m=2，n=4中司令和副官3是叛徒的情形）

副官1和副官2得到的V1=V2={A,R}，他们采用choice函数后得到的命令也相同。即使命令不是布尔值，经过上面的分析框架，也可以得到相似的结论。至于这个算法的证明，有兴趣的读者可以参考Lamport的原文，笔者就不做过多解释了，如有问题仍可与笔者联系。

                                                                                                                                                                        （图14：Lamport在论文中对书面协议算法的证明）

书面协议的本质就是引入了签名系统，这使得所有消息都可追本溯源。这一优势，大大节省了成本，他化解了口头协议中1/3要求，只要采用了书面协议，忠诚的将军就可以达到一致（实现IC1和IC2）。这个效果是惊人的，相较之下口头协议则明显有一些缺陷。

书面协议的结论非常令人兴奋，这不是解决了拜占庭将军问题了吗？但请注意我们在A1~A4中实际上是添加了一些条件的，这使得拜占庭将军问题在这些假设下能够解决，但是在实际状况中却会有一些问题。观察A1~A4，我们做了一些在现实中比较难以完成的假设，比如没考虑传输信息的延迟时间，书面协议的签名体系难以实现，而且签名消息记录的保存难以摆脱一个中心化机构而独立存在。事实上，存在能够完美解决书面协议实际局限的方法，这个方法就是区块链。

区块链源自比特币，不过在这之前，已有多项跨领域技术，皆是构成区块链的关键技术；而现在的区块链技术与应用，也已经远超过比特币区块链。要追溯区块链（Blockchain）是怎么来的，不外乎先想到比特币（Bitcoin），比特币是第一个采用区块链技术打造出的P2P电子货币系统应用，不过比特币区块链并非一项全新的技术，而是将跨领域过去数十年所累积的技术基础结合。

比特币区块链所实现的基于零信任基础、且真正去中心化的分散式系统，其实解决一个30多年前由Leslie Lamport等人所提出的拜占庭将军问题。

1982年Leslie Lamport把军中各地军队彼此取得共识、决定是否出兵的过程，延伸至运算领域，设法建立具容错性的分散式系统，即使部分节点失效仍可确保系统正常运行，可让多个基于零信任基础的节点达成共识，并确保资讯传递的一致性，而2008年出现的比特币区块链便解决了此问题。而比特币区块链中最关键的工作量证明机制，则是采用由Adam Back在1997年所发明Hashcash（杂凑现金），为一种工作量证明演算法（Proof of Work，POW），此演算法仰赖成本函数的不可逆特性，达到容易被验证，但很难被破解的特性，最早被应用于阻挡垃圾邮件。

在隐私安全方面的技术，可回溯到1982年David Chaum提出注重隐私的密码学网路支付系统，具有不可追踪的特性，成为比特币区块链在隐私安全面上的雏形，之后David Chaum也基于这个理论打造出不可追踪的密码学网路支付系统eCash，不过eCash并非去中心化系统。

在区块链中每笔交易，采用椭圆曲线数位签章演算法（Elliptic Curve Digital Signature Algorithm，ECDSA），可追溯回1985年Neal Koblitz和Victor Miller分别提出椭圆曲线密码学（Elliptic curve cryptography，ECC），首次将椭圆曲线用于密码学，建立公开金钥加密的演算法。相较于RSA演算法，采用ECC好处在于可以较短的金钥，达到相同的安全强度。到了1992年，由Scott Vanstone等人提出ECDSA。

区块链最早源于比特币，但区块链的应用却不仅于此。

过去几年也陆续出现许多基于区块链技术的电子货币（统称为Altcoins)，不过随着比特币持续备受争议，各国政府与金融机构纷纷表态，直到近1、2年，大家才终于意识到区块链的真实价值，远超过于电子货币系统。

区块链可结合认许制，以满足金融监管需求

若要将比特币与区块链技术分开来看，最大的不同之处在于，由于比特币为虚拟货币应用，因此面临各国法规的限制，但区块链现在已经可结合认许制或其他方式来管控节点，决定让哪些节点参与交易验证及存取所有的资料，并提供治理架构（Governance Structure）及商业逻辑（Business Logic）两大关键特性。目前区块链可分为非实名制和实名制两种，前者如比特币区块链，后者如台大地的GCoin区块链。现在的区块链已经可结合认许制 (Permissioned)，来配合金融监管所需的反洗钱 (AML) 与身份验证 (KYC) 规范。而银行和金融机构想采用的都是实名制的区块链。

区块链演进阶段

区块链技术随着比特币出现后，经历了几个不同的阶段，常见的分法将比特币视为Blockchain 1.0，为数位货币（Currency）应用，Blockchain 2.0开始出现如智慧资产（Smart Assets）、智慧契约（Smart Contracts）等货币以外的应用，Blockchain3.0则是指更复杂的智慧契约，将区块链用于政府、医疗、科学、文化与艺术等领域。

区块链新创DTCO执行长李亚鑫基于现有的分法进行补充，他认为，Blockchain 2.0以彩色币（Colored Coin）为代表，在区块链上运行Open Assets Protocal，可传递货币以外的数位资产，如股票、债券等。而从Blockchain 2.0之后，可再分出一类属于Blockchain 2.5的应用，包括代币（货币桥）应用、分散式帐本（Distributed Ledgers）、资料层区块链（Data Layers Blockchain）、结合人工智慧（Artificial Intelligent），以及无交易所的国际汇款网路，以Ripple为代表，资料层、分散式储存则以Factom、MaidSafe为代表，Blockchain3.0则以Ethereum为代表。他表示，Blockchain2.5跟Blockchain3.0最大的不同在于，3.0较强调是更复杂的智慧契约，以2.5则强调代币（货币桥）应用，如可用于金融领域联盟制区块链，如运行1:1的美元、日圆、欧元等法币数位化。由于区块链协议几乎都是开源的，因此要取得区块链协议的原始码不是问题，重点是要找到好的区块链服务供应商，协助导入现有的系统。而银行或金融机构得对区块链有一定的了解，才能知道该如何选择，并应用于适合的业务情境。去年金融科技（Fintech）才刚吹进亚洲，没想到才过几个月，一股更强劲的区块链技术也开始引爆，全球金融产业可说是展现了前所未有的决心，也让区块链迅速成为各界切入金融科技的关键领域。

尽管现在就像是区块链的战国时代，不过银行或金融机构要从理解并接受区块链，到找出一套大家都认可的区块链，且真正应用于交易上，恐怕还需要一段时间。这次只比国外晚了半年，引爆点可从台大释出一套自行开发的开源区块链协议GCoin，并宣布将成立金融科技暨区块链中心说起，短短一周的时间，便引发各界高度关注，接着研讨会不断，不过，由于区块链具有较高的技术门槛，大家都知道它拥有许多特性跟好处，但却迟迟处于观望阶段，就连区块链的新创业者，也非常稀少。银行业目前也还卡在门口，除了少数金控开始分享这个议题之外，多数金融业者仍处于试图理解技术面的阶段。

技术演进：区块链是怎么来的

1982年

拜占庭将军问题

Leslie Lamport等人提出拜占庭将军问题（Byzantine Generals Problem），把军中各地军队彼此取得共识、决定是否出兵的过程，延伸至运算领域，设法建立具容错性的分散式系统，即使部分节点失效仍可确保系统正常运行，可让多个基于零信任基础的节点达成共识，并确保资讯传递的一致性，而2008年出现的比特币区块链便解决了此问题。

David Chaum提出密码学网路支付系统

David Chaum提出注重隐私安全的密码学网路支付系统，具有不可追踪的特性，成为之后比特币区块链在隐私安全面的雏形。

1985年

椭圆曲线密码学

Neal Koblitz和Victor Miller分别提出椭圆曲线密码学（Elliptic Curve Cryptography，ECC），首次将椭圆曲线用于密码学，建立公开金钥加密的演算法。相较于RSA演算法，采用ECC好处在于可用较短的金钥，达到相同的安全强度。

1990年

David Chaum基于先前理论打造出不可追踪的密码学网路支付系统，就是后来的eCash，不过eCash并非去中心化系统。

Leslie Lamport提出具高容错的一致性演算法Paxos。

1991年

使用时间戳确保数位文件安全

Stuart Haber与W. Scott Stornetta提出用时间戳确保数位文件安全的协议，此概念之后被比特币区块链系统所采用。

1992年

Scott Vanstone等人提出椭圆曲线数位签章演算法（Elliptic Curve Digital Signature Algorithm，ECDSA）

1997年

Adam Back发明Hashcash技术

Adam Back发明Hashcash（杂凑现金），为一种工作量证明演算法（Proof of Work，POW），此演算法仰赖成本函数的不可逆特性，达到容易被验证，但很难被破解的特性， 最早被应用于阻挡垃圾邮件。Hashcash之后成为比特币区块链所采用的关键技术之一。（Adam Back于2002年正式发表Hashcash论文）

1998年

Wei Dai发表匿名的分散式电子现金系统B-money

Wei Dai发表匿名的分散式电子现金系统B-money，引入工作量证明机制，强调点对点交易和不可窜改特性。不过在B-money中，并未采用Adam Back提出的Hashcash演算法。Wei Dai的许多设计之后被比特币区块链所采用。

Nick Szabo发表Bit Gold

Nick Szabo发表去中心化的数位货币系统Bit Gold，参与者可贡献运算能力来解出加密谜题。

2005年

可重复使用的工作量证明机制（RPOW）

Hal Finney提出可重复使用的工作量证明机制（Reusable Proofs of Work，RPOW），结合B-money与Adam Back提出的Hashcash演算法来创造密码学货币。

2008年

Blockchain 1.0：加密货币

数位货币与支付系统去中心化、比特币：Satoshi Nakamoto（中本聪）发表一篇关于比特币的论文，描述一个点对点电子现金系统，能在不具信任的基础之上，建立一套去中心化的电子交易体系。

2012年

Blockchain2.0：智慧资产、智慧契约

市场去中心化，可作货币以外的数位资产转移，如股票、债券。如Colored Coin便是基于比特币区块链的开源协议，可在比特币在区块链上发行多项资产

2014年

Blockchain 3.0：更复杂的智慧契约

更复杂的智慧合约，将区块链用于政府、医疗、科学、文化与艺术等领域。

2016年

Blockchain 2.5：金融领域应用、资料层

Blockchain2.5：强调代币（货币桥）应用、分散式帐本、资料层区块链，及结合人工智慧等金融应用

Blockchain 3.0：更复杂的智慧契约

拜占庭将军问题”（Byzantine Generals Problem）是一个建立于共识机制解决的实例。拜占庭为过去东罗马帝国的首都，现在位于土耳其的伊斯坦堡。由于当时拜占庭罗马帝国的国土辽阔，基于防御目的，每个军队都分隔遥远，因此将军间只能靠信差传递消息。于战争时，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军，因为唯有达成一致的行动才能获致胜利。将军中若存在叛徒，叛徒可以采取行动以欺骗某些将军进行进攻行动，或致使他们无法做出决定，缺乏一致行动的结果则将注定战事的失利。

类比于区块链上的共识机制，拜占庭消息误传系指区块链上分散式网络中节点所出现的任何错误（如，伪造签名、恶意破坏系统的一致性、超时、重复发送消息等）。共识机制通常具有容错的设计，即使某些节点失败或是缓慢的，分散式网络中节点的独立处理器仍能达成某种精确的相互一致性。但是共识机制具多样种类且其各自特性，并由小表显示的共识机制基本参数来决定。

共识机制基本参数 定义
分散式治理 一个中央节点不能提供交易最终确定
仲裁结构 在预先定义的方式进行节点间讯息交换
身份验证 验证参加身份
完整性 交易完整性的验证
不可否认性 验证发送者应该是交易讯息的真正发送者
隐私 确保只有预期的收件者才能阅读交易讯息
高效容错 网络能高效快速的运行，即使某些节点失败或缓慢
性能 吞吐量，活跃度，可扩展性和延迟
实用拜占庭容错算法（Practical Byzantine Fault Tolerance - PBFT）的共识运作为讯息在分散式网络中节点间互相交换后，由各节点列出所有得到的信息，以大多数的结果作为解决办法。而在PBFT算法中，主要依据法定多数（quorum）的决定，一个节点代表一票，以少数服从多数的方式实现了拜占庭的容错演算。至多容错量以不超过全部节点数的1/3，意即如果有超过2/3的正常节点，整个系统就便可正常运作(R ≥ 3F + 1; R：节点总数，F：有问题节点总数)。

PBFT算法的运作步骤为：

(1)取一个副本作为主节点，其他的副本作为备份；

(2)用户端向主节点发送使用服务操作的请求；

(3)主节点通过广播将请求发送给其他副本；

(4)所有副本执行请求并将结果发回用户端；

(5) 用户端需要等待F+1个不同副本节点发回相同的结果，作为整个操作的最终结果。

因此，PBFT算法对所有非有问题之副本节点的请求执行总顺序可达成一致，据以保证安全性。所有用户端最终都会收到针对他们请求的回复，据以确保活跃度(liveness)。

实用拜占庭容错算法保证安全性与活跃度示意图

与传统的数据库在私有和中心化服务器上进行存储和维护不同，区块链是一种去中心化的，公开分配的并且是透明的。

身份保护是当今数字化世界中的一个常见问题。看似每隔一个星期，头条都会透露一些黑客已经突破了一个中心化服务器，导致数以百万计的财务记录，医疗记录或身份被盗。这个问题在开始好转之前可能会变得更糟。截至2016年，有130亿个设备与互联网相连。这些设备中持有我们的个人信息，银行记录和信用卡号码。到了2020年，这个数字将达到400亿，这将使我们比以往任何时候都更暴露。

从数字来看身份盗窃

每年有大约1500万的美国居民的身份被冒用。

政府维护的记录和企业数据库丢失或被盗，每年额外还有近1亿美国人的个人身份信息处于身份盗窃的风险中。

2014年数据泄露总计达到1540起，导致超过十亿个数据记录被损害。

45%的信用卡诈骗是网上交易，通过网络无需展示卡片。

身份盗窃对美国经济造成的损失总体上估计达到每年1000亿美元。全球损失轻易就达到千亿美元。

去年，近1亿的医疗记录被攻破。

医疗记录可以在暗网上以每条60美元的价格进行购买。社会保障号码只要用15美元就可以买到。

区块链的进入点

数据库成为黑客的主要目标，因为它们上面存有中心化信息。如果加密被破解，黑客也许能够窃取所有正在被存储的信息。区块链技术通过将所有这些数据去中心化，能够为这个问题提供一种独特的解决方案。因此，数据将不会存在于一个单一的服务器上，取而代之的是一个在世界各地的成千上万的计算机维护的分布式公共账本。由此，各种数据攻击将几乎不可能实现，因为没有一个实体在掌控这些信息。

个人用户如何保护他们的数据不受恶意行为的伤害？

“拜占庭将军问题”

从一部电影中挑出一个场景：一个中世纪的城堡正遭受攻击。城堡内200名士兵正在保卫自己的国王。城堡之外有4支军队，各有100名士兵正在等待来自中尉的命令。如果他们不能同时发起进攻，那么他们将会输掉这场战争。领导这些军队的中尉如何能够就同时向城堡发起进攻达成一致？这存在两个变量。一个是由将军创建的‘下午7点进攻’消息命令，需要通过骑马用手传递给每一个中尉。第二个，中尉中可能存在叛徒，可能会试图改变消息，从而输掉战争。因此，将军弄了一个特殊的带锁的盒子，并且有两套钥匙，私有的和公开的。四个中尉都有一个公钥，只能顺时针旋转，看看盒子里是什么。将军拥有私钥，可以逆时针方向旋转，改变盒内的信息。

那个将军拿着这个带锁的盒子，逆时针转动私钥，并放入必要的信息——7pm攻击城堡。盒子然后送往第一个中尉，他拿出自己的公钥顺时针旋转，看到将军发出的7pm攻击命令。然后这个盒子被传送到第二个中尉那里。他决定使用他的公钥逆时针转动，希望改变和破坏里面的攻击命令信息。然而，因为将军的这个非常先进的锁，公钥不会允许这个中尉这样做。信息无法被改变，因此在不被破坏的情况下传递到第三个和第四个中尉那里。攻击最终按照原计划成功发起。

现在，让我们将这与区块链联系起来。你可以将任何有价值的东西存储在一个‘数字锁盒’中。盒子中的内容只能通过一个独特的私钥来打开和改变。盒中的内容然后可以根据需要进行共享，并且不会被改变或者复制。这就是比特币所实现的私有/公共密钥加密的简化架构。

身份验证的未来是什么样子的？

有多个创业公司正在致力于创建区块链身份解决方案。Shocard，由Armin Ebrahimi于2015年创建的公司，正在寻找创建一种移动ID，能够使用加密和比特币公有账本的不可更改性来进行实时验证。Ebrahimi将Shocard视为一种方式，人们可以用来安全和即时地核实自己的保险事故，电子商务供应商，银行或者任何第三方机构等，这些他们必须提供身份信息的机构。

界面

用户可以上传身份证件到Shocard应用。这些文件将被立即存储和加密到区块链。Shocard自己不必存储或持有任何这些文件。文件被密封在区块链上，因此不能被改变。Shocard可以由任何需要知道你的身份的人来认证。例如，如果一家银行需要验证你的身份，你可把你的经过加密的Shocard发送过去。然后，银行核实Shocard数据与区块链上的密封数据匹配。然后，银行创建他们自己与你的Shocard相联系的记录，并使用他们的私钥加密。这样，银行在任何需要的时候就会知道是你。这种验证可以用于账户登录，账户管理，信用卡认证等等。它类似于一个银行保存在文件中的签名卡，用于匹配个人支票上的签名。

银行和旅游行业的使用案例

例1：在登录时，代替输入容易被黑和忘记的用户名和密码，你只需要简单扫描一下来自你的Shocard app的银行网页上的二维码即可。然后，会向你的app推送一个通知，要求提供指纹验证。提供指纹之后，你就会自动登录。

例2：如果你因为账户问题需要呼叫银行客服。传统而言，他们可能会问你一些安全问题。这些问题可能是，你母亲的娘家姓？你的账户号？你的用户名？如果你的账户被黑，这些都可能会被破坏。相反，使用Shocard，一个通知将被发送到您的应用程序，同时与银行运营商通话：通知将要求一个指纹来验证你是谁。指纹被Shocard app验证之后，银行就会确定电话的另一端就是你本人。

例3：乘客使用Shocard APP上传他们的所有旅行文件。这些文件然后会在区块链上进行密封和加密，任何人都可以使用公共密钥来验证它们的真实性。乘客在办理登机手续，机场安检和移民检查站时通过扫描二维码来分享这些信息。也许第一次的时候乘客需要提供原始文件来验证，不过，经常坐飞机的人将能够根据需要使用这个app。

总结

有一点是肯定的，身份盗窃保护服务业将在未来十年内出现激进的变化。共享秘密（用户名/密码）已经变成了一场噩梦。中心化密钥服务器非常危险，墨水签名很容易伪造，文件和身份证是第十九世纪的技术，双因素授权服务往往是不方便和不可靠的。在此之上，到2020年，我们会看到与互联网连接的设备数量增加3倍，使我们比以往任何时候都更暴露给黑客。我并不是宣传区块链技术能够解决一切问题，但这种技术看起来是朝着正确方向的一步。像Shocard, Solidx,和Civic 这样的公司处于这种创新的前沿，而这种创新可能会为整个行业带来颠覆性变化。