您的位置:首页 > 块财经 > 币库 >

BFT是分布式计算的容错技术 可降低拜占庭协议的运行复杂度

2019-10-22 09:59:42 来源: 区块网

共识算法是区块链技术的核心要素,也是近年来分布式系统研究的热点。一、前言众所周知,区块链架构是一种分布式的架构。其部署模式有公共链...

共识算法是区块链技术的核心要素,也是近年来分布式系统研究的热点。

一、前言

众所周知,区块链架构是一种分布式的架构。其部署模式有公共链、联盟链、私有链三种,对应的是去中心化分布式系统、部分去中心化分布式系统和弱中心分布式系统。

分布式系统中,多个主机通过异步通信方式组成网络集群。在这样的一个异步系统中,需要主机之间进行状态复制,以保证每个主机达成一致的状态共识。然而,异步系统中,可能出现无法通信的故障主机,而主机的性能可能下降,网络可能拥塞,这些可能导致错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议,以确保各主机达成安全可靠的状态共识。

共识理解起来很简单,就是大家都达成一致的意思。在现实生活中,有很多达成共识的场景。比如我们开会讨论,需要得出一个结果;双方或多方签订一份合作协议时;又或者是哈士奇……呃,不好意思,跑远了。

而在区块链系统中,每个节点必须要做的事情就是让自己的账本跟其他节点的账本保持一致。如果是在传统的软件结构中,这根本不算事儿,因为有一个中心服务器,就像是一个公司老板发布一个通知,员工就照着做一样。可是区块链是一个分布式的对等网络结构,在这个结构中没有哪个节点是“老大”,什么事儿都得一起商量。

所以在区块链系统中,如何让每个节点通过一个规则将各自的数据保持一致是一个很关键的问题,这个问题的解决方案就是制定一套共识算法,实现不同账本节点上的账本数据的一致性和正确性。这就需要借鉴已有的在分布式系统中实现状态共识的算法,确定网络中选择记账节点的机制,以及如何保障账本数据在全网中形成正确、一致的共识。

在20世纪80年代出现的分布式系统共识算法,是区块链共识算法的基础。下面我们就从基本的拜占庭容错技术入手,往后逐步介绍适合于私有链/联盟链和公共链的共识算法。

二、拜占庭容错技术

拜占庭容错技术(Byzantine Fault Tolerance, BFT)是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因,计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为,并满足所要解决的问题的规范要求。

1、拜占庭将军问题

拜占庭容错技术来源于拜占庭将军问题(点此了解:https://ethfans.org/tinyxiong/articles/874)。拜占庭将军问题(Byzantine Generals Problem),是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。

这里我们给出分布式计算机中有关拜占庭缺陷和故障的两个定义:

定义1:拜占庭缺陷(Byzantine Fault):

任何观察者从不同角度看,表现出不同症状的缺陷。

定义2:拜占庭故障(Byzantine Failure):

在需要共识的系统中由于拜占庭缺陷导致丧失系统服务。

不是所有的缺陷或故障都能称作拜占庭缺陷或故障,比如死机、丢消息这样的。在分布式系统中,特别是在区块链网络环境中,也和拜占庭将军的环境类似,有运行正常的服务器(类似忠诚的拜占庭将军),还有破坏者或者中木马的服务器(类似叛变的拜占庭将军)。共识算法的核心是在正常的节点间形成对网络状态的共识。

2、拜占庭容错系统

通常,发生故障节点被称为拜占庭节点,而正常的节点即为非拜占庭节点。

拜占庭容错系统是一个拥有n 台节点的系统,整个系统对于每一个请求,满足以下条件:

1)所有非拜占庭节点使用相同的输入信息,产生同样的结果;

2)如果输入的信息正确,那么所有非拜占庭节点必须接收这个信息,并计算相应的结果。

拜占庭系统普遍采用的假设条件包括:

1)拜占庭节点的行为可以是任意的,拜占庭节点之间可以共谋;

2)节点之间的错误是不相关的;

3)节点之间通过异步网络连接,网络中的消息可能丢失、乱序并延时到达,但大部分协议假设消息在有限的时间里能传达到目的地;

4)服务器之间传递的信息,第三方可以嗅探到,但是不能篡改、伪造信息的内容和验证信息的完整性。

3、实用拜占庭容错系统

实用拜占庭容错系统(Practical Byzantine Fault Tolerance, PBFT),降低了拜占庭协议的运行复杂度,从指数级别降低到多项式级别(Polynomial),使拜占庭协议在分布式系统中应用成为可能。

PBFT是一类状态机拜占庭系统,要求共同维护一个状态,所有节点采取的行动一致。为此,需要运行三类基本协议,包括一致性协议、检查点协议和视图更换协议。我们主要关注支持系统日常运行的一致性协议。

一致性协议至少包含若干个阶段:请求(request)、序号分配(pre-prepare)和响应(reply)。根据协议设计的不同,可能包含相互交互(prepare),序号确认(commit)等阶段。

这个协议把服务器节点分为两类:主节点和从节点,主节点只有一个。

PBFT的一致性协议如下图所示。

为了描述方便,PBFT系统通常假设故障节点数为m个,而整个服务节点数为3m+1个。每一个客户端的请求需要经过5个阶段,通过采用两次两两交互的方式在服务器达成一致之后再执行客户端的请求。由于客户端不能从服务器端获得任何服务器运行状态的信息,PBFT中主节点是否发生错误只能由服务器监测。如果服务器在一段时间内都不能完成客户端的请求,则会触发视图更换协议。

上图显示了一个简化的PBFT的协议通信模式,其中C为客户端,N0~N3表示服务节点,特别的,N0为主节点,N3为故障节点。整个协议的基本过程如下。

1)客户端发送请求,激活主节点的服务操作。

2)当主节点接收请求后,启动三阶段的协议以向各从节点广播请求。

[2.1]序号分配阶段,主节点给请求赋值一个序列号n,广播序号分配消息和客户端的请求消息m,并将构造PRE-PREPARE消息给各从节点;

[2.2]交互阶段,从节点接收PRE-PREPARE消息,向其他服务节点广播PREPARE消息;

[2.3]序号确认阶段,各节点对视图内的请求和次序进行验证后,广播COMMIT消息,执行收到的客户端的请求并给客户端以响应。

3)客户端等待来自不同节点的响应,若有m+1个响应相同,则该响应即为运算的结果。

PBFT在很多场景都有应用,在区块链场景中,一般适合于对强一致性有要求的私有链和联盟链场景。例如,在IBM主导的区块链超级账本项目中,PBFT是一个可选的共识协议。(pixabay)

精选 导读

小米前置双摄的专利出现 可能在小米10上首发

2020年,三星将推出含有屏下摄像头的智能手机,据传还有其他制造商正在研发屏下摄像头的智能手机,其中一家就是小米。这家中国智能手机制造

发布时间: 2019-10-22 09:14
科技   2019-10-22

中兴挖孔摄像头专利曝光 开孔隐藏在信号栏的浮标中

如今所谓的全面屏手机到底有多少解决方案?其实无论是升降、刘海还是挖孔,都没有达到大家心中的最完美形态。为了追求最完美的全面屏效果,

发布时间: 2019-10-22 09:12
科技   2019-10-22

BitMax.io与FTX.com与Alameda Research合作 BitMax.io将上线ERC20杠杆代币

简介BitMax io (BTMX com), FTX com 与Alameda Research宣布达成战略合作,合作内容包括FTX com将上线BTMX,BitMax io亦将上线ERC20杠杆代币

发布时间: 2019-10-22 08:24
区块链   2019-10-22

华为畅享10正式发布 搭载屏下镜头+6秒手持拍照

10月18日下午消息,今天在华为北京会展中心,华为畅享系列又一新品——华为畅享10正式发布。共有三个版本,其中4+64GB售价1199元,6+64GB售价13

发布时间: 2019-10-21 16:39
科技   2019-10-21

到家集团将推出老人陪护业务 正与千人计划的科学家合作

10月21日下午消息,第六届世界互联网大会在浙江乌镇举办,本次大会以智能互联开放合作——携手共建网络空间命运共同体为主题。到家集团CEO陈小

发布时间: 2019-10-21 16:23
行业   2019-10-21

EUU-5G是汽车数据的区块链平台 可建立终身数字档案

大数据显示2018年中国车联网市场规模已达到1236亿元,未来五年(2018-2022)年均复合增长率约为21 60%,2022年中国车联网市场规模将达到2702

发布时间: 2019-10-21 15:51
币库   2019-10-21

联想威6 新款笔记本开启预售 预付100元可抵600元+2年保修

预付100元可狂抵600元现金使用!开售当日购买仅需3999元!搭载全新第十代英特尔酷睿处理器,整体性能提升达16%!指纹开机一键解锁、双通道内存

发布时间: 2019-10-21 15:31
学院   2019-10-21

Bibox 3天收到超过300个BTC的托管申请 公布矿工托管计划

北京时间10月18日,知名数字资产交易平台Bibox在上海举办了超级VIP线下交流会,本次会议主题为Bibox私人银行AI资产成绩展示发布暨矿业电力

发布时间: 2019-10-21 11:29
币库   2019-10-21

Bibox设立创新交易区 Prism/QEC即将上线

西风响,蟹脚痒,金秋正好吃蟹黄。10月18日,知名数字交易平台Bibox,联合鸵鸟区块链,举办了Bibox全球合作伙伴私邀蟹宴。鲁迅曾赞叹第一个

发布时间: 2019-10-21 11:24
币库   2019-10-21

杭州互联网交换中心揭牌 将打造1+N的工业平台体系

图为国家(杭州)新型互联网交换中心正式揭牌现场10月20日电,19日,工业和信息化部与浙江省人民政府在浙江乌镇召开部省合作推进工业互联网发

发布时间: 2019-10-21 09:08
管理   2019-10-21