为什么拜占庭系统因为区块链才火起来？

拜占庭系统发展到今天，已经30余年了，直至2009年中本聪以比特币和区块链的模型，重新优化了拜占庭问题的解决方案，拜占庭系统才逐渐被大众所熟知。既然拜占庭问题可以就人类伟大的信任决策问题达成共识协议，那么为什么区块链技术出现之前，拜占庭系统没有引起大家的关注？区块链真正做了哪些改变呢？

小资料：

拜占庭问题起源于1982年，由Lamport教授首次提出，其实它可以简单的理解成：3个或者更多的将军共同决定进攻还是撤退的问题。

在这个决策过程中，如果一个将军发布命令，其他的人作为将军的下属，分别决定进攻还是撤退。但是如果一个甚至多个将军或者下属叛变，决策就会出现问题，无法达成一致的行动。如果司令叛变，他可能会让一个下属进攻，另一个撤退。同样，如果一个下属叛变，他可能告诉其他的下属说司令让他进攻，而告诉另一个下属说司令让他撤退，这样就无法达成一致的行动。拜占庭系统正是为了在这个复杂的环境中，取得一致决策而设计。

我们之前创业做的业务主要是帮助企业快速定位App上线后，并发压力加大导致的使用缓慢，崩溃等系统问题的原因。所以积累了大量的业务数据，所以应用了各类的分布式系统的方案。今年，我们团队主要在做Lamba分布式存储的业务，是要解决区块链中DApp数据没有分布式存储可用的痛点。所以，我们完整的经历了分布式系统到区块链的演进过程。对于拜占庭系统的变化分享给大家。

一、N>=3f+1就可以解决拜占庭问题

首先。我们先来理解拜占庭将军问题能够被解决的客观限制N>=3f+1。也就是说，如果拜占庭将军问题的节点数为N<=3f，那么拜占庭将军问题将无法解决，我们以3个节点为例来推导：

在左边的场景中，下属P3有故障;对于右边的情况，司令P1有故障。我们可以看到两个回合的信息交换：司令发送的值和两个中尉相互发送的值。数字前缀表面消息来源，并且给出不同的回合数。

在左边的场景中，P2接受到了2个不同的值（v，u），但是不知道那个是司令传来的。因此无法做出决策。

在右边的场景中，司令有错误发送了2个不同的值。P3也收到了2个不同的值，因此P3也无法判断哪一个是正确的。

当解决拜占庭将军问题的节点数量为N>=3f+1时，我们再来推导一下上述的问题，以N>=4，f=1的场景为例：

当出现左图的场景时，majority函数（最多返回为最终结果）可以取最多数值作为下属的最终决定值。因此下属可以就决策达成一致：

l P2 决定 majority（v,u,v）=v

l P4决定majority（v,v,w）=v

在右图的场景中，司令是错的，但是正确的3个下属节点可以达成一致：

P2, P3, P4决定majority（u,v,w）= ⊥（表示没有占多数的值存在）

这个推导由Lamport教授在1982年时完成，看到这里我们很容易理解，从逻辑的角度解决拜占庭问题的方法其实非常简单，我们只需要决策的节点数量为 N>=3f+1即可。

但是，为什么拜占庭系统在这么多年内中没有被广泛的使用和认知呢？

尽管拜占庭系统可以就人类信任决策的问题达成最终一致共识，有很大的商业应用场景，但是当我们想应用时，却发现系统是非常低效的。我们知道每一轮决策的代价是消息传递的轮数以指数级的方式增长，因此使用这个办法解决拜占庭问题，因为效率的影响也无法在实际业务中得到应用。

二、拜占庭系统的技术演进

PBFT拜占庭系统

随着时间的发展，效率问题一直是拜占庭系统技术演进的主要方向，Castro 和Liskov 在1999 年提出了Practical Byzantine Fault Tolerance（PBFT）系统，首次将拜占庭协议的复杂度从指数级降低到多项式级别，使拜占庭协议在分布式系统中应用成为可能。

PBFT 的一致性协议如图所示，每一个客户端的请求需要5 个阶段才能完成。其通过采用两次两两交互的方式，在服务器达成一致之后再执行客户端的请求。由于客户端不能从服务器端获得任何服务器运行状态的信息，因此PBFT 协议中主节点是否发生错误只能由服务器监测。如果服务器在一段时间内都不能完成客户端的请求，则会触发视图更换协议（即节点切换）。

PBFT 采取的设计思路是将所有的工作都放在服务器端进行，例如达成一致性、监测拜占庭主节点等等。因此它的问题就是，尽管复杂度相对于Lamport模型已经降低了，但是一致性协议设计依然很复杂，其中有两个阶段需要服务器之间的两两交互，数据的处理量大，而且计算复杂。

HQ拜占庭系统

于是Cowling等人在2006年HQ来改进PBET，下图为HQ模型的原理图：

我们会看到在HQ协议通信模型中，取消了主节点选择的问题。客户端向所有的节点发出请求，并在Write 1阶段中检查是否有3f+1个节点（最少决策节点数）中的2f+1，有共同的返回值。如果有，那么就判定服务器处于相同的状态中。

在HQ模型中，将请求分成2个阶段。第一个阶段，当客户端发送请求的同时收集服务器的状态，如果有2f+1台以上的服务器处于相同状态，并能够执行客户端的请求，那么客户端才执行第二阶段的操作，暨发送指令，让服务器执行的客户端请求。否则说明请求遇到竞争，将执行PBFT的流程。

所以HQ协议通信模型并没有改变PBFT的架构，只是当客户端发送请求，并且没有竞争的情况出现时，这个模式才有效。

基于Speculation的拜占庭系统

Dahlin 等人在2007 年提出了Zyzzyva 和Zyzzyva5 协议，将Speculation 技术引入了拜占庭协议。因为Zyzzyva协议客户端不需要等待服务器交互确认，所以极大程度的提高了拜占庭系统的性能。

其主要思想是：服务器绝大部分时间处于正常的状态，因此不用每一个请求都在达成一致性之后再执行，只需要在错误发生之后再达成一致性即可。

与传统的协议相比，Speculation 机制的不同主要在于一致性协议部分。下图为Speculation 的执行流程，服务器收到客户端的请求之后，并不像传统的协议一样首先进行代价较大的两两交互，而是直接执行了客户端的请求。

只要客户端接收到所有服务器反馈的信息（执行结果、服务器状态、执行历史等），并且这些信息是一致的，客户端认为结果正确，并返回给上层应用;否则，客户端在接收到 2f+1 服务器反馈的信息后，就执行一个序号确认的阶段，告诉至少f+1 台非拜占庭服务器，已经有至少f+1 台非拜占庭服务器执行了请求。

总的来说，在Speculation 中，如果服务器执行结果是一致的，那么客户端采用这个结果。如果不一致，那么客户端丢弃这个结果，并且反馈给服务器触发视图更换协议切换主节点。这样虽然可能暂时导致系统不一致，但是并不会影响非拜占庭的客户端请求的执行。

如果客户端是拜占庭的，那么即使系统结果不一致也没有关系。如果客户端是非拜占庭的，发现系统不一致之后，一定会触发视图更换协议将系统重新调整，从而确保系统的一致性状态。

Speculation技术单一请求所需的阶段数较少，从理论上来说达到了最优，降低了系统的响应延时。除了基于客户端的Speculation技术以外，2009年时也提出了基于客户端的Specutaion技术，其本质是改进型的Zyzzyva 算法，核心思想是客户端不需要收到所有的服务端返回再执行操作，客户端再收到的第一个服务器请求后，就执行响应。当系统没有拜占庭节点时，这极大的优化了系统的效率，但是当拜占庭节点出现时，大规模的部署中依然存在效率问题。所以尽管有广阔的商业前景，拜占庭系统一直没有受到主流媒体的追捧。

三、区块链对拜占庭将军问题的优化

我们知道，区块链的很大创新就是进一步优化了解决大规模节点部署时的拜占庭系统的效率。

拜占庭将军问题的难点在于，任意时间，一个节点都要考虑面对多个提案进行决策的问题。

区块链优化了这个模型，引入了POW机制，在同一时刻通过竞争出块的方式，只允许一个节点发出请求。同时通过非对称加密技术，保证了消息接受方可以确认发送方的身份，系统也变成了可信的分布式网络。

此外，区块链与以往的纯粹算法演进来优化拜占庭问题的方式不同。区块链同时引入了经济模型，让拜占庭的犯错成本为负数。我们知道在安全领域的一个基本观点是，攻击的收益必须大于成本。

在区块链中，下一个节点由谁作为将军，由POW工作量证明来决定。如果要做叛徒，攻击整个网络，需要付出相应的成本，而这个成本在比特币的PoW（Proof of Work）工作量共识机制下，就是要掌握整个网络50%以上的算力。换句话说，有50%以上的叛徒才行，这是比PBFT高得多的容错率。从经济学的角度来说，如果真的掌握那么大的算力的话，用这些算力维护网络（诚实地挖矿）获得的收益其实会高于破坏网络。