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

  • 时间:
  • 浏览:0
  • 来源:幸运快3_快3倍率_幸运快3倍率

背景:

  拜占庭将军问题报告 好多好多 人不可能 听过,但我沒有乎 具体是几个意思。不也能究竟几个是拜占庭将军问题报告 呢? 本文从最通俗的故事讲起,并对该问题报告 进行抽象,并告诉亲戚亲戚他们拜占庭将军问题报告 为几个在区块链领域作为一一四个重点研究问题报告 。

几个是拜占庭将军问题报告 :

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

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