《迅雷链精品课》第十课：共识算法理论基础

上一节课我们学习了区块链 P2P 网络，今天我们将学习共识算法理论基础，通过这节课我们将了解分布式系统面临的挑战，共识算法的理论基础等内容。

在学习课程的时候，你也可以领取 BaaS 平台为期一个月的试用机会，免费使用高性能区块链服务（点击链接即可免费领取https://blockchain.xunlei.com/baas/try.html）。课程学习结合实践操作，让你迅速成为区块链大牛！

*以下为第十课的内容~

第十课 共识算法理论基础

1. 分布式系统面临的挑战

区块链是一个分布式系统，分布式系统碰到的最为基础的问题就是一致性问题。在分布式系统中，一致性是指：对于系统中的多个服务节点，给定一系列操作，在协议（往往通过某种共识算法）保障下，试图使得他们对处理结果达成某种程度的一致。

如果一个分布式系统无法保证处理结果一致的话，那任何建立于其上的业务系统都无法正常工作。而要保障系统的一致性，则需要依赖于共识算法。讨论共识算法之前，我们需要先来了解下分布系统的一些特性和基础理论。

相对于单机系统，分布式系统面临的主要挑战包括：

1) 资源受限：节点间的通信需要通过网络，而网络存在带宽限制和时延，节点也无法做到瞬间响应和高吞吐。

2) 故障的独立性：系统的任何一个模块都可能发生故障，如节点之间的网络通讯是不可靠的，随时可能发生网络故障或任意延迟；节点的处理可能是错误的，甚至节点自身随时可能宕机。

3) 不透明性：分布式系统中任何组件所在的位置、性能、状态、是否故障等情况对于其它组件来说都是不可见的、也无法预知的。

4) 异步通信：分布式系统的目的，是为了更好的共享资源。同步调用会让系统阻塞，因此节点间通信通常设计成异步的。

5) 缺乏全局时钟：在程序需要协作时，它们通过交换消息来协调它们的动作。紧密的协调经常依赖于对程序动作发生时间的共识，但是，实际上网络上计算机同步时钟的准确性受到极大的限制，即没有一个一致的全局时间的概念。这是通过网络发送消息作为唯一的通信方式这一事实带来的直接结果。

由于上述挑战的存在，分布式系统中的一致性保证机制是分布式系统设计中最关键也是最有难度的领域，分布式系统中关于一致性的理论基础已经比较完善，在理论指导下，学术界和业界都提出了很多的共识算法试图解决分布式系统中的一致性问题。

接下来我们先了解下分布式系统中关于一致性的理论基础，再基于理论来分析几个被区块链项目所广泛采用的一致算法。

2. 共识算法的理论基础

2.1. FLP 不可能定理

因为同步通信中的一致性被证明是可以达到的，因此一直有人尝试各种算法解决异步环境的一致性问题。然而 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表了一篇论文《Impossibility of Distributed Consensus with One Faulty Process》，提出并证明了一个定理，即“FLP 不可能定理”：

在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

FLP 不可能定理论证了最坏的情况是没有下限，要实现一个完美的容错的异步的一致性系统是不可能的。

2.2. CAP 定理

但 FLP 不可能定理只是说明了 100%保证一致性是不可能的，这并不影响我们对分布一致性的探索。例如 99%以上的一致性还是完全有可能做到的；又如放宽时间限制，即要求系统在一段时间后最终达到一致性(达不成一致则系统不可用)，也是可以做到的；再如，将部分通信改成同步的，牺牲一定的可用性和吞吐量，就能得到一个一致性较强的协议。

CAP 定理即描述了分布式系统中关于一致性和可用性的关系：

一个分布式系统最多只能同时满足(强)一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项要素中的两项。

CAP 定理起源于计算机科学家埃里克·布鲁尔在 2000 年的分布式计算原则研讨会（Symposium on Principles of Distributed Computing（PODC））上提出的一个猜想。在 2002 年，麻省理工学院（MIT）的 Nancy Lynch(跟证明 FLP 定理的 Lynch 是同一位) 和 Seth Gilbert 发表了布鲁尔猜想的证明，使之成为一个定理。

对于分布式数据系统，分区容错性是基本要求，因为故障的存在是必然的。因此设计分布式数据系统，就是在一致性和可用性之间取一个平衡。

2.3. 拜占庭将军问题

拜占庭将军问题（Byzantine Generals Problem），是由 Leslie Lamport 在其同名论文中提出的分布式对等网络通信容错问题，对网络中存在作恶节点的情况进行建模。由于作恶节点的存在，拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

Lamport 在其论文中描述了如下问题：

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

但问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。

上述的故事映射到计算机系统里，将军便成了计算机，而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全，却没办法单纯的用密码学与数字签名来解决。因为不正常的电压仍可能影响整个加密过程，这不是密码学与数字签名算法在解决的问题。因此计算机就有可能将错误的结果提交去，亦可能导致错误的决策。

在分布式对等网络中需要按照共同一致策略协作的成员计算机即为问题中的将军，而各成员计算机赖以进行通讯的网络链路即为信使。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况。

2.4. DSS 猜想

不同于中心化的分布式系统，去中心化是区块链系统的一个核心特性。去中心化的系统中，为了保证数据可信，需要所有节点参与共识、避免被攻击（如 51%攻击）、任何节点都要有能力验证交易的合法性、所有交易要按顺序执行和验证、所有节点都要保存所有的交易数据等。

在分布式系统中，可扩展性是指系统的总体性能随着节点的增多而提升。在中心化的分布式系统设计中，可扩展性是必须保证的、最基本要求之一。对于中心化的系统，要保证可扩展性也是相对简单的。

而去中心化的全量共识和存储的要求，是难以扩展的。因为若要可扩展性，就不能要求节点执行全量、全量存储，而是要分散计算和存储，每个节点只保存部分数据，即每个交易数据只存储在少数节点中，但这样一来，安全性就无法保证，因为攻击者只要攻击少数节点，即能控制区块数据。例如数据分成 100 份保存在不同节点，那攻击者只要实施 1%攻击，即能控制其中 1 份区块数据，攻击难度大大降低。

由于去中心化的要求，区块链的分布式系统也有自身特有的理论，其中一个描述了去中心化与可扩展性之间的矛盾，它尚未被严格证明，只能被称为猜想，但实际系统设计过程中却能感觉到时时受其挑战：

DSS 猜想：去中心化(Decentralization)，安全性(Security)和可扩展性(Scalability)这三个属性，区块链系统最多只能三选其二。

上图演示了区块链如何在这三个因素之间作选择及对应的策略，例如若若要满足安全性与去中心化，则需要所有节点参与共识、计算、全量存储，但由此带来的问题是失去可扩展性，也就是系统的总体性能无法随着节点的增多而提升；若要满足可扩展性与安全性，则需要中心化管理，需要保证参与共识的节点是可信的；若要满足可扩展性与去中心化，则采用分散存储、计算的策略，不做全量共识，则攻击网络的难度降低，安全性难以保证。

2.5. 共识算法应该满足的条件

尽管算法多种多样，可以根据需要采用各种策略，但大家公认的理想的共识算法应该满足的条件包括：

1) 可终止性（Termination）：一致的结果在有限时间内能完成。

2) 共识性（Consensus）：不同节点最终完成决策的结果应该相同。

3) 合法性（Validity）：决策的结果必然是其它进程提出的提案。

3. 小结

本节课我们了解了分布式系统面临的主要挑战之一是一致性问题，这个问题的由来和一些理论基础。区块链由于去中心化的特性，需要考虑作恶节点的存在，其共识算法的设计更加具有挑战性。下节课我们将会讨论一些区块链系统常用的一些共识算法。

*恭喜完成第十课的学习，第十一课我们将继续深入学习区块链常用的共识算法，欢迎关注~