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

  • 时间:
  • 浏览:1

背景:

  拜占庭将军大问题全都人将会听过,但真不知道具体是那先 意思。如此 究竟那先 是拜占庭将军大问题呢? 本文从最通俗的故事讲起,并对该大问题进行抽象,并告诉一帮人拜占庭将军大问题为那先 在区块链领域作为一个 多重点研究大问题。

那先 是拜占庭将军大问题:

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

  拜占庭将军大问题是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/