【论文翻译】HotStuff:BFT Consensus in the Lens of Blockchain – Related work

这是《HotStuff:BFT Consensus in the Lens of Blockchain》论文翻译的第二篇,包含了论文的相关工作部分。


2. 相关工作

面对拜占庭失败,如何能够让节点达成共识,就是Lamport等研究人员提出的“拜占庭将军问题”。当然,所谓“拜占庭失败”这个概念也是他们创造出来的。该问题的第一个同步解决方案是由Pease等人提出的,经由Dolev和Strong等人的改进后,通信复杂度被降至O(n^3)级别,这个复杂度由Dolev和Resichuk等人进行了严格证明。Katz和Koo给出了一个基于leader节点的同步解决方案,具有期望常数轮的运行次数以及(n-1)/2的节点容错量。

Reaching consensus in face of Byzantine failures was formulated as the Byzantine Generals Problem by Lamport et al. [37], who also coined the term “Byzantine failures”. The first synchronous solution was given by Pease et al. [43], and later improved by Dolev and Strong [24]. The improved protocol has O(n^3) communication complexity, which was shown optimal by Dolev and Reischuk [23]. A leader-based synchronous protocol that uses randomness was given by Katz and Koo [32], showing an expected constant-round solution with (n-1)/2 resilience.

同时,在异步的场景下,Fischer等人证明了问题在单一故障下,是无法被确切地解决的。此外,Ben等人证明了任意异步解决方案拥有一个容错量(n-1)/3的界限。两种技巧被提出,用于规避上述的“无解性”。一个是由Ben提出的基于随机化的做法,使用持续随机的“虚拟硬币”翻转,直到恰好收敛到共识状态。后续的工作使用加密方法来共享一个不可预测的“硬币”,将复杂度降低到可预期的恒定回合,以及复杂度O(n^3)的通信开销。

Meanwhile, in the asynchronous settings, Fischer et al. [27] showed that the problem is unsolvable deterministically in asynchronous setting in face of a single failure. Furthermore, an (n-1)/3 resilience bound for any asynchronous solution was proven by Ben-Or [12]. Two approaches were devised to circumvent the impossibility. One relies on randomness, initially shown by Ben-Or [12], using independently random coin flips by processes until they happen to converge to consensus. Later works used cryptographic methods to share an unpredictable coin and drive complexities down to constant expected rounds, and O(n^3) communication [18].

第二种做法则依赖于部分同步,该方法最初由Bwork, Lynch和Stockmyer(DLS)提出,该协议在异步执行期间保证了安全性,并且在系统同步后,DLS保证系统可停机。一旦同步性被成功维护,DLS总计会产生O(n^4)的通信开销和后续单次决策的O(n)级别开销。

The second approach relies on partial synchrony, first shown by Dwork, Lynch, and Stockmeyer (DLS) [25]. This protocol preserves safety during asynchronous periods, and after the system becomes synchronous, DLS guarantees termination. Once synchrony is maintained, DLS incurs O(n^4) total communication and O(n) rounds per decision.

状态复制机(SMR)通过其核心的共识机制对客户端请求进行排序,已达到确定性的执行结果。这种SMR反复出现的需求,让Lamport设计出了Paxos协议,该协议提供了一个高效的流水线,在这个流水线上,一个稳定的leader节点可以在一轮通信中,使用线性的通信开销来广播决策。Castro和Liskov也实现了相似的需求,他们提供了一个高效的基于leader节点的拜占庭SMR协议,该协议名字叫做PBFT。在PBFT中,一个稳定的leader节点需要(n^2)的通信开销和两轮通信来完成一次决策广播,同时,倘若leader节点需要更替,则需要花费O(n^3)的通信开销。PBFT被部署在了多个系统中,其中就包括BFTSMaRt。Kotla等研究者则在PBFT基础上,引入了一个乐观的线性路径(optimistic linear path),并得到了Zyzzyva协议,该协议也被部署在了Upright、Byzcoin等系统中。乐观路径拥有线性的复杂度,但leader节点的更替仍然需要O(n^3)的时间复杂度。Abraham等人随机表示Zyzzyva协议存在安全漏洞,并提交了修正方案。改修正方案还有效地减小了协议自身的复杂度。Song等人提出了Bosco协议,这是一个建议的单阶段协议,在乐观路径上拥有较低的延迟。该协议要求5f+1个副本节点。SBFT协议引入了一个能够在O(n^2)通信复杂度夏,实现view-change的协议,并且支持一个稳定的leader节点实现乐观的线性、单轮决策。协议利用两种方法来降低通信复杂度,Reiter提出的一个机遇收集者(collector)的通信机制,以及Cachin等人提出的通过门限密码(threshold crptography)对协议投票以实现部分签名合并的算法。

State machine replication relies on consensus at its core to order client requests so that correct replicas execute them in this order. The recurring need for consensus in SMR led Lamport to devise Paxos [36], a protocol that operates an efficient pipeline in which a stable leader drives decisions with linear communication and one roundtrip. A similar emphasis led Castro and Liskov [20, 21] to develop an efficient leader-based Byzantine SMR protocol named PBFT, whose stable leader requires O(n^2) communication and two round-trips per decision, and the leader replacement protocol incurs O(n^3) communication. PBFT has been deployed in several systems, including BFTSMaRt [13]. Kotla et al. introduced an optimistic linear path into PBFT in a protocol named Zyzzyva [34], which was utilized in several systems, e.g., Upright [22] and Byzcoin [33]. The optimistic path has linear complexity, while the leader replacement protocol remains O(n 3 ). Abraham et al. [4] later exposed a safety violation in Zyzzyva, and presented fixes [5, 30]. On the other hand, to also reduce the complexity of the protocol itself, Song et al. proposed Bosco [49], a simple one-step protocol with low latency on the optimistic path, requiring 5f + 1 replicas. SBFT [30] introduces an O(n^2) communication view-change protocol that supports a stable leader protocol with optimistically linear, one round-trip decisions. It reduces the communication complexity by harnessing two methods: a collector based communication paradigm by Reiter [45], and signature combining via threshold cryptography on protocol votes by Cachin et al. [18].

Ramasamy等人提出了一个基于leader节点的随机化拜占庭SMR协议,同时,Miller等人则提出了一个无leader节点的变种,称之为HoneyBadgerBFT。他们的核心思想是,随机化的拜占庭解决方案应该由随机化的异步共识解决。他们最佳的通信复杂度为O(n^3),并通过批处理摊销成本。然而,最近,基于HotStuff文章中提到的思想,本文同时投递的另一篇PODC’19的论文将通信复杂度降低到了O(n^2)

A leader-based Byzantine SMR protocol that employs randomization was presented by Ramasamy et al. [44], and a leaderless variant named HoneyBadgerBFT was developed by Miller et al. [39]. At their core, these randomized Byzantine solutions employ randomized asynchronous Byzantine consensus, whose best known communication complexity was O(n^3) (see above), amortizing the cost via batching. However, most recently, based on the idea in this HotStuff paper, a parallel submission to PODC’19 [8] further improves the communication complexity to O(n^2).

比特币的核心模块是一个称之为中本共识(Nakamoto Consensus)的协议,这是一个异步协议,仅保证了概率意义上的安全性,并存在不确定性。该协议是在一个无许可限制的网络中运行的,也就是说参与者是未知的。通过工作量证明保证其摊销。正如上述所介绍的,最近的区块链解决方案都是以各种方式将工作量证明和经典的BFT协议混合设计的。这些混合的解决方案中,都需要解决轮流领导的问题,这为HotStuff提供了设计动机。

Bitcoin’s core is a protocol known as Nakamoto Consensus [40], a synchronous protocol with only probabilistic safety guarantee and no finality (see analysis in [28, 41, 6]). It operates in a permissionless model where participants are unknown, and resilience is kept via Proof-of-Work. As described above, recent blockchain solutions hybridize Proof-of-Work solutions with classical BFT solutions in various ways [26, 33, 7, 17, 29, 31, 42]. The need to address rotating leaders in these hybrid solutions and others provide the motivation behind HotStuff.

发表评论

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

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