链块技术：共识机制，拜占庭容错系统

什么是区块链？

区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。

显而易见，利用区块链构造基于互联网的去中心化账本，需要解决的首要问题是如何实现不同节点上的账本数据的一致性和正确性，即如何达成共识，这就需要借鉴已有的分布式系统中实现状态共识的算法。

在20世纪80年代出现的分布式系统共识算法，是区块链共识算法的基础。

我们从基本的拜占庭容错技术入手，逐步介绍适合于私有链/联盟链和公有链的共识算法。

（一）拜占庭将军问题

问题描述

拜占庭将军问题是20世纪80年代的一个假想问题。

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。

基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。

困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。

在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商达成一致，从而赢取战斗？

区块链网络的记账共识和拜占庭将军问题是相似的：

记账节点——将军

消息传递——信使

恶意节点——拜占庭节点

正常节点——非拜占庭节点

问题假设

应该明确的是，在研究拜占庭将军问题的时候，假定了消息传递的信道是没有问题的，并不去考虑通信兵是否会被截获或无法传达信息等问题，并在这个前提下，去做一致性和容错性相关研究。

问题实质

寻找一个方法，使得将军们能在一个有叛徒的非信任环境中建立战斗计划的共识。

条件定义

回顾问题，一群将军想要实现某一个目标（一致进攻或者一致撤退），但是单独行动行不通，必须合作，达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。

注意，这里“一致性”才是拜占庭将军问题探讨的内容，如果本来叛徒数量就已经多到了问题不可解的地步，这个就是“反叛”的问题了；

同时，我们的目标是忠诚的将军能够达成一致，对于这些忠诚的将军来说，进攻或者撤退都是可以的，只要他们能够达成一致就行。

但是，光靠“一致”就可以解决问题吗？

如果万事俱备，客观上每个忠诚的将军只要进攻了就一定能够胜利，但是却因为叛徒的存在他们都“一致的”没有进攻；

反之，条件不利，将军们不应该进攻，但是却因为叛徒的存在所有人都“一致的”进攻了。

可以发现，只有“一致性”是不足以解决拜占庭将军问题的，我们还需要提出一个“正确性”要求。

这个要求是值得斟酌的，因为如果客观来看或许会有“绝对正确的”判断，但是针对每一个将军，大家的判断或许都不相同，我们如何定义“正确”呢？

我们或许可以简单地说，正确就是每个忠诚的将军都正确的表达了自己的意思，不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。

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

一致性：每个忠诚的将军必须收到相同的命令值vi（vi是第i个将军的命令）

正确性：如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的vi相同。

条件演进

进一步地讲拜占庭将军的问题可以描述为：

一个发送命令的将军要发送一个命令给其余n-1个将军，使得

C1. 所有忠诚的接收命令的将军遵守相同的命令

C2. 如果发送命令的将军是忠诚的，那么所有忠诚的接收命令的将军遵守所接收的命令

（二）拜占庭容错系统

拜占庭容错系统要解决的正是分布式系统中存在恶意节点（即拜占庭节点）时，系统的一致性、正确性等问题（即达成上述C1和C2条件）。

假设分布式系统拥有n台节点，并假设整个系统拜占庭节点不超过m台（n≥3m+1），拜占庭容错系统需要满足如下两个条件：

1. 所有非拜占庭节点使用相同的输入信息，产生同样的结果。在区块链系统中，可以理解为，随机数相同、区块算法相同、原账本相同的时候，计算结果相同。

2. 如果输入的信息正确，那么所有非拜占庭节点必须接收这个消息，并计算相应的结果。在区块链系统中，可以理解为，非拜占庭节点需要对客户的请求进行计算并生成区块。

另外，拜占庭容错系统需要达成如下两个指标：

安全性：任何已经完成的请求都不会被更改，它可以在以后请求看到。在区块链系统中，可以理解为，已经生成的账本不可篡改，并且可以被节点随时查看。

活性：可以接受并且执行非拜占庭客户端的请求，不会被任何因素影响而导致非拜占庭客户端的请求不能执行。在区块链系统中，可以理解为，系统需要持续生成区块，为用户记账，这主要靠挖矿的激励机制来保证。

在分析拜占庭问题的时候，假设信道是可信的。拓展开来，在拜占庭容错系统，普遍采用的假设条件包括：

1. 拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋；

2. 节点之间的错误是不相关的；

3. 节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间里能传达到目的地；

4. 节点之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和破坏信息的完整性。

注意：并非所有的缺陷或故障节点都称为拜占庭节点，拜占庭节点的行为有不可预测、任意性的特点，例如遭黑客破坏，中木马的服务器就是一个拜占庭服务器。

（三）实用拜占庭容错系统

原始的拜占庭容错系统由于需要展示理论上的可行性而缺乏实用性。

另外，算法的复杂度也是随节点的增加而呈指数级增加。

实用拜占庭容错系统降低了拜占庭协议的运行复杂度，从指数级别降低到多项式级别，使拜占庭协议在分布式系统中应用成为可能。

实用拜占庭容错系统是一类“状态机”拜占庭系统，要求系统所有节点共同维护一个状态，所有节点采取的行动一致。

注：这里的状态机可以理解为“系统状态”，以区块链记账为例，系统每新增一个区块，账本就更新到一个新的状态。前面讲过，拜占庭容错系统是一个强一致性协议，每次记账后系统都会达成新的状态。

实用拜占庭容错系统需要运行三类基本协议：

一致性协议：解决如何达成共识

检查点协议：类似于操作系统的还原点

视图更换协议：系统的每个服务器节点在同样的配置信息下工作，该配置信息被称为“视图”。配置信息由主节点确定，主节点更换，视图也随之变化。

我们主要关注支持系统日常运行的一致性协议，该协议要求来自客户端的请求在每个服务节点上都按照一个确定的顺序执行。

一致性协议至少包含：请求（request）、序号分配（pre-prepare）、响应（reply）三个阶段。

根据协议设计的不同，可能包含：相互交互（prepare)、序号确认（commit）等阶段，如下图所示：

假设故障节点个数为m个，而整个服务节点数为3m+1个。

实用拜占庭容错系统中服务节点分为两类：

主节点：全系统有且仅有一个主节点，负责将客户端的请求排序。

从节点：按照主节点提供的顺序执行请求。

上图中，C为客户端，N0~N3为服务节点，N0为主节点，N3为故障节点。协议的节本过程如下：

1. Request：客户端发送请求，激活主节点的服务操作

2. 当主节点接收请求后，启动三阶段的协议以向各从节点广播请求

a) Pre-Prepare：主节点给请求赋值一个序列号n，广播序号分配消息和请求消息，并构造PRE-PREPARE消息给各从节点

b) Prepare：从节点接收PRE-PREPARE消息，并向其他服务节点广播PREPARE消息

c) Commit：各节点对视图内的请求和次序进行验证后，广播COMMIT消息，执行收到的客户端的请求并给客户端以响应

3.Reply：客户端等待来自不同节点的响应，若有m+1个响应相同，则该响应即为运算的结果。

其中，主节点给请求赋值一个序列号是为了保证输入信息的一致性，从而保证执行的一致性。

从节点将收到的消息向其它节点广播，使得各个节点可以验证所收到的信息，保证输入信息一致，从而保证计算后的输出一致。

所有从节点将请求返回给用户，使得用户能够知晓请求执行的完成情况。

根据上述流程，在n≥3m+1的情況下，一致性是可能解決的，其中，n为总节点数，m为恶意节点总数。如下所示：

由此可以看出：实用拜占庭容错系统能够容纳将近1/3的拜占庭节点。实用拜占庭容错系统在很多场景都有应用，在区块链应用中，一般适合于对强一致性有要求的私有链和联盟链场景。

例如，在IBM主导的区块链超级账本项目中，实用拜占庭容错系统是一个可选的共识协议。

文章声明：本文为火星财经专栏作者作品，版权归作者所有，不代表火星财经观点。