共识算法详解

区块链架构是一种分布式的架构。其部署模式有公共链、联盟链、私有链三种，对应的是去中心化分布式系统、部分去中心化分布式系统和弱中心分布式系统。

分布式系统中，多个主机通过异步通信方式组成网络集群。在这样的一个异步系统中，需要主机之间进行状态复制，以保证每个主机达成一致的状态共识。然而，异步系统中，可能出现无法通信的故障主机，而主机的性能可能下降，网络可能拥塞，这些可能导致错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议，以确保各主机达成安全可靠的状态共识。

利用区块链构造基于互联网的去中心化账本，需要解决的首要问题是如何实现不同账本节点上的账本数据的一致性和正确性。这就需要借鉴已有的在分布式系统中实现状态共识的算法，确定网络中选择记账节点的机制，以及如何保障账本数据在全网中形成正确、一致的共识。

在20世纪80年代出现的分布式系统共识算法，是区块链共识算法的基础。我们下面从基本的拜占庭容错技术入手，逐步介绍适合于私有链/联盟链和公共链的共识算法。

一、拜占庭容错技术

拜占庭容错技术（Byzantine Fault Tolerance，BFT）是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为，并满足所要解决的问题的规范要求。

二、拜占庭将军问题

拜占庭容错技术来源于拜占庭将军问题。拜占庭将军问题是Leslie Lamport在20世纪80年代提出的一个假象问题。拜占庭是东罗马帝国的首都，由于当时拜占庭罗马帝国国土辽阔，每支军队的驻地分隔很远，将军们只能靠信使传递消息。发生战争时，将军们必须制订统一的行动计划。然而，这些将军中有叛徒，叛徒希望通过影响统一行动计划的制定与传播，破坏忠诚的将军们一致的行动计划。因此，将军们必须有一个预定的方法协议，使所有忠诚的将军能够达成一致，而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说，拜占庭将军问题的实质就是要寻找一个方法，使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识。在分布式系统中，特别是在区块链网络环境中，也和拜占庭将军的环境类似，有运行正常的服务器（类似忠诚的拜占庭将军），有故障的服务器，还有破坏者的服务器（类似叛变的拜占庭将军）。共识算法的核心是在正常的节点间形成对网络状态的共识。

求解拜占庭将军问题，隐含要满足以下两个条件：

1）每个忠诚的将军必须收到相同的命令值vi（vi是第i个将军的命令）。

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

于是，拜占庭将军问题的可以描述为：一个发送命令的将军要发送一个命令给其余n-1个将军，使得：

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

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

Lamport对拜占庭将军问题的研究表明，当n>3m时，即叛徒的个数m小于将军总数n的1/3时，通过口头同步通信（假设通信是可靠的），可以构造同时满足IC1和IC2的解决方案，即将军们可以达成一致的命令。但如果通信是可认证、防篡改伪造的（如采用PKI认证，消息签名等），则在任意多的叛徒（至少得有两个忠诚将军）的情况下都可以找到解决方案。

而在异步通信情况下，情况就没有这么乐观。Fischer-Lynch-Paterson定理证明了，只要有一个叛徒存在，拜占庭将军问题就无解。翻译成分布式计算语言，在一个多进程异步系统中，只要有一个进程不可靠，那么就不存在一个协议，此协议能保证有限时间内使所有进程达成一致。

由此可见，拜占庭将军问题在一个分布式系统中，是一个非常有挑战性的问题。因为分布式系统不能依靠同步通信，否则性能和效率将非常低。因此寻找一种实用的解决拜占庭将军问题的算法一直是分布式计算领域中的一个重要问题。