【论文翻译】HotStuff:BFT Consensus in the Lens of Blockchain – One-Chain and Two-Chain BFT Protocols

7. One-Chain/Two-Chain的BFT协议

在本节中,我们研究了四个BFT副本协议,这些协议跨越了拜占庭式容错研究的四十余年,并将它们植入类似于Chained HotStuff的基于链的框架中。

图3提供了我们考虑的包括HotStuff在内的五个协议的提交规则的鸟瞰图。

简而言之,DLS的提交规则是单链(One-Chain)的,允许节点仅由其自己的领导者提交。 PBFT、Tendermint和Casper中的提交规则几乎相同,由双链(Two-Chain)组成。 他们在介绍活动的机制上有所不同,PBFT具有二次方规模的leader“证明复杂度”(非线性),Tendermint和Casper在每个leader提议之前引入了强制性性的Δ延迟(非乐观响应性)。 HotStuff使用三链(Three-Chain)规则,并具有无延迟的线性leader协议。

图3 不同BFT协议的提交规则

In this section, we examine four BFT replication protocols spanning four decades of research in Byzantine fault tolernace, casting them into a chained framework similar to Chained HotStuff.

Figure 3 provides a birds-eye view of the commit rules of five protocols we consider, including HotStuff.

In a nutshell, the commit rule in DLS [25] is One-Chain, allowing a node to be committed only by its own leader. The commit rules in PBFT [20], Tendermint [15, 16] and Casper [17] are almost identical, and consist of Two-Chains. They differ in the mechanisms they introduce for liveness, PBFT has leader “proofs” of quadratic size (no Linearity), Tendermint and Casper introduce a mandatory ∆ delay before each leader proposal (no Optimistic Responsiveness). HotStuff uses a Three-Chain rule, and has a linear leader protocol without delay.

7.1 DLS

最简单的提交规则是单链(One-Chain)。服从该规则有第一个已知的异步拜占庭共识解决方案Dwork,Lynch和Stockmeyer(DLS)模型,如图3(a)所示。副本将锁定在其投票的最高节点上的DLS中。

不幸的是,如果在某个高度处,领导者模棱两可,此规则将很容易导致僵局,并且在该高度处的两个有冲突的提议被锁定在了两个正确的副本中。除非有2f +1表示他们没有投票赞成锁定的值,否则放弃任何一个锁定都是不安全的。

实际上,在DLS中,只有每个高度的leader本身都可以通过单链提交规则来达成提交决定。因此,如果领导者模棱两可,只会受到伤害。如果2f +1个副本没有投票赞成该副本,或者存在冲突的提议(由领导者签名),则副本可以放弃该锁。出现在DLS中每个高度末端的解锁协议非常复杂且昂贵。在没有故障且网络及时的最佳情况下,只有高空领导者可以决定这一事实,DLS每次决策都需要n次领导者轮换和O(n^4)条消息传输。虽然DLS在演示安全的异步协议方面开辟了新天地,但DLS并非设计为实用的解决方案。

The simplest commit rule is a One-Chain. Modeled after Dwork, Lynch, and Stockmeyer (DLS), the first known asynchronous Byzantine Consensus solution, this rule is depicted in Figure 3(a). A replica becomes locked in DLS on the highest node it voted for.

Unfortunately, this rule would easily lead to a deadlock if at some height, a leader equivocates, and two correct replicas became locked on the conflicting proposals at that height. Relinquishing either lock is unsafe unless there are 2f + 1 that indicate they did not vote for the locked value.

Indeed, in DLS only the leader of each height can itself reach a commit decision by the One-Chain commit rule. Thus, only the leader itself is harmed if it has equivocated. Replicas can relinquish a lock either if 2f +1 replicas did not vote for it, or if there are conflicting proposals (signed by the leader). The unlocking protocol occurring at the end of each height in DLS turns out to be fairly complex and expensive. Together with the fact that only the leader for a height can decide, in the best scenario where no fault occurs and the network is timely, DLS requires n leader rotations, and O(n^4) message transmissions, per single decision. While it broke new ground in demonstrating a safe asynchronous protocol, DLS was not designed as a practical solution.

7.2 PBFT

以PBFT为模型,更实际的方法是使用两链提交规则,请参见图3(b)。当副本为构成单链的节点投票时,它就锁定在该节点上。完全不可能在同一高度上冲突单链,因为每个链都有一个QC,因此避免了DLS的死锁情况。

但是,如果一个副本具有比其他副本更高的锁定,则即使领导者从n-f个副本中收集信息,领导者也可能对此一无所知。这可能会导致领导者纯粹由于调度而无法做出最终决定。为了获得“解粘”效果,PBFT会通过携带由2f +1个副本的最高单链组成的证明来解锁所有副本。如下所述,该证明相当复杂。

原始的PBFT已开源[20]并在多项后续工作中采用[13,34],领导者证明包含从n-f个副本收集的一组消息,报告每个成员投票支持的最高单链。每个单链包含一个QC,因此总通信成本为O(n^3)。利用[45,18],SBFT [30]中的签名组合方法,可以通过将每个QC设置为单个值,将成本降低到O(n^2)

在[21]中的PBFT变体中,领导者证明包含从仲裁群体中收集的最高领导者一次链。它还包括每个仲裁成员的一个已签名的值,证明它没有投票赞成更高的单链。广播该证明会导致通信复杂度O(n^2)。请注意,尽管QC上的签名可以组合为一个值,但是由于来自仲裁的不同成员的消息可能具有不同的值,因此作为一个整体的证明不能减少到恒定的大小。

在这两种变体中,正确的副本都可以解锁,即使它的单链比领导者的证明更高。因此,正确的领导者可以在同步期间强制其提议被接受,从而确保活动的活力。费用是每次更换领导者的二次通信费用。

Modeled after PBFT, a more practical appraoch uses a Two-Chain commit rule, see Figure 3(b). When a replica votes for a node that forms a One-Chain, it becomes locked on it. Conflicting One-Chains at the same height are simply not possible, as each has a QC, hence the deadlock situation of DLS is avoided.

However, if one replica holds a higher lock than others, a leader may not know about it even if it collects information from n − f replicas. This could prevent leaders from reaching decisions ad infinitum, purely due to scheduling. To get “unstuck”, the PBFT unlocks all replicas by carrying a proof consisting of the highest One-Chain’s by 2f + 1 replicas. This proof is quite involved, as explained below.

The original PBFT, which has been open-sourced [20] and adopted in several follow up works [13, 34], a leader proof contains a set of messages collected from n − f replicas reporting the highest One-Chain each member voted for. Each One-Chain contains a QC, hence the total communication cost is O(n^3). Harnessing signature combining methods from [45, 18], SBFT [30] reduces this cost to O(n^2) by turning each QC to a single value.

In the PBFT variant in [21], a leader proof contains the highest One-Chain the leader collected from the quorum only once. It also includes one signed value from each member of the quorum, proving that it did not vote for a higher One-Chain. Broadcasting this proof incurs communication complexity O(n^2). Note that whereas the signatures on a QC may be combined into a single value, the proof as a whole cannot be reduced to constant size because messages from different members of the quorum may have different values.

In both variants, a correct replica unlocks even it has a higher One-Chain than the leader’s proof. Thus, a correct leader can force its proposal to be accepted during period of synchrony, and liveness is guaranteed. The cost is quadratic communication per leader replacement.

7.3 Tendermint 和 Casper

Tendermint具有与PBFT相同的“双链”提交规则,而Casper具有“双链”规则,其中叶子不需要具有控制父节点的QC。也就是说,在Casper中,图3(c,d)分别描述了Tendermint和Casper的提交规则。

在这两种方法中,领导者都只是简单地发送其所知道的最高单链及其提议。如果副本从领导者接收到更高的副本,它将解锁单链。

但是,由于正确的副本可能无法投票给领导者的节点,因此要保证进度,新领导者必须通过等待最大的网络延迟来获得最高的单链。否则,如果领导者仅等待第一个n-f条消息开始新的高度,则无法保证进度。领导者的延迟在Tendermint和Casper中都是固有的,以便提供生气。

这个简单的领导者协议体现了HotStu ff借鉴的领导者协议的通信复杂度的线性飞跃。如上所述,可以使用阈值签名将QC捕获为单个值,因此领导者可以收集和传播具有线性通信复杂性的最高单链。但是,至关重要的是,由于额外的QC步骤,HotStu ff不需要领导者等待最大的网络延迟。

Tendermint has a Two-Chain commit rule identical to PBFT, and Casper has a Two-Chain rule in which the leaf does not need to have a QC to direct parent. That is, in Casper, Figure 3(c,d) depicts the commit rules for Tendermint and Casper, respectively.

In both methods, a leader simply sends the highest One-Chain it knows along with its proposal. A replica unlocks a One-Chain if it receives from the leader a higher one.

However, because correct replicas may not vote for a leader’s node, to guarantee progress a new leader must obtain the highest One-Chain by waiting the maximal network delay. Otherwise, if leaders only wait for the first n − f messages to start a new height, there is no progress guarantee. Leader delays are inherent both in Tendermint and in Casper, in order to provide liveness.

This simple leader protocol embodies a linear leap in the communication complexity of the leader protocol, which HotStuff borrows from. As already mentioned above, a QC could be captured in a single value using threshold signatures, hence a leader can collect and disseminate the highest One-Chain with linear communication complexity. However, crucially, due to the extra QC step, HotStuff does not require the leader to wait the maximal network delay.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据