精华内容
下载资源
问答
  • 区块链是一个分布式账本系统,参与者通过点对点网络连接,所有消息都通过广播的形式来 发送。实用拜占庭容错算法详解,包括拜占庭将军问题、三阶段过程、主节点是拜占庭节点问题、以及视图切换机制。
  • 课程目标:理解拜占庭容错系统(PBFT); 适用人群:大数据/Java基础人群 课程收益:理解拜占庭容错系统(PBFT);? 课程配套学习资料,建议学员学习过程中跟着视频教程实操,可理解更加深入。技术问题可在下方留言...
  • 区块链中实用拜占庭容错共识机制的研究与改进,王若琪,徐明昆,区块链技术是近年来出现的具有革命性的技术,通过运用数据加密、时间戳、分布式共识等手段,实现去中心化、去信任的点对点交易。
  • 基于评分机制的实用拜占庭容错共识算法,李景然,亓峰,针对区块链的实用拜占庭容错(PBFT)共识算法中存在的网络节点扩展性差和主节点选取不合理等问题,通过引入评分机制,提出了基于评分
  • 拜占庭容错证明

    2018-01-23 16:48:35
    一个实用的拜占庭容错复制算法的正确性证明 。
  • 拜占庭容错共识算法介绍

    千次阅读 2020-12-22 17:34:07
    区块链的共识算法中,除了常见的工作量证明(PoW,Proof of Work)和权益证明(PoS,Proof of Stake)外,还有拜占庭容错(Byzantine Fault Tolerance, BFT)共识算法。 拜占庭容错(Byzantine Fault Tolerance, BFT...

    1. 前言

    区块链的共识算法中,除了常见的工作量证明(PoW,Proof of Work)和权益证明(PoS,Proof of Stake)外,还有拜占庭容错(Byzantine Fault Tolerance, BFT)共识算法。

    拜占庭容错(Byzantine Fault Tolerance, BFT)共识算法是由拜占庭将军问题衍生出来的共识算法。

    拜占庭将军问题
    拜占庭将军问题是Leslie Lamport在10世纪80年代提出的一个假想问题。拜占庭是东罗马帝国的首都,由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。发生战争时将军们必须制订统一的行动计划。然而,这些将军中有叛徒,叛徒希望通过影响统一行动计划的制定与传播,破坏忠诚的将军们一致的行动计划。因此,将军们必须有一个预定的方法协议,使所有忠诚的将军够达成一致。而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说,拜占庭将军问题的实质就是要寻找一个方法,使得将军们在一个有版徒的非信任环境中建立对战斗计划的共识。

    在分布式系统中,特别是在区块链网络环境中,也和拜占庭将军的环境类似,有运行正常的服务器(类似忠诚的拜占庭将军),还有故障的服务器,有破坏者的服务器(类似叛变的拜占庭将军),即拜占庭错误节点。共识算法的核心是在正常的节点间形成对网络状态的共识。



    2. 拜占庭容错共识算法的版本分类

    拜占庭容错共识算法有3种版本,每种版本都具有各自的优缺点。这些版本分别是:
    1) 实用拜占庭容错(PBFT,Practical Byzantine Fault Tolerance)
    2) 联邦拜占庭协议(FBA,Federated Byzantine Agreement)
    3) 授权拜占庭容错算法(dBFT,Delegated Byzantine Fault Tolerance)




    3. 各种拜占庭容错共识算法版本的优缺点

    下面来看看它们的优缺点:

    3.1 实用拜占庭容错(PBFT,Practical Byzantine Fault Tolerance)

    优点:高速、可扩展。
    缺点:通常用于私有网络和许可网络。
    采用者:Hyperledger Fabric、Ripple

    实用拜占庭容错PBFT是首个解决拜占庭将军问题的方案,当前已被 Hyperledger Fabric 采用。PBFT 使用了较少(少于 20 个,之后会稍有增加)的预选定将军数,因此运行非常高效。它的优点是高交易通量和吞吐量,但是不足之处在于是中心化的,并用于许可网络。使用拜占庭容错机制是一种采用“许可投票、少数服从多数”来选举领导者并进行记账的共识机制,该共识机制允许拜占庭容错,允许强监督节点参与,具备权限分级能力,性能更高,耗能更低,而且每轮记账都会由全网节点共同选举领导者,允许33%的节点作恶,容错率为33%。换句话说,PBFT假设区块链上总的节点数是3f+1个,那么网络中可以容忍整个网络中最多f个节点出现拜占庭错误而不影响正确的共识。

    这里简单对瑞波Ripple介绍一下:
    在Ripple的共识算法中,将军(验证者)是 Ripple 基金会预先选定的,即参与投票节点的身份是事先知道的,因此,算法的效率比PoW等匿名共识算法要高效,交易的确认时间只需几秒钟。当然,这点也决定了该共识算法只适合于权限链(Permissioned chain)的场景。Ripple共识算法的拜占庭容错(BFT)能力为(n-1)/5,即可以容忍整个网络中20%的节点出现拜占庭错误而不影响正确的共识。
    瑞波共识算法使一组节点能够基于特殊节点列表形成共识。初始特殊节点列表就像一个俱乐部,要接纳一个新成员,必须由该俱乐部51%的会员投票通过。共识遵循这些核心成员的“51%权利”,外部人员则没有影响力。由于该俱乐部由中心化开始,它将一直是中心化的,而如果它开始腐化,股东们什么也做不了。与比特币及Peercoin一样,瑞波系统将股东们与其投票权隔开,因此,它比其他系统更中心化。

    顺便提一下,EOS公链除了使用DPoS(DPoS,Delegated Proof-of-Stake,授权权益证明)外,也使用了拜占庭容错来加速区块的确认。所以,在区块的确认时间上,EOS比起它的前身比特股要快很多,几秒内就可以完成区块的确认。


    3.2 联邦拜占庭协议(FBA,Federated Byzantine Agreement)

    优点:吞吐量、低交易开销和网络扩展性
    采用者:Stellar

    另一类拜占庭将军问题的解决方案是 FBA,已被 Stellar 等代币使用。FBA 的通用理念是每个拜占庭将军负责自身的链、消息一旦到来,通过排序建立事实。在 Stellar 中,任何人都可以成为验证者,需要用户选择去相信哪个验证者

    这里简单对恒星Stellar介绍一下:
    恒星Stellar项目是使用恒星共识(Stellar Consensus)来实现的。恒星共识是基于联邦拜占庭共识(FBA)。恒星共识协议(SCP,Stellar Consensus Protocol)提供了一种不依赖闭合系统实现准确记录金融交易而达成共识的方法。

    恒星共识协议(SCP) 具有一组可验证的安全属性,这些属性根据如何安全地保持活力而做了优化。一旦出现分区或不当行为节点,它将会终止网络过程,直至达成共识。SCP 同时具备四种属性:去中心控制、低延迟、灵活信任机制和渐进安全(Asymptotic security)。关于恒星项目的介绍,可以参考这篇文章:
    https://www.codercto.com/a/80941.html

    目前比较火的免费手机挖矿项目Pi Network是基于恒星共识协议(SCP)和联邦拜占庭协议(FBA)的算法进行开发(官网 https://minepi.com/#download,邀请码 powervip。关于Pi Network更多的资料可以参考这篇文章:
    https://bihu.com/article/1935912799

    网上相关的资料不是很详实,根据网上查到的资料和我个人的理解,实用拜占庭容错(PBFT)和联邦拜占庭协议(FBA)这2种共识算法的区别在于:PBFT是单邦制(可以理解为一个国家就是由一个邦组成),FBA是联邦制(可以理解为一个国家由多个联邦组成)。另外,PBFT的节点是预先选定或通过授权的。FBA是一个完全可以自由加入成为节点或退出节点的共识方式,每个邦内的白名单中节点(有记账和出块权的节点)通过投票选举产生(需要至少获得该联邦2/3节点的的同意)。因此,FBA比PBFT的去中心化程度更高,但是牺牲了一定的性能。
    如果要进一步验证上面的观点,最好的方法还是去查阅官方的文档甚至是代码。


    3.3 授权拜占庭容错算法(dBFT,Delegated Byzantine Fault Tolerance)

    优点:快速;可扩展。
    缺点:每个人都争相成为根链。其中可能存在多个根链。
    采用者:Neo

    授权拜占庭容错算法,简称 dBFT,是一种支持通过代理投票实现大规模参与共识的拜占庭容错共识算法。在国产第一条公链小蚁Neo中,令牌持有者可以通过投票选取其支持的 bookkeeper。之后,选定的 bookkeeper 组采用 BFT 算法达成共识,并生成新区块。Neo 网络中的投票是实时的,而非因人而异的。
    dBFT 可为具有个共识节点的共识系统提供f=n−13容错。这种容错也涵盖了安全性和可用性、不受将军和拜占庭错误影响,并且适合任何网络环境。dBFT 具有很好的最终性(finality),这意味着一旦最终确认,区块将不可分叉,交易将不可再撤销或是回滚。
    Neo 的 dBFT 机制生成一个区块需 15 到 20 秒钟。交易吞吐量测定约为 1000 TPS。这对于公共区块链而言,这是很好的性能。通过一定优化,dBFT 具有达到一万 TPSS 的潜力,这样就可支持大规模的商业应用。
    dBFT 中加入了数字身份技术,这意味着 bookkeeper 可以是真实的个人,也可以是某些机构。因此,dBFT 根据存在于其本身之中的司法判决,可以冻结、撤销、继承、检索和拥有代币兑换权。它有利于实现合规金融资产在 Neo 网络中的注册。Neo 网络从设计上,就是在必要时为此提供支持。

    同样是为了解决拜占庭将军问题,授权拜占庭容错机制,是一种在Neo区块链内部实现的保证容错的共识算法。

    在这个机制当中,存在两个参与者,一个是专业记账的“记账节点”,一个是系统当中的普通用户。

    普通用户基于持有权益的比例来投票决定记账节点,当需要通过一项共识时,在这些记账节点中随机推选出一名发言人拟定方案,然后由其他记账节点根据拜占庭容错算法,即少数服从多数的原则进行表态,如果超过66%的节点表示同意发言人方案,则共识达成;否则,重新推选发言人,重复投票过程。

    所以说,dBFT机制实际使用了一种迭代共识的方法来保证系统达成一致决定。然而,这种机制的缺点在于,当系统中有超过三分之一的记账节点停止工作时,整个区块链网络将无法提供正常的服务;当超过三分之一的节点联合作恶时,区块链将有可能发生分叉。

    参考文献:
    https://zhuanlan.zhihu.com/p/32585236
    https://blog.csdn.net/Blockchain_lemon/article/details/84801413
    https://blog.csdn.net/shangsongwww/article/details/89040823
    https://blog.csdn.net/weixin_43946212/article/details/109378449

    我的程序员主页:https://blog.csdn.net/powervip
    我的知乎: https://www.zhihu.com/people/powervip
    我的腾讯微云网盘:https://share.weiyun.com/5qT0TvG

    如果你觉得这篇文章写得还可以,请帮忙点个赞,谢谢!
    你的鼓励,我的动力!

    展开全文
  • 拜占庭容错算法是去中心化的经典共识算法,又名PBFT算法,该算法曾经获得2002年图灵奖。
  • 拜占庭容错2001

    2018-01-23 16:50:01
    拜占庭容错 2001 。
  • #资源达人分享计划#
  • #资源达人分享计划#
  • 拜占庭容错共识(PBFT)

    千次阅读 2020-12-15 15:26:32
    文章目录一、拜占庭容错共识1. 什么是PBFT拜占庭将军的问题是什么?pBFT 原理2. 与最传统的PoW共识机制相比,PBFT优势和劣势二、参考 一、拜占庭容错共识 1. 什么是PBFT 共识机制堪称区块链的核心。我们知道,EOS、...

    一、拜占庭容错共识

    1. 什么是PBFT

    共识机制堪称区块链的核心。我们知道,EOS、Hyperledger(之前0.x是,现在2.x已经不是。现在是Raft共识: Raft共识可以处理集群中部分节点的崩溃故障,但不能处理恶意节点行为,因此通常用于节点身份已知的环境中,例如许可制区块链 Hyperledger Fabric 就使用了基于Raft共识的排序服务。)等著名的项目,都采用了BFT(拜占庭容错)共识机制,那么,BFT到底是什么?

    什么是 pBFT?
    Practical Byzantine Fault Tolerance ,实用拜占庭容错。

    什么是 BFT?
    Byzantine Fault Tolerance ,拜占庭容错。

    区块链中最重要的便是共识算法,比特币使用的是POS(Proof of Work,工作量证明),以太币使用的是POS(Proof of Stake,股权证明)使得算理便的不怎么重要了,而今POS的变体DPOS(Delegated Proof of Stake,股份授权证明)进一步削减算力的浪费,同时也加强了区块链的安全性。
    不过,对于不需要货币体系的许可链或者私有链而言,绝对信任的节点,以及高效的需求上述共识算法并不能够提供,因此对于这样的区块链,传统的一致性算法成为首选,RAFT。

    拜占庭将军的问题是什么?

    简单地说,是一种少数服从多数的问题。拜占庭罗马帝国的每块封地都驻扎一支由将军统领的军队,将军与将军之间只能靠信差传递消息。在战争时期,拜占庭军队只有占据人数优势情况下,才能夺取目标的胜利。但在军队内有可能存有叛徒,当敌军与之联合起来大于忠诚将军数量时,进攻就会失败。

    pBFT 算法的提出主要是为了解决拜占庭将军问题。

    pBFT 原理

    POS、PBFT共识算法的介绍
    参考URL: https://mathpretty.com/9602.html
    pBFT 原理
    参考URL: https://zhuanlan.zhihu.com/p/71075569

    基于拜占庭将军问题,PBFT算法一致性的确保主要分为这三个阶段:预准备(pre-prepare)、准备(prepare)和确认(commit)。流程如下图所示:

    在这里插入图片描述我们首先解释一下上面各个符号表达的意思:

    • C表示客户端;
    • 0,1,2,3表示4个节点;
    • 0在这里为主节点,1,2,3为从节点;(注意,这里其他节点也可以作为主节点,若0发生错误只能由服务器监测。如果服务器在一段时间内不能完成客户端的请求,则会触发视图更换协议,将其他节点换为主节点)
    • 3为故障节点;

    下面我们结合上图,详细说一下PBFT的步骤:

    1. Request:请求端C发送请求到主节点,这里是0节点;
    2. Pre-Prepare:节点0收到C的请求后进行广播,扩散至123;
    3. Prepare:123节点收到后记录并再次广播,1->023,2->013,3因为宕机无法广播;(这一步是为了防止主节点给不同从节点发送不同的请求)
    4. Commit:0123节点在Prepare阶段,若收到超过一定数量(2F,实际使用中,F为可以容忍的拜占庭节点个数)的相同请求,则进入Commit阶段,广播Commit请求;
    5. Reply:0123节点在Commit阶段,若其中有一个收到超过一定数量(2F+1)的相同请求,则对C进行反馈;

    根据上述流程,在 N ≥ 3F + 1 的情況下一致性是可能解決,N为总计算机数,F为有问题的计算机总数。

    一个例子:
    下面我们来举一个PBFT(实用拜占庭容错算法)的例子来进行说明。

    我们假设N=4,F=1,即有四个节点,其中有一个节点是坏的,我们还使用上面的图,即节点3为故障节点。

    1. 请求端C发送请求到0节点,假设这里请求内容为“1”;
    2. 节点0收到C的请求后进行广播,将请求内容“1”扩散至节点123;
    3. 节点1、2、3收到后内容“1”后,再次广播,节点1->023,节点2->013,节点3因为宕机无法 广播;
    4. 节点0,1,2会在上一阶段分别收到三个请求内容“1”,均超过了2个,于是节点0、1、2会分别广播请求内容“1”;
    5. 此时如果一个节点(0,1,2中任意一个)收到3即(2+1)条commit消息,即对C进行反馈。

    一个问题说明 — 为什么至少需要N=3F+1个节点
    我们在上面讲到,当网络中有F台有问题的计算机时,至少需要3F+1台计算机才能保证一致性问题的解决,我们在这里讨论一下原因。

    我们可以考虑:由于有F个节点为故障或被攻击的节点,故我们只能从N-F个节点中进行判断。但是由于异步传输,故当收到N-F个消息后,并不能确定后面是否有新的消息。(有可能是目前收到的N-F个节点的消息中存在被攻击的节点发来的消息,而好的节点的消息由于异步传输还没有被收到。)

    我们考虑最坏的情况,即剩下F个都是好的节点,收到的中有F个被攻击的节点,故我们需要使得收到的中好节点的数量N-2F大于被攻击节点的数量F,于是有N-2F>F,即N>3F,所以N的最小整数为N=3F+1。

    2. 与最传统的PoW共识机制相比,PBFT优势和劣势

    1、效率高

    PBFT要求所有节点之间的两两通信,因此这种通信机制要求节点数量不能太多,通常是几十个,在这种模式下,节点达成一致的速度更快,延时更低。

    2、吞吐量高

    节点数量的控制,使PBFT网络不用像大型PoW网络那样,受限于处理能力最低的节点;因此带来全网吞吐量的大幅提升。

    3、节能
    无须使用工作量证明的耗电模式,因此更加节能环保。

    所谓有得必有失,相对而言,PBFT又有以下劣势:

    1、可扩展性及去中心化程度较弱

    由于节点数量的限制,因此可扩展性较弱;同时节点需要选举、或者许可,不像PoW节点那样可以自由加入,去中心化程度较弱。

    2、容错性较低

    PoW网络的容错性是50%,也就是须防范51%攻击;而PBFT容错性只有三分之一,也就是34%的恶意节点即可发起攻击。

    在这里插入图片描述表 共识算法对比 来源:中国信息通信研究院,2018 年8 月

    总结:
    pBFT 的优点
    高效,由于各个节点达成共识是在同一时刻决定的首先,所以pBFT 无需等待确认。
    节能,因为pBFT 是无需挖矿的,所以pBFT 不用耗能。

    pBFT 的缺点:
    中心化,由于要保证各个节点间的频繁的通信,所以节点数不能太多。
    门槛高,由于pBFT 不能防止女巫攻击,也就无法防御一个恶意用户用多个账户来进行共识的造假行为,所以需要审核加入节点。

    所以pBFT 比较适合需审批的联盟链,不太适合做无条件加入的公链。

    3. BFT共识开发库

    区块链主流共识算法的15个开源实现
    参考URL: https://zhuanlan.zhihu.com/p/99403520

    Tendermint

    BFT共识算法可以应对分布式系统中的拜占庭故障(Byzantine failures),也就是可以在集群中部分节点存在恶意行为时依然保证整个系统的正常工作。

    Tendermint Core 是一个拜占庭容错的中间件,可以安全的将任何语言开发的状态机复制到集群中的其他机器上。Tendermint Core已经被用于Cosmos、币安链等多种公链环境中。

    在这里插入图片描述
    Tendermint Core的协议详情可以参考这里,开发教程访问这里:tendermint开发详解(http://xc.hubwiz.com/course/5bdec63ac02e6b6a59171df3?affid=csdn7878)。

    开发语言:Go
    下载地址:https://github.com/tendermint/tendermint

    Tendermint Core是一种拜占庭容错(BFT)共识引擎,可以抵御双重攻击,并且能够容忍网络中一组高达1/3的拜占庭角色。Tendermint应用程序区块链接口(ABCI)平台是一个适用于区块链应用程序开发人员的工具包。该工具包与任何编程语言兼容,允许对仅运行业务逻辑的去中心化应用程序进行更高级别的开发,而无需在共识层上进行更低级别的修补。Ethermint等平台建立在Tendermint ABCI平台之上。

    另一个建立在Tendermint ABCI之上的项目是Cosmos Network,它被设计为“区块链互联网”。Cosmos设想了一个可互操作的多链网络,它提供了在独立区块链(称为区域)之间无信任地交换加密资产的方法,通过称为Cosmos Hub的主集线器链。为了使区块链开发人员尽可能轻松,Cosmos还附带了一个名为Cosmos-SDK的工具包,使开发人员可以使用即插即用模块轻松创建自定义区块链。

    BFT-SMaRt

    BFT-SMaRt是一个拜占庭容错的状态机复制实现,采用Java开发,目前由里斯本大学的LsSIGE研究组负责维护。BFT-SMaRt要求JRE 1.8+。

    BFT-SMaRt是最知名的Java版BFT实现,京东的区块链就是采用这个库解决共识问题。

    开发语言:Java
    下载地址:https://github.com/bft-smart/library

    BABBLE

    Babble是用于分布式应用的拜占庭共识平台,它可以让一组计算机表现的如同单一计算机。Babble它使用P2P网络和BFT共识算法来保证一组彼此互联的计算机可以同样的顺序处理同样的命令,也就是通常说的状态机复制。Babble可以让整个系统安全的应对部分节点的故障或恶意行为。

    Babble主要采用Go语言开发,但是其设计目标是可以集成进任何语言开发的应用,如上图所示。

    开发语言:Go
    下载地址:https://github.com/mosaicnetworks/babble

    Concord-BFT

    concord-bft是vmware开源的一个通用的状态机复制库,可以应对集群中的恶意行为(拜占庭故障)。 concord-bft被设计用于分部署数据仓库复制的核心构建模块,特别适合作为许可制区块链系统的基础。

    concord-bft的实现基于这片论文中的算法:SBFT: a Scalable Decentralized Trust Infrastructure for Blockchains。

    开发语言:Python
    下载地址:https://github.com/vmware/concord-bft

    HBBFT

    HBBFT是论文Honey Badger of BFT Protocols提出的蜜獾BFT共识算法的Rust实现。HBBFT要求Rust 1.36+以及cargo

    蜜獾(Honey Badger)共识算法可以让分布式异步环境中的节点交易达成一致,该算法不需要主导节点,可以应对恶意节点的攻击,适合于去中心化数据库和区块链应用。

    开发语言:Rust
    下载地址:https://github.com/poanetwork/hbbft

    libbft

    libbft是一个轻量级的拜占庭容错库,用于neo区块链,采用C++开发,由neo研究院维护,计划移植到Python、go等多种语言。

    开发语言:C++
    下载地址:https://github.com/NeoResearch/libbft

    二、参考

    什么是 pBFT
    参考URL: https://zhuanlan.zhihu.com/p/71075569
    从0到1搞懂拜占庭容错共识机制
    参考URL: https://www.jianshu.com/p/6420eb1661a0?from=groupmessage
    区块链共识算法 PBFT(拜占庭容错)、PAXOS、RAFT简述
    参考URL: https://www.cnblogs.com/yuluoxingkong/p/13542788.html
    对PBFT算法的理解
    参考URL: https://www.cnblogs.com/gexin/p/10242161.html
    实用拜占庭容错系统(PBFT)共识算法
    参考URL: https://blog.csdn.net/JonasErosonAtsea/article/details/109236413
    [比较全面,推荐]参考URL: https://github.com/xipfs/IPFS-Internals/blob/master/ebook/13.0.md
    区块链主流共识算法的15个开源实现
    参考URL: https://zhuanlan.zhihu.com/p/99403520

    展开全文
  • 实用拜占庭容错算法

    千次阅读 2021-05-17 14:11:46
    实用拜占庭容错算法 作者:段玉龙2018201112 、朱江2018201116、卢薪丞2017201116 背景提出——拜占庭将军问题 拜占庭将军问题是由Leslie Lanport提出的分布式对等网络通信融资问题,那么它具体是什么呢,我们来...

    哈尔滨工程大学计算机学院2021年区块链技术课程

    实用拜占庭容错算法

    作者:段玉龙2018201112 、朱江2018201116、卢薪丞2017201116

    背景提出——拜占庭将军问题

    拜占庭将军问题是由Leslie Lanport提出的分布式对等网络通信融资问题,那么它具体是什么呢,我们来打个比方,如果你是一支拜占庭军队的将军,并且准备攻击一座敌方城市,在城市周围有几支有其他将军领导的军队,如果大家一起合作进攻,那么一定会大获全胜。但是如果大家各顾各,零散攻击,那么会导致进攻失败。这个时候作为将军的你,决定在傍晚攻击。在那个时期你并没有办法通过电话商量,也没有办法发送可能被敌方看到的信号弹,来联系所有的将军,让大家达成共识一起发动傍晚的攻击。所以您只能通过传令兵来传递信息。那么问题来了,如果传令兵在路途中被杀害怎么办,被敌方逮捕换成假信息怎么办,再者其他将军又如何判定你的传令兵递送的消息就是你的消息呢?更要命的是如果其中有叛军故意发送同意攻击的信息,但是实际进攻中不出兵又怎么办,这样各支军队的一致协同就遭到了破坏,所以你该怎么确保所有的军队会达成共识,并且同时出击呢?这个就是困扰了近千年的拜占庭将军问题,他问题的核心就是:单独个体如何可以不带任何条件地相信彼此。

    由此引出拜占庭容错算法。

    BFT拜占庭容错系统

    拜占庭容错技术被设计用来处理异常行为(包括硬件错误、网络拥塞、以及恶意攻击),被设计用来处理这些异常行为。发生故障的节点是拜占庭节点,正常的节点为非拜占庭节点。

    但是拜占庭容错算法(BFT)在实用中有很多不便之处, 早期提出的能解决拜占庭问题的算法(包括随拜占庭问题论文提出来的两种原生算法),要么仅仅停留在展示算法的理论可能性阶段,而实用性不高,要么就假设算法的使用环境为同步系统,而真实生产中的信息系统往往是异步的,例如互联网。由此衍生出了实用拜占庭容错算法(PBFT),它也是庭容错算法(BFT)下的一个分支。下面会详细讲解实用拜占庭容错算法(PBFT)。

    实用拜占庭容错算法(PBFT)

    PBFT算法前提,采用密码学算法保证节点之间的消息传送是不可篡改的。

    PBFT容忍无效或者恶意节点数:f,为了保障整个系统可以正常运转,需要有2f+1个正常节点,系统的总节点数为:|R| = 3f + 1。也就是说,PBFT算法可以容忍小于1/3个无效或者恶意节点。
    PBFT是一种状态机副本复制算法,所有的副本在一个视图(view)轮换的过程中操作,主节点通过视图编号以及节点数集合来确定,即:主节点 p = v mod |R|。v:视图编号,|R|节点个数,p:主节点编号。

    PBFT算法每个客户端请求需要经过5个阶段,主要是①request——请求②pre-Prepare——序号分配③Prepare——交互④commit——序号确认⑤reply——响应

    以下详细说明一下这五个阶段流程:

    1. Request:

    客户端c向主节点p发送<REQUEST, o, t, c>请求。o: 请求的具体操作,t: 请求时客户端追加的时间戳,c:客户端标识。REQUEST: 包含消息内容m,以及消息摘要d(m)。客户端对请求进行签名。

     

    1. Pre-Prepare:

    主节点收到客户端的请求,需要进行校验客户端请求消息签名是否正确。校验的步骤如下

     

    非法请求丢弃。正确请求,分配一个编号n,编号n主要用于对客户端的请求进行排序。然后广播一条<<Pre-Prepare, v, n, d>,  m>消息给其他副本节点。v:视图编号,d客户端消息摘要,m消息内容。<Pre-Prepare, v, n, d>进行主节点签名。n是要在某一个范围区间内的[h, H]。

     

    1. Prepare:

    副本节点i收到主节点的Pre-Prepare消息,需要进行以下校验:

     

    a. 主节点Pre-Prepare消息签名是否正确。

    b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n,但是签名不同的Pre-Prepare信息。

    c. d与m的摘要是否一致。

    d. n是否在区间[h, H]内。

    非法请求丢弃。正确请求,副本节点i向其他节点包括主节点发送一条<Prepare, v, n, d, i>消息, v, n, d, m与上述Pre-Prepare消息内容相同,i是当前副本节点编号。<Prepare, v, n, d. i>进行副本节点i的签名。记录Pre-Prepare和Prepare消息到log中,用于View Change过程中恢复未完成的请求操作。

     

    1. Commit

    主节点和副本节点收到Prepare消息,需要进行以下校验:

     

    a. 副本节点Prepare消息签名是否正确。

    b. 当前副本节点是否已经收到了同一视图v下的n。

    c. n是否在区间[h, H]内。

    d. d是否和当前已收到Pre-Prepare中的d相同

    非法请求丢弃。如果副本节点i收到了2f+1个验证通过的Prepare消息,则向其他节点包括主节点发送一条<Commit, v, n, d, i>消息,v, n, d,  i与上述Prepare消息内容相同。<Commit, v, n, d, i>进行副本节点i的签名。记录Commit消息到日志中,用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的Prepare消息到log中。

     

    1. Reply:

    主节点和副本节点收到Commit消息,需要进行以下校验:

     

    a. 副本节点Commit消息签名是否正确。

    b. 当前副本节点是否已经收到了同一视图v下的n。

    c. d与m的摘要是否一致。

    d. n是否在区间[h, H]内。

    非法请求丢弃。如果副本节点i收到了2f+1个验证通过的Commit消息,说明当前网络中的大部分节点已经达成共识,运行客户端的请求操作o,并返回<Reply, v, t, c, i, r>给客户端,r:是请求操作结果,客户端如果收到f+1个相同的Reply消息,说明客户端发起的请求已经达成全网共识,否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的Commit消息到log中。

     

    (流程示意参考图)

    总结

    PBFT算法由于每个副本节点都需要和其他节点进行P2P的共识同步,因此随着节点的增多,性能会下降的很快,但是在较少节点的情况下可以有不错的性能,并且分叉的几率很低,可以较好的解决拜占庭容错问题。

     

     

    参考文献:https://blog.csdn.net/jfkidear/article/details/81275974

    展开全文
  • 通俗易懂解释拜占庭容错

    千次阅读 2019-11-10 23:10:15
    拜占庭容错问题需要解决的也同样是谁来发起信息,如何实现信息的统一同步的问题。 到这里也可以知道了,基于互联网的区块链技术,它克服了口头协议与书面协议的种种缺点,使用消息加密技术、以及公平的工作量证明...

    作者:苏江同学 
    链接:https://www.jianshu.com/p/5fea30b25f0a 
    來源:简书 
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    拜占庭将军问题很多人可能听过,但不知道是什么意思,本文从非专业的角度来讲讲,拜占庭将军问题到底是说什么的。

    拜占庭将军问题(Byzantine Generals Problem),首先由Leslie Lamport与另外两人在1982年提出,很简单的故事模型,却困扰了计算机科学家们数十年。

    故事大概是这么说的:

    拜占庭帝国即中世纪的土耳其,拥有巨大的财富,周围10个邻邦垂诞已久,但拜占庭高墙耸立,固若金汤,没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败,同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强,至少要有十个邻邦中的一半以上同时进攻,才有可能攻破。

    然而,如果其中的一个或者几个邻邦本身答应好一起进攻,但实际过程出现背叛,那么入侵者可能都会被歼灭。

    于是每一方都小心行事,不敢轻易相信邻国。这就是拜占庭将军问题

    在拜占庭问题里,各邻国最重要的事情是:所有将军如何能过达成共识去攻打拜占庭帝国。

    达成共识并非坐下来开个会那么简单,有的将军心机深不可测,口是心非,如果有叛徒,可能会出现各种问题:

    叛徒可能欺骗某些将军自己将采取进攻行动。 
    叛徒可能怂恿其他将军行动。 
    叛徒可能迷惑其他将军,使他们接受不一致的信息,从而感到迷惑。

    针对拜占庭问题的深入研究,科学家们得出一个结论:如果叛徒的数量大于或等于1/3,拜占庭问题不可解。

    解释过程可以用一个副官模型来解释:

    假设只有3个人,A、B、C,三人中如果其中一个是叛徒。当A发出进攻命令时,B如果是叛徒,他可能告诉C,他收到的是“撤退”的命令。这时C收到一个“进攻”,一个“撤退“,于是C被信息迷惑,而无所适从。

    如果A是叛徒。他告诉B“进攻”,告诉C“撤退”。当C告诉B,他收到“撤退”命令时,B由于收到了司令“进攻”的命令,而无法与C保持一致。

    正由于上述原因,在只有三个角色的系统中,只要有一个是叛徒,即叛徒数等于1/3,拜占庭问题便不可解。

    当然,只要叛徒数小于1/3,问题还是可解的。

    科学家们提出了口头信息方案和书面协议两个方案。

    解决方案一:用口头信息

    口头信息即使将军们派人用口信传达消息,口头传达消息的实际含义指的是:

    每个被发送的消息都能够被正确投递 
    信息接受者知道消息是谁发的 
    沉默(不发消息)可以被检测 
    口头协议的算法很简单,如果其中一个节点,比如1发布消息出去,210都接受到1的消息,然后210也分别转告给其他的节点,每个节点都是信息的转达者,一轮下来,每个节点手上都会有10个信息(进攻或者撤退),有叛徒的话,那信息可能有进攻或者不进攻的不一致消息。每个人相当于手里有一本消息的账本,该怎么决策呢?如果有一半以上的人说进攻,那么采取进攻行动就是能成功的,所以这时即便有叛徒,只要听大部分人的,少数服从多数来行动即是有利的。

    这种口头协议的算法也存在明显的缺点:口头协议并不会告知消息的上一个来源是谁,也就是消息不可追根溯源,出现信息不一致也很难找到叛徒在哪。

    解决方案二:用书面协议

    可以假设10个国家,每个国家都可以派人向各个国家派信,比如一起约定 “某天早上六点,大家一起进攻拜占庭,同意就签个字”。收到信的国家如果同意的话,就可以在原信上签名盖章。

    书面协议相比口头协议,实际说的是在这个多人的将军模型中加了了个隐含条件:

    将军们能够使用签名技术,签名不可伪造,一旦篡改即可发现。 
    同时任何人都可以验证签名的可靠性。 
    书面协议相比口头协议,所有的消息都是有记录的,解决了追根溯源的问题。

    但在现实中仍然可能面临各种问题:

    中世纪的邻邦之间沟通只能靠信使骑马,将军们互不信任,也不可能亲自聚在一起开会,物理距离导致信息传输延迟。

    真正可信的签名体系难以实现。签名造假的问题也没法避免。

    签名消息记录的保存难以摆脱中心化的机构。

    另外,倘若每个国家都各自向其他9个国家派出信使,在这个网络即需要90次的传输才能完成一轮信息交流,但是每个国家可能回馈不同的进攻时间,在这种异步通信的条件下,要能协商一致是个大问题。

    也就是如果能够依赖中心化可信的机构,也许能通过多方的签名记录整合在一起,更容易地实现9个国家的意见统一,但这是个伪假设,因为前提是这个网络就是互不信任的。

    这就是一个由互不信任的各个邻邦国家所构成的分布式网络,要获得最大的利益,又必须一起努力才能完成,如何达成一致的共识,变成了一个难题。

    莱斯利·兰伯特提出了“拜占庭将军问题”,但真正解决这以难题的是——中本聪。

    终极解决方案:区块链技术 
    互联网的存在,首先降低了信息的流通成本。每个将军配一台电脑,就解决了”书面协议“中骑马通讯造成时间延迟的问题。

    如果10个将军中的几个同时发起消息,势必会造成系统的混乱,造成各说各的攻击时间方案,行动难以一致。

    谁都可以发起进攻的信息,但由谁来发出呢?中本聪巧妙地在个系统加入了发送信息的成本,即:一段时间内只有一个节点可以传播信息。

    它加入的成本就是”工作量“——节点必须完成一个计算工作才能向各城邦传播消息,当然,谁第一个完成工作,谁才能传播消息。

    当某个节点发出统一进攻的消息后,各个节点收到发起者的消息必须签名盖章,确认各自的身份。中本聪在这里引用现代加密技术为这个信息签名。

    这种加密技术——非对称加密完全可以解决古代难以解决的签名问题:

    消息传送的私密性 
    能够确认身份 
    签名不可伪造、篡改 
    非对称加密算法的加密和解密使用不同的两个密钥.这两个密钥就是我们经常听到的”公开密钥”(公钥)和”私有密钥”(私钥).

    公钥和私钥一般成对出现, 如果消息使用公钥加密,那么需要该公钥对应的私钥才能解密; 同样,如果消息使用私钥加密,那么需要该私钥对应的公钥才能解密.

    非对称加密的作用是:保护消息内容, 并且让消息接收方确定发送方的身份.

    比如,将军A想给将军B发送消息,为防止消息泄露,将军A只需要使用B的公钥对信息加密,而B的公钥是公开的,B只需要用只有他自己只的私钥解密即可。

    将军B想要在信件上声明自己的身份,他可以自己写一段”签名文本“,并用私钥签名,并广播出去,所有人可以根据B的公钥来验证该签名,确定的B的身份。

    由此,一个不可信的分布式网络变成了一个可信的网络,所有的参与者可以在某件事在达成一致。

    写到这里,同时终于明白了工作量证明(Proof Of Work)的意义。有人说挖矿浪费了巨大的社会资源,但建立信任的成本可不是0,挖矿是维护比特币网络可靠性的最好办法。

    工作量证明,简单的理解就是一份证明,现实中的毕业证、驾驶证都属于工作量证明,它用以检验结果的方式证明你过去所做过了多少工作。

    在拜占庭的系统里,加入工作量证明,其实就是简单粗暴地引入了一个条件:大家都别忙着发起消息,都来做个题,看谁最聪明,谁就有资格第一个发起消息。

    这个题必须是绝对公平的,中本聪在设计比特币时,它采用了一种工作量证明机制叫哈希现金,在一个交易块这要找到一个随机数,计算机只能用穷举法来找到这个随机数,可以说,能不能找到全靠运气,所以对于各个节点来说,这个世界上,只有随机才是真正的公平,实现随机的最好办法是使用数学,所有的将军在寻找共识的过程,借助了大家都认可的数学逻辑。

    如果不同的将军先后解出了题,各自先后向这个网络发布消息,于是各个节点都会收到来自不同节点发起的进攻或者不进攻的消息,那怎么办的?只有时间最早的发起者才是有效的。中本聪巧妙的设计了一个时间戳的东西,为每个将军在解好题的时间(出块时间)盖上时间印章。

    将军们那又凭什么要一起做工作量证明呢?中本聪也完全可以设置一个奖励机制,比特币的奖励机制是每打包一个块,目前是奖励25个比特币,当然,拜占庭将军问题的奖励机制可以是瓜分拜占庭获得的利益。

    对了,如果有出现背叛怎么办?

    在这个分布式网络里:

    每个将军都有一份实时与其他将军同步的消息账本。 
    账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致,可以知道消息不一致的是哪些将军。 
    尽管有消息不一致的,只要超过半数同意进攻,少数服从多数,共识达成。 
    由此,在一个分布式的系统中,尽管有坏人,坏人可以做任意事情(不受protocol限制),比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。但是,只要大多数人是好人,就完全有可能去中心化地实现共识(Consensus)。

    区块链上的共识机制主要解决由谁来构造区块,以及如何维护区块链统一的问题。

    拜占庭容错问题需要解决的也同样是谁来发起信息,如何实现信息的统一同步的问题。

    到这里也可以知道了,基于互联网的区块链技术,它克服了口头协议与书面协议的种种缺点,使用消息加密技术、以及公平的工作量证明机制,创建了一组所有将军都认可的协议,这套协议的出现,拜占庭将军问题也就完美的得到了解决。

    伟大的创新往往是站在前人的肩膀上,中本聪就是各种前沿技术的整合者,古老的疑难杂症在这种整合创新下,就变得不再是问题了。

    展开全文
  • 磅 pbft-实用的拜占庭容错
  • 异步拜占庭容错(ABFT)是拜占庭容错共识算法的一个属性,它允许网络的诚实节点保证公平、安全地就一组交易的时间和顺序达成一致。 什么是拜占庭容错? 让我们首先了解拜占庭容错实际上意味着什么。术语拜占庭...
  • 拜占庭容错算法的新发展——GBFT 本文为哈尔滨工程大学计算机学院2021年区块链技术课程,由2018201319 李合尧同学查阅相关博客以及论文进行的总结描述,由于第一次发表学术文章,才疏学浅,若有疏漏以及版权问题还请...
  • 拜占庭容错(BFT)介绍

    千次阅读 2019-06-03 10:26:52
    请注意,拜占庭容错算法不能100%忍受拜占庭缺点,但由于本钱密集型的挖矿和底层加密技术,工作量证明已被证明是区块链网络最安全可靠的完成之一。从这个意义上说,由中本聪规划的工作量证明一起算法被许多人认为是...
  • 摘要拜占庭容错问题简称BFT,实用拜占庭容错系统(PBFT)在区块链中的应用很普遍,简介PBFT算法步骤。 拜占庭容错问题简称BFT,BFT是区块链共识算法中需要解决的一个核心问题,以比特币和以太访为代表的POW,...
  • BW筏 实现分布式共识协议Raft及其扩展版本BW-Raft(支持拜占庭容错
  • PBFT实用拜占庭容错算法详解

    千次阅读 2019-08-26 10:30:40
    解决了原始拜占庭容错(BFT)算法效率不高的问题,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。 缺点: 仅仅适用于permissioned systems (联盟链/私有链)。 通信复杂度过高,...
  • 关于区块链技术原理应用实践的详细介绍 一种用于区块链的拜占庭容错算法.pdf
  • 实用拜占庭容错(PBFT)算法详细介绍

    千次阅读 2020-03-18 11:29:54
    本文主要讲述实用拜占庭容错算法(PBFT)的算法部分。
  • 出品|白话区块链责编 | 晋兆雨头图 |付费下载于视觉中国实用拜占庭容错机制( Practical Byzantine Fault Tolerance),简称 PBFT, 今天我们就来...
  • 简单介绍了一种目前联盟链中常用的共识算法——实用拜占庭容错(PBFT,practical Byzantine fault tolerance)算法,并在其基础上优化算法机制,增加可扩展性,提出了一种改进的算法。经改进后,降低了算法的复杂度,...
  • 解释拜占庭容错

    2019-11-12 22:57:53
    作者:苏江同学  链接:... 來源:简书  著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 拜占庭将军问题很多人可能听过,但不知道是什么意...
  • 随着W比特币为代表的数字货币的风靡,区块链作为其关键底层技术也越来 越受各国政府和企业巨头的关注。区块链的去中也化、数据不可篡改性、动态灵 活的体系特征,使得其在银行、征信、金融等多领域应用前景...
  • 完整整理了4种分布式共识算法(拜占庭容错算法)的原理,包括PBFT、PoW、PoS、DPos
  • 拜占庭容错系统简介

    2018-08-06 07:12:16
    拜占庭容错系统简介 原始的拜占庭容错系统由于需要展示理论上的可行性而缺乏实用性。另外,算法的复杂度也是随节点的增加而呈指数级增加。实用拜占庭容错系统(Practical Byzantine Fault Tolerance, PBFT)降低了...
  • 区块链快速入门(三)——CFT(非拜占庭容错)共识算法 一、CFT简介 CFT(Crash Fault Tolerance),即故障容错,是非拜占庭问题的容错技术。 Paxos 问题是指分布式的系统中存在故障(crash fault),但不存在恶意...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,793
精华内容 1,917
关键字:

拜占庭容错