Byzantine Fault Tolerance: Protocols, Forensics, and Research
Explore the realm of Byzantine fault tolerance through protocols like State Machine Replication and HotStuff, discussing safety, liveness, forensic support, and the impact of Byzantine faults. Dive into decades of research on achieving fault tolerance and examining forensic support in the face of Byzantine behavior.
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
BFT Protocol Forensics Kartik Nayak Peiyao Sheng, Gerui Wang, Sreeram Kannan, Pramod Viswanath
State Machine Replication A group of servers provide the same interface as a single non-faulty server even if some of the servers are Byzantine faulty (Safety) Any two non-faulty servers do not learn different sequence of values (Liveness) A value proposed by a client will be eventually executed by every non-faulty server cmdj cmdi
BFT Protocol Research 40 years of research Tolerate more faults Better efficiency Byzantine Agreement: Byzantine threshold: t < n Actual number of faults: f Safety and liveness: f t
BFT Protocol Forensics What happens when f > t? Safety and/or liveness can be violated Forensic support: provide irrefutable evidence of bad behavior Is it always possible? What does it take to obtain such evidence?
BFT Protocol Forensics Safe and live No forensic support Forensic support (d = t+1) for d > n-2t t n-t Actual number of Byzantine parties (f) d: Number of Byzantine replicas detected
Existing Works on Forensic Support for BFT Multiple previous works PeerReview, Casper, Polygraph, Grandpa BFT, To design protocols with forensic support (accountability) Our goal: Analyze existing protocols based on Number of Byzantine replicas detected (d) Number of witnesses Distributedness (k)
Todays Talk Algorand BA d = 0 k = n - f (all honest parties) Honest parties involved (k) HotStuff d = t + 1 k = 1 Byzantine parties held culpable (d)
HotStuff Partially synchronous protocol, tolerates 1/3rd Byzantine faults [YMRGA 19] (2t+1 votes) prepareQC(v) precommitQC(v) commitQC(v) propose(v, hQC) vote1(v) vote2(v) vote3(v) Messages in some view e
HotStuff: Key Invariant vote3(v): locked on v; will not vote differently prepareQC(v) precommitQC(v) commitQC commitQC(v) (v) propose(v, hQC) vote1(v) vote2(v) vote3(v) vote3(v) Messages in some view e
HotStuff: Key Invariant vote3(v): locked on v; will not vote differently unless it is safe it is safe : hQC shared by leader is from a higher view prepareQC(v) precommitQC(v) commitQC(v) propose(v, hQC) hQC: highest prepareQC known to leader vote1(v) vote2(v) vote3(v) Messages in some view e
An Attack Across Views commitQC(v) Party i commits v commitQC(v ) Party j commits v Propose(v , hQC) vote3(v) A A A A B B B B No commits in these views C C C C D D D D View e . . . View e
Q: Which parties are Byzantine? Hint: D is not, it did not vote3(v) Observe: vote2, vote3 do not matter Claim: B and C are culpable. commitQC(v) Party i commits v commitQC(v ) Party j commits v Propose(v , hQC) vote3(v) A A A A B B B B No commits in these views C C C C D D D D View e . . . View e
Claim: B and C are culpable A: False, hQC can be a prepareQC on v in some view > e Holds for all views > e except the first one where prepareQC was formed commitQC(v) Party i commits v commitQC(v ) Party j commits v Propose(v , hQC) vote3(v) A A A A B B B B No commits in these views C C C C D D D D View e View e
Identifying Culpable Replicas (Across Views) e*: first higher view prepareQC for a different value was formed We re locked on v in view e commitQC(v) Party i commits v (hQC from a lower view) commitQC(v ) Party j commits v Propose(v , hQC) prepareQC(v ) Propose(v , hQC) not vote1 A vote3(v) A vote1 B B We are locked on v or our locks are older than e vote1 C C vote1 D D View e* View e View e
Identifying Culpable Replicas (Across Views) Culpable replicas: Intersection of commitQC(v) and parties forming the first prepareQC(v ) Q: Who has access to the first prepareQC(v ) formed in e*? A: If v was committed, 2t+1-f honest parties hold prepareQC(v ) - Many witnesses
Identifying Culpable Replicas (Across Views) Culpable replicas: Intersection of commitQC(v) and parties forming the first prepareQC(v ) Q: How do we know e* was the first such view? A: Implementation details matter - Depending on information included with vote1(v ), we can have (a) Single witness identifying t+1 Byzantine replicas (b) Require multiple witnesses (c) Have no forensic support even after obtaining all honest transcripts
Todays Talk Algorand BA d = 0 k = n - f (all honest parties) Honest parties involved (k) HotStuff d = t + 1 k = 1 Byzantine parties held culpable (d)
Algorand BA Synchronous protocol, tolerating 1/3 faults [CM 16] Byzantine Agreement on a binary value
Algorand BA Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 (terminate if step 1) #(1) > 2t, update b = 1 (terminate if step 2) Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Step 1 Step 2 Step 3 Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1
Safety Violation when f > t: World 1 Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 #(1) > 2t, update b = 1 Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Byzantine do not send 0 Step 1 Step 2 Step 3 Honest parties switch to b = 1 f > t Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1 can 2t
World 1 Culprits: Parties who did not send b Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 #(1) > 2t, update b = 1 Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Byzantine do not send 0 Step 1 Step 2 Step 3 Honest parties switch to b = 1 f > t Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1 can 2t
World 2 Culprits: Parties who switched to b = 1 Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 #(1) > 2t, update b = 1 Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Byzantine do not send 0 All parties send 0 Step 1 Step 2 Byzantine parties switch to b = 1 Step 3 Honest parties switch to b = 1 f > t Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1 can 2t
Summary Two protocols: HotStuff and Algorand BA HotStuff has strong forensic support Algorand BA does not have any forensic support Implementation details matter Our paper: PBFT, VABA Implement forensic client on DiemBFT Generic impossibility results
