在HotStuff
的PODC
版本论文和Arxiv
版本论文中,多次将不同共识协议的活性(liveness
)和响应度(responsiveness
)进行比较。此外,一些博客和其他相关论文中也有关于liveness
问题和responsiveness
问题的叙述。其中涉及到两点叙述:
Tendermint
中在leader
切换的时候需要等待一个最大的网络延迟\(\Delta\),导致Tendermint
无法做到optimistic responsiveness
- 如果
Tendermint
在leader
切换的时候不等待\(\Delta\),将导致Tendermint
中无法进行有效共识,从而破坏协议的liveness
。
但笔者在看这两点叙述的时候,总感觉论文作者和博主没有将问题讲透,看得云里雾里的。可能大佬们觉得这两点叙述很容易理解,甚至是一些一点就该通的常识。
为了真正弄懂以上两点叙述,笔者查阅了大量资料,并将自己的一些理解整理在这篇博客中。这篇博客需要读者对共识算法已经有了一定的理解。
I.两/三阶段共识中的锁定机制
我们先从共识协议中的“锁定机制”开始说起。 无论是PBFT
、Tendermint
还是HotStuff
,都在共识过程中隐式或显示地引入了锁定机制。其中,PBFT
论文中没有显示定义这种锁定机制,但每个replica
在本地prepared
之后,就可以认为是在锁定了。 PBFT
和Tendermint
/HotStuff
中锁定的作用是不同的:
PBFT
中的锁定机制只是为了防止一个诚实replica
同时对两个矛盾的proposal
投票,而不会检查新的proposal
是否基于已锁定的proposal
。这样的锁定机制也就不对已锁定的proposal
做出任何承诺,即:在发生leader
切换的时候,上一个view
中锁定的proposal
在本轮中可以被轻易推翻。- 相反,
Tendermint
/HotStuff
中的锁定机制除了防止一个诚实replica
对两个矛盾proposal
投票外,还会进一步检查新的proposal
是否基于已锁定的proposal
。这样的锁定机制对于已锁定的proposal
做出了一定的承诺,即:在上一个view
中已经被锁定的proposal
,除非发生特殊情况(replica
接收到的proposal
基于更高的QC
),在新的view
中不会被推翻。
这两种锁定机制的不同源于他们对于leader
赋予的可信度是不同的。
II.共识协议中Leader可信度的不同
PBFT
中leader
的可信度是很大的(其作恶空间很小),这是因为leader
在进行View
的切换时,其在发出的New-View
消息中携带了充分的证明性数据,其他replica
有理由相信leader
在New-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
都只会对基于自己的QC
的proposal
投票。 我们考虑如下一个例子:
- 假设在
view 0
的时候,replica 0
是leader
,且只有其收到了QC
并在本地锁定了v0
,此时由于网络原因发生了view
的切换.- 在
view 1
的时候,新的leader
(replica 1
)由于没有在v0
锁定,于是基于更早的一个view
(假设是vold
)发起了proposal
;此时replica 0
是不会进行投票的,因为这个proposal
不是基于v0
的,但其他的节点还是可能会投票,当replica 1
收到了足够多的投票组成QC
后,其在本地锁定v1
;此时也由于网络原因发生了view
的切换。- 在
view 2
的时候,同理,replica 2
锁定了v2
。 ...- 在
view f
的时候,replica f
锁定了vf
。- 此时,
replica (2f+1)
~replica (3f)
下线了,只剩下replica 0
~replica 2f
。(这也是满足系统假设的,有超过2f+1
个正确节点,并且我们假设接下来是同步网络)- 但接下来,协议就会卡住。
- 在新一轮次(所有
replica
轮一遍称为一个轮次)的view
中,replica 0
发起的新proposal
,replica 1
~replica f
都不认,因为不是基于他们锁定的view
发起的,从而无法收集到新的QC
;- 同理,
replica 1
发起的新proposal
,replica 0
,replica 2
~replica f
都不认,因为不是基于他们锁定的view
发起的,从而无法收集到新的QC
; ...
上面这个例子在第4步之后,replica 0
~ replia f
都不会给除了自己之外的其他节点的proposal
投票。在每个view
中leader
无法都无法收集到2f+1
个投票,也无法生成/锁定新的QC
。 因此,整个协议就卡住了。
也就是说,在没有规则2的情况下,Single-modal
类共识会卡住,从而失去活性。
相反,当引入规则2后,我们看看上面的例子会怎么变化:
- 假设在
view 0
的时候,replica 0
是leader
,且只有其收到了QC
并在本地锁定了v0
,此时由于网络原因发生了view
的切换.- 在
view 1
的时候,新的leader
(replica 1
)由于没有在v0锁定,于是基于更早的一个view
(假设是vold
)发起了proposal
;此时replica 0
是不会进行投票的,因为这个proposal
不是基于v0
的,但其他的节点还是可能会投票,当replica 1
收到了足够多的投票组成QC
后,其在本地锁定v1
;此时也由于网络原因发生了view
的切换。- 在
view 2
的时候,同理,replica 2
锁定了v2
。 ...- 在
view f
的时候,replica f
锁定了vf
。- 此时,
replica (2f+1)
~replica (3f)
下线了,只剩下replica 0
~replica 2f
。(这也是满足系统假设的,有超过2f+1
个正确节点,并且我们假设接下来是同步网络)---------- 上面和前一个例子一样,下面是规则2引入后的不同
- 在新一轮的
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
问题。为了解释该问题,我们也举个例子如下。该例子中一开始是异步网络,后面切换到同步网络。
- 假设一开始所有
replica
都是锁定在一个view
(vold
)的QC
上。 接下来,在view 0
的时候,replica 0
是leader
,其首先收集2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),这2f+1
个QC
中的最大值是vold
的QC
;replica 0
基于该QC
发起了proposal
;其他replica
对该proposal
纷纷进行投票;replica 0
收集到2f+1
个投票后组成QC
,并在本地锁定了v0
;此时,由于网络原因发生view
的切换,使得除了replica 0
之外其他的节点都没有收到v0
对应的QC
;- 在
view 1
的时候,replica 1
是leader
,其首先收集2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),这2f+1
个QC
中的最大值是vold
的QC
(也即其未收到replica 0
发来的QC
);replica 1
基于该QC
发起了proposal
;除了replica 0
之外的其他replica
对该proposal
纷纷进行投票;replica 1
收集到2f+1
个投票后组成QC
,并在本地锁定了v1
;此时,由于网络原因发生view
的切换,使得除了replica 1
之外其他的节点都没有收到v1
对应的QC
;- 同理,在
view 2
的时候,只有replica 2
在本地锁定了v2
对应的QC
,其他replica
都未收到; ...- 在
view f
的时候,只有replica f
在本地锁定了vf
对应的QC
,其他replica
都未收到;- 在
view (f+1)
的时候,replica (f+1)
发起proposal
,但replica 0
~replica f
都不会进行投票。这一轮的view
不会生成任何QC
...- 在
view (3f)
的时候,replica (3f)
发起proposal
,但replica 0
~replica f
都不会进行投票。这一轮的view
不会生成任何QC
-----------以上是异步网络环境,接下来进入同步网络环境。在该网络环境中,除了拜占庭节点,所有的节点之间的消息在\(\Delta\)时间内都能正确送达------------
- 在
view (3f+1)
的时候,又回到replica 0
,其首先收集了2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1
个QC
中的最大值是replica 0
自身的QC
,也即锁定在v0
上的QC
(这种情况下,replica 0
收到的前2f
个QC
中没有来自replica 1
~replica f
节点的)。于是,其基于v0
发起新的proposal
,但replica 1
~replica f
都不会投票,replica (f+1)
~replica (3f)
中的拜占庭节点也全不投票(假设其中有k个拜占庭节点),导致replica 0
只能收到(2f+1-k)
个投票(包含自身的),无法组成QC
。其他诚实节点由于无法及时收到QC
将view
切换到3f+2
。此时,拜占庭节点进行投票,使得replica 0
又收到了足够多的投票,组建出QC
。于是,replica 0
锁定了v (3f+1)
。但其他节点已经切换到view (3f+2)
了,即使接收到replica 0
发来的QC
,也不会更新自己本地锁定的QC
了。- 在
view (3f+2)
的时候,又回到replica 1
,其首先收集了2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1
个QC
中的最大值是replica 1
自身的QC
,也即锁定在v1
上的QC
。于是,其基于v1
发起新的proposal
,但replica 0
和replica2
~replica f
都不会投票,replica (f+1)
~replica (3f)
中的拜占庭节点也全不投票(假设其中有k
个拜占庭节点),导致replica 1
只能收到(2f+1-k)
个投票(包含自身的),无法组成QC
。其他诚实节点由于无法及时收到QC
将view
切换到3f+3
。此时,拜占庭节点进行投票,使得replica 1
又收到了足够多的投票,组建出QC
。于是,replica 1
锁定了v (3f+2)
。 ...- 在
view (3f+f+1)
的时候,又回到replica f
,同理,只有replica f
锁定了v (3f+f+1)
。- 在
view (3f+f+2)
的时候,又回到replica (f+1)
,其首先收集了2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1
个QC
中的最大值是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
。其他诚实节点由于无法及时收到QC
将view
切换到3f+f+3
。 ...- 在
view (3f+3f+1)
的时候,又回到replica (3f)
,其同样无法组成QC
。其他诚实节点由于无法及时收到QC
将view
切换到3f+3f+2
。- 在
view (3f+3f+2)
的时候,又回到replica 0
,其又回到步骤6 ...
上面的例子可能叙述得比较复杂,简单来说就是:在每个轮次中,前f+1
个view
中有且只有leader
对应得replica
锁定到当前view
上,后2f
个view
中所有replica
都无法更新锁定的view
。这两点又是分别通过以下的思路来实现的: 1. 前f+1
个view
中,在leader
收集QC
的时候,只收集到自身的QC
和后2f
个replica
的QC
,导致这2f+1
个QC
中的最大值是leader
自身的QC
,leader
基于该QC
发起新的proposal
;对于发起的proposal
,前f+1
个replica
中除了自身之外都不会投票;后2f
个replica
中所有拜占庭节点一开始也不投票,导致leader
收集不到足够的投票,触发其他诚实节点超时切换到下一个view
;然后,拜占庭节点进行投票,使得leader
收集到足够多的投票,生成更新的QC
,该QC
比前f+1
个replica
中的其他replica
中的QC
都要大。 2. 在后2f
个view
中,在leader
收集QC
的时候,除了收集到的后2f
个replica
中发来的QC
,也会收集到前f+1
个replica
中的某一个QC
,我们假设其只能收集到最低的那个QC
;leader
基于该QC
发起新的proposal
;对于发起的proposal
,前f+1
个replica
只有一个会进行投票;后2f
个replica
中所哟有拜占庭节点一直不投票,导致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 1
和replica 0
中分别生成的两个QC
是两连跳的。
C. 为什么HotStuff
不需要等待\(\Delta\)
HotStuff
增加了一个轮次。其中第一个轮次后的QC
称为prepareQC
,第二个轮次后的QC
称为lockedQC
。 Leader
在发起新的proposal
时将基于收集到的最高的prepareQC
进行,而replica
投票时将基于proposal
中携带的最高prepareQC
和本地保存的lockedQC
作比较。 对于任意一个lockedQC
而言,其至少在2f+1
个节点中保存有对应的prepareQC
,这进一步保证了leader
在发起新的proposal
时至少收集到一个该prepareQC
。 因此,对于所有节点中保存的最高的lockedQC
,leader
一定会接收到其对应的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
的消息后,都会调用MATCHINGQC
或MATCHINGMSG
对消息进行检查,其中就包括消息中包含的viewNumber
是否等于curView
。也即:当replica
已经切换到下一个view
后,即使其再接收到上一个view
中的消息,也会直接丢弃。
但另一方面,在HotStuff
论文的Algorithm 4
(Event-driven HotStuff
)中,并没有对接收到的消息的viewNumber
进行明确检查。这一点需要阅读HotStuff
源码后进行进一步确认。
B. 假设二:认为旧view
中的消息有效的
Tendermint
论文对是否进行viewNumber
检查也没有进行明确说明。我们暂且不考虑Tendermint
以及HotStuff
中Algorithm 4
的设计,来推演一下:如果认可旧view
中的消息,Single-modal
类的二阶段共识会存在什么问题。
基于该假设,我们需要对III.B.1小节中构造的例子进行更新,更新后的例子如下:
- 假设一开始所有
replica
都是锁定在一个view
(vold
)的QC上 接下来,在view 0
的时候,replica 0
是leader
,其首先收集2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),这2f+1
个QC
中的最大值是vold
的QC
;replica 0
基于该QC
发起了proposal
;其他replica
对该proposal
纷纷进行投票;replica 0
收集到2f+1
个投票后组成QC
,并在本地锁定了v0
;此时,由于网络原因发生view
的切换,使得除了replica 0
之外其他的节点都没有收到v0
对应的QC
;- 在
view 1
的时候,replica 1
是leader
,其首先收集2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),这2f+1
个QC
中的最大值是vold
的QC
(也即其未收到replica 0
发来的QC
);replica 1
基于该QC
发起了proposal
;除了replica 0
之外的其他replica
对该proposal
纷纷进行投票;replica 1
收集到2f+1
个投票后组成QC
,并在本地锁定了v1
;此时,由于网络原因发生view
的切换,使得除了replica 1
之外其他的节点都没有收到v1
对应的QC
;- 同理,在
view 2
的时候,只有replica 2
在本地锁定了v2
对应的QC
,其他replica
都未收到; ...- 在
view f
的时候,只有replica f
在本地锁定了vf
对应的QC
,其他replica
都未收到;- 在
view (f+1)
的时候,replica (f+1)
发起proposal
,但replica 0
~replica f
都不会进行投票。这一轮的view
不会生成任何QC
...- 在
view (3f)
的时候,replica (3f)
发起proposal
,但replica 0
~replica f
都不会进行投票。这一轮的view
不会生成任何QC
-----------以上是异步网络环境,接下来进入同步网络环境。在该网络环境中,除了拜占庭节点,所有的节点之间的消息在\(\Delta\)时间内都能正确送达------------
- 在
view (3f+1)
的时候,又回到replica 0
,其首先收集了2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),但巧合(也可能是恶意节点对网络的操纵)的是这2f+1
个QC
中的最大值是replica 0
自身的QC
,也即锁定在v0
上的QC
(这种情况下,replica 0
收到的前2f
个QC
中没有来自replica 1
~replica f
节点的)。于是,其基于v0
发起新的proposal
,但replica 1
~replica f
都不会投票,replica (f+1)
~replica (3f)
中的拜占庭节点也全不投票(假设其中有k
个拜占庭节点),导致replica 0
只能收到(2f+1-k)
个投票(包含自身的),无法组成QC
。其他诚实节点由于无法及时收到QC
将view
切换到3f+2
,并将一个旧的QC
(低于3f+1
)发送给下一任leader
(replica 1
)。- 在
view (3f+2)
的时候,又回到replica 1
,其首先收集了2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),这2f+1
个QC
中的最大值是replica f
中的QC
,也即锁定在vf
上的QC
。于是,其基于vf
发起新的proposal
。与此同时,拜占庭节点向replica 0
发送view (3f+1)
的投票,使得replica 0
又收到了针对view (3f+1)
的足够多的投票,组建出v (3f+1)
的QC
,并进一步将这个QC
广播给其他节点。当诚实的replica
(replica 0
~replica 2f
)接收到replica 1
的proposal
后,除了replica 0
,其他的replica
都会进行投票(尚未收到v (3f+1)
的QC
),所有的拜占庭节点(replica 2f+1
~replica 3f
)也都不投票。导致,replica 1
只能收到2f
个投票(包含自身的),无法组成QC
。其他诚实节点由于无法及时收到QC
将view
切换到3f+3
。此时,所有诚实节点都接收到了v (3f+1)
的QC
,因而在进行view
切换时,将v (3f+1)
的QC
发送给下一任leader
(replica 2
)。- 在
view (3f+3)
的时候,又回到replica 2
,其首先收集了2f
个其他replica
发来的QC
(加上自身的QC
一共2f+1
个),这2f+1
个QC
中的最大值是锁定在v (3f+1)
上的QC
。于是,其基于v (3f+1)
发起新的proposal
。与此同时,拜占庭节点向replica 1
发送view (3f+2)
的投票,使得replica 1
又收到了针对view (3f+2)
的足够多的投票,组建出v (3f+2)
的QC
,并进一步将这个QC
广播给其他节点。当诚实的replica
(replica 0
~replica 2f
)接收到replica 2
的proposal
后,除了replica 1,其他的replica都会进行投票(尚未收到v (3f+2)
的QC
),所有的拜占庭节点(replica 2f+1
~replica 3f
)也都不投票。导致,replica 2
只能收到2f
个投票(包含自身的),无法组成QC
。其他诚实节点由于无法及时收到QC
将view
切换到3f+4
。此时,所有诚实节点都接收到了v (3f+2)
的QC
,因而在进行view
切换时,将v (3f+2)
的QC
发送给下一任leader
(replica 3
)。 ...- 同理,在
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
。其他诚实节点由于无法及时收到QC
将view
切换到3f+2f+2
。此时,所有诚实节点都接收到了v (3f+2f)
的QC
,因而在进行view
切换时,将v (3f+2f)
的QC
发送给下一任leader
(replica 2f+1
)。replica (2f+1)
~replica (3f)
都是拜占庭节点,直接跳过view (3f+2f+2)
~view( 3f+3f+1)
- 在
view (3f+3f+2)
的时候,又回到replica 0
,其基于v (3f+2f)
的QC
发起新的proposal
;与此同时,拜占庭节点对view (3f+2f+1)
进行投票,使得replica (2f)
组建成v (3f+2f+1)
的QC
,并广播给其他节点。其他节点接收到replica 0
的proposal
后,replica 1
~replica (2f-1)
会进行投票,replica (2f)
和所有拜占庭节点都不投票,导致replica 0
只能收到2f
个投票(包含自身的),无法组成QC
。其他诚实节点由于无法及时收到QC
将view
切换到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 2
和Algorithm 3
需要对消息的viewNumber
进行检查的原因。