0

Image Description

荆文征

Zhidu Inc.


你好,再见

分布网络-共识算法

  • 小酒馆老板
  • /
  • 2018/7/20 18:25:43


H2

分布式网络

我们来大致的看一下网络的发展脚步

在1961年,麻省理工学院的L.克莱因罗克(L.Klenrock)博士发表论文《大型通讯网络的信息流》,第一次详细论述了分布式网络理论。

我们可以看到,从这个理论开始到现在也不过50多个年头,连一个世纪都没有,甚至说,L.克莱因罗克(L.Klenrock)博士(互联网的创始人之一)至今还在世。

不仅让我们感叹,人类的进步的速度…

之后60年代,美籍波兰人保罗·巴兰(Paul Baran)撰写多份报告,不仅系统地阐述了分布式网络理论而且提出后来网络传播的核心——“包切换”(Packet Switching)

与此同时,英国物理学家D.W.戴维斯也提出“分布式网络”理论,其原理同巴兰的构想如出一辙,唯一的区别在于命名。巴兰将拆分的、便于传送的数据称为“块”。而戴维斯经过深思熟虑,并请教语言学家后,选择了“包”(packet)这个术语,从此拆分传送数据的方式也就被称为“包切换”。另外,戴维斯构想包切换的初衷,也同巴兰为军方服务有所不同,他是想创建一个更加有效的网络系统,从而使更多的人可以利用网络进行交流。

1964年伊凡·沙日尔兰德(Ivan Sutherland)继任担任该处处长,两年后的鲍勃·泰勒(Bob Taylor)上任,他在任职期间萌发了新型计算机网络的想法,并筹集资金启动试验。在鲍勃·泰勒的一再邀请下,日后成为“阿帕网之父”的拉里·罗伯茨出任信息处理处处长。

1965年的时候,在兰德公司(Rand)的支持下,巴兰正式向美国空军提出创建分布式网络的计划。由于巴兰的想法适合军方的需要,因而受到美国国防部的高度重视。按照分布式网络的原理,由于单个节点的重要性大大降低,所以网络的任何节点遭到破坏,都不至于影响整个网络,而且节点越多,网络的安全性能就越高。

这个包切换,网络专家尼葛洛庞帝(Nicholas Negropoute)对包切换及网络传播原理做了如下解释:

一个个信息包各自独立,其中包含了大量讯息,每个信息包都可以经由不同的传输路径,从甲地传输到乙地。现在,假定我要从波士顿把这段文字传到旧金山给你。每个信息包……基本上都可以采取不同的路径,有的经由丹佛,有的经由芝加哥,有的经由达拉斯,等等。假设信息包在旧金山以此排序时,却发现6号信息包不见了。6号信息包究竟出了什么事?军方拨款资助阿帕网时,正值冷战高峰。核战的威胁让人忧心忡忡。因此,假设6号信息包经过明尼阿波利斯时,敌人的飞弹正好落在这个城市。6号信息包因此不见了。其他的信息包一确定它不见了,就会要求波士顿重新传输一次(这次不会再经过明尼阿波利斯了)。也就是说,因为我总是有办法可以找到可用的传输途径,假如要阻止我把讯息传输给你,敌人必须扫荡大半个美国。没错,在寻找可用的传输路径时(假如越来越多城市被敌人摧毁),系统的速度就会减慢,但系统不会灭亡。了解这个道理非常重要,因为正是这种分布式体系结构令互联网能像今天这样三头六臂。无论是通过法律还是炸弹,政客都无法控制整个网络。讯息还是传提交去了,不是经由这条路,就是走另一条路出去。

有了这些理论的支持,以及政府的介入。

1967年,罗伯茨来到高级研究计划署ARPA,着手筹建“分布式网络”。人员调度和工程设计很顺利,不到一年,就提出阿帕网的构想。随着计划的不断改进和完善,罗伯茨在描图纸上陆续绘制了数以百计的网络连接设计图,使之结构日益成熟。

1968年,罗伯茨提交研究报告《资源共享的计算机网络》,其中着力阐发的就是让“阿帕”的电脑达到互相连接,从而使大家分享彼此的研究成果。根据这份报告组建的国防部“高级研究计划网”,就是著名的“阿帕网”,拉里·罗伯茨也就成为“阿帕网之父”。

1969年底,阿帕网正式投入运行。
最初的“阿帕网”,由西海岸的4个节点构成。第一个节点选在加州大学洛杉矶分校(UCLA),因为罗伯茨过去的麻省理工学院同事L.克莱因罗克教授,正在该校主持网络研究。第二个节点选在斯坦福研究院(SRI),那里有道格拉斯·恩格巴特(D.Engelbart)等一批网络的先驱人物。此外,加州大学圣巴巴拉分校(UCSB)和犹他大学(UTAH)分别被选为三、四节点。这两所大学都有电脑绘图研究方面的专家,而泰勒之前的信息处理技术处处长伊凡·泽兰教授,此时也任教于犹他大学。

我们可以看到这就是最初的互联网的雏形,它本身就是 peer to peer的分布式网络。

ARPA网无法做到和个别计算机网络交流,这引发了研究者的思考。根据诺顿的看法,他的设计需要太多的控制和太多的网络中机器设备的标准化。因此,1973年春,文顿·瑟夫和鲍勃·康(Bob Kahn)开始思考如何将ARPA网和另外两个已有的网络相连接,尤其是连接卫星网络(SAT NET)和基于夏威夷的分组无线业务的ALOHA网(ALOHA NET)瑟夫设想了新的计算机交流协议,最后创造出传送控制协议/互联网协议(TCP/IP)。

1975年,ARPA网被转交到美国国防部通信处(Defense Department Communicationg Agence)。此后ARPA网不再是实验性和独一无二的了。大量新的网络在1970年代开始出现,包括计算机科学研究网络(CSNET,Computer Science Research Network),加拿大网络(CDnet,Canadian Network),因时网(BITNET,Because It’s Time Network)和美国国家自然科学基金网络(NSFnet,National Science Foundation Network)。最后一个网络最终将在它自身被商业网络取代前代替ARPA网作为互联网的高速链路。

1982年中期ARPA网被停用,原先的交流协议NCP被禁用,只允许使用Cern的TCP/IP语言的网站交流。1983年1月1日,NCP成为历史,TCP/IP开始成为通用协议。

1983年ARPA网被分成两部分,用于军事和国防部门的军事网(MILNET)和用于民间的ARPA网版本。

1985年成为TCP/IP协议突破的一年,当时它成为UNIX操作系统的组成部分。最终将它放进了Sun公司的微系统工作站。

当免费的在线服务和商业的在线服务兴起后,例如Prodigy、FidoNet、Usenet、Gopher等,当NSFNET成为互联网中枢后,ARPA网的重要性被大大减弱了。系统在1989年被关闭,1990年正式退役。

另外,咱们现在这种 服务端-客户端的方式是从80年代到90年代,开始流行的。当时大部分文件传输还是依靠电话线,使用FTP或者Usenet网络。90年代后,新的数据压缩技术出现,例如 MP3,MPEG。在此背景下,Napster 出现了。用户可以免费下载 Napster 客户端,然后从别人那里下载 MP3 文件,同时自己也作为一台服务器,供别人下载。Napster 有一台中心服务器,向所有用户提供文件目录服务,客户想下载音乐时,需要先到这台中心服务器上查询哪些客户端拥有这首音乐,然后直连到那台机器下载。不到一年时间,它的用户量达到100万,两年时间不到,金属乐队起诉这家公司。2001年七月,Napster 被关闭,此时距它成立还不到三年时间。

我们可以来看看虽然,Napster服务是以p2p网络以基础,但是它依靠中心节点来存储索引,所以这也是为什么 Napster 容易被关闭的原因。

在 2000年的时候,Gnutella出现,它向与自己直接连接的节点发起查询,被查询的结点再去查询与自己连接的节点,如此递归下去,直到查询到为止。尽管它没有直接查询中心节点有效率,但它不再依赖一个中心化的索引节点。

并且与此同时,Freenet在2000年也开启了。Freenet 是一个内容发布和沟通平台,专为抵御内容审查而设计。在 Freenet 网络中,任何人都可以在上面自由发表言论,做自己想做的网站,传自己想传的资源。Freenet 开启了暗网时代!

在2001年,诸多肥宅的希望-Bittorrent!降世!!

Bittorrent 是基于 TCP/IP 协议开发的。发布文件之前需要制作种子文件,种子是一个记录了下载文件的服务器信息的索引文件。BitTorrent 协议下载的特点是,下载的人越多,提供的带宽也越多,下载速度就越快。同时,拥有完整文件的用户也会越来越多,文件的“寿命”也就越长。
BitTorrent 引入了分布式哈希技术( DHT ),相比泛洪查询技术,DHT 效率显著提升。

2009年bitcoin出现,在此之前从未让这么多民众开始关心这些东西。它的出现,可以说是一场革命。

Namecoin,2011年。Namecoin 是一个去中心化的域名系统,功能和传统的域名供应商类似,用来解析域名。我们现在使用的域名系统是分布式而非去中心化的,所以理论上强权是可以做到控制整个域名系统,从而控制互联网的访问。而 Namecoin 是去中心化的,理论上是没有人可以关闭他的。Namecoin 提供的域名后缀是 .bit,目前主流浏览器都还不支持它,要想使用就需要安装插件。可以说 Namecoin 是第一个非货币的区块链应用。早期以太坊的创始人就提到了用区块链来做 DNS 系统的可能性。
所以愣着干嘛,赶紧把 google.bit baidu.bit mi.bit 搞下来~ 等升值去吧

Diaspora,2012年。Diaspora 将自己定位为开源的个人 Web 服务器和去中心化的社交网络。2010年在 Kickstarter 上筹资20万美金后,项目正式成立,并迅速发布了一个测试版本,到了2012年,稳定的社区版才算正式发布。Diaspora 的目标之一就是替代Facebook。Facebook 是一个集中式的平台,用户使用它时,只需要一台 Web 浏览器即可,而 Diaspora 是需要专门下载自己的程序客户端的,这也使得推广起来比较难。另外,有的人其实根本不关心集中式平台带来的隐私问题。

DSNs, Descentralised Storage Networks。 去中心化存储网络的背后思想是将云存储转变成一种带有激励措施的去中心化存储系统,并向愿意提供存储空间的矿工节点发放代币。经济激励是关键,它是系统可持续运行的重要保障。目前代表作有 IPFS。在比特币这样的区块链上存储数据,效率非常低,并且成本高,而在 IPFS 上,我们可以很方便的存储例如 PDF、mp4 等文件。

以上就是P2P网络的发展历史,我们可以将它们分为4个阶段

  1. 依赖中心索引系统的 Napster 时代
  2. 使用泛洪查询,摆脱中心索引的 Gnutella 的时代
  3. 使用分布式哈希(DHT)的 BitTorrent
  4. 带激励的分布式存储

H2

共识问题

区块链核心价值就在于实现了去中心化的价值传输。那么区块链是如何做到这种价值传输的呢,很显然共识机制起到了决定性作用,今天我们就来深入讲解共识机制背后的原理及其发展。

首先我们来看一个我们不能绕开的问题,“拜占庭将军问题”,这个问题,首次是由 Leslie Lamport等人在1982年在他的同名论文The Byzantine Generals Problem 中提到。Fischer, Lynch 和 Patterson在1985年发表的论文中提出了可以说是最重要的分布式系统定理:FLP不可能定理(在异步通信场景,即使只有一个进程失败,也没有任何算法能保证非失败进程达到一致性);2000年,EricBrewer教授又进一步提出了CAP猜想:一致性、可用性和分区容错性三者无法在分布式系统中被同时满足,并且最多只能满足其中两个;2002年,Lynch与其他人证明了Brewer的猜想,从而把CAP上升为一个定理。这期间和之后,涌现了一些著名的分布式一致性算法,如LeslieLamport在1989年提出的Paxos算法,1999年Castro和Liskov提出的PBFT算法等。直到比特币采用POW进行记账后,共识算法才真正进入到了大众的视野里。


H3

共识资料


H4

FLP不可能原理

任何问题一般都存在一个理论上的下限(最坏的情况),那么对于分布式系统的共识问题,其理论上的解是什么呢?经过科学家的证明,异步分布式系统的共识问题的通用解决方法是:无解,也就是说即便是在网络通信可靠的情况下,可扩展的分布式系统的共识问题是无解的。这个定理由Fischer,Lynch和Patterson三位科学家于1985年发表的论文中给出了证明,也叫做FLP不可能原理。这个定理也告诉人们不要试图去设计一套在任意场景下都适用的共识算法,否则等同于浪费时间。


H4

CAP原理

CAP定理(CAP theorem),又被称作布鲁尔定理(Brewer’s theorem),它指出对于一个分布式计算系统来说,不可能同时满足以下三点:

  • 一致性(Consistence) (等同于所有节点访问同一份最新的数据副本)
  • 可用性(Availability)(每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据)
  • 分区容错性(Partition tolerance)(以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择[3]。)

根据定理,分布式系统只能满足三项中的两项而不可能满足全部三项。

理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致,即丧失了C性质。如果为了保证数据一致性,将分区一侧的节点设置为不可用,那么又丧失了A性质。除非两个节点可以互相通信,才能既保证C又保证A,这又会导致丧失P性质。

此定理也是由FLP定理证明的作者之一的Lynch给出证明。


H4

BASE原理

BASE是对CAP原理中一致性和可用性权衡以后的结果:

Base Available:基本可用性,是指在系统的部分节点出现故障以后,允许损失一部分可用性;

Soft state:软状态,允许系统中的数据存在中间状态,允许不同节点之间的数据副本的同步过程存在延迟;

Eventually consistent:最终一致性,是指系统中的数据,在经过一定的时间以后会最终达到一致状态,也就是降低一致性要求,不要求实时的强一致性。

比特币区块链就是一个很好的例子,在区块链延长的过程中,有可能会出现分叉,不同的节点上区块不一样(不一致),但是经过一定时间以后,随着所有节点都切换到最长的主链,分叉的情况就会消失(最终一致)。


H3

拜占庭容错

我们现在来看一下,拜占庭容错,到底讲了什么?

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题,将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果,因此各位将军必须通过投票来达成一致策略,即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向,他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军,这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

要让这个问题有解,有一个十分重要的前提,那就是信道必须是可靠的。如果信道不能保证可靠,那么拜占庭问题无解。关于信道可靠问题,会引出两军问题。两军问题的结论是,在一个不可靠的通信链路上试图通过通信以达成一致是基本不可能或者十分困难的。


H4

两军问题


Image Description
两军问题

白军驻扎在沟渠里,蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大,但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通,只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议,这就是两军问题。

看到这里您可能发现两军问题和拜占庭将军问题有一定的相似性,但我们必须注意的是,通信兵得经过敌人的沟渠,在这过程中他可能被捕,也就是说,两军问题中信道是不可靠的,并且其中没有叛徒之说,这就是两军问题和拜占庭将军问题的根本性不同。

倘若1号蓝军(简称1)向2号蓝军(简称2)派出了通信兵,若1要知道2是否收到了自己的信息,1必须要求2给自己传输一个回执,说“你的信息我已经收到了,我同意你提议的明天早上10点9分准时进攻”。

然而,就算2已经送出了这条信息,2也不能确定1就一定会在这个时间进攻,因为2发出的回执1并不一定能够收到。所以,1必须再给2发出一个回执说“我收到了”,但是1也不会知道2是否收到了这样一个回执,所以1还会期待一个2的回执。

虽然看似很可笑,但在这个系统中永远需要存在一个回执,这对于两方来说都并不一定能够达成十足的确信。更要命的是,我们还没有考虑,通信兵的信息还有可能被篡改。由此可见,经典情形下两军问题是不可解的,并不存在一个能使蓝军一定胜利的通信协议。

不幸的是,两军问题作为现代通信系统中必须解决的问题,我们尚不能将之完全解决,这意味着你我传输信息时仍然可能出现丢失、监听或篡改的情况。但我们能不能通过一种相对可靠的方式来解决大部分情形呢?这需要谈到TCP协议。事实上,搜索“两军问题与三次握手”,您一定可以找到大量与TCP协议相关的内容


Image Description
TCP 握手协议

TCP协议中,A先向B发出一个随机数x,B收到x了以后,发给A另一个随机数y以及x+1作为答复,这样A就知道B已经收到了,因为要破解随机数x可能性并不大;然后A再发回y+1给B,这样B就知道A已经收到了。这样,A和B之间就建立一个可靠的连接,彼此相信对方已经收到并确认了信息。

而事实上,A并不会知道B是否收到了y+1;并且,由于信道的不可靠性,x或者y都是可能被截获的,这些问题说明了即使是三次握手,也并不能够彻底解决两军问题,只是在现实成本可控的条件下,我们把TCP协议当作了两军问题的现实可解方法。

解决方法,可参考量子纏結,量子信道。

所以,在这种情况下,我们必须默认,信道是安全的,才可以继续去看待拜占庭容错这个问题。


H4

拜占庭容错问题

回到刚才的问题,我们可以看出来,问题在于,将军中可能出现叛徒,他们不仅可能向较为糟糕的策略投票,还可能选择性地发送投票信息。假设有9位将军投票,其中1名叛徒。8名忠诚的将军中出现了4人投进攻,4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻,而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来,投票结果是5人投进攻,从而发起进攻;而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯,叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下,也不能排除信使被敌人截杀,甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假始那些忠诚(或是没有出错)的将军仍然能通过多数决定来决定他们的战略,便称达到了拜占庭容错。在此,票都会有一个默认值,若消息(票)没有被收到,则使用此默认值来投票。

上述的故事映射到计算机系统里,将军便成了计算机,而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全,却没办法单纯的用密码学与数字签名来解决。因为不正常的电压仍可能影响整个加密过程,这不是密码学与数字签名算法在解决的问题。因此计算机就有可能将错误的结果提交去,亦可能导致错误的决策。


H4

拜占庭容错论文证明

Lamport在其论文中证明:假设将军总数为N,叛变的将军数为f,则在N > 3f 时,上述的拜占庭将军问题可以解决,将军达成共识的时间复杂度为O(N^(f+1)),即指数级的复杂度。

接下来,让我们来推算下这个容错。

假设总共有3个将军A,B,C,其中1个将军叛变,按照上面的结论,因为不满足N >= 3f + 1的条件,因此不可能达成一致:

假设A是叛变者同时也是提案者,他派出两名信使分别告诉B说进攻,告诉C说防守,结果最终C会得到两份矛盾的消息:A的信使告诉他说防守,但是B的信使又告诉他说进攻,无法形成共识;

假设叛变的将军是A,但提案者是B,B派出信使告诉A和C某日某时某刻发起进攻,但是A收到消息后可以篡改,他可以告诉C说收到的是防守的指令,同样无法达成共识;

如果加1名将军,总共A,B,C,D四名将军,同样只有1名将军叛变,此时满足N >= 3f + 1的条件,我们再来验证看是否能达成一致:

假设A是提案者,同时也是叛徒,此时无论他怎么安排,剩余的3名将军中总会有至少2名的将军得到相同的指令,假设B和C得到的是A发出的进攻指令,而D得到的是A发出的防守的指令,根据少数服从多数的原则,最终B,C,D都会达成共识:

D收到A的防守指令,但是收到B和C的进攻指令,少数服从多数,D认为要进攻;

B收到A和C的进攻指令,收到D的防守指令,少数服从多数,B也选择进攻;

C收到A和B的进攻指令,收到D的防守指令,同样C也决定进攻;

最终B,C,D都进攻,A的诡计无法得逞。

通过上面的简单验证,我们已经了解到N >= 3f + 1确实能做到存在拜占庭节点的分布式系统的共识,换句话说PBFT算法最多可以容许不超过(N-1) / 3个问题节点。作者Lamport凭借他在分布式系统共识算法上的杰出成绩,获得了2013年的图灵奖。


H3

PAXOS 共识算法

paxos算法是由Leslie Lamport于1990年提出的一种非拜占庭模型的分布式系统共识算法,对的就是提出拜占庭问题的大牛,自己提出的解答。

为了描述算法,Lamport虚拟了一个希腊城邦paxos(这也是算法名字的由来),这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题(Byzantine failure,即虽然有可能一个消息被传递了两次,但是绝对不会出现错误的消息);只要等待足够的时间,消息就会被传到。另外,Paxos 岛上的议员是不会反对其他议员提出的决议。

paxos算法的推导过程理解起来有一定困难,但是从操作层面讲,paxos解决共识的思路其实并不难。

首先算法将网络中的节点划分为3种角色:提案者,接受者和学习者。

  • 提案者:负责提出提案,这里提案可以是任何可以达成共识的东西,比如某个要写入DB的值,一条日志等等;
  • 接受者:接收提案,确定接受还是拒绝提案;
  • 学习者:获取并同步最终选择的提案;

提案是一个由提案编号和提案值组成的pair,即[proposalNo, proposalValue],一个提案被半数以上的接受者接受即认为达成共识。提案编号是最终能达成共识的关键,每个接受者都会记录已响应过的提案的最大编号,并且承诺不会接受比此提案号小的提案。

具体操作时,paxos可以分为两个阶段:

第一阶段:准备阶段,提案者选择一个提案号,发送提案给接受者,试探能否得到半数以上接受者的响应;
第二阶段:如果第一阶段收到超过半数的接受者的响应,则提交提案,如果能够得到半数以上接受者的响应,则共识完成;


H4

paxos算法推导过程

paxos算法最初的论文被公认为是晦涩难懂,后来作者Lamport又发布了《paxos made simple》,用更加容易理解的方式对paxos做了阐述。

论文中通过从简单到复杂逐步添加约束条件的方式来论证其共识算法。虽然作者已经做了简化,但毕竟还是比较学术化,理解论文中提出的几个约束条件还是有一定的困难,详细的过程读者可以自行阅读论文。

paxos算法的论证过程虽然比较难理解,但是实际的操作过程却比较简单,网上有人用一个形象的例子来说明paxos达成共识的过程:

假设有2个商人P1和P2想从政府买块地,商人想要最终拿下这块地,需要经过3个政府官员A1,A2和A3的审批,只有经过2个以上的官员同意,才能最终拿下地皮,现在的目标是:最终只能有一个商人拿到地。另外假设商人要想通过官员的审批,必须给一定数量的贿赂费。

我们看看这样一个场景下,如何达成共识(选定一个商人把地批给他)。

拿地是一件争分夺秒的事情,于是商人P1和P2开始准备了:

  1. 假设P1的行动快一些,他很快找到了官员A1和A2,告诉两人只要批了地就给100W的感谢费,两个官员很高兴,告诉P1回去拿钱吧;
    注:这一步实际上是P1在进行paxos算法中的准备阶段;
  2. 商人P2在P1之前先找了官员A3,告诉他只要批了地就给他200W,A3愉快的接受了;
  3. P2又跑到官员A1和A2那,承诺只要批地,就给200W,因为这份费用比此前P1承诺的高,于是贪财的官员A1和A2变卦了;
    注:以上两步是P2在进行paxos的准备阶段;
  4. 商人P1此前已经初步贿赂A1和A2成功,于是满心欢喜的拿着准备好的钱找到了A1和A2,结果却是A1和A2都告诉他:对不起,MrXX,就在刚刚有人承诺了200W,你是个聪明人,你懂得该怎么做的。商人P1很是郁闷,告诉A1和A2:容我想想再给答复;
    注:以上P1拿钱给A1和A2,对应与paxos算法的提交阶段,因为此前P1已经得到了3位官员中2位的同意;
  5. 就在P1还在犹豫要不要提高贿赂费的时候,商人P2按之前承诺的向A1和A2的账户分别打入200W,于是A1,A2拿钱办事,批准通过,因为超过半数的官员审批通过,于是在政府网站上向大众公布P2最终拿地成功,所有人都知道了这个结果。

注意上面的过程中的一个问题:假设上面第(4)步中P1被拒绝以后,立刻向官员承诺一个更高的费用,那么当商人P2拿着钱到A1和A2时,同样也会被拒绝,于是P2又可能会抬价,这样交替下去就可能造成死循环,这就是paxos算法中的活锁问题。


Image Description
paxos 算法交互图


H4

paxos 算法优化

paxos算法有很多变种和优化算法,这里只说一下multi paxos算法。

之前提到paxos算法存在活锁的问题:一个提案者提案被拒以后用更高的提案,另一个提案者发现被提案被拒以后也增加提案编号,从而形成死循环,造成活锁

multi paxos算法对paxos进行了优化,引入leader这个角色以避免活锁问题。首先选举出一个节点作为leader,之后所有的提案先提交给leder节点,因为通过leader可以控制提案提交进度,从而避免活锁发生。

考虑前面商人买地的那个例子:此时官员们不直接和商人碰面,而是由官员指定一个总代理,啥事情都先跟代理说,再由代理统一汇报。于是P1跑到代理那承诺说:只要能批,咱就给领导100W酬劳,但是代理可以选择不立刻就去把这事给官员汇报,他可以等一等,结果不久后P2来承诺说事成之后200W,代理就可以选择报价高的拿给官员审批。

可以参考paxos和multi paxos算法的流程图仔细体会一下:


Image Description
paxos 算法交互图


Image Description
multi paxos 算法交互图

从图中可以看到最大的区别在于,multi paxos算法没有了第一阶段(prepare阶段),而是直接由leader发送提案(直接进行第二阶段),如果收到半数以上的acceptor的应答就达成共识。

引入leader节点虽然可以解决活锁问题,但是又引出其他一些问题:比如leader应该如何选举产生等等。


H4

paxos 算法总结

paxos是CFT类共识算法,不考虑拜占庭错误即节点可能作恶的情况;

paxos算法将节点分成三个角色:提案者(proposer),接受者(acceptor)和学习者(learner)

paxos算法分成两个阶段来完成共识:

  1. 准备阶段:提案者发出提案,试探是否能得到半数以上acceptor的同意;
  2. 提交阶段:如果提案在准备阶段得到半数以上的支持,则尝试提交此提案,如果响应的acceptor超过半数以上,则此提案被选定,完成共识;否则提案者需要新选定一个提案编号重新进入准备阶段;


在这里,我们有必要解释一下 CFT类,其实分布式系统的共识算法主要分为: CFT算法(Crash falut)和BFT(Byzantine fault)算法。CFT算法主要解决网络中节点可能出错(比如宕机),但是节点不会作恶(比如伪造数据)的情况下节点之间如何达成共识,而BFT算法则针对网络中可能存在节点作恶的情况下节点间达成共识的方法。


H3

RAFT 共识算法

结合咱们刚才学习的 paxos 共识算法,在后面我们提到的 multi paxos算法的leader选举问题,raft给出了答案。它是一种paxos改进算法。它有许多的开源参考实现,具有 GO,C++,Java和Sacle的完整规范实现。更多的实现可以查看The Raft Consensus Algorithm,具体的实现可以查阅 In Search of an Understandable Consensus Algorithm

raft是 paxos 的改进方法,所以他是 CFT类,在他的算法中,他的容错率为 n > 2f即可,也就是说,有超过一半的节点进行了统一,那么就说明完成了共识操作了。因为不存在做恶的节点。

在这里,我们就不想进行这个验证了。大家可以思考一下。


H4

角色划分

raft 把节点分为三种角色,

  • leader: 负责Client交互和log复制,同一时刻系统中最多存在1个
  • follower: 被动响应leader请求RPC,从不主动发起请求RPC
  • candidate: 由Follower向Leader转换的中间状态


Image Description
server states - 节点的状态


H4

Terms

众所周知,在分布式环境中,“时间同步”本身是一个很大的难题,但是为了识别“过期信息”,时间信息又是必不可少的。Raft为了解决这个问题,将时间切分为一个个的Term,可以认为是一种“逻辑时间”。如下图所示:


Image Description
term 示意图

  1. 每个Term至多存在1个Leader
  2. 某些Term由于选举失败,不存在Leader
  3. 每个Server本地维护currentTerm

H4

选举过程

在开始启动之初,所有的节点都以 follower 角色启动,如果某个 follower 不想听从 领导者意见了,想起义。那么就把自己的状态修改为 candidate 状态,并且向其他的节点发起投票请求,我想当leader,其他的节点回复他的请求。如果大多数的节点都进行了投票,该 node 就会再次修改状态 从 candidate -> leader.

以上的过程就被称为 选举过程。

接下来,我们来看一下实际中 raft 操作。

我们假设存在三个节点,Nodea,Nodeb,Nodec,raft 会给每一个节点都设置两个 timeout settings,也就是时间超时设置. 第一个时间的超时是 election timeout,也就是选举超时,如果达到这个时间,节点就会由follower转换为 candidate,也就是咱们之前说的起义。其中 在 raft中,这个选举超时的值设置为150ms和300ms之间的随机值。在达到时间超时之后,节点会转换身份为 candidate,并且将自己的 term 增加1,我们可以理解为 要换代了,进行国号的修改。另外,默认的 转换身份的节点会给自己投上一票~然后向其他的follwer节点发送所有选票的请求(大家支持支持我吧~)。此时我们假设NodeA时间超时了,成为了candidate,并且更改了 term为1,并且NodeA 给自己投上一票
接下来,收到消息的 follower,也就是NodeB和NodeC,要确认国号,也就是 term 为 1 的这个朝代内,他没有投票过!之后他会针对为这个 candidate 即 Nodea 进行投票~并且在此之后,follower 节点即 Nodeb,Nodec重置自己的 election timeout.
一旦 candidate即Nodea 获得了大多数的支持票之后,它就成为了 leader 起义完成。

随后的时间里,leader会对他的follower 通过心跳超时heartbeat timeout的方式发送互动消息。这里我们就接触到了第二个 时间超时。follower 会在接收到消息之后,重置他的选举超时时间,并进行回复。

这种情况会一直存在,直到 leader Nodea 死去(死机,宕机),接下来,选举超时的节点,有可能是 Nodeb,有可能是 Nodec,会重复以上选举超时,进行选举的操作。

要求,在一个term下只能存在一个 leader。 (一个国号下只能存在一个领导人)

那么如果出现了!两个follower 在同一个时刻成为了 candidate 那怎么办?

这种情况我们称为 分裂投票,好的,我们接下来进行一次分裂投票吧。

在这个时候我们在加入的一个 Noded。假设此时。 Nodea 和 Noded,timeout settings 在同一个时刻进行了起义,他们都会成为 candidate,他们定国号都为 term 2. 他们向 node bc 发送所有选票请求。因为 时间先后的顺序,bc只能为同一个 term2 朝代内的一个节点投票,所有最后 a d 他们选票都是 2.所以进入第二次超时投票,因为超时时间是随机的额,所以肯定会最终出现一个领导。当然 term2 这个朝代内就不存在领导了~


H4

日志复制

此时基本的流程就是, 客户端发送一个提案(值)给 leader ,leader 将提案追加到log中,将日志中的值广播给他的 follower,大于一半的 follower 给予肯定反馈,那么 leader 确认提案。
接下来, leader 告诉会再次发送请求告诉所有的 follower ,刚才的提案已经提交了。所有的follower,此时该集群内就现在的系统状态达成了共识。这个过程叫做 日志复制

我们来看一下 raft内的日志复制的做法吧

还是 Node abc。三个节点,其中 Nodea为leader。

我们的客户端向 Nodea发送更改,例如为5。发送给leader nodea,nodea不会立马发布,他会把这个值放置在日志中。然后再下一次心跳超时消息时,把值带给他的follower。如果大多数的粉丝同意这个值,nodea就会把这个值,设置为提交,并修改 nodea节点值。并把这个响应结果返回给客户端。其中设置为提交的这个消息会在下一次的心跳超时消息时传递给 其他的 follower。


H4

raft 网络分区

raft 可以在网络分区同样适用。假设我们此时有 5个节点 node abcde,其中 ab为一个分区(a为leader),cde为一个分区(c为leader)。

我们添加使用两个客户端尝试更新这两个leader。

假如此时,我们向A发送一个 消息,A会向他的 follower B 发送消息,但是因为他的个数达不到满足,所以他的消息状态始终为 为提交。
此时,我们向C发送一个消息,它最终会因为拥有两个 follower而达到消息最终确定。

此时我们来 治愈分区.

NodeA 会看到的更高的 term,而停止。节点A和B都将回滚他们未提交条目并且匹配到最新的leader的条目。

这个时候整个 网络达成一致~


H4

raft 总结

raft 算法的容错率为 2f < n, 原因是 它并没有把做恶的节点这种情况算入,也就是他只针对 节点死机宕机的情况进行了处理。

其他的特性,我们在讲完 PBFT 之后,会与 PBFT 一起进行对比查看。

!!!!!都是虚的!!!!! raft 动画演示


H3

PBFT 算法

PBFT是Practical Byzantine Fault Tolerance的缩写,意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov(利斯科夫)在1999年提出来的,解决了原始拜占庭容错算法效率不高的问题,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上(OSDI99)。没错,这个Loskov就是提出著名的里氏替换原则(LSP)的人,2008年图灵奖得主。

PBFT算法目前在许多区块链项目中都有运用,例如国内的迅雷,腾讯等公司的区块链使用的就是PBFT算法(应该是对算法进行了优化),超级账本的Farbic v0.6版本也使用了PBFT作为其共识算法。

简单来说一下 PBEF,在网上看到一个故事可以概述这个算法。

PBFT算法要求至少要4个参与者,一个被选举为军长,3个师长。军长接到总司令命令:你们向前行军500公里。军长就会给3个师长发命令向前行军500公里。3个师长收到消息后会执行命令,并汇报结果。A师长说我在首都以东500公里,B师长说我在首都以东500公里,C师长说我在首都以东250公里。军长总结3个师长的汇报,发现首都以东500公里占多数(2票>1票),所以就会忽略C师长的汇报结果,给总司令汇报说,好了,现在部队是在首都以东500公里了。这就是PBFT算法。

在可以理解为:对于每一个收到命令的将军,都要去询问其他人,他们收到的命令是什么。也就是说利用不断的信息交换让可行的节点确认哪一个记录选择是正确的,即发现其中的背叛者

采用PBFT方法,本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息,通信代价是非常高的。通常采用PBFT算法,节点间的通信复杂度是节点数的平方级的

但是即使如此,也已经把之前的指数级 变成了现在的 多项式级


H4

PBFT 算法 3f+1 <= n 的推论

我们会在 下面和 raft 对比的时候进行详细说明。这里我们就知道这个就是如此就好了。


H4

PBFT 算法基本流程

pbft算法的基本流程主要有以下四步:

  1. 客户端发送请求给主节点
  2. 主节点广播请求给其它节点,节点执行pbft算法的三阶段共识流程。
  3. 节点处理完三阶段流程后,返回消息给客户端。
  4. 客户端收到来自f+1个节点的相同消息后,代表共识已经正确完成。

为什么收到f+1个节点的相同消息后就代表共识已经正确完成?从上一小节的推导里可知,无论是最好的情况还是最坏的情况,如果客户端收到f+1个节点的相同消息,那么就代表有足够多的正确节点已全部达成共识并处理完毕了。


H4

算法核心三阶段流程


Image Description
PBFT流程

算法的核心三个阶段分别是pre-prepare阶段(预准备阶段),prepare阶段(准备阶段),commit阶段(提交阶段)。图中的C代表客户端,0,1,2,3代表节点的编号,打叉的3代表可能是故障节点或者是问题节点,这里表现的行为就是对其它节点的请求无响应。0是主节点。整个过程大致是:

首先,客户端向主节点发起请求,主节点0收到客户端请求,会向其它节点发送pre-prepare消息,其它节点就收到了pre-prepare消息,就开始了这个核心三阶段共识过程了。

Pre-prepare阶段:节点收到pre-prepare消息后,会有两种选择,一种是接受,一种是不接受。什么时候才不接受主节点发来的pre-prepare消息呢?一种典型的情况就是如果一个节点接到了一条pre-pre消息,消息里的v和n在之前收到里的消息是曾经出现过的,但是d和m却和之前的消息不一致,或者请求编号不在高低水位之间(高低水位的概念在2.4节会进行解释),这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的v和n,但d和m却不同的消息。

Prepare阶段:节点同意请求后会向其它节点发送prepare消息。这里要注意一点,同一时刻不是只有一个节点在进行这个过程,可能有n个节点也在进行这个过程。因此节点是有可能收到其它节点发送的prepare消息的。在一定时间范围内,如果收到超过2f个不同节点的prepare消息,就代表prepare阶段已经完成。

Commit阶段:于是进入commit阶段。向其它节点广播commit消息,同理,这个过程可能是有n个节点也在进行的。因此可能会收到其它节点发过来的commit消息,当收到2f+1个commit消息后(包括自己),代表大多数节点已经进入commit阶段,这一阶段已经达成共识,于是节点就会执行请求,写入数据。

处理完毕后,节点会返回消息给客户端,这就是pbft算法的全部流程。

为了更清晰的展现这个过程和一些细节,下面以流程图来表示这个过程。


Image Description
PBFT交互图

注解:

V:当前视图的编号。视图的编号是什么意思呢?比如当前主节点为A,视图编号为1,如果主节点换成B,那么视图编号就为2.这个概念和raft的term任期是很类似的。
N:当前请求的编号。主节点收到客户端的每个请求都以一个编号来标记。
M:消息的内容
d或D(m):消息内容的摘要
i: 节点的编号


H4

checkpoint、stable checkpoint和高低水位

什么是checkpoint呢?checkpoint就是当前节点处理的最新请求序号。前文已经提到主节点收到请求是会给请求记录编号的。比如一个节点正在共识的一个请求编号是101,那么对于这个节点,它的checkpoint就是101.

那什么是stable checkpoint(稳定检查点)呢?stable checkpoint就是大部分节点(2f+1)已经共识完成的最大请求序号。比如系统有4个节点,三个节点都已经共识完了的请求编号是213.那么这个213就是stable checkpoint了。

那设置这个stable checkpoint有什么作用呢?最大的目的就是减少内存的占用。因为每个节点应该记录下之前曾经共识过什么请求,但如果一直记录下去,数据会越来越大,所以应该有一个机制来实现对数据的删除。那怎么删呢?很简单,比如现在的稳定检查点是213,那么代表213号之前的记录已经共识过的了,所以之前的记录就可以删掉了。


Image Description
高低水位示意图

图中A节点的当前请求编号是1039,即checkpoint为1039,B节点的checkpoint为1133.当前系统stable checkpoint为1034.那么1034这个编号就是低水位,而高水位H=低水位h+L,其中L是可以设定的数值。因此图中系统的高水位为1034+100=1134。

举个例子:如果B当前的checkpoint已经为1034,而A的checkpoint还是1039,假如有新请求给B处理时,B会选择等待,等到A节点也处理到和B差不多的请求编号时,比如A也处理到1112了,这时会有一个机制更新所有节点的stabel checkpoint ,比如可以把stabel checkpoint设置成1100,于是B又可以处理新的请求了,如果L保持100不变,这时的高水位就会变成1100+100=1200了。


H4

ViewChange(视图更改)事件

当主节点挂了(超时无响应)或者从节点集体认为主节点是问题节点时,就会触发ViewChange事件,ViewChange完成后,视图编号将会加1。

下图展示ViewChange的三个阶段流程。


Image Description
View Change 流程

如图所示,viewchange会有三个阶段,分别是view-change,view-change-ack和new-view阶段。从节点认为主节点有问题时,会向其它节点发送view-change消息,当前存活的节点编号最小的节点将成为新的主节点。当新的主节点收到2f个其它节点的view-change消息,则证明有足够多人的节点认为主节点有问题,于是就会向其它节点广播

New-view消息。注意:从节点不会发起new-view事件。对于主节点,发送new-view消息后会继续执行上个视图未处理完的请求,从pre-prepare阶段开始。其它节点验证new-view消息通过后,就会处理主节点发来的pre-prepare消息,这时执行的过程就是前面描述的pbft过程。到这时,正式进入 v+1(视图编号加1)的时代了。

为了更清晰的展现ViewChange这个过程和一些细节,下面以流程图来表示这个过程。


Image Description
View Change 交互图

上图里红色字体部分的O集合会包含哪些pre-prepare消息呢?假设O集合里消息的编号范围:(min~max),则Min为V集合最小的stable checkpoint,Max为V集合中最大序号的prepare消息。最后一步执行O集合里的pre-preapare消息,每条消息会有两种情况: 如果max-min>0,则产生消息 ;如果max-min=0,则产生消息


H4

从Fabric源码看出些东西

fabric v0.6 将项目荡到本地之后,我们发现在consensus内的 pbft 就是整个 fabric 共识代码。

type pbftCore struct {
    // internal data
    internalLock sync.Mutex
    executing    bool // signals that application is executing

    idleChan   chan struct{} // Used to detect idleness for testing
    injectChan chan func()   // Used as a hack to inject work onto the PBFT thread, to be removed eventually

    consumer innerStack

    // PBFT data
    activeView    bool              // view change happening
    byzantine     bool              // whether this node is intentionally acting as Byzantine; useful for debugging on the testnet
    f             int               // max. number of faults we can tolerate
    N             int               // max.number of validators in the network
    h             uint64            // low watermark
    id            uint64            // replica ID; PBFT `i`
    K             uint64            // checkpoint period
    logMultiplier uint64            // use this value to calculate log size : k*logMultiplier
    L             uint64            // log size
    lastExec      uint64            // last request we executed
    replicaCount  int               // number of replicas; PBFT `|R|`
    seqNo         uint64            // PBFT "n", strictly monotonic increasing sequence number
    view          uint64            // current view
    chkpts        map[uint64]string // state checkpoints; map lastExec to global hash
    pset          map[uint64]*ViewChange_PQ  //已经完成prepare阶段的请求
    qset          map[qidx]*ViewChange_PQ //已经完成pre-prepare阶段的请求

    skipInProgress    bool               // Set when we have detected a fall behind scenario until we pick a new starting point
    stateTransferring bool               // Set when state transfer is executing
    highStateTarget   *stateUpdateTarget // Set to the highest weak checkpoint cert we have observed
    hChkpts           map[uint64]uint64  // highest checkpoint sequence number observed for each replica

    currentExec           *uint64                  // currently executing request
    timerActive           bool                     // is the timer running?
    vcResendTimer         events.Timer             // timer triggering resend of a view change
    newViewTimer          events.Timer             // timeout triggering a view change
    requestTimeout        time.Duration            // progress timeout for requests
    vcResendTimeout       time.Duration            // timeout before resending view change
    newViewTimeout        time.Duration            // progress timeout for new views
    newViewTimerReason    string                   // what triggered the timer
    lastNewViewTimeout    time.Duration            // last timeout we used during this view change
    broadcastTimeout      time.Duration            // progress timeout for broadcast
    outstandingReqBatches map[string]*RequestBatch // track whether we are waiting for request batches to execute

    nullRequestTimer   events.Timer  // timeout triggering a null request
    nullRequestTimeout time.Duration // duration for this timeout
    viewChangePeriod   uint64        // period between automatic view changes
    viewChangeSeqNo    uint64        // next seqNo to perform view change

    missingReqBatches map[string]bool // for all the assigned, non-checkpointed request batches we might be missing during view-change

    // implementation of PBFT `in`
    reqBatchStore   map[string]*RequestBatch // track request batches
    certStore       map[msgID]*msgCert       // track quorum certificates for requests
    checkpointStore map[Checkpoint]bool      // track checkpoints as set
    viewChangeStore map[vcidx]*ViewChange    // track view-change messages
    newViewStore    map[uint64]*NewView      // track last new-view we received or sent
}

我们可以发现, bfpt中的view 就是一个 正整数。

其中我可以看到他的主节点,判断如下。

// Given a certain view n, what is the expected primary?
func (instance *pbftCore) primary(n uint64) uint64 {
    return n % uint64(instance.replicaCount)
}

主节点由公式p = v mod |R|计算得到,这里v是视图编号,p是副本编号,|R|是副本集合的个数。当主节点失效的时候就需要启动视图更换(view change)过程


H4

PBFT 算法总结

PBFT 就属于 BFT 类的共识算法了,他可以解决分布式系统中存在做宕机的节点,也可以处理存在做坏事儿节点的问题。

  1. pbft算法可以容忍不超过(N - 1) / 3个问题节点,共识算法的时间复杂度为O(n^2);
  2. pbft算法完成共识需要经过三个阶段:pre-prepare、prepare和commit阶段;
  3. pbft算法需要一个主节点,每个主节点的任期就是一个view。当从节点发现主节点有问题(比如请求在规定时间内没有相应)时通过view change来请求更换主节点。

PBFT算法非常重要,很多大厂的区块链项目中都有运用,例如国内的迅雷、腾讯等公司的区块链项目,超级账本的fabric等,都使用了pbft或者优化后的pbft作为共识算法,理解pbft算法是区块链学习过程中非常重要的一环。


H3

PBFT 与 RAFT 对比

我就一展示数据的表格
对比点 RAFT PBFT
适用环境 私链 联盟链
算法通信复杂度 O(n) O(n^2)
最大故障合同错节点 2f+1<=N 3f+1<=N
流程对比 1. 初始化leader(谁快谁当)
2. 共识过程
3. 重选leader机制
1. 初始化leader选举(按编号依次轮流做主节点)
2. 共识过程
3. 重选leader机制

公链:公链不仅需要考虑网络中存在故障节点,还需要考虑作恶节点,这一点和联盟链是类似的。和联盟链最大的区别就是,公链中的节点可以很自由的加入或者退出,不需要严格的验证和审核。


H4

最大容错率

首先我们先来思考一个问题,为什么pbft算法的最大容错节点数量是(n-1)/3,而raft算法的最大容错节点数量是(n-1)/2?

对于raft算法,raft算法的的容错只支持容错故障节点,不支持容错作恶节点。什么是故障节点呢?就是节点因为系统繁忙、宕机或者网络问题等其它异常情况导致的无响应,出现这种情况的节点就是故障节点。那什么是作恶节点呢?作恶节点除了可以故意对集群的其它节点的请求无响应之外,还可以故意发送错误的数据,或者给不同的其它节点发送不同的数据,使整个集群的节点最终无法达成共识,这种节点就是作恶节点。

raft算法只支持容错故障节点,假设集群总节点数为n,故障节点为f,根据小数服从多数的原则,集群里正常节点只需要比f个节点再多一个节点,即f+1个节点,正确节点的数量就会比故障节点数量多,那么集群就能达成共识。因此raft算法支持的最大容错节点数量是(n-1)/2。

对于pbft算法,因为pbft算法的除了需要支持容错故障节点之外,还需要支持容错作恶节点。假设集群节点数为N,有问题的节点为f。有问题的节点中,可以既是故障节点,也可以是作恶节点,或者只是故障节点或者只是作恶节点。那么会产生以下两种极端情况:

第一种情况,f个有问题节点既是故障节点,又是作恶节点,那么根据小数服从多数的原则,集群里正常节点只需要比f个节点再多一个节点,即f+1个节点,确节点的数量就会比故障节点数量多,那么集群就能达成共识。也就是说这种情况支持的最大容错节点数量是(n-1)/2。

第二种情况,故障节点和作恶节点都是不同的节点。那么就会有f个问题节点和f个故障节点,当发现节点是问题节点后,会被集群排除在外,剩下f个故障节点,那么根据小数服从多数的原则,集群里正常节点只需要比f个节点再多一个节点,即f+1个节点,确节点的数量就会比故障节点数量多,那么集群就能达成共识。所以,所有类型的节点数量加起来就是f+1个正确节点,f个故障节点和f个问题节点,即3f+1=n。

结合上述两种情况,因此pbft算法支持的最大容错节点数量是(n-1)/3。下图展示了论文里证明pbft算法为什么3f+1<=n的一段原文,以及根据原文提到的两种情况对应的示意图。

paxos主要用于解决非拜占庭模型的共识问题,一般适用于私链,因为私链仅在组织内部使用,因此可以不考虑集群中存在拜占庭节点问题,而公链或者联盟链则必须要考虑存在恶意节点的情况,因此不适合用paxos或者raft这类非拜占庭模型的共识算法。


H4

时间复杂度

为什么raft是o(n),而pbft是o(n^2)呢?这里主要考虑算法的共识过程。

对于raft算法,核心共识过程是日志复制这个过程,这个过程分两个阶段,一个是日志记录,一个是提交数据。两个过程都只需要领导者发送消息给跟随者节点,跟随者节点返回消息给领导者节点即可完成,跟随者节点之间是无需沟通的。所以如果集群总节点数为 n,对于日志记录阶段,通信次数为n-1,对于提交数据阶段,通信次数也为n-1,总通信次数为2n-2,因此raft算法复杂度为O(n)。

对于pbft算法,核心过程有三个阶段,分别是pre-prepare(预准备)阶段,prepare(准备)阶段和commit(提交)阶段。对于pre-prepare阶段,主节点广播pre-prepare消息给其它节点即可,因此通信次数为n-1;对于prepare阶段,每个节点如果同意请求后,都需要向其它节点再 广播parepare消息,所以总的通信次数为n(n-1),即n^2-n;对于commit阶段,每个节点如果达到prepared状态后,都需要向其它节点广播commit消息,所以总的通信次数也为n(n-1),即n^2-n。所以总通信次数为(n-1)+(n^2-n)+(n^2-n),即2n^2-n-1,因此pbft算法复杂度为O(n^2)。


H4

流程对比上

对于leader选举这块,raft算法本质是谁快谁当选,而pbft算法是按编号依次轮流做主节点。对于共识过程和重选leader机制这块,为了更形象的描述这两个算法,接下来会把raft和pbft的共识过程比喻成一个团队是如何执行命令的过程,从这个角度去理解raft算法和pbft的区别。

一个团队一定会有一个老大和普通成员。对于raft算法,共识过程就是:只要老大还没挂,老大说什么,我们(团队普通成员)就做什么,坚决执行。那什么时候重新老大呢?只有当老大挂了才重选老大,不然生是老大的人,死是老大的鬼。

对于pbft算法,共识过程就是:老大向我发送命令时,当我认为老大的命令是有问题时,我会拒绝执行。就算我认为老大的命令是对的,我还会问下团队的其它成员老大的命令是否是对的,只有大多数人(2f+1)都认为老大的命令是对的时候,我才会去执行命令。那什么时候重选老大呢?老大挂了当然要重选,如果大多数人都认为老大不称职或者有问题时,我们也会重新选择老大。


H4

结语

raft算法和pbft算法是私链和联盟链中经典的共识算法,本文主要介绍了raft和pbft算法的流程和区别。raft和pbft算法有两点根本区别:

  1. raft算法从节点不会拒绝主节点的请求,而pbft算法从节点在某些情况下会拒绝主节点的请求 ;
  2. raft算法只能容错故障节点,并且最大容错节点数为(n-1)/2,而pbft算法能容错故障节点和作恶节点,最大容错节点数为(n-1)/3。

H3

Pow 工作证明

Proof of Work,工作证明相关理念最早于1993年被Cynthia Dwork和Moni Naor提出,之后的几年,该概念在是否能有效对抗拒绝服务攻击的争论中不断被人们所知。PoW机制的核心在于强迫攻击者作出一定量的工作才能进行接下来的交互操作,这样无形中就给攻击者提高了攻击的成本。自然而然的,攻击者需要完成的工作可以按消耗的计算机资源种类分为以下三大类:

消耗CPU资源。例如,反垃圾邮件的Hashcash方案以及受此启发而诞生的比特币;
消耗内存资源。例如,为了防止与比特币采用相同的共识机制所可能导致的51%攻击,以太坊目前就使用了一种需要占用大量内存资源的PoW算法;
消耗网络资源。攻击者在进行拒绝服务攻击之前,必须要获取多个远程服务器发送的命令。
POW作为数字货币的共识机制于 1998 年在 B-money 设计中提出。2008年中本聪发表比特币白皮书,比特币采用POW共识,通过计算来猜测一个数值(nonce),得以解决规定的 Hash 问题(两次SHA256)。保证在一段时间内,系统中只能出现少数合法提案。 同时,这些少量的合法提案会在网络中进行广播,收到的用户进行验证后会基于它认为的最长链上继续难题的计算。因此,系统中可能出现链的分叉(Fork),但最终会有一条链成为最长的链。

Hash 问题具有不可逆的特点,因此,目前除了暴力计算外,还没有有效的算法进行解决。反之,如果获得符合要求的 nonce,则说明在概率上是付出了对应的算力。谁的算力多,谁最先解决问题的概率就越大。 当掌握超过全网一半算力时,从概率上就能控制网络中链的走向。这也是所谓 51% 攻击的由来


H4

比特币POW算法的ASIC化问题

由于比特币采用的是比较简单的SHA256哈希算法作为POW共识算法,这个算法只消耗CPU资源,对内存要求不高,所以可以很容易被制造出ASIC芯片。这是比特币挖矿芯片的更新换代图


Image Description
比特币矿机芯片阶段

而现在,比特币的挖矿都变成了这样子:大量ASIC矿机组成的矿场。


Image Description
大量ASIC矿机组成的矿场

这样算力就越来越集中到了大矿主手里,普通用户使用电脑根本不可能挖到矿,这与中本聪当年设想的人人都能公平记账的愿景相违背。为此,人们设计了各种反ASIC化的方案。主要思想就是将POW算法改的很复杂,需要大量的内存,这样ASIC芯片是不可能集成大量内存进去的,从而无法制造出专门的挖矿芯片。比较有代码的改进方案有:

  • 莱特币:刚性内存哈希函数Scrypt取代SHA256
  • 达世币:X11,11种哈希函数混合使用
  • 以太坊:Ethash,大内存DAG搜索

但是实际上,只要利益足够大,人们总能够设计出专门POW挖矿的矿机,莱特币矿机和达世币矿机先后被制造了出来,以太坊之前也顶多是使用显卡挖矿,最近比特大陆也研发出了专门进行以太坊挖矿的专业矿机“蚂蚁矿机E3。具体可以参考这个新闻:http://t.cj.sina.com.cn/articles/view/1181714847/466f899f001007d4h

比特币的POW算法是没有任何实际意义的SHA256运算,那么有没有可能在挖矿的同时,把这些算力算出一些副产物?以下是几个比较有名的进行有效工作量证明的区块链:

  • 质数币:Primecoin(质数币)发布于2013年7月。其最大的特点是将虚拟货币中浪费的算法资源利用起来。它的PoW可以搜索质数,从而计算孪生素数表。所以有一定的科学价值。
  • 治疗币:Curecoin(治疗币)发布于2013年5月。治疗币最大的特点是将蛋白质褶皱结构的研究SHA256工作量证明算法进行了结合。因为蛋白质褶皱研究需要对蛋白质进行生化反应的模拟过程需要大量的计算资源,所以在“挖矿”的同时,还用于发现治愈疾病的新药,一举两得。
  • 比原链:比原链重新设计一种不同于比特币的哈希运算PoW共识机制,引入了矩阵运算与卷积运算,这样就能让人工智能运算充分利用比原链的挖矿设备。在这个过程中,人工智能加入了新的硬件,其算法运行速度得到明显提高。同时,这样也能减少一定的资源浪费。在这种情况下,矿机市场巨大的经济利益能够极大地加速人工智能ASIC芯片的发展,加快人工智能的研究。反过来,人工智能的快速发展也产生了更多的ASIC矿机需求。因此,这是一种正向反馈良性发展的过程。

H3

Pos 权益证明

PoS也称股权证明机制,其诞生的初衷是为了解决PoW带来的能耗问题。这种模式下持有币的数量越多、时间越长,记账成功率就越高(持有越多,获得越多),类似于利息制度。举例来说,PoS算法中有一个名词叫币龄,每个币每天产生1币龄,如果你持有100个币,总共持有了30天,那么此时你的币龄就为3000。这个时候如果你发现了一个PoS区块,你的币龄就会被清空为0。你每被清空365币龄,你将会从区块中获得0.05个币的奖励(相当于年利率5%),在这个案例中,奖励 = 3000 * 5% / 365 = 0.41个币,即持币有利息。

PoS作为PoW的一种升级共识机制,根据每个节点所持有代币的数量和时间,等比例的降低挖矿难度,在一定程度上缩短了共识达成的时间,但最重要的是不再需要消耗大量能源进行挖矿。它的缺点在于:性能提升有限,持币吃息的模式会导致代币的大量集中,流动性变得匮乏起来。典型项目如以太坊,目前正在从PoW切换至PoS机制。

第一个POS虚拟货币——点点币
Peercoin(点点币,PPC)于2012年8月发布,最大创新是其采矿方式混合了POW工作量证明及POS权益证明方式,其中POW主要用于发行货币,未来预计随着挖矿难度上升,产量降低,系统安全主要由POS维护。目前区块链中存在两种类型的区块,POW区块和POS区块。PPC的作者为同样不愿意公开身份的密码货币极客Sunny King,同时也是Primecoin的发明者。

第一个纯POS虚拟货币——未来币
2013年9月,一个名为BCNext的用户在Bitcointalk论坛发起一个帖子,宣布将发行一种全新的纯POS币种,后来取名为Nextcoin,简称NXT。Nxt是且是第一个100%的股权证明(PoS)机制的电子货币,Nxt不再通过消耗大量的资源“挖矿”产生新货币,而是通过现有账户的余额去“锻造”区块,并给与成功“锻造”区块的账户交易费用奖励。NXT的POS实现方式与PPC完全不同,合格区块判定方法为:

hit < baseTarget effectiveBalance elapseTime

hit是根据最新区块和用户的私钥生成的值,用户在挖一个区块时只需要计算一次即可。而右边的值跟账户余额成正比,跟流逝的时间成正比。也就意味着,用户账户余额越多,挖到矿的几率越高,随着时间的流逝越久,越容易找到新的区块。NXT区块的生成完全摒弃了竞争的理念,有点“上帝早已安排好一切”的味道,下一个区块由谁来生成冥冥中早就注定了,全网节点能做的就是静静等待那一刻的到来。


Image Description
POS

POS的本质就是比谁的钱多,钱越多越容易挖到区块,这将会造成富者越富,资源越来越集中,从而变得更中心化。


H3

DPOS 代理权益证明

DPoS是权益证明的一种改进版本,共识过程不再需要所有参与节点进行验证,而是委托部分代表来进行,很大程度上提高了共识效率。BitShares社区首先提出了DPoS机制,并引入了见证人的概念。见证人可以生成区块(记账并获得奖励),每一个持有比特股的人都可以投票选举见证人。得票数前100名的候选者可以当选为见证人,见证人的候选名单每个维护周期更新一次。见证人通过随机排列后,依次轮流生成区块(限时2s内出块),若见证人在2s内未能出块,则自动跳到下一个见证人。由于持股人可以随时通过投票更换见证人,因此见证人为了获得奖励和避免损失保证金,就必须提供稳定高效的出块能力。

可以看出,DPoS实际上是对共识进行了分级,先通过投票选举达成见证人共识(选出极少数可信的见证人),然后见证人之间再达成交易验证共识,这样大大提高了整个系统的共识效率。从某种角度来看,DPoS与议会制度或人民代表大会制度有相似之处。如果代表不能履行他们的职责,例如未能按时出块,就会被网络选出的新见证节点所取代。DPoS算法从性能和能耗的角度来说完全可以满足商用,但也不可避免地带来了过于中心化的问题。比如现在很火的EOS超级节点竞选就变成了鲸鱼们的合纵游戏,甚至被质疑是伪区块链项目。当然这种看法笔者并不赞同,毕竟上期也讲到3类区块链,采用DPoS算法的项目应当算作联盟链,只不过有些联盟比较开放有了大量散户,从运营模式上看更像公链。


H4

EOS

另外目前最火的区块链项目之一EOS也是采用了DPOS共识。EOS通过投票的方式选举出21个超级节点作为记账节点,每个节点有3秒的时间片,轮流记账。如果轮到某节点记账而没有出块,则该节点可能被投票出局,由其他备选节点顶替。出块速度是0.5秒!

EOS.IO软件允许区块精准的以每0.5秒产生一个区块,只有一个生产者被授权在任何给定的时间点生产一个区块。如果区块在预定的时间没有被生产出来,那么,那个时间的区块将被跳过。当一个或多个区块被跳过,将会有0.5秒或更多秒的区块间隔。
使用EOS.IO软件,区块以126个区块为一轮(每个生产者可以生产6个,有21个生产者,二者相乘)。在每一轮的开始,21个区块生产者通过token持有者的投票被选中。选中的生产者依据商定好的顺序生产区块,这个顺序由15个或者更多的生产者商定。
如果一个生产者错过了一个区块,并且在24小时内没有生产任何区块,他们将会被移除。直到这些“宕机”的生产者们及时通知区块链,他们将打算再次生产区块才被重新加入。通过不安排那些不够可靠的节点,尽可能的减少错过区块创建,来让整个网络运行得更平稳。

DPOS的特殊性,也是奠定拜占庭容错能力的基础框架,是它的算力节点是固定21个人,并且由大型的机构运营节点,其信息也相对透明,例如运营节点的地点、运营的情况等等。并且DPOS的算力节点是固定出块顺序的,固定地从A到B到C······。

传统DPOS中加入了拜占庭容错算法(BFT),只要没有生产者盖上相同的时间戳或相同区块高度的两个区块,便允许所有生产者签署所有区块。一旦15个生产者签署了一个区块,该区块就被认为是不可逆转的。在这种模式下,不可逆转的共识应该在1秒内完成。

在这种情况下,其实DPOS是拜占庭容错的特殊解,如何理解特殊解?原来的拜占庭容错(POW工作量证明),解决的是不限数量、随机广播同步的算力节点的容错能力,DPOS解决的拜占庭容错从两个维度降低了难度:

1、节点数量固定只有21个。并且节点信息透明。
2、固定出块顺序。每个节点跟接力棒一样,一个个往下接力出块。每个节点不能还没轮到它出块的时候,就出块。都是必须轮到再出块。如果出现出块故障,会跳过这个节点。

在POW或者其他的POS共识里,节点不限、随机出块顺序的问题,就变成只要解决「固定数量和固定出块顺序情况下的拜占庭问题」,其难度就大大降低。

一直以来以太坊的创始人Vitalik和EOS创始人BM关于POW和DPOS谁更中心化进行互怼。Vitalik认为EOS的21个超级节点违反了区块链的去中心化原则,有失公平。而BM则认为几个几大矿池控制了比特币和以太坊的绝大部分算力,这相当于以太坊只有几个超级节点,比21个节点还要少,对手里拿着BTC和ETH的人他们对社区和整个生态,他们是没有确定的发言权的,在比特币的世界里算力就是王道,面对算力大量集中在部分矿场的现在,它真的实现了中本聪的本心了吗?同样需要挖矿POS也是一样,需要看概率来决定你能否发声,但是DPOS是有发言权的,不管持有多少,我都有发言权。这种看似由“直接民主”转为“间接民主”的机制,或许才是真正体现了去中心化精神。


H3

NEO的dBFT

NEO采用的是 Delegated Byzantine Fault Tolerance (dBFT) 共识算法,由于它目前只有 7 个 代理节点,而代表节点则是通过用户投票选出。dBFT参与记账的是超级节点,普通节点可以看到共识过程,并同步账本信息,但不参与记账。总共n个超级节点分为一个议长和n-1个议员,议长会轮流当选。每次记账时,先有议长发起区块提案(拟记账的区块内容),一旦有至少(2n+1)/3个记账节点(议长加议员)同意了这个提案,那么这个提案就成为最终发布的区块,并且该区块是不可逆的,所有里面的交易都是百分之百确认的。


H3

以太坊的下一代POS共识:Casper

Casper(投注共识)是一种以太坊下一代的共识机制,属于PoS。Casper的共识是按块达成的而不是像PoS那样按链达成的。

为了防止验证人在不同的世界中提供不同的投注,我们还有一个简单严格的条款:如果你有两次投注序号一样,或者说你提交了一个无法让Casper合约处理的投注,你将失去所有保证金。从这一点我们可以看出,Casper与传统的PoS不同的是Casper有惩罚机制,这样非法节点通过恶意攻击网络不仅得不到交易费,而且还面临着保证金被没收的风险。

Casper协议下的验证人需要完成出块和投注两个活动。具体如下:

出块是一个独立于其它所有事件而发生的过程:验证人收集交易,当轮到他们的出块时间时,他们就制造一个区块,签名,然后发送到网络上。投注的过程更为复杂一些。目前Casper默认的验证人策略被设计为模仿传统的拜占庭容错共识:观察其他的验证人如何投注,取33%处的值,向0或者1进一步移动。
而客户端的确认当前状态的过程如下所示:

一开始先下载所有的区块和投注,然后用上面的算法来形成自己的意见,但是不公布意见。它只要简单的按顺序在每个高度进行观察,如果一个块的概率高于0.5就处理它,否则就跳过它。在处理所有的区块之后得到的状态就可以显示为区块链的“当前状态”。客户端还可以给出对于“最终确定”的主观看法:当高度k之前的每个块,意见要么高于99.999%或者低于0.001%


H3

HyperLedger Fabric下一代共识:SBFT

PBFT在Fabric0.6的时候被采用,但是由于一些说不清的原因,在Fabric1.0中并没有采用PBFT,而是使用Kafka进行排序,作为共识节点。在Fabric的提案中,打算会采用SBFT(Simple BFT),这种BFT算法会对PBFT进行简化,具体什么时候实现还没准呢。


H3

PalletOne的陪审团共识

在英美,陪审团制度是一个使用了几百年的共识制度,关于一个案件中嫌疑人是否有罪,是由随机抽选的陪审员组成陪审团共同决定的。提到陪审团,就不得不提一部非常经典的电影《十二怒汉》:

十二怒汉》讲述的是一个在贫民窟长大的18岁少年因为涉嫌杀害自己的父亲被告上法庭,证人言之凿凿,各方面的证据都对他极为不利。十二个不同职业的人组成了这个案件的陪审团,他们要在休息室达成一致的意见,裁定少年是否有罪,如果罪名成立,少年将会被判处死刑。
《十二怒汉》通过一场陪审团审判,生动演绎了美国的法律制度与文化,是美国宣传法律和法律制度的“银法槌奖”的首部获奖作品。同名电影在IMDB上排名第五,高于《阿甘正传》《辛德勒的名单》等,是一部超越时代的经典之作!其中的一段台词也很能体现陪审团制度的特点:

“我们都肩负责任。我一直认为,这正是民主社会了不起的地方。我们接到邮件通知,大老远跑到这里,决定一个跟我们素昧平生的人到底有没有罪。不论作出什么样的裁决,我们都拿不到任何好处,也不会有任何损失。这正是我们国家强大的原因之一。我们不能把它当成个人的事”

PalletOne提供了对各个底层链的抽象,用户使用常用的开发语言,基于对底层链的抽象接口进行操作。而合约的执行就是靠一个个的陪审团来完成的。


Image Description
PalletOne 示意图

除了陪审团这个角色,在PalletOne中还有一个叫仲裁中介(Mediator)的角色,该角色是基于DPOS选举的,相当于现实生活中的法官的角色,在接到一个新的智能合约后,Mediator会随机选择陪审员组成陪审团,由该陪审团负责该智能合约的执行和共识。


Image Description
仲裁中介(Mediator)

陪审团共识与传统POW、POS等共识的不同之处在于,陪审团共识是一个并行的共识机制,在同一个时刻,有多个陪审团同时在执行不同的合约。为了配合陪审团的并行共识,PalletOne采用了DAG作为分布式存储,合约的状态数据可以并行写入DAG中。所以PalletOne使用陪审团并行共识+DAG的并行写入,可以实现极高的TPS。


H2

总结

共识算法的选择与应用场景高度相关,可信环境使用Paxos或者Raft,带许可的联盟可使用PBFT,非许可链可以是POW、POS、DPOS共识等。

现在区块链上数字资产的应用越来越多来源于真实世界或金融资产,对交易的最终确认有很高的要求,需要有不同的共识机制。
共识机制是区块链的核心技术,现在各种区块链共识机制的选择是认为至今为止的相对的最优选择;当未来区块链技术越来越多应用于现实,未来将会不断有所改进,以切合实际的需要。

现在仍然有很多共识算法在不断的被研究出,被优化,这是一条不会终止的路。

专栏: 区块链
标签: 区块链 p2p consensus