幸运快3_快3app娱乐_幸运快3app娱乐

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

时间:2020-01-10 05:05:40 出处:幸运快3_快3app娱乐_幸运快3app娱乐

背景:

  拜占庭将军现象所以人肯能听过,但我而是知道具体是有哪些意思。那末究竟有哪些是拜占庭将军现象呢? 本文从最通俗的故事讲起,并对该现象进行抽象,并告诉亲戚亲戚让让让我们 拜占庭将军现象为有哪些在区块链领域作为另另另三个白重点研究现象。

有哪些是拜占庭将军现象:

  “拜占庭将军现象”也被称为“拜占庭容错”。

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

  所以例子大意是那我的:

  拜占庭帝国你会进攻另另另三个白强大的敌人,为此派出了10支军队去包围所以敌人。所以敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状况下同时攻击。亲戚亲戚让让让我们 任一支军队单独进攻都毫无胜算,除非有为宜6支军队(一半以上)同时袭击都前会 攻下敌国。亲戚亲戚让让让我们 分散在敌国的四周,依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰有有哪些将军的现象是,亲戚亲戚让让让我们 不选则亲戚亲戚让让让我们 中是不是 有叛徒,叛徒肯能擅自变更进攻意向肯能进攻时间。在所以状况下,拜占庭将军们都前会 保证有多于6支军队在同一时间同时发起进攻,从而赢取战斗? 

注:“  拜占庭将军现象中我过多 说去考虑通信兵是不是 会被截获或无法传达信息等现象,即消息传递的信道绝无现象。Lamport肯能证明了在消息肯能丢失的不可靠信道上试图通过消息传递的最好的方式达到一致性是不肯能的。所以,在研究拜占庭将军现象的时候,肯能假定了信道是那末现象的。 ”


 通俗分析:

  单从上端的说明肯能无法理解所以现象的繁杂性,亲戚亲戚让让让我们 来简单分析一下:

  先看在那末叛徒状况下,而是另另另三个白将军A提另另另三个白进攻提议(如:明日下午1点进攻,你你会加入吗?)由通信兵通信分别告诉所以的将军,肯能幸运中的幸运,他收到了所以6位将军以上的同意,发起进攻。肯能不幸,所以的将军也在此时发出不同的进攻提议(如:明日下午2点、3点进攻,你你会加入吗?),肯能时间上的差异,不同的将军收到(并认可)的进攻提议肯能是不一样的,这是肯能一直出显A提议有五个支持者,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/


热门

热门标签