什么是拜占庭将军问题

接触区块链的同学,多少都听说过拜占庭将军问题,经常看到或听到某某区块链使用某某算法解决了拜占庭将军问题,那么究竟什么是拜占庭将军问题呢?

什么是拜占庭将军问题

也被称为“拜占庭容错”、“拜占庭将军问题”。 拜占庭将军问题是Leslie Lamport(2013年的图灵讲得住)用来为描述分布式系统一致性问题(Distributed Consensus)在论文中抽象出来一个著名的例子。

这个例子大意是这样的:

拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算,除非有至少6支军队(一半以上)同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定他们中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下,拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻,从而赢取战斗?

拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题,即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以,在研究拜占庭将军问题的时候,已经假定了信道是没有问题的.

问题分析

单从上面的说明可能无法理解这个问题的复杂性,我们来简单分析一下:

  1. 先看在没有叛徒情况下,假如一个将军A提一个进攻提议(如:明日下午1点进攻,你愿意加入吗?)由通信兵通信分别告诉其他的将军,如果幸运中的幸运,他收到了其他6位将军以上的同意,发起进攻。如果不幸,其他的将军也在此时发出不同的进攻提议(如:明日下午2点、3点进攻,你愿意加入吗?),由于时间上的差异,不同的将军收到(并认可)的进攻提议可能是不一样的,这是可能出现A提议有3个支持者,B提议有4个支持者,C提议有2个支持者等等。
  2. 再加一点复杂性,在有叛徒情况下,一个叛徒会向不同的将军发出不同的进攻提议(通知A明日下午1点进攻, 通知B明日下午2点进攻等等),一个叛徒也会可能同意多个进攻提议(即同意下午1点进攻又同意下午2点进攻)。 叛徒发送前后不一致的进攻提议,被称为“拜占庭错误”,而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」,简称为BFT。

相信大家已经可以明白这个问题的复杂性了。

中本聪的解决方案

在出现比特币之前,解决分布式系统一致性问题主要是Lamport提出的Paxos算法或其衍生算法。Paxos类算法仅适用于中心化的分布式系统,这样的系统的没有不诚实的节点(不会发送虚假错误消息,但允许出现网络不通或宕机出现的消息延迟)。

中本聪在比特币中创造性的引入了“工作量证明(POW : Proof of Work)”来解决这个问题,有兴趣可进一步阅读工作量证明。 通过工作量证明就增加了发送信息的成本,降低节点发送消息速率,这样就以保证在一个时间只有一个节点(或是很少)在进行广播,同时在广播时会附上自己的签名。 这个过程就像一位将军A在向其他的将军(B、C、D…)发起一个进攻提议一样,将军B、C、D…看到将军A签过名的进攻提议书,如果是诚实的将军就会立刻同意进攻提议,而不会发起自己新的进攻提议。

以上就是比特币网络中是单个区块(账本)达成共识的方法(取得一致性)。

理解了单个区块取得一致性的方法,那么整个区块链(总账本)如果达成一致也好理解。 我们稍微把将军问题改一下:假设攻下一个城堡需要多次的进攻,每次进攻的提议必须基于之前最多次数的胜利进攻下提出的(只有这样敌方已有损失最大,我方进攻胜利的可能性就更大),这样约定之后,将军A在收到进攻提议时,就会检查一下这个提议是不是基于最多的胜利提出的,如果不是(基于最多的胜利)将军A就不会同意这样的提议,如果是的,将军A就会把这次提议记下来。

这就是比特币网络最长链选择。

经济学分析

工作量证明其实相当于提高了做叛徒(发布虚假区块)的成本,在工作量证明下,只有第一个完成证明的节点才能广播区块,竞争难度非常大,需要很高的算力,如果不成功其算力就白白的耗费了(算力是需要成本的),如果有这样的算力作为诚实的节点,同样也可以获得很大的收益(这就是矿工所作的工作),这也实际就不会有做叛徒的动机,整个系统也因此而更稳定。

很多人批评工作量证明造成巨大的电力浪费,促使人们去探索新的解决一致性(共识)问题的机制:权益证明机制(POS: Proof of Stake)是一个代表。在拜占庭将军问题的角度来看,它同样提高了做叛徒的成本,因为账户需要首先持有大量余额才能有更多的几率广播区块,POS不是本文重点,以后在讲。

共识算法的核心就是解决拜占庭将军问题(分布式网络一致性问题)。

原文发布于微信公众号 - 深入浅出区块链技术(blockchaincore)

原文发表时间:2018-02-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

如何向你的“弱智室友”解释区块链?

行业报道 ? 导读:事情是这样的,最近我的室友Hasaki一直在问我区块链和比特币的事情,我尝试了很多种不通的姿势以求简单通俗形象生动地跟他解释什么是区块链技术...

3769
来自专栏Coco的专栏

区块链 PoW 与 PoS 的纷争

1153
来自专栏圆方圆学院精选

【董天一】Filecoin: 影响力容错(PFT)和预期共识(EC)

这是filecoin协议里面对 PFT的解释,power概念就是矿工的影响力(influence),“Power”是filecoin系统的投票权力的大小度量,根...

1251
来自专栏Coco的专栏

区块链 PoW 与 PoS 的纷争

1603
来自专栏极客编程

以太坊、EOS、Hyperledger、Cosmos和Cardano等区块链的比较

不同的区块链智能合约和区块链技术现在风靡一时。越来越多的人出于某种原因试图进入这个神奇的世界。如果你是这项技术的新手并正在寻找基于区块链的开发平台的快速入门,那...

1372
来自专栏量化投资与机器学习

【精选干货】区块链相关资料汇总

精选整理了一些有关区块链方面的资料 希望大家有所收获 1、Blockchain For Dummies:初学者指南 http://byteacademy.co/...

1939
来自专栏区块链大本营

你没看过的V神早期神文,现在读起来仍受益匪浅

本文作于2014年初,其中部分区块链术语目前已不再使用。可能由于该类术语使用时间较短,国内尚无对应翻译,编译时处理如下:

872
来自专栏不止思考

从拜占庭将军问题看:区块链「 共识算法 」

而由于地域上特殊原因,你们这10支军队不能集合在一起单点进攻,必须在分开的状态下同时包围攻击敌国。如果是单支军队单独进攻的话是毫无胜算的,除非有至少有6支军队同...

1343
来自专栏企鹅号快讯

名为“闪电比特币”Lightning Bitcoin,LBTC的新型比特币硬叉被释放

闪电比特币是第一个在DPOS共识机制上运行的硬币,目的是使比特币的传输速度更快。 比特币网络目前面临的主要问题之一是交易速度的降低和交易成本的增加。比特币可扩展...

2086
来自专栏区块链开发科技公司

区块链开发公司 区块链的基本原理.

“区块链”技术最初是由一位化名中本聪的人为比特币(一种数字货币)而设计出的一种特殊的数据库技术,它基于密码学中的椭圆曲线数字签名算法(ECDSA)来实现去中心化...

310

扫码关注云+社区