[Extended Abstract: HotStuff-2: Optimal Two-Phase Responsive BFT](https://eprint.iacr.org/2023/397) # Abstract Turns out it is possible to solve partially-synchronous BFT while achieving O(n^2) worst-case communication, optimistically-linear communication, two-phase commit regime within a view, and optimistic responsiveness [[HotStuff]] required a three-phase view to do all of that Hotstuff-2 is simple and adds no substantive complexity to original protocol # Introduction We want a solution to the known log replication problem in the [[partial synchrony]] model that has the following measures to reach a single commit decision: - Optimal O(n^2) communication cost and latency of O(n) against a worst-case cascade of failures - Optimistically linear communication - Two-phase commit regime - No extra delay for failure-free leader rotation Operates in view-by-view manner where each view has a leader driving progress towards commit decision Sub-protocol for view-synchronization (pacemaker) so parties enter the view around the same time as the leader ## Relationship to Closely Related Results There was a belief that there was not a solution satisfying: - **F-0** two-phase view regime - **F-1** optimistically no wait over sequences of decisions - **F-2** optimistically linear communication - **F-3** balanced communication load over sequences of decisions - **F-4** 𝑂(𝑛^2 ) worst-case communication [[PBFT]] obtained F-0 and F-1 Enhancements on top of it got F-2 [[Tendermint]], [[Casper]], and [[HotStuff]] achieved F-3 through a simpler view-change regime At the cost of requiring each new view to wait for the maximal network delay $\Delta$ Thus they sacrifice F-1 F-2 would need signature aggregation F-4 requires pacemaker protocol HotStuff got F-1 through F-4 but gave up F-0 **GOOD OTHER PAPERS IN HERE** # Intuition Presented as single-shot protocol for simplicity, meaning participants reach consensus in a single round (?) View-by-View consensus overview. View consists of two abstract steps: 1. Designed leader attempts to reconcile an output value 1. Key ingredient: *validity condition:* leader's reconciled value is accepted subject to safety with respect to commit values of previous views and to non-equivocation 2. Parties check whether there is an agreed value and ratify it 1. Key ingredient: *commit adopt:* If any honest party commits an output, 2t+1 parties adopt and protect it, meaning they *lock* the value. Full consensus proceeds by alternating the two steps: 1. Commit-adopt value is carried into a reconciliation step of the next view in order to protect a commit decision 2. Reconciliation value is carried into a commit-adopt step to drive progress Different protocols differ in how commit-adopt is implemented and how the leader generates and drives acceptance of a valid proposal #### PBFT Leader collects a status of locks from 2t+1 parties at the start of a view If some party has committed in earlier views, among the 2t+1 locks in the status, up to t can be malicious, up to 2 can be from honest parties that are not guarding the safety of the commit, but there is at least one that corresponds to the committed value Leader proposes highest lock it obtains *On the other hand*, if not party had committed in an earlier view, even if some had locked onto the value, their status may or may not be a part of the locks the leader receives. Leader is guaranteed that no honest party committed the value and is free to propose anything Leader convinces honest parties to vote for its proposed value by sending a certificate containing 2t+1 locks in its proposal. Status certificate from an honest leader provides sufficient information to all honest parties to vote on the proposal #### Tendermint Improves PBFT by not requiring the 2t+1-sized status certificate How does a leader know what to propose and how can it be sure that all honest parties would vote for it? *Observe:* By receiving 2t+1 locks, an honest leader might know what to propose, but if parties don't have access to those locks (through status certificate), they may not vote for it. In particular, when p is locked on a value and a leader proposes a conflicting value, p can't distinguish whether or needs to guard the safety of the value or vote for the proposal **Livenessness concern** To remedy this, Tendermint requires the leader waits for an O($\Delta$) time at the start of the view. After GST, this wait ensures the leader receives locks from all honest parties. *Thus,* it can send a proposal that conforms with the value corresponding to the lock from the highest view, and send this lock together with the proposal. The highest-ranked lock is enough to convince all honest parties to vote on this proposal. #### HotStuff Obtains a linear view change and responsiveness when the leader is honest after GST Addresses livelessness concern differently while still ensuring that the value corresponding to the highest lock is proposed by the leader. Uses the same argument as the one for safety For safety, we say "if some party commits, then >= 2t+1 parties hold a lock that will guard the safety of the commit and ensure that the next leader receives it" For liveness, HotStuff introduces another phases of votes and obtains "if some party locks, then >= 2t+1 parties know about the existence of this lock and thus hold a *key* corresponding to it. This key will be shared with the next leader to decide on a proposal appropriately." The next leader will learn about the highest lock through the 2t+1 keys it receives, and the proposal would respect the globally highest lock held by any honest party **Note:** locks guard the safety of a commit, but keys do not, and thus honest parties only holding a higher key on a different value than the proposal can still vote for the proposal. #### HotStuff-2 Looks at livelessness and asks *do we really need to add another phase to address this concern while still obtaining linear communication complexity and optimistic responsiveness?* If a leader knows about the highest lock and it can convince all honest parties about it, then the problem is solved. If a leader would receive a lock corresponding to the previous view, there cannot even exist a higher lock *Thus,* a proposal respecting this lock would be voted for by all honest parties and the livelessness concern does not exist. If a leader does not obtain a lock from preivous view, it'll wait to hear about the locks from all honest parties by waiting O($\Delta$) Happens when previous view is malicious or previous view before GST If we have a sequence of honest leaders after GST, each of them is guaranteed to drive progress responsively and generate a certificate in a view that will aid the next leader. *Thus,* all leaders except the first one in the chain can make honest parties commit responsively. # Model and Performance Measures Partial synchrony, n = 3t+1, t of which are faulty Parties output increasing log prefixes with the following guarantees: - **Safety** - At all times, the outputs of every pair of correct parties is a prefix of one another - **Liveness** - After GST, agreement decisions to extend the log one position are repeatedly delivered by at least one correct party (no progress guaranteed until after GST) lt;x>_p$ denotes signature on message x by party p # The HotStuff-2 Protocol Consists of two parts: 1) a steady-state protocol and 2) pacemaker protocol for advancing views Steady-state protocol drives a commit decision in a view when all correct parties overlap in he view for sufficiently long, and a designated leader for vire v known to all parties is honest/correct. Nearly identical to the two-chain HotStuff protocol, but we let the leader drive the commit of an entire block in a view in two phases **Block Format** A block $B_{k}$ at height k has the format of $B_{k} = (b_{k}, h_{k-1})$ $b_{k}$ denotes a proposed value at height k and $h_{k-1}=H(B_{k-1})$ a hash digest of the predecessor block A block is *valid* if is predecessor is valid and its proposed value meets app-level validity conditions and is consistent with its chain of ancestors **Block Extension and Equivocation** Blocks extend one another if one is the ancestor of the other Blocks equivocate one another if they are not equal and do not extend one another **Certificates and certified blocks** Parties vote for blocks by signing using a threshold signature $C_{v}(B_{k})$, a certificate for Bk, denotes a set of signatures on $h_{k}=H(B_{k})$ by 2t+1 parties in view v **Timeout** - occurs if there is no progress, uses the pacemaker to justify and coordinate entrance to the next view **Locked Blocks** - Party locks the highest certified block to its knowledge Used to guard the safety of a commit **Steady-State Protocol** Goal of a view leader is to extend the highest certified block in the current sequence with a new block and get it certified by parties - Leader forms a block $B_{k}$ that contains its proposed value, the view number, and the highest-ranked certificate the leader knows. It sends this proposed block to all parties - Each party keeps the highest certificate it's received. Party votes for $B_{k}$ if it extends the highest certificate by sending a signed vote to the leader - Block becomes certified if 2t+1 parties vote for it. The certificate formed from 2t+1 signed votes is aggregated by the leader - Leader engages in another round of votes; however, parties send these votes to the leader of view v+1 **Pacemaker** Responsible for synching entrance to views, which happens in one of two ways 1. If $C_{v}(C_{v}(B_{k}))$ is obtained, advance to next view immediately 1. Note that since certificate is broadcast by leader, pacemaker does not require any further action to synchronize entering to the next view 2. Wait at delay time to allow correct leader to make progress. Ensures liveness upon leader failure and is mandated by [[Aguilera and Toueg]] **View-Synchronization** Bundles consecutive views into epochs, each consisting of t+1 views Employ Cogsworth-like (explained later) coordination in the first view of each epoch then advance through the rest of the views There is a mechanism to guarantee that an honest leader can form a certified block in a view after GST In case 1 from above, it already has the certified block In case 2, the mandatory latency required for advancing a view without forming a certificate can be recognized by the leader. Thus, the leader can wait a time bound for all honest parties to respond and then proceed to propose Leader doesn't need to convince parties about the safety of its proposal by sending all the certificates it received, because it provides enough time for all parties to report their highest lock - it will attach the highest certificate among all honest parties ![[Pasted image 20230820083430.png]]