PBFT:解决拜占庭容错问题的中心化共识算法

你一觉醒来,发现自己没躺床上,而是站到皇帝身边,变成贴身侍卫。皇帝合上奏折,扭头问你:甘肃有没有旱灾?

你刚来,不熟悉业务,但欺君是罪,只好抱着问题溜出门,幸亏遇到三位大臣围在门口点烟,于是你凑前一步说:皇上让我问问你们,甘肃有旱灾?

两个大臣连忙点头,但另一个却吐出两个烟圈,笑而不语。

你的挑战才刚刚开始——到底有没有旱灾?

按照PBFT共识算法,你应该马上挽起两位点头大臣的手臂,找皇上汇报:甘肃确有旱灾一事。因为已达成2/3多数的共识,但且慢一步,先搞清楚一件事:

一、什么是PBFT?

PBFT指实用拜占庭容错算法,和POW(戳蓝字复习概念)一样,PBFT也是一种共识算法,解决的是拜占庭将军问题:几名将军带领各自部队围住敌城,合攻则胜,分攻则败,于是将军们约定攻城时间,但必须通过信使联络,可如果出现叛徒该怎么办?

将军喻指网络节点,解决拜占庭将军问题就要祭出一个概念:拜占庭容错。

网络节点总有错误,它们可能是叛徒(恶意节点),也可能是傻子(故障节点),各节点并不能确保收到的信息没被做过手脚。“拜占庭容错”指在分布式系统里容下这些“错”的同时,又能达成正确的共识。

我们已经熟悉经典的拜占庭容错解决方案:POW算法——使用工作量证明找随机数。

如果你读过专栏第一季的文章,就能体验到那场面的轰轰烈烈:腱鞘炎都快翻出来了,但随机数还是很难找到。可一旦找到随机数,硬邦邦的事实就戳在地上,谁都无法撼动。

很安全,但是没效率。

PBFT只是嫌弃传统方案不实用而已,所以增加一个假设,千万别小看这个假设,它把原本铺漫到天边的工作量变成几乎不需要工作量,这个假设就是:不良节点不超过节点总数的1/3

最终,从效率角度望过去,拜占庭将军问题的传统解法POW在PBFT这种火箭推进器面前顿时灰头土脸,像台烧劈柴的锅炉。

那PBFT具体是如何运作的?

二、PBFT的运作过程

PBFT共识算法的全过程分五步:第一步是“请求”,相当于客户端发出读写需求,第五步是“答复”,相当于系统给客户端的最终答复。

真正达成共识的是中间三步:

第二步:你问大臣(预准备

第三步:大臣回答(准备

第四步:官僚系统间再次确认(确认

PBFT把你和所有大臣(全网节点)称为“副本”,而你是最重要的副本,即“主节点”,负责从大臣们处搜集信息,统筹分发确认,最终牵头答复。

主节点向全网广播,这个过程就是预准备。预准备的关键是分发,主节点为每个请求编上号,然后群发向所有副本。

640_wx_fmt_png

图1 PBFT算法的前两步:请求和预准备

预准备消息(图1右侧三个箭头)含有请求的数字签名(戳此复习),这使得其他副本很容易验证真伪。

通过验证后进入准备阶段:此时,副本向全网广播它自己的答复。为防恶意攻击,副本把预准备消息和准备消息都记在自己的小本子上。如果看预准备消息不顺眼,就什么都不做。

640_wx_fmt_png 1

图2 PBFT算法的前三步:请求、预准备和准备

准备阶段最重要的事:确保所有正常节点达成一致

但总有不一致的节点,比如那位只吐烟圈不吐字的大臣(副本3),PBFT将这种没有响应的节点视作失效。处理失效节点是下一步“确认阶段”要做的事。

进入确认阶段,副本首先验证消息的数字签名,广播确认后,主节点负责统计共识,说白了,你只做一件事:统计出达到系统节点总数2/3的共识,这个共识就是最终答复。

你发现:两票点赞,一票失效,于是主节点在图3右侧双虚线处敲定共识:甘肃有旱灾。

640_wx_fmt_png 2

图3 PBFT的完整过程

最后,进入答复环节,主节点和其他正常副本一起答复客户端,整个过程都在全网监督下一气呵成,“一气呵成”的意思是一秒钟完成。

但你可能会提个问题:如果主节点不按规矩办事系统会怎么办?即,图3左下角的“×”画在主节点上,那系统又该如何应对?

我们称这种情况为“主节点失效”,一旦遇到主节点失效时,系统的应对方案很简单:变更视图

什么是视图?视图即节点排位,变更视图就是其他副本确认主节点出问题后,立即认副本1为主节点,原主节点到后面去排队,变成副本3。

640_wx_fmt_jpeg

图4 变更视图示例

当主节点无法执行请求时,副本必须变更视图,这样才能保持系统活性,关于变更视图条件有三点说明:

第一,至少确保2/3多数的正常节点在同一视图中,换句话说,如果共识未超越2/3多数,主节点就跑去答复客户端,副本就会认定主节点失效。

第二,请求编号必须在系统规定的范围内。还记得在预准备环节里,主节点要给请求分配编号才能广播么?设计这一编号,本来是为便于相互确认,否则请求一多就会对不上账,但这也给主节点扰乱系统的留下一个后门:故意分配超大编号,塞爆内存。

应对方案也很朴素,设一个编号上限就ok,这个上限称为“水线”。一旦副本发现请求编号超出水线范围,就会认定主节点失效。

第三,必须定义出超时的时长,不能让副本无底线地等待;

为满足这点要求,每当副本收到一个请求,就开始计时,直到副本做出最终答复计时才停止。如果超过系统设定的响应时间,而没有看到主节点答复客户端,副本就会认定主节点失效。

于是,系统始终能够应对主节点失效:好好干活你就是中心,一旦作假或怠工,找人换你只是下一秒的事,这就是PBFT算法的核心逻辑

作者把PBFT说成了花,那它有没有软肋呢?

你一定看出来了,如果涌进足够多的不良节点(超过总节点的1/3),则网络势必奔溃,因为根本假设已不成立,所以基于PBFT构建的网络不能像比特币网络一样完全开放。

于是,我们必须引入一个新概念:

三、许可链

指经许可才能接入的链。

小规模的许可链就像私家庄园,称为私有链;较大规模的许可链就像经济开发区内的企业集群,我们称之为联盟链。不管是私有链还是联盟链,入网都必须经过有权人核准。

与许可链对应的概念就是公有链(公链),公有链的代表是比特币,任何节点都能随时出入、随时读取,账本全公开,没有私密性。

而许可链则在地上围了一圈篱笆,你想进来吗?先拿到批准再说,所以私密性好。

当然,和公有链相比,许可链的安全性就短了一截。比如就在4天前,基于PBFT开发的应用Ripple就被曝永久丢失32570个区块,这意味着没有人能够审核Ripple的完整区块链。

虽然当事方称未对普通用户造成影响,但和比特币平稳运行9年多相比,安全性瞬间矮下一头。甚至有人称Ripple的PBFT共识机制为“没有必要又毫无意义的烟雾镜像”。

没有错,PBFT算法并不是去中心化的共识,而是中心化的控制,这就是为什么很多人并没有把Ripple的代币XRP划分至中心化货币的原因。

但PBFT的效率终究秒杀POW,所以几乎所有的大型金融项目都倾向使用PBFT构建联盟链,那这么做对我们有什么好处呢?

举个小例子:传统跨境支付需要3-5天,而基于PBFT的Ripple搞定同样的事只需3-5秒,同时费用下降50%以上。

你看,不管是去中心化还是中心化,足够先进的科技,都和魔法无异。结语

1779年,和珅上表乾隆,西征军在甘肃遇涝,行军延期。皇帝合上奏折,心中蹊跷不已,甘肃已报旱灾多年,不仅减税,而且开捐(卖官),所得全部赈济灾民。

1781年,甘肃布政司王亶望被处斩,陪他一起被诛的还有56名官员,乾隆亲手终结清史上最轰动的欺上瞒下运动——甘肃冒赈案。

原来,链并不会因为私有而安全,如果缺乏足够的信息回路,PBFT算法就会失效,古代官场就是一个例子。

虽然皇帝端坐权力系统中央,但他并不居于信息系统中心,皇帝只是一个与信息系统若即若离的客户端,在本文的例子中,你才是信息系统的君王

官僚体系本质上是权力系统,但它同时也是信息系统。皇帝要了解民情,得通过官僚,民情想上传天听,也得过官僚,而官僚内部的贪腐网络阻断着上下政情。

而我们现代社会就不同,因为有更多的信息流,这让信息系统从权力系统中独立出来,最终使得传统权贵的招数在现代社会根本玩不下去。

有人说根治腐败得靠讲道德,有人说严刑峻法更有效,还有人说只要贴上民主的膏药就能药到病除。但历史证明,这些符合常人直觉的土办法,都炼不出好钢。

腐败看起来是权力问题,但说到底是信息问题,只要我们凿通更多的信息回路,把更多事实摆在人们面前,把内部信息摊到阳光下一晒,自然能根治腐败。

所以,想想这两年清透很多的官场,难道是因为公务员们多上了两节党课、多抄了三遍党章?还是因为全国人手一部智能手机?

一段视频了断一堆官员前途的故事,不应该被忘记。

本文从PBFT共识算法分叉聊到治理腐败,结论也就一句话,这句话同时也是区块链的意义所在:

阳光是最好的杀毒剂

640_wx_fmt_jpeg 1


回到我们专栏的主题,考虑到难度已经爬坡,为让你的思路更柔顺,正文没有铺设一个英文单词。

如果你想深扒一层,请自行对照文末词汇表,这可以让你更润滑地阅读PBFT算法发明者的说明书:

http://pmg.csail.mit.edu/papers/osdi99.pdf

如果你不习惯看原文,可参考趣链科技联合创始人、浙大博士李启磊的文章:

http://blog.liqilei.com/bai-zhan-ting-gong-shi-suan-fa-zhi-pbftjie-xi/

其中不仅有对预准备、准备和确认三步的技术描述,而且一些小概念的精致说明,如消息日志、稳定检查点和水线。

词汇表

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

Practical Byzantine Fault Tolerance

拜占庭容错(BFT)

Byzantine Fault Tolerance

工作量证明(POW)

Proof Of Work

客户端 client  文中的皇帝

副本 replica   系统中的记账节点,文中的官僚系统

主节点 primary  文中的你

备份 backup 即除主节点外的其他节点,当主节点失效时按序备份

视图 view “你-大臣1-大臣2-大臣3”的顺位架构就是一种视图

变更视图 change view 主节点失效时的系统策略

活性 liveness 主节点没失效,就说明系统有活性

消息日志 message log

水线  watermark

稳定检查点 stable checkpoint

请求 request

预准备 pre-prepare

准备 prepare

确认 commit

答复 reply

640_wx_fmt_jpeg 2

为便于你理解,和上篇讲述DPOS的文章一样,作者把共识确认条件从2/3+1多数简化为2/3,因为当节点数足够多时,2/3+1多数≈2/3多数。

另外,实际场景中不可能只有4个节点,更可能是40个、400个或者更多,你可以把本文的例子推广到9个大臣,然后在A4纸上推演一遍五步过程和视图变更。

因为这样你就能轻而易举地发现:正文变更视图的案例好不严谨——4个副本一旦变更视图,只剩2个正常副本,另外2个是失效节点:吐烟圈的大臣和你。所以,这局视图根本玩不下去。

如果用9个节点推演就不存在这样的问题,相信我,在A4纸上推演一遍,你一定能彻底理解PBFT。

祝你每周都有进步。