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

  • 时间:
  • 浏览:0
  • 来源:大发快三_快三预测_大发快三预测

背景:

  拜占庭将军哪些地方的问提却说人过后听过,但不知道具体是哪些地方意思。这麼究竟哪些地方是拜占庭将军哪些地方的问提呢? 本文从最通俗的故事讲起,并对该哪些地方的问提进行抽象,并告诉亲戚亲戚大伙拜占庭将军哪些地方的问提为哪些地方在区块链领域作为有有兩个 重点研究哪些地方的问提。

哪些地方是拜占庭将军哪些地方的问提:

  “拜占庭将军哪些地方的问提”也被称为“拜占庭容错”。

  拜占庭将军哪些地方的问提是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/