原创 THU学生区块链
点击“阅读全文”，观看完整视频
【《区块链系列课程》2.2 拜占庭容错协议-哔哩哔哩】https://b23.tv/7i2UIhV
本系列课程是清华大学学生区块链协会THUBA推出，由PlatON赞助的区块链课程，涵盖了从区块链基础学习到深度原理研究等方面。
当我们讨论区块链共识的时候，经常被人提起的就是拜占庭将军问题。拜占庭将军问题是分布式系统当中非常经典的问题，近年来由于区块链行业的发展，存在恶意节点的共识算法的探索和研究也逐渐收到了人们更多的关注。区块链网络的本质就是一个分布式系统，在存在恶意节点的情况下，希望整个系统当中的善良节点能够对于重要的信息达成一致，这个机制通常被称作共识机制（Consesus）。而上述问题的本质就是拜占庭将军问题。
为了防止大家概念的混淆，这里会给大家区分一下崩溃容错协议（Crash Fault Tolerant）和拜占庭容错协议（Byzantine Fault Tolerant），两者最大的区别在于安全假设的不同，崩溃容错协议针对的是系统当中存在故障节点的情况，计算机节点可能会崩溃宕机，常见的协议有Paxos和Raft。
而拜占庭容错协议所要解决的问题更加困难，针对的是系统中存在恶意节点的情况，恶意节点可能会故意停止运行，也可能故意发送错误的信息阻碍正常的计算机节点之间达成共识，常见的协议有PBFT和Hotstuff。
# 1. 拜占庭将军问题
那么接下来我们开始正式介绍拜占庭问题。
拜占庭将军问题是由莱斯利·兰伯特（Leslie Lamport）在其1982 年发表的同名论文当中提出的分布式对等网络通信的容错问题。
拜占庭帝国就是东罗马帝国， 东罗马帝国曾经经历过一个繁荣发展的时期，地域十分辽阔。而拜占庭将军问题是一个虚构的例子，我们一起来想象这样的一个情景，拜占庭帝国的军队在外分别有一个将军来指挥，将军们只能通过信使来相互交流。
将军们观察到敌人驻扎的城池，这些将军们需要制定一个共同的行动计划。由于敌人的战斗力比较强，只有大家共同行动，才能获得战斗的胜利，如果单打独斗，就有可能面临失败的风险。但是，拜占庭将军当中出现了叛徒，会通过信使发送虚假情报的方式，试图阻止忠诚的将军达成统一意见。
为了我们方便分析，假设一共有n个将军，其中有一个指挥官，可以发出一个进攻或者撤退的命令，之后所有的将军要为这个命令投票，目标是希望：
1.所有忠诚的将军能够达成共识。
2.如果指挥官是忠诚的，那么所有忠诚的将军会遵守这个指挥官的命令。
这里稍微强调一下，这里的忠诚只是用来区分己方阵营和敌方阵营的一种说法，现实情况中，忠诚指的是未出现宕机或者被黑客入侵的计算机。
通过简单的分析可以发现：实际上如果这个指挥官是一个忠诚的指挥官，那么只要别人能验证命令是指挥官发出来的，然后按照命令的要求进攻或者撤退，那么就可以达成共识。
但是问题恰恰在于这个指挥官本身也有可能是叛徒，当指挥官是叛徒时，有可能给不同的将军发送不同的命令，从而造成将军之间行动策略的不一致。所以，拜占庭问题变得复杂和有趣起来。
上述的事例是一种形象生动的类比，在分布式系统当中，将军就是计算机节点。其中有一部分计算机节点可能本身就是恶意节点，或者由于计算机节点的本身出现的问题导致发送了错误的信息，信使代表的是计算机节点之间通过网络发送的信息。由于通信网络本身的不可靠，可能导致传送信息的损坏，或者没有办法传送信息。而拜占庭将军问题，就是要在上述种种困难和问题当中，提出一个能够让网络当中的忠诚节点对于全体协作的策略达成一致，通常把这个过程叫做达成分布式系统的共识。
# 2. 拜占庭容错问题的基本假设
经过之前的分析，我们会很自然地想到，需要对网络的条件以及对于恶意节点的占比需要进行一个系统的假设。因为如果所有的信息在不可靠的信道当中都无法送到，或者说恶意节点占比是100%，那么我们讨论这个问题是没有意义的。
通常会假设恶意节点小于某一个固定的值， 然后以此作为前提条件进行共识算法的设计，例如比特币的工作量证明假设了恶意节点数量小于1/2, 实用拜占庭容错算法恶意节点数量小于1/3。
对于网络条件来说，通常有如下的三种假设模型的分类，在不同的模型之下会有不同的共识算法的方案。
这三类分别是：
· 同步模型（Synchronous Model）
·部分异步模型（Partial Asynchronous Model）
· 异步模型（Asynchronous Model）
在同步网络的模型中，网络当中的传送消息的延迟小于某个确定的值，这个值可以被参与这个分布式系统的节点所知道。
在部分异步的网络模型当中，网络当中传送的消息的延迟小于某一个值，也就意味着消息一定能够在某个确定的时间之后传送到，但是这个值的是参与分布式系统的节点所不知道，这也就意味着分布式系统当中的节点无法利用这个值来设计等待机制。
在异步的网络模型中，信息传送的时间可以无限大，只保证信息最终能够传送到。根据FLP不可能原理：在网络可靠、但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法（No completely asynchronous consensus protocol can tolerate even a single unannounced process death）。当然这是一种学术的理论分析，在工程当中，某次共识的失败之后多尝试几次很大程度上就成功了。在这种网络模型当中的典型算法代表是：HoneyBadgerBFT。感兴趣的朋友可以进一步研究，之后的内容会主要集中在同步模型和部分异步模型当中。
# 3.解决拜占庭将军问题的算法
在存在恶意节点的情况下依然能够达成共识的特性叫做拜占庭容错（Byzantine Fault Tolerant ）。解决拜占庭将军问题的方案一般叫做拜占庭容错协议或者拜占庭容错算法。
实际上从1982年这个问题提出以来有许许多多的共识算法被提出。
下面的这个表格是从2019年发表的hotstuff论文当中截取的，展示了各种各样的拜占庭容错协议。最左侧是具体协议的名称， 右侧罗列了一些具体步骤的时间复杂度和一些协议的性质，感兴趣的朋友可以阅读一下hotstuff的论文[4]
# 3.1 实用拜占庭容错算法
首先来重点介绍的是实用拜占庭容错协议 (Practical Byzantine Fault Tolerance) [5]。PBFT协议是针对部分异步网络设计的，假设恶意节点的数量小于1/3
如下是实用拜占庭算法流程的一个展示，突出的特点是三阶段提交，也就是分为了预先准备，准备和提交三个阶段
接下来我们以总结点数为4为例，来为大家解释一遍这个流程。
在预准备阶段，这个红色的Primary代表的就是指挥官，指挥官向其他的将军来发送自己签名过的行动信息。
在准备阶段，各个将军收到信息后决定是否接受提议，如果接受提议就发送带有自己签名的预备信息发给所有的将军，如果不赞成就不发送任何讯息。
发出准备信息的将军就会进入到准备阶段。
准备阶段的将军如果决定要执行该指令，就发送带有签名的执行讯息发送给所有的将军，如果不执行就不发送任何的信息；发出执行讯息之后就开始执行阶段，一个将军如果收到3条以上的执行信息，就开始执行信息内容，这代表该提议取得了共识。执行讯息后的将军进入到已执行的状态，并且将执行结果返回。返回后结束这一个回合。
我们通过分析会发现，上述流程的正确执行依赖于指挥官是一个诚实的节点，如果是恶意节点，那么就需要进行换届，换届的流程是按照编号从0到1，到2，到3，再到0进行轮流换届。
· 每个将军从收到“预备”讯息后开始计时，转为“已执行”状态后结束计时。
如果在计时后T时间内未执行讯息，则该将军可以发送“视图切换”(View-change)讯息，讯息内容包含新的代数(目前代数+1)以及其他重要讯息。
如果指挥官未提案，则每个诚实的验证者最终都会因为超时而发出视图切换的讯息。
· 新指挥官若收到3则以上“视图切换”讯息，则新指挥官可以发送“新视图”(New-view)讯息。讯息内容包含新代数、所有具有“已预备证明”且尚未被执行的“就位”讯息，以及其他讯息。
· 各验证者收到“新视图”讯息后，逐一针对尚未执行的“就位”讯息进行投票流程。
· 接下来由新指挥官负责接收拜占庭将军（外界）的命令。
原文摘录了 参考文件当中的内容：
当然上述所陈述的是一种典型的指挥官作恶的情况，指挥官也有可能给不同的将军发送不同的命令，其他将军可以相互之间的通信来确认指挥官的是否是忠诚的节点。当然上面陈述的是核心的思路，面对其他情况PBFT协议也有更加细节的设计。
# 4.拜占庭容错在区块链当中的应用
区块链共识就是在有一定比例的恶意节点的情况下，在区块链系统当中的节点要达成一致的过程。实际上本质就是一个拜占庭将军问题，现在区块链共识算法主要可以分成两大派别，第一派是在工作量证明的基础上进行各种改进，第二派是在经典的BFT算法的基础上进行一定的改进
当然这两派之间并没有说一个非常明确的优劣，因为一个成熟的区块链共识算法往往需要考虑很多个方面的问题，在一系列的条件当中进行取舍。
课程总结
本节课是THUBA推出的区块链系列课程第二章共识协议介绍的第二节课，我们介绍了拜占庭容错共识算法，下次课程我们将会介绍工作量证明协议，感谢大家的观看！
参考资料
1.维基百科 ：拜占庭将军问题
https://zh.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98
2.维基百科：东罗马帝国
https://zh.wikipedia.org/wiki/%E6%9D%B1%E7%BE%85%E9%A6%AC%E5%B8%9D%E5%9C%8B
3.snow white 共识算法团队的 Elaine Shi 的text book Foundations of Distributed Consensus and Blockchains
http://elaineshi.com/
4. haichaozhu的博客（algorand员工）
https://www.haichaozhu.com/consensus-introduction/
5. A Survey of Distributed Consensus Protocols for Blockchain Networks Yang Xiao , Student Member, IEEE, Ning Zhang , Member, IEEE, Wenjing Lou , Fellow, IEEE, and Y. Thomas Hou , Fellow, IEEE
6. https://yeasy.gitbook.io/blockchain_guide/04_distributed_system/flp
7. 图片来自网络
https://charlesliuyx.github.io/2018/03/03/%E3%80%90%E5%8C%BA%E5%9D%97%E9%93%BE%E3%80%91%E5%A6%82%E4%BD%95%E8%A7%A3%E5%86%B3%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98/
8.https://medium.com/taipei-ethereum-meetup/intro-to-pbft-31187f255e68
9.https://lessisbetter.site/2020/03/22/why-pbft-needs-viewchange/
END
文稿&视频 | ddy
编辑 | 土BA
审核 | Zeo Celia
发布者：PlatONWorld-M6，转载请注明出处：https://platonworld.org/zh/?p=10917
