Consensus Algorithm PBFT

PBFT共识协议

算法介绍

Posted by Emo on April 25, 2022

共识算法

EMO’s Blog

Byzantine Problem

拜占庭问题的具体描述我就不详细说了。

拜占庭节点的行为方式

  1. 不发送消息，等同于一个Failure Node。

  2. 发送虚假消息，或者说给不同的节点发送不同的消息。

拜占庭节点能伪造消息吗？

不能，通过签名算法，我们能够防止消息在传递的过程中不会被修改，任何节点也无法伪装成其他节点去发送消息，因为他们无法伪造其他节点的签名。这也是拜占庭问题提出的一个基础，节点之间的交流是可靠的。

BFT中3f+1以及2/3投票结论推导

初始变量定义:
    M: 总的节点数量

    f: 总的拜占庭节点数量

    V: 需要接受到的投票的数量

    M-f: 所有的好节点的数量

    V好: 收到的V个投票中，好节点的数量

    V坏: 收到的V个投票中，拜占庭节点的数量

已知等式以及不等式:

    V好 + V坏 = V         ①

    V好 > V坏             ② (好人投票的数量大于坏人投票的数量是做决定的基础)

    V坏 <= f             ③ (坏人数量最多就f个，所以收到的华人投票数量也不会超过f)

    V <= M – f          ④ (收到投票数必须小于等于好人的总数，不然永远无法做出决定)

推导过程:

    由②可推:		  
        V好 > V坏
        V好 + V坏 > 2/V坏

    结合①:		  
        V > 2/V坏

    结合③:  	  
        V > 2f          ⑤

    结合④:		  
        M-f >= V > 2f
        M-f > 2f
        M > 3f          ⑥

    由⑤⑥可推:		
        V/M > 2f/3f
        V/M > 2/3 	(2/3投票的由来)

    由⑥可推:		
        M > 3f
        M >= 3f+1	(最少3f+1个节点的由来)

    当M为3f+1时:	
        M-f >= V > 2f
        3f+1-f >= V > 2f
        2f+1 >= V > 2f
        V = 2f+1        (投票数量只能设定为2f+1)

PBFT

节点类型

Leader/Primary

Replica

三段式提交

PBFT的提交阶段分为pre-prepare, prepare以及commit。虽然分为了三个阶段，但是其本质其实也是两段式提交。在这里我们先介绍一下常规的两段式提交prepare-commit，其中prepare阶段的目的是确认拜占庭网络中2/3的节点都已经收到并验证了request，而commit阶段这是为了确认2/3的节点都已经更新了状态。只有当commit阶段的验证结束后，我们才能够回复发起请求的用户请求的执行结果。在这里有一个比较有意思的点，用户再确认回复的真实性上只需要收到超过1/3的回复即可。我们可以看到在之前的提交阶段里，信息的确认都必须要达到2/3以上的门槛，为什么用户只需要达到1/3以上即可呢？这是因为用户不参与系统内部的共识过程，他只需要收到一个来自非拜占庭节点的回复即可，因为作为代表的这个非拜占庭节点的回复一定是通过了所有非拜占庭节点共识后的回复。又因为整个系统中的拜占庭节点的数量是1/3，所以用户只需要接受超过1/3的投票即可保证其中有一个非拜占庭节点，而只要有一个便满足了我们刚刚提到的需求。

讲完了这些，我们再来谈谈为什么PBFT为什么需要三段式提交，其实本质就是，第一阶段的pre-prepare阶段其实只是两段式提交前的一个准备阶段。与RAFT系统中的Leader不同，PBFT中的Leader的权限其实很有限，他唯一的特别点就在于，他会作为用户与整个网络的交流中转站，会将用户发送过来的消息转发给网络中的所有节点。而在共识过程中他不具备任何优越性。而pre-prepare阶段其实就是PBFT将用户的消息转发给网络中的其他节点的阶段，当然这也算是他自己的一个prepare投票阶段。我们可以这样看，如果用户可以直接和网络中的所有节点交流，那么其实PBFT中就不需要Leader了，也不需要pre-prepare阶段了。所以Leader只是在第一阶段帮助用户转发了一下消息。

而为什么我又提到pre-prepare阶段也算是Leader节点自身prepare阶段呢，是因为Leader节点完全可以把消息转发和prepare投票放在一起，没必要分开来发送，而Replica节点则必须要接收到Leader转发过来的用户信息后才能进行prepare阶段投票，这也是为什么我们可以看到Leader节点在prepare阶段并没有参与消息发送的原因。我们也可以得知，三阶段投票中的消息总量其实和两阶段投票一样，都是2*( N^2)。

垃圾回收/checkpoint

在上面的投票阶段中，我们可以看到，在投票的过程中，每个节点都需要记录以及维护大量的消息。随着网络的运行，这些消息日志的数量会变得越来越庞大，所以我们需要一个垃圾回收机制来回收无用的消息日志。

首先，这些日志是什么了，以及为什么需要保存这些日志。这些日志大部分其实就是三阶段投票共识中接收到的信息。我们需要知道接受到的日志的数量，才能够判断2/3的条件是否达成。那为什么不能只记录收到的投票消息的数量，而要保存记录完整的投票信息呢？因为我们需要防止有节点重复投票。如果我们对所有收到的投票信息都做了保留，那么我们很容易就能判断一个新的投票信息是否是重复的投票。

其实从上面的描述中，我们可以看到，一旦一个节点对某个请求的commit完成后，其实这些消息日志就不在需要了。为了保证所有节点在日志清除上的一致性，我们每次清除日志都需要向其他节点发送消息，只有当其他节点也确认后，才能删除消息。如果每一次commit都进行垃圾回收效率太低下了，所以我们一般会设定一个阙值k，只有当最新commit的消息的序号n满足(n % k == 0)时，才会发起垃圾回收流程。这里也叫做checkpoint。当前发起发起垃圾回收流程的消息被称为一个checkpoint，一旦投票通过后，这个checkpoint以及之前的所有的消息都可以删除了。

PBFT中有一个[h,H]的高低水位线设计，垃圾回收也可以移动高低水位线，h就是最新完成checkpoint的消息的序号，H则需要满足(H>h+k)。

视图切换以及两段式提交

每个节点都会维护一个视图编号v，当primary作恶或者共识阶段超时，节点都会发起view-change，并且新的视图编号为v=v+1。视图的编号可以用于确认新的primary，如果网络中的节点数量是N，那么编号为v%N的节点就是新的primary节点。下面我会主要讲两段式共识机制是如何防止视图切换带来的分叉问题。(虽然PBFT是三段式提交，但是他依旧属于两段式共识范畴，因为第一个pre-prepare阶段只是在做消息转发，真正在做共识的还是后面两次提交)

投票阶段的节点有三种阶段，pre-prepare，prepare和commit。很好理解，收到来自Primary的pre-prepare消息后，节点的状态会变成pre-prepare。当节点收到超过2/3的prepare投票后，状态会变成prepare。当节点收到超过2/3的commit投票后，状态会变成commit。这也是两段式提交当中，节点的状态变化流程。那么为什么要引入两段式提交呢？其实是为了防止视图切换的时候，产生分叉。

看上图，网络在对a和a’这个高度的区块进行三段式提交的时候，如果发生了view-change会怎么样。在PBFT中，如果一个节点发现共识过程超时或者主节点作恶，便会发起view-change请求，并且带上自己当前的状态，当然他需要证明自己的确处于这个状态，于是他需要将他在当前共识流程中收到的所有投票都一并广播出去。

这个时候我们可以看到view-change消息的大小已经不是和之前投票阶段消息一样的O(1)了，而是O(n)。新的primary确认view-change合法的方式依旧是需要收到2/3个合法的view-change请求。于是view-change阶段的IO复杂度就成了O(n*n^2)，即O(n^3)，也就是消息的大小乘以消息的总次数。如果新的primary收到了超过2/3的view-change请求，那么他就会广播new-view请求给所有的节点，这个阶段消息传递的次数的复杂度是O(n)，但是新的primary需要证明自己的确收到了2/3个view-change请求，所以它需要在发送的new-view消息里面包含自己收到的所有view-change请求，因为每个view-change的请求的大小是O(n)，所以new-view消息的大小会是O(n*n)，即O(n^2)。再由于消息传递的次数是O(n)，所以IO的复杂度依旧是O(n^3)。

在新的primary接收到的2/3个view-change请求这里存在两种情况：

  1. 收到的view-change请求里没有人的状态是prepare

如果view-change里面不存在prepare阶段，新的primary是无法判断好人节点在a和a’中选择了谁。自然新的primary也是无法从两个中选出一个作为主链并在其之上发布新的区块的。所以，这个时候primary可以判断出，自己需要在a和a’的上一个达成共识的pre节点上开辟新区块。我们可以知道，节点当中肯定没有人达到commit状态，因为有节点达到commit阶段的前置条件就是有超过2/3的节点达到了prepare状态。而如果有2/3的节点都达到了prepare阶段，那么新的primary收到的超过2/3个节点的view-change里面肯定会存在注明prepare阶段的view-change消息。因此，没有人达到commit阶段则说明，还没有节点在a和a’中选出一个作为状态更新。也就是说在pre上提出新的区块a’’不会导致分叉。

  1. 收到的view-change请求里有人的状态是prepare

和上面相反，这个时候我们虽然无法判断是否有人一定已经commit了，但是我们也无法排除这种可能。所以如果我们这个时候依旧在pre上去提出新的区块，就会有分叉的风险性。但好在prepare阶段的view-change消息告诉了新的primary在a和a‘中做出的选择是什么，而且这个选择是通过了超过2/3个节点确认的。比如这个prepare消息中指明选择的是a，那么新的primary只需要在a的基础上提出新的区块，并且将这个prepare状态的view-change消息里的prepare投票集合一起发给其他的节点，大家就能继续在a上达到commit共识，然后继续对a上新产生的新区块b进行共识投票。

缺点

  1. 身份认证

因为我们在投票中，每个阶段的认证和消息传递是需要知道网络中存在的节点的总数以及位置的。

  1. IO消耗大

因为在N个节点的网络的投票阶段中，每个节点都需要与其他的N-1个节点做P2P的消息传递，整个网络IO的复杂度是O(N^2)。随着节点的数量增大，整个网络的延时也会越来越大，效率也会越来越低。

以上两个缺点导致了PBFT很难直接在公链项目中使用。一般都用在联盟链中，或者是基于POS构建了选举制度的公链当中。无论是上面这两种的那一种，其实本质都是提供了身份验证并且限制了参与投票的节点数量。

优点

  1. 在节点数量少的时候，效率比较高。

  2. 对分叉的抵御能力强。

CATALOG
    FEATURED TAGS
    UniMelb Assignment Blockchain Consensus Algorithm Bitcoin Notes ETH 设计模式 JVM OpenZeppelin chainlink Oracle
    { % if page.mermaid % } { % endif % }