Sync HotStuff: Practical Synchronous State Machine Replication

Slide Note

Sync HotStuff is a practical synchronous protocol that tolerates Byzantine replicas and handles weaker synchrony models. It overcomes issues of requiring a large number of rounds and lock-step execution. The protocol ensures safety by committing blocks and guarantees liveness by continuing to commit new blocks. Key components include setup phase, block format, steady state protocol, view change protocol, and proof of safety and liveness.

buffaloe_w Follow

Uploaded on Sep 29, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Sync HotStuff: Simple and Practical Synchronous State Machine Replication

Synchronous Protocol Issues Require a large amount number of rounds Require lock-step execution Adversary my attack the network to violate synchrony assumption

Sync HotStuff Tolerate one half Byzantine replicas No lock-step in steady state Handle weaker or more realistic synchrony model with minor modifications

Setup Phase Minority fault replicas Synchronous communications Authenticated messages No-drift clocks

Block format

Steady State Protcol 1. Leader L broadcast propose, Bk, v, Cv(Bk 1) L 1. Each replica r broadcast vote,Bk,v rand forward proposal after receiving proposal 1. Once vote for Bk, r starts a timer, commit-timerv,k. If r does not detect leader equivocation or leader change within 2?, r commits Bk(non-blocking) Why 2?? i) Bk will be certified ii) No equivocating block can be certified

Steady State Scenario L t ? ? r1 r2 r3

View Change Protocol 1. Blame and quit view a. Stalling detected: each replica r broadcast blame, v rand quit current view v after gathering f+1 blames b. Leader equivocation detected: r broadcast equivocating messages signed by L and quit v 2. r stops voting and commit-timers of v and waits for ? before locking on and sending highest certified block Cv (Bk ) to new Leader L , then enters view v+1 3. L waits for 2? and broadcast new-view, v + 1, Cv (Bk ) L 4. If r receives a block of rank not less than its locked one, it forwards the new view message and broadcast vote, Bk , v + 1 r

Proof Safety: no two honest replicas commit different blocks at the same height Liveness: all honest replicas keep committing new blocks

Lemma 1 Directly: a block Bk is committed because of its own commit-timerv,kexpiring Indirectly: a block Bkis committed as a result of directly committing Bl(l>k) that extends Bk If an honest replica directly commits Blin view v, then No equivocating block is certifies in view v Every honest replica locks on a certified block that ranks equal or higher than Cv(Bl) before entering next view v+1 Proof: suppose Blis directly committed at in view v at time t No honest replica quits v by t-?, OTRW, r has quit by t Since r enters v before t-2?, all honest replicas enter v before t-? Therefore, every honest replica vote for Bl by time t-? so all honest replicas receive Cv(Bl) before t+? Before entering next view, all replicas will wait for ?

Lemma 2 Unique Extensibility If an honest replica directly commits Bl in view v, then any certified block that ranks equal to or higher than Cv(Bl) must extend Bl Proof: Suppose S is the set of certified blocks that rank equal to or higher than CvBlbut do not extend Bl. Let Cv*(Bk*) be the lowest ranked block in S v* > v Some honest parties must have voted for Bk*, from either new-view, v*, Cv (Bk*) or a proposal New-view: Cv (Bk*) must rank higher than or equal to Cv(Bl), by lemma1 and every replica never decrease its locked value s rank Contradiction to definition of Cv*(Bk*)

Safety Suppose two distinct blocks Bkand Bk are committed at height k. Bkis committed because of direct commitment of Blat V Bk is committed because of direct commitment of B l at V By lemma 2, either Blextends Bl or vice versa Thus, Bk = Bk

Latency and complexity Latency: 2? + O(?) Leader: 2? + ? Client: 2? + 4? O(n2) communication complexity

Compare with Dfinity No lock-step execution by not voting for equivocating proposals A stable leader drive many decisions, not waste of proposal on leader election 2? vs 8/14?