深入理解PBFT算法——提交阶段的作用

文章目录

1. 前述

PBFT(Practical Byzantine Fault Tolerance,实用拜占庭容错算法)是联盟链常用的一种共识算法。本文讨论PBFT提交阶段的作用,要求读者对PBFT的算法有一个大致了解,如果你是刚听过这个算法,知道算法的基本流程,看完本文可能会对PBFT有更深入的理解;如果你研读过PBFT原论文,那么本文也许可以作为阅读拓展。如果有不同理解或者认为文中表述有问题,欢迎讨论指正。

2. PBFT算法的QC性质

在讨论主题之前,我们需要先了解PBFT算法的QC性质,这是证明PBFT正确性的重要前提。

Q 和 C 分别表示 Quorum 和 Certificate。

  • Quorum 意思为 仲裁数,法定人数。在PBFT中,当总节点数为3f+1时(用 f 表示拜占庭节点数量时,总节点数大于等于 3f+1 时拜占庭问题才有解,这个问题的证明不在本文的讨论范围),Quorum 表示数量不少于 2f+1 的节点集合。
  • Quorum certificate 则表示来自一个Quorum的每个节点的某种消息组成的一个集合,称为证书,如准备证书和提交证书。

Quorum 有两个重要的性质:

  1. 相交性: 任何两个 Quorum 至少有一个共同的正确节点。
  2. 可得性: 总能找到一个没有错误节点的 Quorum 。

Intersection property: any two quorums have at least one correct replica in common.
Availability property: there is always a quorum available with no faulty replicas.

这两个性质贯穿了PBFT的整个证明过程,特别是性质1。

第一个性质,我们可以用一个图直观地理解:

图1. Quorum 的相交性

我们在一个大小为3f+1的集合中,画两个2f+1子集,并且使得交集尽可能地小,可以看到,即使尽最大的努力减小交集,最小的交集还是f+1,即交集中至少有一个正确节点。

另外,当 f=1 时,3f+1=4,当 f=2 时,3f+1=7,那么当总节点数等于5或6时,Quorum 的数量该如何计算呢?我们记总节点数为N,且 3f+1≤N<3(f+1)+1 ,则一个 Quorum 的数量不少于\\lceil\\frac{2N}{3}\\rceil ,其中\\lceil\\rceil 表示向上取整,推导:

设 Quorum 的数量为x,为了满足性质1,两个 Quorum 的交集大小至少为 f+1,则有

2x-N≥f+1
x≥\\frac{N+f+1}{2}

3f+1≤N<3(f+1)+1 ,即 \\frac{N-1}{3}-1<f≤\\frac{N-1}{3} ,可得 f = \\lfloor\\frac{N-1}{3}\\rfloor ,其中\\lfloor\\rfloor 表示向下取整,带入上式,并由\\lfloor\\frac{n}{m}\\rfloor=\\lceil\\frac{n+1}{m}\\rceil-1 1有:

x≥\\frac{N+\\lfloor\\frac{N-1}{3}\\rfloor+1}{2}=\\frac{N+(\\lceil\\frac{N}{3}\\rceil-1)+1}{2}=\\frac{1}{2}\\lceil\\frac{4N}{3}\\rceil

因为x为整数,可对上式右侧向上取整,得:

x≥\\lceil\\frac{1}{2}\\lceil\\frac{4N}{3}\\rceil\\rceil=\\lceil\\frac{2N}{3}\\rceil=\\lfloor\\frac{2N-1}{3}\\rfloor+1

转化为向下取整可以方便转化为编程语言(编程语言的整数除法一般为向下取整)。

N=3f+1时带入校验,同样满足上式。

3. 提交阶段的作用

3.1 前两个阶段

PBFT包含三个阶段:预准备阶段、准备阶段、提交阶段。

图2. PBFT算法大致流程

准备阶段收集2f+1个来自不同节点的序列号相同、请求相同的准备消息(可以含1个预准备消息),这一步确保了请求顺序在所有正确节点上达成一致。这利用了性质1,对于任意两个节点来说,如果他们分别收到了2f+1个来自不同节点的序列号相同的准备消息,那么一定有一个消息来自一个共同的正确节点,再加上正确节点不会对同一个请求发送两个序列号不同的消息(算法决定),所以他们收到的准备消息的序列号一定相同。

前两个阶段是用于同一个视图内保证请求的顺序一致,提交阶段是用于保证跨视图(主节点切换)的请求顺序一致。也就是说,如果没有视图切换,前两个阶段已经能够保证顺序一致。

3.2 假设只有两个阶段

为了看清提交阶段的作用,我们假设没有这个阶段,看是否能够保证算法的正确(安全性和活动性),或者说,我们能否设计出一个算法,可以将提交阶段去除。

我们考虑四个节点的情况,节点1为主节点、且为恶意节点,在一次共识周期中,主节点向节点3和4发送编号为n、请求为m的预准备消息,向节点2发送编号为n、请求为m’(与m不同)的预准备消息,假设在一定时间之后,节点3收集到了准备证书(2f个准备消息和1个预准备消息),并执行了该请求,对客户端进行了响应。

图3. 假设没有提交阶段

假设此时发生了主节点切换,新的主节点为节点2,我们知道,节点2并没有收集到请求m的准备证书,但由于此时节点3认为该请求已达成共识,并且已经执行了该请求,所以请求m必须被重放,以使得所有节点达成一致。为了重放请求m,节点2需要收集来自其他节点的准备证书,假设只有节点3收集到了准备证书,那么只有保证节点2能够收到来自节点3的准备证书,才能重放该请求。

我们尝试能否通过设计一定的算法来达到这样的目的:在视图切换的时候,所有节点向新的主节点发送已有的准备证书,主节点收集这些证书并对这些请求进行重放,那么主节点要在什么时候停止收集证书呢?假设是收到2f+1个节点的消息时,停止收集,那就可能错过节点3的准备证书;所以不难得出,必须收集所有节点的消息,才能停止,但这更是不可能的,因为拜占庭节点可以选择不发送消息。可见,设计出这样的算法是不太可能的。

3.3 提交阶段的作用

那么提交阶段是如何解决这个问题的呢?通过以上的讨论,我们可以看到,如果收集到准备证书就执行请求,此时由于可能没有足够的节点收集到了准备证书,所以后续无法保证在切换主节点之后,该请求能够被重放(被其他节点执行)。因此,每个节点应该在获知有足够的节点收集到准备证书之后,再执行请求,提交阶段就是做了这样的事情。

首先,提交阶段要求节点收集到2f+1个提交消息之后,才进入已提交状态,此时节点执行该请求并对客户端进行响应。这个要求保证了在执行请求的时候,已经有2f+1个节点收集到了准备证书,这对于后续请求的重放起了关键作用。

在主节点切换时,节点在广播的View-Change消息中包含了(所有未达到稳定检查点的)准备证书,新主节点发出的New-View消息之前,至少收集2f+1个节点的View-Change消息。假设请求m在主节点切换之前已经被提交了,也就是有2f+1个节点持有它的准备证书,由PBFT算法的QC性质1,这**2f+1**个节点与New-View消息中的**2f+1**个节点,一定有一个共同的正确节点,也就是被提交的请求一定会在新的视图中重放,这解决了跨视图的一致性问题。

综上所述,提交阶段是用于与View-Change配合,保证在上一视图中执行的请求,可以在新的视图中重放,并且编号n相同,即保证了跨视图请求顺序的一致性。

参考:

本站文章资源均来源自网络,除非特别声明,否则均不代表站方观点,并仅供查阅,不作为任何参考依据!
如有侵权请及时跟我们联系,本站将及时删除!
如遇版权问题,请查看 本站版权声明
THE END
分享
二维码
海报
深入理解PBFT算法——提交阶段的作用
PBFT(Practical Byzantine Fault Tolerance,实用拜占庭容错算法)是联盟链常用的一种共识算法。本文讨论PBFT提交阶段的作用...
<<上一篇
下一篇>>