0%

也谈PBFT/Tendermint/HotStuff中的活性问题、响应度问题和锁定问题

HotStuffPODC版本论文Arxiv版本论文中,多次将不同共识协议的活性(liveness)和响应度(responsiveness)进行比较。此外,一些博客和其他相关论文中也有关于liveness问题和responsiveness问题的叙述。其中涉及到两点叙述:

  1. Tendermint中在leader切换的时候需要等待一个最大的网络延迟\(\Delta\),导致Tendermint无法做到optimistic responsiveness
  2. 如果Tendermintleader切换的时候不等待\(\Delta\),将导致Tendermint中无法进行有效共识,从而破坏协议的liveness

但笔者在看这两点叙述的时候,总感觉论文作者和博主没有将问题讲透,看得云里雾里的。可能大佬们觉得这两点叙述很容易理解,甚至是一些一点就该通的常识。

为了真正弄懂以上两点叙述,笔者查阅了大量资料,并将自己的一些理解整理在这篇博客中。这篇博客需要读者对共识算法已经有了一定的理解。

I.两/三阶段共识中的锁定机制

我们先从共识协议中的“锁定机制”开始说起。 无论是PBFTTendermint还是HotStuff,都在共识过程中隐式或显示地引入了锁定机制。其中,PBFT论文中没有显示定义这种锁定机制,但每个replica在本地prepared之后,就可以认为是在锁定了。 PBFTTendermint/HotStuff中锁定的作用是不同的:

  1. PBFT中的锁定机制只是为了防止一个诚实replica同时对两个矛盾的proposal投票,而不会检查新的proposal是否基于已锁定的proposal。这样的锁定机制也就不对已锁定的proposal做出任何承诺,即:在发生leader切换的时候,上一个view中锁定的proposal在本轮中可以被轻易推翻。
  2. 相反,Tendermint/HotStuff中的锁定机制除了防止一个诚实replica对两个矛盾proposal投票外,还会进一步检查新的proposal是否基于已锁定的proposal。这样的锁定机制对于已锁定的proposal做出了一定的承诺,即:在上一个view中已经被锁定的proposal,除非发生特殊情况(replica接收到的proposal基于更高的QC),在新的view中不会被推翻。

这两种锁定机制的不同源于他们对于leader赋予的可信度是不同的。

II.共识协议中Leader可信度的不同

PBFTleader的可信度是很大的(其作恶空间很小),这是因为leader在进行View的切换时,其在发出的New-View消息中携带了充分的证明性数据,其他replica有理由相信leaderNew-View消息中是很难作恶的。所以大家都把本地锁定的数据修改为leader发来的New-View中携带的数据。 这也导致了HotStuff等论文中诟病的PBFT进行View切换时的高开销问题,因为New-View消息中需要携带证明性数据。

相反,Tendermint/HotStuff中的leader在进行view切换时,无需携带证明性数据。因此,leader的可信度较低(作恶空间很大)。对于leader发来的新的proposal,其他replica需要对其进行更为严格的检查,也即出现了在上一节中所述的:Tendermint/HotStuff中的锁定机制要求进一步检查新的proposal是否基于已锁定的proposal

接下来,我们继续对Tendermint/HotStuff类的锁定机制的设计进行分析,并将这一类共识简称为“single-modal”类共识(PBFT被称为bi-modal类共识)

III.Single-modal类共识中锁定机制的设计

在第I节中,我们介绍到:Single-modal类共识在检查新的proposal时,会进一步检查该proposal是否基于其本地已经锁定的proposal(或者说QC)。如果新proposal不是基于锁定的QC,那么这个replica会拒绝对该proposal投票。 同时,我们也补充说明了另外一种情况:如果新的proposal所指向(基于)的QC高于replica本地锁定的QC,该replica会将自己锁定的QC更新到proposal所基于的QC,并对其进行投票。 为了方便讨论,我们对这两种投票的情况分别命名为规则1和规则2。这两条规则也对应于HotStuff论文中的SAFENODE原语的设计,如下所示: 关于规则1,前面也讨论了,是为了减小leader的作恶空间,从而保证安全性;关于规则2,论文中写到是为了保证活性(liveness)。我们来看看这一点如何理解。

A. 对锁定机制中规则2活性的理解

我们假想一下,如果没有规则2,Single-modal类共识会出现什么样的问题。没有规则2,也就意味着:每个replica都只会对基于自己的QCproposal投票。 我们考虑如下一个例子:

  1. 假设在view 0的时候,replica 0leader,且只有其收到了QC并在本地锁定了v0,此时由于网络原因发生了view的切换.
  2. view 1的时候,新的leader (replica 1)由于没有在v0锁定,于是基于更早的一个view(假设是vold)发起了proposal;此时replica 0是不会进行投票的,因为这个proposal不是基于v0的,但其他的节点还是可能会投票,当replica 1收到了足够多的投票组成QC后,其在本地锁定v1;此时也由于网络原因发生了view的切换。
  3. view 2的时候,同理,replica 2锁定了v2。 ...
  4. view f的时候,replica f锁定了vf
  5. 此时,replica (2f+1) ~ replica (3f)下线了,只剩下replica 0 ~ replica 2f。(这也是满足系统假设的,有超过2f+1个正确节点,并且我们假设接下来是同步网络
  6. 但接下来,协议就会卡住。
  7. 在新一轮次(所有replica轮一遍称为一个轮次)的view中,replica 0发起的新proposalreplica 1 ~ replica f都不认,因为不是基于他们锁定的view发起的,从而无法收集到新的QC
  8. 同理,replica 1发起的新proposalreplica 0replica 2 ~ replica f都不认,因为不是基于他们锁定的view发起的,从而无法收集到新的QC; ...

上面这个例子在第4步之后,replica 0 ~ replia f都不会给除了自己之外的其他节点的proposal投票。在每个viewleader无法都无法收集到2f+1个投票,也无法生成/锁定新的QC。 因此,整个协议就卡住了。

也就是说,在没有规则2的情况下,Single-modal类共识会卡住,从而失去活性。

相反,当引入规则2后,我们看看上面的例子会怎么变化:

  1. 假设在view 0的时候,replica 0leader,且只有其收到了QC并在本地锁定了v0,此时由于网络原因发生了view的切换.
  2. view 1的时候,新的leader (replica 1)由于没有在v0锁定,于是基于更早的一个view(假设是vold)发起了proposal;此时replica 0是不会进行投票的,因为这个proposal不是基于v0的,但其他的节点还是可能会投票,当replica 1收到了足够多的投票组成QC后,其在本地锁定v1;此时也由于网络原因发生了view的切换。
  3. view 2的时候,同理,replica 2锁定了v2。 ...
  4. view f的时候,replica f锁定了vf
  5. 此时,replica (2f+1) ~ replica (3f)下线了,只剩下replica 0 ~ replica 2f。(这也是满足系统假设的,有超过2f+1个正确节点,并且我们假设接下来是同步网络

---------- 上面和前一个例子一样,下面是规则2引入后的不同

  1. 在新一轮的view中,虽然replica 0 ~ replica f-1发起的新proposal,都无法得到其他所有节点的认可,从而无法收集到新的QC;但当轮转到replica f的时候,其基于view f发起新的proposal能够得到所有replica的认可,从而对其投票,因而replica f可以收集到足够多的投票并生成QC。 这就从上面例子中“协议卡住”的情况解脱出来了。

这里,我们可能会有一个想法

每一个轮次,前面的replica 0 ~ replica f-1发起的proposal都无法得到其他所有节点的投票,只有等到replica f的时候,才真正收集到足够多的投票形成QC,不会效率太低了嘛?

针对该问题,Single-modal类共识都做了一个优化设计:

在每个replica发起新的proposal之前,允许其收集其他replica中的锁定的QC信息,再基于收集到的最高的QC发起新的proposal,就可以大大提升效率了。

举例来说,在上个例子中,如果replica 0在发起proposal之前就收到了replica f发来的QC(锁定在vf高度),其基于该QC发起新的proposal,就可以得到其他所有replica的认可了。

B. 为什么Tendermint在进行leader切换的时候要等待\(\Delta\)

一切似乎都很美好了。但Tendermint在进行leader切换的时候,要求leader在发起proposal之前等待一个网络时延的上限\(\Delta\)。这使得Tendermint无法实现optimistic responsiveness。 我们先来分析一下为什么要等待\(\Delta\)

1. Tendermint不等待\(\Delta\)导致的Hidden Lock问题

Hidden lock考虑的是同步网络下的问题,因为异步网络比同步网络更难解决。如果同步网络中存在Hidden lock问题,异步网络中也会存在类似且更复杂的问题。 以下,我们考虑同步网络下的Hidden lock问题。为了解释该问题,我们也举个例子如下。该例子中一开始是异步网络,后面切换到同步网络。

  1. 假设一开始所有replica都是锁定在一个view (vold)的QC上。 接下来,在view 0的时候,replica 0leader,其首先收集2f个其他replica发来的QC(加上自身的QC一共2f+1个),这2f+1QC中的最大值是voldQCreplica 0基于该QC发起了proposal;其他replica对该proposal纷纷进行投票;replica 0收集到2f+1个投票后组成QC,并在本地锁定了v0;此时,由于网络原因发生view的切换,使得除了replica 0之外其他的节点都没有收到v0对应的QC
  2. view 1的时候,replica 1leader,其首先收集2f个其他replica发来的QC(加上自身的QC一共2f+1个),这2f+1QC中的最大值是voldQC(也即其未收到replica 0发来的QC);replica 1基于该QC发起了proposal;除了replica 0之外的其他replica对该proposal纷纷进行投票;replica 1收集到2f+1个投票后组成QC,并在本地锁定了v1;此时,由于网络原因发生view的切换,使得除了replica 1之外其他的节点都没有收到v1对应的QC
  3. 同理,在view 2的时候,只有replica 2在本地锁定了v2对应的QC,其他replica都未收到; ...
  4. view f的时候,只有replica f在本地锁定了vf对应的QC,其他replica都未收到;
  5. view (f+1)的时候,replica (f+1)发起proposal,但replica 0 ~ replica f都不会进行投票。这一轮的view不会生成任何QC ...
  6. view (3f)的时候,replica (3f)发起proposal,但replica 0 ~ replica f都不会进行投票。这一轮的view不会生成任何QC

-----------以上是异步网络环境,接下来进入同步网络环境。在该网络环境中,除了拜占庭节点,所有的节点之间的消息在\(\Delta\)时间内都能正确送达------------

  1. view (3f+1)的时候,又回到replica 0,其首先收集了2f个其他replica发来的QC(加上自身的QC一共2f+1个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1QC中的最大值是replica 0自身的QC,也即锁定在v0上的QC(这种情况下,replica 0收到的前2fQC中没有来自replica 1~replica f节点的)。于是,其基于v0发起新的proposal,但replica 1 ~ replica f都不会投票,replica (f+1)~ replica (3f)中的拜占庭节点也全不投票(假设其中有k个拜占庭节点),导致replica 0只能收到(2f+1-k)个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+2。此时,拜占庭节点进行投票,使得replica 0又收到了足够多的投票,组建出QC。于是,replica 0锁定了v (3f+1)。但其他节点已经切换到view (3f+2)了,即使接收到replica 0发来的QC,也不会更新自己本地锁定的QC了。
  2. view (3f+2)的时候,又回到replica 1,其首先收集了2f个其他replica发来的QC(加上自身的QC一共2f+1个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1QC中的最大值是replica 1自身的QC,也即锁定在v1上的QC。于是,其基于v1发起新的proposal,但replica 0replica2 ~ replica f都不会投票,replica (f+1) ~ replica (3f)中的拜占庭节点也全不投票(假设其中有k个拜占庭节点),导致replica 1只能收到(2f+1-k)个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+3。此时,拜占庭节点进行投票,使得replica 1又收到了足够多的投票,组建出QC。于是,replica 1锁定了v (3f+2)。 ...
  3. view (3f+f+1)的时候,又回到replica f,同理,只有replica f锁定了v (3f+f+1)
  4. view (3f+f+2)的时候,又回到replica (f+1),其首先收集了2f个其他replica发来的QC(加上自身的QC一共2f+1个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1QC中的最大值是replica 0发来的QC,即锁定在v (3f+1)上。于是,其基于v (3f+1)发起新的proposal,但replica 1 ~ replica f都不会投票,replica (f+1)~ replica (3f)中的拜占庭节点也全不投票(假设其中有k个拜占庭节点),导致replica (f+1)只能收到(2f+1-k)个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+f+3。 ...
  5. view (3f+3f+1)的时候,又回到replica (3f),其同样无法组成QC。其他诚实节点由于无法及时收到QCview切换到3f+3f+2
  6. view (3f+3f+2)的时候,又回到replica 0,其又回到步骤6 ...

上面的例子可能叙述得比较复杂,简单来说就是:在每个轮次中,前f+1view中有且只有leader对应得replica锁定到当前view上,后2fview中所有replica都无法更新锁定的view。这两点又是分别通过以下的思路来实现的: 1. 前f+1view中,在leader收集QC的时候,只收集到自身的QC和后2freplicaQC,导致这2f+1QC中的最大值是leader自身的QCleader基于该QC发起新的proposal;对于发起的proposal,前f+1replica中除了自身之外都不会投票;2freplica中所有拜占庭节点一开始也不投票,导致leader收集不到足够的投票,触发其他诚实节点超时切换到下一个view然后,拜占庭节点进行投票,使得leader收集到足够多的投票,生成更新的QC,该QC比前f+1replica中的其他replica中的QC都要大。 2. 在后2fview中,在leader收集QC的时候,除了收集到的后2freplica中发来的QC,也会收集到前f+1replica中的某一个QC,我们假设其只能收集到最低的那个QCleader基于该QC发起新的proposal;对于发起的proposal,前f+1replica只有一个会进行投票;2freplica中所哟有拜占庭节点一直不投票,导致leader一直收集不到足够多的投票,从而无法生成更新的QC,其他诚实节点也被触发超时切换到下一个view

这里需要引入Single-modal类共识有效运行的定义:只有发生了两连跳才算是真正完成了一次有效(为什么要求这一点,我们在后面的博客进行详细解释,这里先记住这个结论)。也即:在view k,必须是基于view (k-1)中锁定的QC发起proposal

而上面举的例子显然无法完成任何共识,因为整个协议在运行过程中不存在两连跳。这个问题也被称为hidden lock问题。

2. 为什么等待\(\Delta\)可以解决Hidden Lock问题

造成hidden lock问题的根本原因是,一个leader在发起新的proposal之前并没有等待其他所有诚实节点发来的QC,从而从中选出最高的QC。也即:有些诚实节点中的QC被隐藏 (hidden)了。 反过来说,如果我们要求每个leader在发起新的proposal之前必须等待同步网络中的一个最大网络时延,使得其能接收到所有诚实节点发来的QC,那么在上面的例子中:replica 1中就可以基于replica 0中刚刚更新的QC发起proposal。该QC是网络中最高的QC,一定可以得到其他所有诚实节点的投票,从而在replica 1中生成QC。这样,就保证了replica 1replica 0中分别生成的两个QC是两连跳的。

C. 为什么HotStuff不需要等待\(\Delta\)

HotStuff增加了一个轮次。其中第一个轮次后的QC称为prepareQC,第二个轮次后的QC称为lockedQCLeader在发起新的proposal时将基于收集到的最高的prepareQC进行,而replica投票时将基于proposal中携带的最高prepareQC和本地保存的lockedQC作比较。 对于任意一个lockedQC而言,其至少在2f+1个节点中保存有对应的prepareQC,这进一步保证了leader在发起新的proposal时至少收集到一个该prepareQC。 因此,对于所有节点中保存的最高的lockedQCleader一定会接收到其对应的prepareQC,从而基于该prepareQC发起proposal,也一定会被所有诚实节点投票。

总结来说,HotStuff通过增加一个阶段,保证了leader一定可以搜集到最高lockedQC对应的prepareQC。 因而,HotStuff不需要等待\(\Delta\)

IV. 一个问题:replica接收到旧view中的消息如何处理

在III.B.1小节中,我们举了个例子来说明hidden lock问题。其中,我们假设:当replica切换到下一个view后,即使其再接收到上一个view中的QC,也不会更新自己本地锁定的QC。这样的假设源于我们对于HotStuff论文中伪代码的解读,而且可以简化III.B.1小节中的例子。 但笔者在在思考另外一种假设的合理性:replica接收并认可上一个view中的QC貌似也是合情合理的,而且可以让协议更加鲁棒。在本节,我们就对两种假设进行更深入的讨论。

A. 假设一:认为旧view中的消息是无效的

这一种假设在HotStuff论文中的Algorithm 2 (Basic HotStuff)和Algorithm 3(Chained HotStuff)都是明确指明的,相应的伪代码分别截图如下: 这三处伪代码中,replica在收到来自leader的消息后,都会调用MATCHINGQCMATCHINGMSG对消息进行检查,其中就包括消息中包含的viewNumber是否等于curView。也即:当replica已经切换到下一个view后,即使其再接收到上一个view中的消息,也会直接丢弃。

但另一方面,在HotStuff论文的Algorithm 4Event-driven HotStuff)中,并没有对接收到的消息的viewNumber进行明确检查。这一点需要阅读HotStuff源码后进行进一步确认。

B. 假设二:认为旧view中的消息有效的

Tendermint论文对是否进行viewNumber检查也没有进行明确说明。我们暂且不考虑Tendermint以及HotStuffAlgorithm 4的设计,来推演一下:如果认可旧view中的消息,Single-modal类的二阶段共识会存在什么问题。

基于该假设,我们需要对III.B.1小节中构造的例子进行更新,更新后的例子如下:

  1. 假设一开始所有replica都是锁定在一个view (vold)的QC上 接下来,在view 0的时候,replica 0leader,其首先收集2f个其他replica发来的QC(加上自身的QC一共2f+1个),这2f+1QC中的最大值是voldQCreplica 0基于该QC发起了proposal;其他replica对该proposal纷纷进行投票;replica 0收集到2f+1个投票后组成QC,并在本地锁定了v0;此时,由于网络原因发生view的切换,使得除了replica 0之外其他的节点都没有收到v0对应的QC
  2. view 1的时候,replica 1leader,其首先收集2f个其他replica发来的QC(加上自身的QC一共2f+1个),这2f+1QC中的最大值是voldQC(也即其未收到replica 0发来的QC);replica 1基于该QC发起了proposal;除了replica 0之外的其他replica对该proposal纷纷进行投票;replica 1收集到2f+1个投票后组成QC,并在本地锁定了v1;此时,由于网络原因发生view的切换,使得除了replica 1之外其他的节点都没有收到v1对应的QC
  3. 同理,在view 2的时候,只有replica 2在本地锁定了v2对应的QC,其他replica都未收到; ...
  4. view f的时候,只有replica f在本地锁定了vf对应的QC,其他replica都未收到;
  5. view (f+1)的时候,replica (f+1)发起proposal,但replica 0 ~ replica f都不会进行投票。这一轮的view不会生成任何QC ...
  6. view (3f)的时候,replica (3f)发起proposal,但replica 0 ~ replica f都不会进行投票。这一轮的view不会生成任何QC

-----------以上是异步网络环境,接下来进入同步网络环境。在该网络环境中,除了拜占庭节点,所有的节点之间的消息在\(\Delta\)时间内都能正确送达------------

  1. view (3f+1)的时候,又回到replica 0,其首先收集了2f个其他replica发来的QC(加上自身的QC一共2f+1个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1QC中的最大值是replica 0自身的QC,也即锁定在v0上的QC(这种情况下,replica 0收到的前2fQC中没有来自replica 1~replica f节点的)。于是,其基于v0发起新的proposal,但replica 1 ~ replica f都不会投票,replica (f+1)~ replica (3f)中的拜占庭节点也全不投票(假设其中有k个拜占庭节点),导致replica 0只能收到(2f+1-k)个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+2并将一个旧的QC(低于3f+1)发送给下一任leader (replica 1)
  2. view (3f+2)的时候,又回到replica 1,其首先收集了2f个其他replica发来的QC(加上自身的QC一共2f+1个),这2f+1QC中的最大值是replica f中的QC,也即锁定在vf上的QC。于是,其基于vf发起新的proposal。与此同时,拜占庭节点向replica 0发送view (3f+1)的投票,使得replica 0又收到了针对view (3f+1)的足够多的投票,组建出v (3f+1)QC,并进一步将这个QC广播给其他节点。当诚实的replicareplica 0 ~ replica 2f)接收到replica 1proposal后,除了replica 0,其他的replica都会进行投票(尚未收到v (3f+1)QC),所有的拜占庭节点(replica 2f+1~ replica 3f)也都不投票。导致,replica 1只能收到2f个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+3。此时,所有诚实节点都接收到了v (3f+1)QC,因而在进行view切换时,将v (3f+1)QC发送给下一任leader (replica 2)。
  3. view (3f+3)的时候,又回到replica 2,其首先收集了2f个其他replica发来的QC(加上自身的QC一共2f+1个),这2f+1QC中的最大值是锁定在v (3f+1)上的QC。于是,其基于v (3f+1)发起新的proposal。与此同时,拜占庭节点向replica 1发送view (3f+2)的投票,使得replica 1又收到了针对view (3f+2)的足够多的投票,组建出v (3f+2)QC,并进一步将这个QC广播给其他节点。当诚实的replicareplica 0 ~ replica 2f)接收到replica 2proposal后,除了replica 1,其他的replica都会进行投票(尚未收到v (3f+2)QC),所有的拜占庭节点(replica 2f+1~replica 3f)也都不投票。导致,replica 2只能收到2f个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+4。此时,所有诚实节点都接收到了v (3f+2)QC,因而在进行view切换时,将v (3f+2)QC发送给下一任leader (replica 3)。 ...
  4. 同理,在view (3f+2f+1)的时候,又回到了replica (2f),其基于 v (3f+2f-1)QC发起新的proposal;与此同时,拜占庭节点对view (3f+2f)进行投票,使得replica (2f-1)组建成v (3f+2f)QC,并广播给其他节点。其他节点接收到replica (2f)proposal后,replica 0~replica (2f-2)会进行投票,replica (2f-1)和所有拜占庭节点都不投票,导致replica (2f)只能收到2f个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+2f+2。此时,所有诚实节点都接收到了v (3f+2f)QC,因而在进行view切换时,将v (3f+2f)QC发送给下一任leader (replica 2f+1)。
  5. replica (2f+1) ~ replica (3f)都是拜占庭节点,直接跳过view (3f+2f+2)~view( 3f+3f+1)
  6. view (3f+3f+2)的时候,又回到replica 0,其基于 v (3f+2f)QC发起新的proposal;与此同时,拜占庭节点对view (3f+2f+1)进行投票,使得replica (2f)组建成v (3f+2f+1)QC,并广播给其他节点。其他节点接收到replica 0proposal后,replica 1~replica (2f-1)会进行投票,replica (2f)和所有拜占庭节点都不投票,导致replica 0只能收到2f个投票(包含自身的),无法组成QC。其他诚实节点由于无法及时收到QCview切换到 3f+3f+3。此时,所有诚实节点都接收到了v (3f+2f+1)QC,因而在进行view切换时,将v (3f+2f+1)QC发送给下一任leader (replica 1)。 ...

以上的例子同样暴露了一个问题,就是不存在两连跳的QC,举例来说:v (3f+3)QC是基于v (3f+1)QC,而v (3f+2f+1)QC是基于v (3f+2f-1)QC。这使得共识无法有效运行,失去了liveness

更严重的是,这是比hidden lock更为棘手的一个问题,因为这个问题是没法通过等待\(\Delta\)来解决的。可能,这也是为什么HotStuff论文的Algorithm 2Algorithm 3需要对消息的viewNumber进行检查的原因。