拜占庭将军问题详解

也许很多人听过拜占庭将军问题,但不知道是什么意思,本文查阅大量相关资料,从起源、面临的问题到解决的方案,系统的阐述一下。希望对你有用。

 拜占庭将军问题详解

 

拜占庭

拜占庭(Byzantine)位于今天土耳其的伊斯坦布尔,是东罗马帝国的首都。

拜占庭将军问题起源


由于东罗马帝国疆域极为辽阔,坐拥巨额财富,多位将军率领各自的部队驻扎在帝国各处,防御还是攻击,都需要多名将军的合作。

由于疆域辽阔,每个军队相隔甚远,将军与将军之间靠信差传消息。要想取得战争的胜利,必须达成一致的共识,才有足够的把握去采取行动。

但是,在军队内有可能存有叛徒和敌军的间谍,影响将军们的决定又扰乱整体军队的秩序。在采取行动时,结果并不代表大多数人的意见。

这时候,在得知有叛徒和间谍的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议?所以拜占庭将军问题就此形成。


拜占庭将军问题:也就是达成共识的问题

1982年,拜占庭将军问题是由莱斯利·兰伯特等人提出来的,这主要说的是点对点通信中的基本问题,也是一个协议问题、达成共识的问题。

拜占庭的n个将军围攻一个敌人,n个将军包围着这个敌人,由于他们在不同的地方。忠诚的将军希望通过某种协议达成某个命令的一致(比如约定某个时间一起进攻)。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。

如果同时发起进攻的将军数量少于m个,那么不足以歼灭敌人反而容易被敌人全部歼灭。怎样做才能保证有多于m个将军在同一时间一起发起进攻?这就是著名的「拜占庭将军问题」。


拜占庭将军问题与比特币共识算法

 

拜占庭是古代东罗马帝国的首都,由于地域宽广,守卫边境的多个将军(系统中的多个节点)需要通过信使来传递消息,达成某些一致决定。但由于将军中可能存在叛徒(系统中节点出错),这些叛徒将向不同的将军发送不同的消息,试图干扰共识的达成。这种情况十分类似于分布式系统中多个节点达成共识的问题。

拜占庭将军问题就是要解决去中心化的共识机制问题,而这个共识问题也是比特币中区块链网络所需要解决的。

拜占庭问题解决办法一:口头协议

在拜占庭问题里,主要需要解决的问题是:所有将军如何达成共识取得最终的胜利。

口头协议即靠人口口相传来传递消息以供决策。

导致的结果可能有:

· 信息在多次的传递中都正确送达;

· 信息接受者知道消息是谁发的,可以追溯;

· 沉默(不发消息 可以被检测;

但这个方案存在的缺陷也很明显:消息无法溯源,无法确定消息的上一来源是谁,因为将军心机深不可测,并且还涉及到内部有叛徒等问题,如有叛徒,则难以找到叛徒。

· 叛徒可能欺骗某些将军自己将采取进攻行动。

· 叛徒可能怂恿其他将军行动。

· 叛徒可能迷惑其他将军,使他们接受不一致的信息,从而感到迷惑。

· 某些将军本身就是间谍

拜占庭问题解决解决办法二:书面协议

发送书面信息,并附其签章,其他国家收到书信后附上自己的意见与签章再发给剩其他将军,最终达成共识。实现了以下三点:

· 签章有记录,解决溯源问题

· 签章难以伪造,篡改会被发现

· 任何国家都可验证其他国家的签章真伪

但这一解决方案依然存在缺陷:签章记录的保存人不一定可信,真正可信的签名体系很难实现。

拜占庭容错算法——区块链共识算法之一

拜占庭容错算法(Byzantine Fault Tolerant)是面向拜占庭问题的容错算法,解决的是在网络通信可靠,但节点可能故障和作恶情况下如何达成共识。

拜占庭容错算法最早的讨论可以追溯到 Leslie Lamport 等人 1982 年 发表的论文《The Byzantine Generals Problem》,之后出现了大量的改进工作,代表性成果包括《Optimal Asynchronous Byzantine Agreement》(1992 年)、《Fully Polynomial Byzantine Agreement for n>3t Processors in t+1 Rounds》(1998 年)等。

长期以来,拜占庭问题的解决方案都存在运行过慢,或复杂度过高的问题,直到“实用拜占庭容错算法”(Practical Byzantine Fault Tolerance,PBFT) 算法的提出。

1999 年,这一拜占庭容错算法算法由 Castro 和 Liskov 于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出。该拜占庭容错算法算法基于前人工作(特别是 Paxos 相关算法,因此也被称为 Byzantine Paxos)进行了优化,首次将拜占庭容错算法复杂度从指数级降低到了多项式级,目前已得到广泛应用。其可以在恶意节点不超过总数 1/3 的情况下同时保证 Safety 和 Liveness。

PBFT 算法采用密码学相关技术(RSA 签名算法、消息验证编码和摘要)确保消息传递过程无法被篡改和破坏。

拜占庭容错算法算法整体的基本过程如下:

· 首先,通过轮换或随机算法选出某个节点为主节点,此后只要主节点不切换,则称为一个视图(View)。

· 在某个视图中,客户端将请求  发送给主节点,主节点负责广播请求到所有其它副本节点。

· 所有节点处理完成请求,将处理结果  返回给客户端。客户端检查是否收到了至少 f+1 个来自不同节点的相同结果,作为最终结果。

 

主节点广播过程包括三个阶段的处理:预准备(Pre-Prepare)、准备(Prepare)和提交(Commit)。预准备和准备阶段确保在同一个视图内请求发送的顺序正确;准备和提交阶段则确保在不同视图之间的确认请求是保序的。

· 预准备阶段:主节点为从客户端收到的请求分配提案编号,然后发出预准备消息 <,message> 给各副本节点,其中 message 是客户端的请求消息,digest 是消息的摘要。

· 准备阶段:副本节点收到预准备消息后,检查消息。如消息合法,则向其它节点发送准备消息,带上自己的 id 信息,同时接收来自其它节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少 2f+1 个验证过的消息才进入准备状态。

· 提交阶段:广播 commit 消息,告诉其它节点某个提案 n 在视图 v 里已经处于准备状态。如果集齐至少 2f+1 个验证过的 commit 消息,则说明提案通过。

具体实现上还包括视图切换、checkpoint 等机制,读者可自行参考论文内容,在此不再赘述。

拜占庭容错类的算法因为要考虑最恶意的存在“捣乱”者的情况,在大规模场景下共识性能往往会受到影响。

拜占庭问题终极解决办法:通过区块链的「共识机制」

 

拜占庭问题的描述是:n 个将军被分隔在不同的地方,忠诚的将军希望通过某种协议达成某个命令的一致(比如一起进攻或者一起后退)。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。

 

因为将军们是分散的,没有一个中心的领导机构,因此他们在进攻敌方的时候必须事先对进攻地点和时间进行协商,达成共识。那么在有限的时间内,要解决提案(进攻方案)的一致性且获取大部分将军的认可,才能解决拜占庭将军问题。

在区块链网络中也是类似情况。区块链的分布式网络中可能会有多个人提出打包区块的请求,并且其中还有可能是有伪造的区块,那么只能靠分布式共识算法来解决这个问题了。

我们知道区块链的核心价值之一就是共识,这也是大家一直所追捧区块链的特性之一。所以2008年出现的比特币区块链则解决了这个“历史遗留问题”。

区块链是通过「共识机制」来解决上述问题的。区块链算是一个将「共识机制」充分应用的一个场景。

其实共识机制的概念并非是由区块链兴起才有的,它早在数学领域就是长期以来在研究和攻克的方向,尤其是在计算机领域针对分布式共识机制也已经有了一些知名的解决方案,取得了非常卓越的成就。

中本聪在比特币白皮书中,通过“比特币协议”给出了终极解决方案。

①引入“工作量证明”机制(PoW),只有第一个完成规定计算工作的将军才能传播信息,从而保证一段时间内只有一个提案。

②引入非对称加密算法,为信息传递提供签名技术支持,以保证消息传递的私密性,且不可抵赖、不可篡改。

这种加密技术——非对称加密完全可以解决古代难以解决的签名问题:

· 消息传送的私密性

· 能够确认身份

· 签名不可伪造、篡改

于是所有将军组成了这样一个分布式网络:

①每个将军都有一份实时与其他将军同步的消息账本。

②账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致,可以知道消息不一致的是哪些将军。

③尽管有消息不一致的,只要超过半数同意进攻,少数服从多数,共识达成。

拜占庭问题终极解决办法:通过区块链的「共识机制」 

基于互联网络的区块链技术,它克服了口头协议与书面协议的各种缺点,使用消息加密技术、以及公平的工作量证明机制,创建了一组所有将军都认可的协议。

比特币网络在设计时使用了 PoW(Proof of Work)的概率型算法思路,从如下两个角度解决大规模场景下的拜占庭容错问题。

首先,限制一段时间内整个网络中出现提案的个数(通过工作量证明来增加提案成本);

其次是丢掉最终确认的约数,约定好始终沿着已知最长的链进行拓展。共识的最终确认是概率意义上的存在。这样,即便有人试图恶意破坏,也会付出相应的经济代价(超过整体系统一半的工作量)。

后来的各种 PoX 系列算法,也都是沿着这个思路进行改进,采用经济博弈来制约攻击者。

正是由于拜占庭将军问题,我们需要达成共识。区块链上的共识机制有很多,没有一种共识机制是完美无缺的。其中也意味着没有一种共识机制是适合所有应用场景的。

伟大的创新往往是站在巨人的肩膀上,中本聪就是各种前沿技术的整合者,古老的疑难杂症在这种整合创新下,就变得不再是问题了。

玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。