HotStuf_f BFT Consensus in the Lens of BlockchainMaofan Yin1,2, Dahlia Malkhi2, Michael K. Reiter2,3, Guy Golan Gueta2, and Ittai Abraham21Cornell University, 2VMware Research, 3UNC-Chapel HillAbstractWe present HotStuf_f, a leader-based Byzantine fault-tolerant replication protocol for the partially synchronousmodel. Once network communication becomes synchronous, HotStuf_f enables a correct leader to drive the pro-tocol to consensus at the pace of actual vs. maximum network delaya property called responsivenessand withcommunication complexity that is linear in the number of replicas. To our knowledge, HotStuf_f is the f_irst par-tially synchronous BFT replication protocol exhibiting these combined properties. HotStuf_f is built around a novelframework that s a bridge between classical BFT foundations and blockchains. It allows the expression of otherknown protocols DLS, PBFT, Tendermint, Casper, and ours, in a common framework.Our deployment of HotStuf_f over a network with over 100 replicas achieves throughput and latency comparableto that of BFT-SMaRt, while enjoying linear communication footprint during leader failover vs. cubic with BFT-SMaRt.1 IntroductionByzantine fault tolerance BFT refers to the ability of a computing system to endure arbitrary i.e., Byzantine failuresof its components while taking actions critical to the system’s operation. In the context of state machine replicationSMR [35, 47], the system as a whole provides a replicated service whose state is mirrored across n deterministicreplicas. A BFT SMR protocol is used to ensure that non-faulty replicas agree on an order of cution for client-initiated service commands, despite the ef_forts off Byzantine replicas. This, in turn, ensures that then f non-faultyreplicas will run commands identically and so produce the same response for each command. As is common, we areconcerned here with the partially synchronous communication model [25], whereby a known bound on messagetransmission holds after some unknown global stabilization time GST. In this model, n 3f 1 is requiredfor non-faulty replicas to agree on the same commands in the same order e.g., [12] and progress can be ensureddeterministically only after GST [27].When BFT SMR protocols were originally conceived, a typical target system size was n 4 or n 7, deployedon a local-area network. However, the renewed interest in Byzantine fault-tolerance brought about by its applicationto blockchains now demands solutions that can scale to much largern. In contrast to permissionless blockchains suchas the one that supports Bitcoin, for example, so-called permissioned blockchains involve a f_ixed set of replicas thatcollectively maintain an ordered ledger of commands or, in other words, that support SMR. Despite their permis-sioned nature, numbers of replicas in the hundreds or even thousands are envisioned e.g., [42, 30]. Additionally,their deployment to wide-area networks requires setting to accommodate higher variability in communicationdelays.The scaling challenge. Since the introduction of PBFT [20], the f_irst practical BFT replication solution in thepartial synchrony model, numerous BFT solutions were built around its core two-phase paradigm. The practicalaspect is that a stable leader can drive a consensus decision in just two rounds of message exchanges. The f_irst phaseguarantees proposal uniqueness through the ation of a quorum certif_icate QC consisting of n f votes. Thesecond phase guarantees that the next leader can convince replicas to vote for a safe proposal.The algorithm for a new leader to collect ination and propose it to replicascalled a view-changeis theepicenter of replication. Unfortunately, view-change based on the two-phase paradigm is far from simple [38], isbug-prone [4], and incurs a signif_icant communication penalty for even moderate system sizes. It requires the newleader to relay ination from n f replicas, each reporting its own highest known QC. Even counting just1authenticators digital signatures or message authentication codes, conveying a new proposal has a communicationfootprint of On3 authenticators in PBFT, and variants that combine multiple authenticators into one via thresholddigital signatures e.g., [18, 30] still send On2 authenticators. The total number of authenticators transmitted ifOn view-changes occur before a single consensus decision is reached is On4 in PBFT, and even with thresholdsignatures is On3. This scaling challenge plagues not only PBFT, but many other protocols developed since then,e.g., Prime [9], Zyzzyva [34], Upright [22], BFT-SMaRt [13], 700BFT [11], and SBFT [30].HotStuf_f revolves around a three-phase core, allowing a new leader to simply pick the highest QC it knows of.It introduces a second phase that allows replicas to “change their mind” after voting in the phase, without requiringa leader proof at all. This alleviates the above complexity, and at the same time considerably simplif_ies the leaderreplacement protocol. Last, having almost canonized all the phases, it is very easy to pipeline HotStuf_f, and tofrequently rotate leaders.To our knowledge, only BFT protocols in the blockchain arena like Tendermint [15, 16] and Casper [17] fol-low such a simple leader regime. However, these systems are built around a synchronous core, wherein proposalsare made in pre-determined intervals that must accommodate the worst-case time it takes to propagate messagesover a wide-area peer-to-peer gossip network. In doing so, they forego a hallmark of most practical BFT SMR solu-tions including those listed above, namely optimistic responsiveness [42]. Inally, responsiveness requires that anon-faulty leader, once designated, can drive the protocol to consensus in time depending only on the actual mes-sage delays, independent of any known upper bound on message transmission delays [10]. More appropriate forour model is optimistic responsiveness, which requires responsiveness only in benef_icial and hopefully commoncircumstanceshere, after GST is reached. Optimistic or not, responsiveness is precluded with designs such as Ten-dermint/Casper. The crux of the dif_f_iculty is that there may exist an honest replica that has the highest QC, but theleader does not know about it. One can build scenarios where this prevents progress ad inf_initum see Section 4.4for a detailed liveless scenario. Indeed, failing to incorporate necessary delays at crucial protocol steps can result inlosing liveness outright, as has been reported in several existing deployments, e.g., see [3, 2, 19].Our contributions. To our knowledge, we present the f_irst BFT SMR protocol, called HotStuf_f, to achieve thefollowing two properties Linear View Change After GST, any correct leader, once designated, sends only On authenticators todrive a consensus decision. This includes the case where a leader is replaced. Consequently, communicationcosts to reach consensus after GST is On2 authenticators in the worst case of cascading leader failures. Optimistic Responsiveness After GST, any correct leader, once designated, needs to wait just for the f_irstn f responses to guarantee that it can create a proposal that will make progress. This includes the casewhere a leader is replaced.Another feature of HotStuf_f is that the costs for a new leader to drive the protocol to consensus is no greaterthan that for the current leader. As such, HotStuf_f supports frequent succession of leaders, which has been arguedis useful in blockchain contexts for ensuring chain quality [28].HotStuf_f achieves these properties by adding another phase to each view, a small price to latency in returnfor considerably simplifying the leader replacement protocol. This exchange incurs only the actual network delays,which are typically far smaller than in practice. As such, we expect this added latency to be much smaller than thatincurred by previous protocols that forgo responsiveness to achieve linear view-change. Furthermore, throughputis not af_fected due to the ef_f_icient pipeline we introduce in Section 5.In addition to the theoretical contribution, HotStuf_f also provides insights in understanding BFT replication ingeneral and instantiating the protocol in practice see Section 6 A framework for BFT replication over graphs of nodes. Safety is specif_ied via voting and commit graph rules.Liveness is specif_ied separately via a Pacemaker that extends the graph with new nodes. A casting of several known protocols DLS, PBFT, Tendermint, and Casper and one new ours, HotStuf_f, inthis framework.HotStuf_f has the additional benef_it of being remarkably simple, owing in part to its economy of mechanism Thereare only two message types and simple rules to determine how a replica treats each. Safety is specif_ied via votingand commit rules over graphs of nodes. The mechanisms needed to achieve liveness are encapsulated within aPacemaker, cleanly separated from the mechanisms needed for safety. At the same time, it is expressive in that it2allows the representation of several known protocols DLS, PBFT, Tendermint, and Casper as minor variations. Inpart this f_lexibility derives from its operation over a graph of nodes, in a way that s a bridge between classicalBFT foundations and modern blockchains.We describe a prototype implementation and a preliminary uation of HotStuf_f. Deployed over a network withover a hundred replicas, HotStuf_f achieves throughput and latency comparable to, and sometimes exceeding, thoseof mature systems such as BFT-SMaRt, whose code complexity far exceeds that of HotStuf_f. We further demonstratethat the communication footprint of HotStuf_f remains constant in face of frequent leader replacements, whereasBFT-SMaRt grows quadratically with the number of replicas.Protocol Authenticator complexity ResponsivenessCorrect leader Leader failure view-change f leader failuresDLS [25] On4 On4 On4PBFT [20] On2 On3 Ofn3 XSBFT [30] On On2 Ofn2 XTendermint [15] / Casper [17] On2 On2 Ofn2Tendermint* / Casper* On On OfnHotStuf_f On On Ofn a33*Signatures can be combined using threshold signatures, though this optimization is not mentioned in their original works.Table 1 Perance of selected protocols after GST.2 Related workReaching consensus in face of Byzantine failures was ulated as the Byzantine Generals Problem by Lamport etal. [37], who also coined the term “Byzantine failures”. The f_irst synchronous solution was given by Pease et al. [43],and later improved by Dolev and Strong [24]. The improved protocol has On3 communication complexity, whichwas shown optimal by Dolev and Reischuk [23]. A leader-based synchronous protocol that uses randomness wasgiven by Katz and Koo [32], showing an expected constant-round solution with n 12 resilience.Meanwhile, in the asynchronous settings, Fischer et al. [27] showed that the problem is unsolvable determin-istically in asynchronous setting in face of a single failure. Furthermore, an n 13 resilience bound for anyasynchronous 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 f_lips by processes untilthey happen to converge to consensus. Later works used cryptographic s to share an unpredictable coin anddrive complexities down to constant expected rounds, and On3 communication [18].The second approach relies on partial synchrony, f_irst shown by Dwork, Lynch, and Stockmeyer DLS [25]. Thisprotocol preserves safety during asynchronous periods, and after the system becomes synchronous, DLS guaranteestermination. Once synchrony is maintained, DLS incurs On4 total communication and On rounds per decision.State machine replication relies on consensus at its core to order client requests so that correct replicas cutethem in this order. The recurring need for consensus in SMR led Lamport to devise Paxos [36], a protocol thatoperates an ef_f_icient pipeline in which a stable leader drives decisions with linear communication and one round-trip. A similar emphasis led Castro and Liskov [20, 21] to develop an ef_f_icient leader-based Byzantine SMR protocolnamed PBFT, whose stable leader requires On2 communication and two round-trips per decision, and the leaderreplacement protocol incurs On3 communication. PBFT has been deployed in several systems, including BFT-SMaRt [13]. Kotla et al. introduced an optimistic linear path into PBFT in a protocol named Zyzzyva [34], whichwas utilized in several systems, e.g., Upright [22] and Byzcoin [33]. The optimistic path has linear complexity, whilethe leader replacement protocol remains On3. Abraham et al. [4] later exposed a safety violation in Zyzzyva, andpresented f_ixes [5, 30]. On the other hand, to also reduce the complexity of the protocol itself, Song et al. proposedBosco [49], a simple one-step protocol with low latency on the optimistic path, requiring 5f 1 replicas. SBFT [30]introduces anOn2 communication view-change protocol that supports a stable leader protocol with optimisticallylinear, one round-trip decisions. It reduces the communication complexity by harnessing two s a collector-based communication paradigm by Reiter [45], and signature combining via threshold cryptography on protocolvotes by Cachin et al. [18].A leader-based Byzantine SMR protocol that employs randomization was presented by Ramasamy et al. [44], anda leaderless variant named HoneyBadgerBFT was developed by Miller et al. [39]. At their core, these randomized3Byzantine solutions employ randomized asynchronous Byzantine consensus, whose best known communicationcomplexity was On3 see above, amortizing the cost via batching. However, most recently, based on the idea inthis HotStuf_f paper, a parallel submission to PODC’19 [8] further improves the communication complexity toOn2.Bitcoin’s core is a protocol known as Nakamoto Consensus [40], a synchronous protocol with only probabilisticsafety guarantee and no f_inality see analysis in [28, 41, 6]. It operates in a permissionless model where participantsare unknown, and resilience is kept via Proof-of-Work. As described above, recent blockchain solutions hybridizeProof-of-Work solutions with classical BFT solutions in various ways [26, 33, 7, 17, 29, 31, 42]. The need to addressrotating leaders in these hybrid solutions and others provide the motivation behind HotStuf_f.3 ModelWe consider a system consisting of a f_ixed set of n 3f 1 replicas, indd by i2[n] where [n] f1;;ng. Aset F [n] of up to f jFjreplicas are Byzantine faulty, and the remaining ones are correct. We will often referto the Byzantine replicas as being coordinated by an adversary, which learns all internal state held by these replicasincluding their cryptographic keys, see below.Network communication is