区块链社会学区块链大学区块链研究

共识机制

2019-03-24  本文已影响5人  HeartGo

共识机制

什么是共识机制

区块链作为一个去中心化的分布式账本系统,然而在实际运行中,怎么解决因为去中心化后,保证整个系统能有效运行,各个节点诚实记账,在没有所谓的中心的情况下,互相不信任的个体之间就交易的合法性达成共识的共识机制。

为什么需要共识机制?

在分布式系统中,各个不同的主机通过异步通信方式组成网络集群。为了保证每个主机达成一致的状态共识,就需要在主机之间进行状态复制。异步系统中,可能会出现各样的问题,例如主机出现故障无法通信,或者新能下降,而网络也可能发生拥堵延迟,类似的种种故障有可能会发生错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议,以确保各主机达成安全可靠的状态共识。所以,利用区块链构造基于互联网的去中心化账本,需要解决的首要问题是如何实现不同账本节点上的账本数据的一致性和正确性。

共识机制有哪些?

常见的共识就机制包括:POW(工作量证明机制)、POS(权益证明机制)、DPOS(股份授权证明)POW+POS(混合共识机制)等等,另外还有Pool验证池、Ripple瑞波共识协议等等

区块链分类

在开始进行共识机制梳理前,首先需要对目前的区块链进行一个简单的了解。目前市面上根据共识算法及应用场景把区块链分为三类:公有链、联盟链和私有链。

公有链,是一个完全开放的分布式系统。公有链中的节点可以很自由的加入或者退出,不需要严格的验证和审核,比如比特币、以太坊、EOS等。共识机制在公有链中不仅需要考虑网络中存在故障节点,还需要考虑作恶节点,并确保最终一致性。

联盟链,是一个相对开放的分布式系统。对于联盟链,每个新加入的节点都是需要验证和审核的,比如Fabric、BCOS等。联盟链一般应用于企业之间,对安全和数据的一致性要求较高,所以共识机制在联盟链中不仅需要考虑网络中存在故障节点,还需要考虑作恶节点,同时除过确保最终一致性外,还需要确保强一致性。

私有链,是一个封闭的分布式系统。由于私有链是一个内部系统,所以不需要考虑新节点的加入和退出,也不需要考虑作恶节点。私有链的共识算法还是传统分布式系统里的共识算法,比如zookeeper的zab协议,就是类paxos算法的一种。只考虑因为系统或者网络原因导致的故障节点,数据一致性要求根据系统的要求而定。

POW

PoW 共识机制
PoW(Proof of Work),即工作量证明,闻名于比特币,俗称“挖矿”。PoW是指系统为达到某一目标而设置的度量方法。简单理解就是一份证明,用来确认你做过一定量的工作。监测工作的整个过程通常是极为低效的,而通过对工作的结果进行认证来证明完成了相应的工作量,则是一种非常高效的方式。PoW是按劳分配,算力决定一起,谁的算力多谁记账的概率就越大,可理解为力量型比较。以下内容基于比特币的PoW机制。
工作量证明( PoW )通过计算一个数值( nonce ),使得拼揍上交易数据后内容的 Hash 值满足规定的上限。在节点成功找到满足的Hash值之后,会马上对全网进行广播打包区块,网络的节点收到广播打包区块,会立刻对其进行验证。
如何才能创建一个新区块呢?通过解决一个问题:即找到一个nonce值,使得新区块头的哈希值小于某个指定的值,即区块头结构中的“难度目标”。
如果验证通过,则表明已经有节点成功解迷,自己就不再竞争当前区块打包,而是选择接受这个区块,记录到自己的账本中,然后进行下一个区块的竞争猜谜。网络中只有最快解谜的区块,才会添加的账本中,其他的节点进行复制,这样就保证了整个账本的唯一性。

假如节点有任何的作弊行为,都会导致网络的节点验证不通过,直接丢弃其打包的区块,这个区块就无法记录到总账本中,作弊的节点耗费的成本就白费了,因此在巨大的挖矿成本下,也使得矿工自觉自愿的遵守比特币系统的共识协议,也就确保了整个系统的安全。

  1. 工作机制
    为了使区块链交易数据记录在区块链上并在一定时间内达到一致(共识),PoW提供了一种思路,即所有区块链的网络节点参与者进行竞争记账,所谓竞争记账是指,如果想生成一个新的区块并写入区块链,必须解出比特币网络出的工作量证明谜题,谁先解出答案,谁就获得记账权利,然后开始记账并将将解出的答案和交易记录广播给其他节点进行验证,自己则开始下一轮挖矿。如果区块的交易被其他节点参与者验证有效并且谜题的答案正确,就意味着这个答案是可信的,新的节点将被写入验证者的节点区块链,同时验证者进入下一轮的竞争挖矿。

这道题关键的三个要素是工作量证明函数、区块及难度值。工作量证明函数是这道题的计算方法,区块决定了这道题的输入数据,难度值决定了这道题的所需要的计算量。

image
首先看一下这道题到底是什么?这道题的目的在于算出一个值,且这个值小于目标值即可,这个值就是上图中的上一个区块的哈希值。

目标值 = 最大目标值 / 难度值(最大目标值恒定:0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
新难度值 = 旧难度值 * ( 过去2016个区块花费时长 / 20160 分钟 )
tips:难度值是随网络变动的,目的是为了在不同的网络环境下,确保每10分钟能生成一个块。

那如何计算呢?SHA256(SHA256(Block_Header)),即只需要对区块头进行两次SHA256运算即可,得到的值和目标值进行比较,小于目标值即可。区块头结构如下:

image
区块头中有一个重要的东西叫MerkleRoot的hash值。这个东西的意义在于:为了使区块头能体现区块所包含的所有交易,在区块的构造过程中,需要将该区块要包含的交易列表,通过Merkle Tree算法生成Merkle Root Hash,并以此作为交易列表的摘要存到区块头中。

至此,我们发现区块头中除过nonce以外,其余的数据都是明确的,解题的核心就在于不停的调整nonce的值,对区块头进行双重SHA256运算。整个工作量证明过程如下:

未命名文件-6.jpg

  1. PoW优缺点
    通过上面的描述,PoW优点很明显:1)完全去中心化(任何人都可以加入);2)节点自由进出,容易实现;3)破坏系统花费的成本巨大;

关于破坏系统成本巨大可以分两层意思理解:

在指定时间内,给定一个难度,找到答案的概率唯一地由所有参与者能够迭代哈希的速度决定。与之前的历史无关,与数据无关,只跟算力有关。
掌握51%的算力对系统进行攻击所付出的代价远远大于作为一个系统的维护者和诚实参与者所得到的。
缺点也相当明显:1)对节点的性能网络环境要求高;2)浪费资源;3)每秒钟最多只能做七笔交易,效率低下;4)矿场的出现违背了去中心的初衷; 5)不能确保最终一致性;6)比特币产量每4年减半,利益驱动性降低导致旷工数量减少从而导致比特币网络瘫痪。

  1. 网络攻击和链分叉
    1)网络攻击
    假定一个恶意节点试图双花之前的已花费的交易,攻击者需要重做包含这个交易的区块,以及这个区块之后的所有的区块,创建一个比目前诚实区块链更长的区块链。只有网络中的大多数节点都转向攻击者创建的区块链,攻击者的攻击才算成功了。由于每一个区块都包含了之前的所有区块的交易信息,所以随着块高的增加,之前的区块都会被再次确认一次,确认超过6次,可以理解为无法被修改。

考虑交易T包含在区块b1中。每个后续区块b2,b3,b4,.........bn会降低交易T被修改的可能性,因为修改这些后续的区块需要更多的算力。中本聪用概率理论证明,六个区块后攻击者追赶上最长链的可能性降低到0.0002428%。在过4个或更多区块后这个可能行会降到0.0000012%。每新增一个区块bn,攻击的可能性就会以指数形式下降,很快整个攻击的可能性就会低到可以忽略的程度。

2)链分叉
所谓的链分叉,主要是由于在计算hash时,每个人拿到的区块内容是不同的,导致算出的区块结果也不同,但都是正确结果,于是,区块链在这个时刻,出现了两个都满足要求的不同区块,那旷工怎么办呢?由于距离远近、网络等原因,不同旷工看到这两个区块的先后顺序是不一样的,通常情况下,旷工会把自己先看到的区块链复制过来,然后接着在这个区块上开始新的挖矿工作,于是就出现了链分叉。

PoW解决方案:从分叉的区块起,由于不同的矿工跟从了不同的区块,在分叉出来的两条不同链上,算力是有差别的。由于解题能力和矿工的算力成正比,因此两条链的增长速度也是不一样的,在一段时间之后,总有一条链的长度要超过另一条。当矿工发现全网有一条更长的链时,他就会抛弃他当前的链,把新的更长的链全部复制回来,在这条链的基础上继续挖矿。所有矿工都这样操作,这条链就成为了主链,分叉出来被抛弃掉的链就消失了。

能够让区块链保证唯一性的前提是:所有矿工都遵从同样的机制。当旷工遵从不同的机制时,就会出现硬分叉,这种分叉会导致资产增加,且两条链同时存在,比如BBC。

pos

PoS 共识机制
对于PoW,由于矿场的出现及挖矿设备性能的不断提升,算力开始集中,节点数和算力值渐渐不适配,同时PoW太浪费了,旷工持续挖矿进行的重复性Hash计算没有任何实际或者科学价值,而且还有一个更大的问题,作恶是没有成本的,旷工的恶意攻击并不会对旷工下次记账并获取相关权益(比特币)产生任何影响,鉴于此,人们提出了PoS。
一. pos的实现原理及公式

    要理解pos的实现原理,我认为从pos的实现算法公式来理解是最为直观的,其公式为:

    hash(block_header) =<target * coinage

    币龄的计算:coinage = 币的个数*币的剩余使用时间

PoS(Proof of Stake):股权证明,与PoW相比,不需要证明你在记账前做了某项工作,而是证明你拥有某些财产。股权决定一起,谁的股权大,谁记账的概率就越大。由于PoS是BitCoin出现后提出的共识算法,目前还有得到实际的验证,并且,PoS不是一个,而是一类共识算法。最先使用PoS的是Peer Coin,不过是一种朴素的PoS,目前呼声很高的是ETH Casper,但还没有投产(拭目以待吧),所以关于PoS的描述基于Peer Coin。

  1. 工作机制
    如下图所示,开始竞争出块记账前,拥有权益的节点将自己的权益放入PoS机制中,同时身份变为验证者,PoS机制根据验证者下注的多少,采用随机的方式选出一个记账者进行出块记账。这个随机并不是真正的随机,一般跟下注的权益成正比,谁的权益多,谁获取记账权的概率就越大。如果选出的记账者在一段时间内没有记账,PoS机制重新选择记账节点,当出块完成,开始进入下一轮的记账。

POS机制.jpg
我们以Peer Coin来举例说明PoS的工作机制。Peer Coin是最先采用PoS共识机制的数字货币。在Peer Coin中,引入了币龄和币天的概念。所谓币天,就是你持有货币的时间,币龄=币的数量比天。比如你有100个币,总共持有30天(Peer Coin中未使用至少30天的币可以参与竞争下一区块),那么你的币龄就是10030=3000,你作为币的持有者,参与下一轮竞争,过程如下:

在竞争开始前,你将3000币龄作为筹码下注,并成为记账验证者,
PoW机制会随机的选出一个记账者,刚好是你
你开始记账并完成
你的3000币龄被清0
你获得利息=3000 * 5% / 365 = 0.41个币(每被清空365币龄,你将会从区块中获得0.05个币的利息)
理解随机:选我、选我、选我?PoS在选择记账者时一般有两种做法,一种是挑选下注多(权益大)的进行轮流记账;还有一种是跟PoW结合,在PoW中,决定旷工能否出块的一个重要因素是出块的难度,PoS将出块难度和权益挂钩,权益越大,难度越小,出块概率越大。

  1. PoS特点及分类
    PoS 特点
    PoS需要一定量的权益作为出块的竞争资本
    PoS不需要进行大量的“无用”Hash计算
    PoS偏向“权利”集中制,但又做了均衡(出块清0)
    PoS通过股权质押对作恶者进行惩罚
    PoS提供激励机制
    PoS 分类
    先说三个问题:

链分叉问题:PoW从经济角度,可以自然做到防止链分叉,但PoS需要精心审计,即nothing at stake问题。PoS可以采用一定的惩罚机制。
远程攻击问题:即如旷工在撤回被定的虚拟资产后,再发起之前发生的例行区块的分叉。
卡特尔形成问题:即区块链的寡头垄断,由于PoS共识算法是谁“富有”,谁就有更大的话语权,这样少数富有旷工之间的“协调”将导致寡头龙蛋的形成。
目前业内PoS共识算法的实现主要分为两类:

简单的的PoS系统。这类PoS很少甚至没有从算法的设计上来解决上述问题,一般是比较早期的PoS尝试。比较典型的例子是Peer Coin(点点币,PPC)、新星币(Nova Coin,NVC)、黑币(Black Coin,BLK)、NextCoin(未来币,NXT)等等
精心设计的PoS系统,相对来说比较新。基于不同的实现方式,精心设计的PoS系统可以分为两种。一种是基于拜占庭容错的权益证明(BFT based PoS),比如Tendermint,另一种是基于链的权益证明(Chain based PoS),比如ETH Casper和ADA的Ouroboros
第一类PoS系统安全性不够。第二类PoS系统目前还不够成熟,有一些处于早期运行阶段,有一些还处理讨论和测试阶段。

  1. PoS的优缺点
    通过上面的描述和PoS的特点,PoS优点为:1)节能环保,不需要无用计算;2)性能高;3)更加安全;4)人人可挖矿(获得利息),不用担心算力集中导致中心化出现;5)避免货币紧缩

为什么PoS更加安全?
在指定时间内,在POS体系中,即使你拥有了全球51%的算力,也未必能够进行51%攻击,因为,有一部分的货币并不是挖矿产生的,而是由利息产生(利息存放在POS区块中),这要求攻击者还需要持有全球超过51%的货币量。这大大提高了51%攻击的难度。
在PoS机制下,持有币越多,越容易获得记账权,接近于赢家通吃的感觉,但持有的币越多,越接近于一个诚实的节点,因为破坏整个网络带来的损失也越大,即假设富人不会做恶,毕竟做恶的目标是钱,若你富有,自然就没有做恶的动力。
除过同PoW一样不能确保最终一致性外,我们从两个维度说,一个是币的维度 ,一个是链的维度:

币维度:

纯PoS机制的加密货币,只能通过IPO的方式发行,这就导致“少数人”(通常是开发者)获得大量成本极低的加密货币,在利益面前,很难保证他们不会大量抛售。
PoS机制的加密货币,信用基础不够牢固。为解决这个问题,很多采用PoW+PoS的双重机制,通过PoW挖矿发行加密货币,使用PoS维护网络稳定。或者采用DPoS机制,通过社区选举的方式,增强信任。
链维度:

权益粉碎攻击:可理解为“穷山恶水出刁民”,权益很少的那一部分节点主动攻击导致链分叉,毕竟光脚不怕穿鞋的,破罐子破摔(权益越大责任越大,权益越少责任越小)。PoS可采用对应的惩罚机制,比如以太坊的 casper 里的slasher。
理性分叉:可理解为“大众心理学之跟风消费”,假如出现分叉,诚实节点为了保证自己的利益,也会趋于理性的去分叉上挖矿(挖了没损失,不挖可能会有损失),如果整个网络足够理性,会出现的情况反而是每条分支都会永远存在因为理性的矿工会同时在所有分支上挖矿。
tips:以太坊开发者Jan对PoS的担心,Jan目前为NERVOS的首席架构师

Jan:我总觉得 PoS有点问题。因为共识是要创造信任,信任是不可能自己创造自己。你想象一条蛇在咬自己的尾巴。PoS用系统自己发布的资产作为押金,去保证这个系统的安全。它没有锚定任何的东西,是漂浮在空中的。我没有看到任何的信任是通过 PoS这样的方式创造出来的。我觉得信任的创造还是要锚定能量。美元锚定是美国的军事实力。如果哪天美国没有这种军事实力,那美元的价值我觉得要打很多问号。PoW是相当于用军队锚定,PoS 是用美元锚定美元。这个问题你会思考很久。因为你可能又会想,归根到底这两种方式,好像都是用资本去锚定,因为电力本质上也是一种资本。但再想想,这两种资本好像是不太一样的。PoW 是体系外的资本。所以,PoS 我总觉得有点问题。

DPoS 共识机制

尽管PoS针对PoW的诸多不足做了改进,但是PoS仍然有一些自身的不足,而这些不足中尤其以“权利集中制”最为显著。在PoS系统中,依据权益的结余来选择,会导致首富账户的权利更大,有可能支配记账权,从而使得基于PoS的区块链系统变成几个少数“有钱人”的游戏,这和区块链的去中心化本意背道而驰,同时PoS的性能(1分钟)相比PoW(10分钟)并没有提升多少,这一点仍然被人诟病。基于此,原Bitshares的首席开发者Dan Larimer (现为EOS CTO)提出了一种更加快速、安全且能源消耗比较小的算法,这就是后来的DPoS。

DPoS(Delegated Proof of Stake):授权股权证明机制,基于PoS,类似投票选举,由被选举节点记账,如果把PoS看成资本主义的“权利集中制”,那么DPoS可以理解为具有特色社会主义的“民主集中制”。目前采用DPoS共识机制的如Bitshares、EOS和Asch等,由于EOS最近主网刚上,且是由BM操刀,所以下文基于EOS的DPoS。

tips:区块链/币圈不得不说的几个大神和区块链时代

区块链大神:

中本聪:比特币创始人、区块链的创世者,区块链 1.0的灵魂人物
V神:Vitalik Buterin,以太坊创始人,90后,区块链 2.0的代表人物,2014年挤掉扎克伯格获得世界科技奖
BM:Bytemaster的简写,本名Daniel Larimer,区块链项目EOS的开发者。主要成就:连续开发了三个区块链平台项目Bitshares(比特股),Steem和EOS(柚子),三个项目在圈内都非常出名,市值排在前50名,特别是近期EOS十分热门
区块链时代

区块链 1.0:以比特币为代表的加密货币为代表。大部分都基于比特币,无法完成上层应用对接,非图灵完备,开发需从底层开始,难度大,成本高
区块链 2.0:以支持智能合约的以太坊为代表,如果把比特币理解为全球账本,那么以太坊可以看成一台全球计算机,任何人都可以上传执行任意的应用程序。智能合约的出现大大降低了区块链应用的开发门槛,提升了开发效率,为应用繁荣提供了好的土壤和平台
区块链 3.0:暂时还没有代表,有些人将Token的出现或者EOS看成区块链3.0都显的有些急躁,暂不做评论,拭目以待

  1. 工作机制
    跟PoS不同的是,持有少数股份(权益)的节点也能行使他们的共识权了,只不过是以一种间接的方式。类似于股东代表大会,每当要决策公司大事(记什么账,谁来记账)的时候,全体股民(节点)依法行使投票权,选出自己心中的股东代表(可信账户),谁得票高谁当选。候选人可以去公开演讲拉票,获得足够多股民(节点)的信任,然后股东代表(被选中的可信节点)代表股民决策公司大事,股东代表的人数由系统决定,比如Bitshares为101个、Asch为51个,EOS为21个。

与生活中的股东代表选举不同:1)DPoS机制中的股民(节点)根据自己持有的加密货币数量占总量的百分比(占股比例)来投票,不是一人一票;2)选举出的股东代表(可信节点)完全对等,可理解为具有同等算力的101个矿池;3)股东代表一旦无能、不作为、胡作为(提供的算力不稳定,计算机宕机、或者试图利用手中的权力作恶),将立刻被股民踢出整个系统,然后由其他后备代表顶上去;4)决策完公司大事(记完账、出完块)有钱分,根据占股比例。DPoS的工作流程如下图所示:

DPOS机制-2.jpg
EOS的DPoS分为两个步骤:1)选举块生产者(Block Producter,简称BP);2)出块共识;

选举块生产者:任何持有Token的人都可以成为块生产者,都拥有投票权。每次投票前,候选BP可以给自己拉票(线下方式),每次投票超过50%代表有效,然后生成一个BP候选池,每次从BP候选池中选择排名靠前的21个节点作为BP,并对选出的21个BP随机排序。

出块共识:21个BP按照随机排序进行出块,在每轮出块共识的过程中,BP如果不出块或者出现恶意行为,将被其他节点举报并接受惩罚(剥夺出块的权利),然后从候选池中再选择一个BP加入,一个BP出块成功,并且经过至少(2/3 + 1)个BP确认(至少15个),出块BP获取相应的奖励,然后轮流至下一个BP出块,如果轮询了10次或者一天,将重新进行投票选举。

  1. DPoS的优缺点
    对于EOS的DPoS优点:1)记账节点减少,交易速度更快,EOS号称可达百万TPS;2)更加安全,一般不不会发生链分叉并不可逆,确保最终一致性;3)相对PoW,解决了资源消耗问题;

基于DPoS的设计,其优点也成为了自己的缺点,这也是为什么V神怒怼DPoS的原因。

首先DPoS通过选举少数的BP来出块记账,确实从网络传输和确认时间上看,性能大幅提升,但是少量的BP数量牺牲了部分去中心化。有人说这些被选举的BP代表着“民意”,相比PoW的5大矿场和PoS的富人玩家,DPoS更加民主,更加去中心化,但是DPoS机制的设计并不能保证一定有足额的真实的区块生产者,因为一个人或一个实体,可能控制着多个节点。比如LBTC,就一度出现半数节点被鱼池一家控制。EOS在启动过程中,也疑似出现一个人虚拟出7个节点的事。
其次,在真实的网络环境中,EOS实际的运行效率远没有吹的那么厉害,同时超级节点的治理全力和经济利益过于集中,如果他们串通,将进一步形成巨头龙垄断,这和区块链思想南辕北辙。
再次,对于坏节点的处理存在诸多困难。社区选举不能及时有效的阻止一些破坏节点的出现,给网络造成安全隐患,同时在网络节点数量少的场景,选举的BP代表性不强。

  1. 网络攻击和链分叉
    DPoS作为去中心化系统被人诟病的很多,这主要表现为会形成卡特尔和贿赂选民的动机。

关于链分叉,在正常运行的情况下,DPoS具有最终一致性,并不会经历任何分叉,因为被选举出来的BP是通过合作而非竞争的方式来生产区块,即便出现了分叉,共识也将自动的切换到最长的链上。简化期间,我们假设有三个BP,分别为A\B\C。

在正常操作模式下,快生产者3秒轮流成成一个快,如果没有人错过自己的轮次,那么将产生最长链,BP在被调度之外的任何时间段都无法出块,同时如果错过出块,可能会被淘汰。如下图所示。

正常出块.jpg
少数恶意或者故障节点的情况,不超过节点总数三分之一的恶意或故障节点可能创建少数分叉。由图可知,在分叉的那条链中,每9秒(设一个轮次三秒,三个轮次)只能产生一个块,而多数分叉每9秒可以产生两个块。这样,诚实的2/3多数将永远比少数分叉的链更长,如下图所示。

少数出块.jpg
少数的多重生产情况,少数人可能试图产生无限数量的分叉,但是他们的所有分叉都将比多数人的那条链短,因为少数人在出块速度上注定比多数人来的更慢。所以这种情况下,诚实的2/3多数还是永远比少数分叉的链更长,如下图所示。

多重.jpg
多数生产者集体作恶情况下,如果多数生产者(2/3)变得腐败,那么他们可以产生无限数量的分叉,每个分叉都看起来以2/3多数确认向前走。这种情况下,会遵循最长链选择。最长链就是为最大多数所批准的那条链,而这将由少数剩下的诚实节点决定。这种行为不会持续很长时间,因为利益相关方最终会投票替换生产者,如下图所示。

RAFT

Raft 共识机制
前面我们介绍了三种共识机制,即PoW、PoS和DPoS,但对于一些特殊场景(私有链和联盟链),并不需要解决拜占庭将军问题(后面会说到,即节点中没有“叛徒”),只需要处理一般的死机故障,同时追求共识的效率和强一致性,显然,这三种共识机制都不太合适。在这种情况下,采用Paxos等协议会更加高效。Paxos是Lamport设计的保持分布式系统一致性的协议,但由于Paxos非常复杂,难以理解,因此后来出现了各种不同的实现和变种,比如Raft。

Raft最初是一个用于管理复制日志的共识算法,注重协议的落地性和可理解性,是在非拜占庭故障下达成共识的强一致协议。目前Hyperledger的Fabric项目中,支持PBTF和Raft等共识协议。

  1. 工作机制
    一个Raft集群通常有5个节点,允许系统有两个故障节点(因为至少要N/2 +1个节点投票)。每个节点有三种状态:leader、follower、candidate。正常状态下,仅有一个Leader,其他均为follower。follower是被动的,不会主动发起请求,只能对leader和candida的请求做出响应。leader处理所有客户端的请求,candidate状态用来选举。

Raft算法包括三个基本组件:leader选举、日志复制、安全性问题。

Leader选举:现有的leader失效时,必须选出一个新的Leader
日志复制(记账):leader必须接受来自客户端的的交易记录,在参与共识记账的节点中进行复制,使其他节点交易所对应的区块
安全性问题:若某个节点对其状态机应用了某个特定的区块项,其他的节点不能对同一区块索引应用不同的命令(这句话真是变态的拗口)
Leader的选举:
选举leader只会在两种情况下发生:1)第一次启动Raft集群的时候;2)一个已知存在的Leader故障的时候;

流程如下图所示。对于初始化网络,每个节点处于follower状态,并自动转化为candidate,然后对自己投票,并发起RequestVoteRPC,然后等待,会出现如下情况:1)当前节点获得超过半数节点的投票,赢得选举成为Leader;2)其他节点赢得选举,当前节点接收到对方心跳 ,当前节点变为follower;3)选举超时,没有节点赢得选举,当前节点自增任期,重新发起选举。

leander-2.jpg
图中有几点需要说明:

term : 指的是任期,跟选举一样,现在咱们开始选举第几届人大代表、选举第几任村委书记,term就是那个“第几届”或“第几任”,每一次选举完成之后,term都会增加。生活中不会有人傻到去参加过去的选举,比如你说你现在要参加2017年的人大代表选举,人家不会投你票,会觉得你脑子有问题。但是在分布式环境中由于网络抖动、延迟等原因,一个节点完全有可能拿到的是之前的任期,并参加一个过去式的选举,对于这种情况,Raft跟正常人的反应一样,只会说一个字:“滚”,意思就是说你是来搞笑的吗?赶紧收拾收拾,参加下一次吧。
quorums:就是你的选票,每一次网络初始化后,每个节点自动变为candidate状态,先给自己投一票(反正自己投自己算数,不投白不投),然后发出投票邀请,等待其他人的投票,如果收到的其他人的投票数超过网络节点的(N/2 +1),那么恭喜你,你当选Leader了!
split vote:指的是在选举过程中,同一个任期内有两名候选人得到的票数一样多,说明大家实力差不多,棋逢对手了,那么谁都不能当选,生成一个新的任期,重新开始投票。
time out:超时,就是follower未能在周期内收到leader的心跳之后,会等待一段时间,如果超过这个时间,当前节点变为candidate,开始选举。这个时间设置不是统一的。Raft采用随机的方式生成timeout,谁的timeout先到,谁先开始选举。
日志复制(共识记账):
在日志复制过程中,分四个步骤,还是画个框框说明一下吧,如下图所示。

复制-2.jpg
Client发送请求给leader,每个请求都是一条指令。
leader接受请求后,把指令(Entry)追加到leader的操作日志中,然后对follower发起AppendEntries操作,尝试让操作指令(Entry)追加到Followers的操作日志中。如果有Follower不可用,则一直尝试
一旦Leader接受到多数(Quorums)Follower的回应,Leader就会进行commit操作,每一台节点服务器会把操作指令交给状态机处理。这样就保证了各节点的状态的一致性
各服务器状态机处理完成之后,Leader将结果返回给Client
安全性问题:
在安全性方面,Raft主要通过如下机制确保。

Election safety: 在一个term下,最多只有一个Leader。
Leader Append-Only: 一个Leader只能追加新的entries,不能重写和删除entries
Log Matching: 集群中各个节点的log都是相同一致的
Leader Completeness:如果一个log entry被committed了,则这个entry一定会出现在Leader的log里。
State Machine Safety: 如果一个节点服务器的state machine执行了一个某个log entry命令,则其他节点服务器,也会执行这个log entry命令,不会再执行其他命令。

  1. Raft优缺点
    由工作机制的描述,Raft的优点为:1)速度快,少量的节点,网络传输及共识效率高;2)不需要挖矿,节能环保;3)不需要考虑拜占庭节点,算法更简单。

由于Raft过度依赖Leader,从而丧失了部分去中心化,这在公链上是不能被接受的,所以Raft一般用于私链或者联盟链。同时,Raft在一定的网络波动或竞争情况下出现断站的网络分叉,需要多次确认。

  1. 网络攻击和链分叉
    先说说网络攻击,基于其优缺点,Raft一般用于私链或者联盟链,趋向与相信没有人作恶或者作恶可能性更小。但是一般出现,并且被选为记账者,那其他节点当时是没办法识破的,最多只能通过事后检查来发现。

链分叉? 要分析链分叉,首先要看看Raft机制是否会产生链分叉,我们知道一般是因为在同一时间出现多个记账者才会导致链分叉,可是按照Raft的机制,任何时刻都只会有一个leader(记账者),不会出现链分叉?

State Machine Safety:
一个candidate在选举的时候,会想其他节点发送包含他的log信息,获取票数,如果log是最新的,则获得选票,如果其他节点还有更加新的log,泽会拒绝投票,保证了State Machine Safety。

follower crashes:
如果follower故障,就不会接受追加entry和投票请求,leader会不断尝试和故障节点保持心跳,当节点回复,泽接受leader的最新log,并将log应用到State machine中,确保了不会分叉。

leader crashes:
leader故障情况下,集群中的所有节点的日志可能不一致,old leader的一些操作日志没有通过集群完全复制,new leader会通过强制followers复制自己的log来处理不一致的情况:

对于每个Follower,new leader将其日志与Followers的日志进行比较,找到他们的达成一致的最后一个log entry。
然后删除掉Followers中这个关键entry后面的所有entry,并将其替换为自己的log entry。该机制将恢复日志的一致性。

拜占庭

PBFT 共识机制
通过上面的描述,我们知道Raft机制最大的问题在于对Leader的强依赖,无法规避拜占庭节点,但PoW、PoS和DPoS的性能都不算很好,更为重要的是,在金融或者一些特殊应用领域,分布式系统需要确保一致性和正确性。基于BFT,人们提出了PBFT共识机制。

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

拜占庭将军问题:拜占庭将军问题是Leslie Lamport在20世纪80年代提出的假想问题,即拜占庭罗马帝国的将军为了使得作战计划统一,避免叛徒作乱,需要提出一种协议,该协议能使将军们达成一致,并且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说拜占庭将军问题是指寻找一个方法,使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识。

我们需要知道的是拜占庭将军问题在将军总数大于3f ,背叛者为f 或者更少时,忠诚的将军可以达成命令上的一致,即3f+1<=n。算法复杂度为o(n^(f+1)),其中n为集群节点数。这个算法太慢了,这是一个在实际生产环境中几乎无法使用的算法。

基于此,Miguel Castro 和Barbara Liskov在1999年发表的论文《Practical Byzantine Fault Tolerance》中首次提出PBFT算法,该算法容错数量也满足3f+1<=n,算法复杂度为o(n^2),PBFT解决了共识算法容错率不高的问题(其他共识算法为50%),并且将算法复杂度由指数级降低到多项式级,使得拜占庭容错在实际系统中应用变的可行。凭借PBFT算法,Liskov获得了2008年图领奖。

  1. PBFT工作机制
    PBFT要系统共同维护一个状态,所有节点采取的行动一致。为此,需要运行三类基本协议,包括:一致性协议、检查点协议和视图更换协议。同时,一致性协议要求来自客户端的请求在每一个服务节点上都按照一个确定的顺序执行,这个协议把节点分为两类:主节点和从节点,主节点仅有一个并负责请求排序,从节点按照主节点排序处理请求。

1)主节点的“选举”
PBFT的主节点“选举”和Raft算法的选举不一样,只是通过一个模运算进行或者选择当前存活的节点编号最小的节点成为新的主节点。p = v mod |R|,其中p为节点编号、v为视图编号,|R|为节点数量。当主节点失效后就需要启动视图更换。

2)PBFT算法基本流程:
客户端发送请求给主节点
主节点广播请求给其它节点,节点执行pbft算法的三阶段共识流程
节点处理完三阶段流程后,返回消息给客户端
客户端收到来自f+1个节点的相同消息后,代表共识已经正确完成
3)算法核心三阶段流程
三阶段流程如下图所示,核心三阶段分别为pre-preare阶段(预准备阶段)、prepare阶段(准备阶段)和commit阶段(提交阶段),图中的C代表客户端,0、1、2、3代表节点的编号,打叉的3代表可能是一个故障节点或者问题节点,0为主节点。

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

tips:相关字母代表含义提前了解一下

v:当前的视图编号,类似Raft的term任期
n:当前的请求编号
m:消息内容
d:消息内容的摘要
i:节点的编号
Pre-prepare阶段:节点收到pre-prepare消息后,要么接受要么拒绝或者等待。当主节点发送两条具有相同的v和n,但d和m的消息时拒绝,或者不在水位区间内则等待(后面会说)。

Prepare阶段:节点同意请求后会向其它节点发送prepare消息。在一定时间范围内,如果收到超过2f个不同节点的prepare消息,就代表prepare阶段已经完成。

Commit阶段:向其它节点广播commit消息,当收到2f+1个commit消息后(包括自己),代表大多数节点已经进入commit阶段,这一阶段已经达成共识,节点就会执行请求,写入数据。

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

三阶段流程-2.jpg
4)检查点协议
checkpoint、stable checkpoint和高低水位

checkpoint就是当前节点处理的最新请求序号,stable checkpoint,就是大部分(2f+1)已经共识完成的最大请求序号。所谓低水位可以理解为stable checkpoint对应的请求序号,而高水位指的是系统设定的一个值L加上stable checkpoint。

比如A节点当前checkpoint为1100,B节点checkpoint为1099,stable checkpoint为1000,L为100,那么高水位H = 1000+100=1100,低水位h=1000。此时由于A节点的请求序号超过高水位,则处于等待状态。当B节点处理速度跟上之后(比如checkpoint=1100),高低水位发生变化后,比如高水位变更为1200,低水位变更为1100时(具有2f+1个节点已经共识完成请求序号小于1100之前的请求),同时请求序号小于1100的请求数据都可以从节点本地删除,这个时候A节点就可以继续处理请求了。

检查点协议有两个功能:

确保pre-prepare阶段的所有请求能在同一水位范围内。所谓水位可以理解为一个滑动窗口。由于网络不同,节点的处理速度不同,会出现一些节点掉队。这个水位就是为了让跑的快的节点等等跟不上的老铁。
进行垃圾回收。由于三阶段会产生各种较小的请求数据,这些都需要保存在节点本地,长此以往,这个数据就很大,为了进行垃圾回收,检查点设置了稳定检查点,序号在稳定检查点前的都可以删除。
5)视图更换协议
当主节点挂了(超时无响应)或者从节点集体认为主节点是问题节点时,就会进行视图变更,视图变更完成后,视图编号将会加1。

视图变更协议分为三个阶段:视图变更阶段、视图变更确认阶段、新建视图阶段。

视图变更阶段:从节点认为主节点有问题时,会向其它节点发送view-change消息,当前存活的节点编号最小的节点将成为新的主节点。
视图变更确认阶段:当新的主节点收到2f个其它节点的view-change消息,则证明有足够多人的节点认为主节点有问题,于是就会向其它节点发送new-view消息
新建视图阶段:对于主节点,发送new-view消息后会继续执行上个视图未处理完的请求,从pre-prepare阶段开始。其它节点验证new-view消息通过后,就会处理主节点发来的pre-prepare消息,此时正式进入 v+1(视图编号加1)的时代了。

  1. PBFT优缺点
    PBFT算法是一种状态复制算法,优点为:1)效率高;2)容错性高;3)不需要代币;4)节能环保;

相反,PBFT依赖状态的维护,1)当网络不稳定或者参与者数量增多时,系统的稳定性和效率会显著下降;2)PBFT是一个部分中心化的网络;3)一旦有超过1/3的阶段作恶,会出现分叉。

  1. 网络攻击和链分叉
    如果说PoW和PoS是以经济模型为主解决共识的话,PBFT就是用算法模型来解决共识,它不需要代币,更适合联盟链,同时更加安全。在联盟链中,节点(机构)的加入都需要授权,这就使得网络攻击的难度大大增加。

PBFT具有强一致性,在少于1/3节点作恶的情况,不会出现分叉,但一旦超过1/3的节点作恶,就会出现硬分叉,不过这种分叉会有历史记录。

写在最后
通过两周的时间,对目前市面上比较流行的5种共识算法进行了梳理,我们发现每一种共识机制(算法)都有各自的优势和劣势,所以在实际的应用场景中,要根据具体情况进行选择。

本文内容比较多,除过自己的理解和总结外,有一部分也属于copy and paste,所以难免出现一些理解不一致和错误,一些细节的东西也很难尽善尽美。

共识机制作为区块链技术的灵魂,正在高速发展,目前已经出现基于上述共识机制的变种,同时一些结合式或者新的共识机制在逐步提出,包括区块链的设计由于不可能三角的原因,也出现一些变种,比如分层设计等。相信在不远的未来,各种流派的区块链技术和共识机制,会成为影响人们日常生活的一把利器,推动社会的变革。

上一篇下一篇

猜你喜欢

热点阅读