拜占庭共识算法之PBFT

          原始的拜占庭容错系统由于需要展示理论上的可行性而缺乏实用性。另外,算法的复杂度也是随着节点的增加而呈现指数级别增加。实用性拜占庭容错系统(Practical Byzantine Fault Tolerance,PBFT)降低了拜占庭协议的运行复杂度。从指数级别降低到多项式级别,使拜占庭在分布式系统中应用称为可能。

概念

          实用拜占庭容错系统是一类“状态机”拜占庭系统(这里的状态机可以理解为“系统状态”,以区块链记账为例,系统每增加一个区块,账本就更新到一个新的状态.拜占庭容错系统是一个强一致协议,每次记账后系统都会达成新的状态),要求系统所有的节点共同维护一个状态,所有的节点采取的行动一致。

实用性拜占庭容错系统需要运行三类基本协议

  • 一致性协议:解决如何达成共识
  • 检查点协议:类似于操作系统的还原点
  • 视图更换协议:系统的每个服务器节点在同样的配置信息下工作,该配置信息被称为视图。配置信息由主节点确定,主节点更换,视图也随之变化

PBFT的一致性协议

1-1

  • 客户端发送请求到主节点,主节点由公式p = V mod R 决定,p是节点的编号,V是视图编号,R是整个系统中节点的个数。请求的消息格式是<REQUEST,o,t,c>,其中o是请求的操作,t是客户端的本地时间,c是客户端

  • 主节点广播请求消息到每一个备份节点
  • 所有节点(主节点和备份节点)执行请求,把结果返回到客户端,返回的消息格式为<REPLY,v,t,c,i,r>,v是节点维持的当前的视图号,t是与请求消息中一样的时间,i是节点编号,r是执行请求的结果
  • 如果客户端收到f+1个来自不同节点且t相同,r也相同的应答,则接受此应答。如果客户端一直没有收到应答,则客户端向每一个节点都发送此请求消息,如果此请求已经被执行,则直接把结果返回给客户端(每一个节点保存上一个发送给客户端的应答);如果此请求还没有执行,那么非主节点把此请求转发给主节点,如果主节点一直不广播请求,备份收不到请求,则怀疑主节点出错,导致view change

四个阶段

       一致性协议至少包含请求(request)序号分配(pre-prepare)响应(reply)三个阶段。可能包含相互交互(prepare)序号确认(commit)等阶段。pre-prepare阶段和prepare阶段用来把在同一个view里发送的请求给确定下序列,就是排好序,让各个备份节点都认可这个序列,照序执行

pre-prepare阶段

          主节点收到来自Client的一条请求并分配了一个编号给这个请求,然后主节点会广播一条PRE-PREPARE信息给备份节点,这个PRE-PREPARE信息包含该请求的编号、所在的view和自身的一个digest。直到该信息送达到每一个备份节点,接下来就看收到信息的备份节点们同不同意主节点分配给该请求的这个编号n,即是否接受这条PRE-PREPARE信息,如果一个备份节点接受了这条PRE-PREPARE,它就会进入下面的prepare阶段。

什么情况下备份节点会拒绝(not accept) PRE-PREPARE信息:当该备份节点之前已经接收到了一条在同一view下并且编号也是n,但是digest不同的PRE-PREPARE信息时,就会拒绝。

prepare阶段

          一个备份节点进入到自己的prepare阶段后,开始将一条PREPARE信息广播给主节点和其它两个备份节点,直到PREPARE信息都抵达那三个节点。与此同时,该备份节点也会分别收到来自其它两个备份节点的PREPARE信息。该备份节点将综合这些PREPARE信息做出自己对编号n的最终裁决(这时进行的判断是在防止主节点是拜占庭节点的情况)。当这个备份节点开始综合比较来自其它两个备份节点的PREPARE信息和自身的PREPARE信息时,如果该备份节点发现其它两个节点都同意主节点分配的编号,又看了一下自己,自己也同意主节点的分配,a quorum certificate with the PRE-PREPARE and 2 f matching PREPARE messages for sequence number n, view v, and request m,如果一个备份节点达到了英文所说的条件,比如就是上面的斜体字描述的一种情况,那么我们就说该请求在这个备份节点上的状态是prepared,该备份节点就拥有了一个证书叫prepared certificate。那我们是不是就可以说至此排序工作已经完成,全网节点都达成了一个一致的请求序列呢,每一个备份节点开始照着这个序列执行吧。

          这是有漏洞的,设想一下,在t1时刻只有备份节点 1把请求m(编号为n)带到了prepared状态,其他两个备份节点 2,3还没有来得及收集完来自其它节点的PREPARE信息进行判断,那么这时发生了view change进入到了一个新的view中,节点 1还认为给m分配的编号n已经得到了一个法定人的同意,可以继续納入序列中,或者可以执行了,但对于备份节点 2来说,它来到了新的view中,它失去了对请求m的判断,甚至在上个view中它还有收集全其他节点发出的PREPARE信息,所以对于备份节点 2来说,给请求m分配的编号n将不作数,同理备份节点 3也是。那么备份节点 1一个人认为作数不足以让全网都认同,所以再新的view中,请求m的编号n将作废,需要重新发起提案。所以就有了下面的commit阶段。

1.需要注意的是,该备份节点会将自己收到的PRE-PREPARE和发送的PREPARE信息记录到自己的log中。 2.该备份节点发出PREPARE信息表示该节点同意主节点在view v中将编号n分配给请求m,不发即表示不同意。 3.如果一个备份节点对请求m发出了PRE-PREPARE和PREPARE信息,那么我们就说该请求m在这个备份节点上处于pre-prepared状态。

commit阶段

          紧接着prepare阶段,当一个备份节点发现有一个法定人同意编号分配时,它就会广播一条COMMIT信息给其它所有节点告诉他们,它有一个prepared certificate了。与此同时它也会陆续收到来自其它节点的COMMIT信息,如果它收到了2f+1条COMMIT(包括自身的一条,这些来自不同节点的COMMIT携带相同的编号n和view v),我们就说该节点拥有了一个叫committed certificate的证书,请求在这个节点上达到了committed状态。此时只通过这一个节点,我们就能断定该请求已经在一个认定人中到达了prepared状态,即一个认定人的节点们都同意了编号n的分配。当请求m到达commited状态后,该请求就会被该节点执行。

          三阶段介绍完毕。我们想象一种情况,主节点是坏的,它在给请求编号时故意选择了一个很大的编号,以至于超出了序号的范围,所以我们需要设置一个低水位(low water mark)h和高水位(high water mark)H,让主节点分配的编号在h和H之间,不能肆意分配。

primary-backup

          这个机制下有一个叫view的概念,在一个view里,一个备份节点会是主节点(primary),其余的都叫备份节点(backups)。主节点负责将来自Client的请求给排好序,然后按序发送给备份节点们。但是主节点可能会是faulty的:它可能会给不同的请求编上相同的序号,或者不去分配序号,或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性,并能通过timeout机制检测到主节点是否已经宕掉。当出现这些异常情况时,这些备份节点就会触发view change协议来选举出新的主节点。

The Client

          一个Client会将请求⟨REQUEST,o,t,c⟩, 其中o表示具体的操作,t表示timestamp,给每一个请求加上时间戳,这样后来的请求会有高于前面的时间戳 replicas会接收请求,如果他们验证了条请求,就会将它写入到自己的log中。在共识算法保证下每个replica完成对该请求的执行后直接将回复返回给client:⟨REPLY,v,t,c,i,r⟩ v是当前的view序号,t就是对应请求的时间戳,i是备份节点的编号,r是执行结果,我们上面提到过weak certificate,在这里,client也会等待这个weak certificate:即有f+1个replicas回复,并且它们的回复拥有相同的 t 和 r,由于至多有f个faulty replicas,所以确保了回复是合法的。我们叫这个weak certificatereply certificate每一个replica会与每一个处于active状态的client共享一份秘钥。秘钥所占据空间较少,加上会限制active client的数量,所以不必担心以后出现的扩展性问题。

垃圾回收

          分布式系统的复杂性在于要考虑到各种各样的意外和蓄意破坏,你要制定出一套有效的法律来约束这个系统里可能发生的一切行为,并没有完美的分布式系统存在。 当备份节点执行完请求时,需要把之前记录的该请求的信息清除掉。但是不能这样轻易的去清除,其中包含的prepared certificate可能会在后面用得上。所以要有种机智来保证何时可以清除。

          其实很简单,每执行完一条请求,该节点会再一次发出广播,就是否可以清除信息在全网达成一致。更好的方案是,我们一连执行了K条请求,在第K条请求执行完时,向全网发起广播,告诉大家它已经将这K条执行完毕,要是大家反馈说这K条我们也执行完毕了,那就可以删除这K条的信息了,接下来再执行K条,完成后再发起一次广播,即每隔K条发起一次全网共识,这个概念叫checkpoint,每隔K条去征求一下大家的意见,要是获得了大多数的认同(a quorum certificate with 2 f + 1 CHECKPOINT messages (including its own)),就形成了一个 stable checkpoint(记录在第K条的编号),我们也说该replica拥有了一个stable certificate就可以删除这K条请求的信息了。 这是理想的情况,实际上当备份节点 i向全网发出checkpoint共识后,其他节点可能并没有那么快也执行完这K条请求,所以备份节点 i不会立即得到响应,它还要继续自己的步伐,那这个checkpoint在它那里就不是stable的。那这个步伐快的备份节点可能会越来越快,可能会把大家拉的越来越远,这时我们来看一下上面提到的高低水位的作用。           对该replica来说,它的低水位h等于它上一个stable checkpoint的编号,高水位H=h+L,L是我们指定的数值,它一般是checkpoint周期K的常数倍(这个常数是比较小的, 比如2倍),这样即使该备份节点的步伐很快,它处理的请求编号达到高水位H后也得停一停自己的脚步,直到它的stable checkpoint发生变化,它才能继续向前。

View change

          当主节点挂掉后就触发了view change协议。我们需要确保在新的view中如何来延续上一个view最终的状态,比如给这时来的新请求的编号,还有如何处理上一个view还没来得及完全处理好的请求。 Data Structures

          所以我们需要记录上一个view里发生什么。 有两个集合P和Q,备份节点 i 的P存着 i 在上一 view 中达到prepared状态的请求的一些信息,有了P,在新的view中,备份节点 i就会明白接下来处于preppared状态的请求不能与上一个view中处于prepared状态的请求的编号相同Q是记录在上一个view里到达pre-prepared状态的请求的一些信息。

View-Change Messages

          我们来看一下Fig 2, 当备份节点 i 怀疑 view v中的主节点出问题(比如是坏节点)后,它会进入 view v+1,并广播一条VIEW-CHANGE信息给所有的备份节点,其中包含该备份节点 i最新的stable checkpoint的编号,还有 备份节点 i上存的每一个checkpoint的编号和digest的集合,还有上面所说的该备份节点的P和Q两个集合。

View-Change-Ack Messages

          备份节点会收集VIEW-CHANGE信息并发送ACK确认给 view v+1 中的主节点 。新的主节点收集了VIEW-CHANGE和VIEW-CHANGE-ACK(包含自己的信息),它会将VIEW-CHANGE存在一个集合S中。主节点需要选出一个checkpoint作为新view处理请求的起始状态。它会从checkpoint的集合中选出编号最大(假设编号为h)的checkpoint。接下来,主节点会从h开始依次选取h到h+L(L就是normal case阶段我们提到的设置值)之间的编号n对应的请求在新的view中进行pre-prepare,如果一条请求在上一个view中到达了committed状态,主节点就选取这个请求开始在新的view中进行三阶段。之所以选取committed的请求,是因为上面我们提到增加COMMIT阶段为了across view来考虑的,处于committed状态的请求的编号在新的view中是有效的,可以继续使用。但是如果选取的请求在上一view中并没有被一个认定人给prepare,那它的编号n有可能是不被一个认定人给同意的,我们选择在新的view中作废这样的请求。

参考

超级账本PBFT(拜占庭容错)算法详解

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦