[区块链] 拜占庭将军问题 [BFT]

  • 时间:
  • 浏览:0
  • 来源:极速快3_快3平台代理_极速快3平台代理

背景:

  拜占庭将军问題什么都人意味着着听过,但不知道具体是哪几种意思。没人 究竟哪几种是拜占庭将军问題呢? 本文从最通俗的故事讲起,并对该问題进行抽象,并告诉朋友拜占庭将军问題为哪几种在区块链领域作为另一一还还有一个重点研究问題。

哪几种是拜占庭将军问題:

  “拜占庭将军问題”也被称为“拜占庭容错”。

  拜占庭将军问題是Leslie Lamport(2013年的图灵讲得住)用来为描述分布式系统一致性问題(Distributed Consensus)在论文中抽象出来另一一还还有一个著名的例子。

  你类式 例子大意是那我 的:

  拜占庭帝国然后进攻另一一还还有一个强大的敌人,为此派出了10支军队去包围你类式 敌人。你类式 敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的共同袭击。这10支军队在分开的包围情况汇报下共同攻击。朋友任一支军队单独进攻都毫无胜算,除非有大概6支军队(一半以上)共同袭击不还能能攻下敌国。朋友分散在敌国的四周,依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰哪几种将军的问題是,朋友不选则 朋友中与非 有叛徒,叛徒意味着着擅自变更进攻意向意味着着进攻时间。在你类式 情况汇报下,拜占庭将军们不还能能保证有多于6支军队在同一时间共同发起进攻,从而赢取战斗? 

注:“  拜占庭将军问題中不须去考虑通信兵与非 会被截获或无法传达信息等问題,即消息传递的信道绝无问題。Lamport意味着着证明了在消息意味着着丢失的不可靠信道上试图通过消息传递的法律辦法 达到一致性是不意味着着的。什么都,在研究拜占庭将军问題的那我 ,意味着着假定了信道是没人 问題的。 ”


 通俗分析:

  单从顶端的说明意味着着无法理解你类式 问題的复杂,朋友来简单分析一下:

  先看在没人 叛徒情况汇报下,却说另一一还还有一个将军A提另一一还还有一个进攻提议(如:明日下午1点进攻,你然后加入吗?)由通信兵通信分别告诉什么都的将军,意味着着幸运中的幸运,他收到了什么都6位将军以上的同意,发起进攻。意味着着不幸,什么都的将军也在此时发出不同的进攻提议(如:明日下午2点、3点进攻,你然后加入吗?),意味着着时间上的差异,不同的将军收到(并认可)的进攻提议意味着着是不一样的,这是意味着着时不时出显A提议有5个支持者,B提议有另一一还还有一个支持者,C提议有另一一还还有一个支持者等等。

  加进去去什么都复杂,在有叛徒情况汇报下,另一一还还有一个叛徒会向不同的将军发出不同的进攻提议(通知A明日下午1点进攻, 通知B明日下午2点进攻等等),另一一还还有一个叛徒也会意味着着同意多个进攻提议(即同意下午1点进攻又同意下午2点进攻)。

  叛徒发送前后不一致的进攻提议,被称为“拜占庭错误”,而不多再还能能防止拜占庭错误的你类式 容错性称为「Byzantine fault tolerance」,简称为BFT。


问題抽象:

  求解拜占庭将军问題,隐含要满足以下另一一还还有一个条件:

  1)每个忠诚的将军时需收到相同的命令值vi(vi是第i个将军的命令)。

  2)意味着着第i个将军是忠诚的,没人 他发送的命令和每个忠诚将军收到的vi相同。

  于是,拜占庭将军问題的可不时需描述为:另一一还还有一个发送命令的将军要发送另一一还还有一个命令给其余n-另一一还还有一个将军,使得:

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

  IC2.意味着着发送命令的将军是忠诚的,没人 所有忠诚的接收命令的将军遵守所接收的命令。

  Lamport对拜占庭将军问題的研究表明,当n>3m时,即叛徒的个数m小于将军总数n的1/3时,通过口头同步通信(假设通信是可靠的),可不时需构造共同满足IC1和IC2的防止方案,即将军们可不时需达成一致的命令。但意味着着通信是可认证、防篡改伪造的(如采用PKI认证,消息签名等),则在任意多的叛徒(大概得有另一一还还有一个忠诚将军)的情况汇报下都可不时需找到防止方案。

  而在异步通信情况汇报下,情况汇报就没人 没人 乐观。Fischer-Lynch-Paterson定理证明了,却说有另一一还还有一个叛徒位于,拜占庭将军问題就无解。翻译成分布式计算语言,在另另一一还还有一个应用应用系统进程异步系统中,却说有另一一还还有一个应用应用系统进程不可靠,没人 就不位于另一一还还有一个协议,此协议能保证有限时间内使所有应用应用系统进程达成一致。

  由此可见,拜占庭将军问題在另一一还还有一个分布式系统中,是另一一还还有一个非常有挑战性的问題。意味着着分布式系统能不还能能 依靠同步通信,否则 性能和传输时延将非常低。否则 寻找类式生活实用的防止拜占庭将军问題的算法时不时是分布式计算领域中的另一一还还有一个重要问題。

在这里,朋友先给出分布式计算涵盖关拜占庭缺陷和故障的另一一还还有一个定义:

  定义1:拜占庭缺陷(Byzantine Fault):任何观察者不须同时延看,表现出不同症状的缺陷。

  定义2:拜占庭故障(Byzantine Failure):在时需共识的系统中意味着着拜占庭缺陷意味着着丧失系统服务。 

  在分布式系统中,都会所有的缺陷或故障都能称作拜占庭缺陷或故障。像死机、丢消息等缺陷或故障能不还能能 算为拜占庭缺陷或故障。拜占庭缺陷或故障是最严重缺陷或故障,拜占庭缺陷有不可预测、任意性的缺陷,类式遭黑客破坏,中木马的服务器什么都 另一一还还有一个拜占庭服务器。

  在另一一还还有一个有拜占庭缺陷位于的分布式系统中,所有的应用应用系统进程都会另一一还还有一个初始值。在你类式 情况汇报下,共识问題(Consensus Problem),什么都 要寻找另一一还还有一个算法和协议,使得该协议满足以下另一一还还有一个属性。

  1)一致性(Agreement):所有的非缺陷应用应用系统进程都时需同意同另一一还还有一个值。

  2)正确性(Validity):意味着着所有的非缺陷的应用应用系统进程有相同的初始值,没人 所有非缺陷的应用应用系统进程所同意的值时需是同另一一还还有一个初始值。

  3)可开始性(Termination):每个非缺陷的应用应用系统进程时需最终选则 另一一还还有一个值。

  根据Fischer-Lynch-Paterson的理论,在异步通信的分布式系统中,却说有另一一还还有一个拜占庭缺陷的应用应用系统进程,就不意味着着找到另一一还还有一个共识算法,可共同满足上述要求的一致性、正确性和可开始性要求。在实际情况汇报下,根据不同的假设条件,有什么都不同的共识算法被设计出来。哪几种算法各有优势和局限。算法的假设条件有以下几种情况汇报:

  1)故障模型:非拜占庭故障/拜占庭故障。

  2)通信类型:同步/异步。

  3)通信网络连接:节点间直连数。

  4)信息发送者身份:实名/匿名。

  5)通信通道稳定性:通道可靠/不可靠。

  6)消息认证性:认证消息/非认证消息。


中本聪的防止方案:

  在时不时出显比特币那我 ,防止分布式系统一致性问題主什么都 Lamport提出的Paxos算法或其衍生算法。Paxos类算法仅适用于中心化的分布式系统,那我 的系统的没人 不诚实的节点(不多再发送虚假错误消息,但允许时不时出显网络不通或宕机时不时出显的消息延迟)。

  中本聪在比特币中创造性的引入了“工作量证明(POW : Proof of Work)”来防止你类式 问題,有兴趣可进一步阅读工作量证明(猛击!)。

  通过工作量证明就增加了发送信息的成本,降低节点发送消息传输时延,那我 就以保证在另一一还还有一个时间能不还能能不还能能 另一一还还有一个节点(或是很少)在进行广播,共同在广播都会附上被委托人的签名。

  你类式 过程就像一位将军A在向什么都的将军(B、C、D…)发起另一一还还有一个进攻提议一样,将军B、C、D…看过将军A签过名的进攻提议书,意味着着是诚实的将军就会立刻同意进攻提议,而不多再发起被委托人新的进攻提议。

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

  理解了单个区块取得一致性的法律辦法 ,没人 整个区块链(总账本)意味着着达成一致也好理解。

  朋友稍微把将军问題改一下:

  假设攻下另一一还还有一个城堡时需多次的进攻,每次进攻的提议时需基于那我 最多次数的胜利进攻下提出的(能不还能能不还能能 那我 敌方已有损失最大,我方进攻胜利的意味着着性就更大),那我 约定那我 ,将军A在收到进攻提议时,就会检查一下你类式 提议是都会基于最多的胜利提出的,意味着着都会(基于最多的胜利)将军A就不多再同意那我 的提议,意味着着是的,将军A就会把这次提议记下来。这什么都 比特币网络最长链选则  (猛击!)


 经济学分析

  工作量证明随便说说大概提高了做叛徒(发布虚假区块)的成本,在工作量证明下,能不还能能不还能能 第另一一还还有一个完成证明的节点不还能能广播区块,竞争难度非常大,时需很高的算力,意味着着不成功其算力就白白的耗费了(算力是时需成本的),意味着着有那我 的算力作为诚实的节点,同样也可不时需获得很大的收益(这什么都 矿工所作的工作),这也实际就不多再有做叛徒的动机,整个系统也否则 而更稳定。

  矿工挖矿获得比特币奖励以及记账所得的交易费用使得矿工更希望维护网络的正常运行,而任何破坏网络的非诚信行为都会损害矿工自身的利益。否则 ,即使什么都比特币矿池具备强大的算力,它们都没人 作恶的动机,反而有动力维护比特币的正常运行,意味着着这和它们的切实利益相关。

  注:原始的拜占庭容错系统意味着着时需展示其理论上的可行性而缺陷实用性另外,还时需额外的时钟同步机制支持算法的复杂度也是随节点增加而指数级增加。实用拜占庭容错系统(PBFT)(猛击!)降低了拜占庭协议的运行复杂度,从指数级别降低到多项式级别(Polynomial),使拜占庭协议在分布式系统中应用成为意味着着。

总结:共识算法的核心什么都 防止拜占庭将军问題(分布式网络一致性问題)。


 REFERENCE

  1. Lamport L,Shostak R,Pease M.The Byzantine generals problem.ACM Trans.on Programming Languages and Systems,1982,4(3):382-401.

  2. Fischer,M.J.,Lynch,N.A.,Paterson,M.:Impossibility of distributed consensus with one faulty process.J.ACM 32(2),374-382(1985).
  3. 《区块链技术指南》邹均,张海宁,唐屹,李磊 著

【时间仓促,如有错误,欢迎指正! ||   欢迎留下您的评语!  朋友共同探讨、学习区块链!】

【转载请注明出处!http://www.cnblogs.com/X-knight/