The Papers Byzantine Fault Tolerance 1 The Byzantine Generals Problem Lamport et al Presented By Wade Fagen Lucas Cook Paper 1 2 3 2 Practical Byzantine Fault Tolerance Castro et al 3 Preserving Peer Replicas By RateLimited Sampled Voting Maniatis et al 1 2 The Byzantine Generals The Byzantine Generals Let us assume we have five generals Let us assume one is malicious 3 4 The Byzantine Generals The Byzantine Generals Each local general decides on an attack and accurately relays their plan 5 6 1 The Byzantine Generals The Byzantine Generals except the random malicious node Each general collects his or her votes 7 8 The Byzantine Generals The Byzantine Generals Assume each general takes the majority vote The generals now move based upon their agreed orders 9 10 The Byzantine Generals The Byzantine Generals Since less than half of the military attacked the military attack failed What s interesting the remaining loyal nodes don t know which node s among them are disloyal 1 2 3 4 5 11 1 2 3 12 2 The Byzantine Generals The Byzantine General Problem Let us replan the attack Let the generals decide for one to be the leader and others to simply be lieutenants I ll be the general 13 14 The Byzantine General Problem The Byzantine General Problem Now the general plans the attack The general sends out his or her order to all lieutenants 15 16 The Byzantine General Problem The Byzantine General Problem Each site records the message they received Each site now sends the attack plan they ve received to the other sites 17 18 3 The Byzantine General Problem The Byzantine General Problem Again each site records all messages received This process may continue for any number of rounds but we ll stop here for now 19 20 The Byzantine General Problem The Byzantine General Problem Each site finds the majority value of its final round Result All loyal nodes agree on the same result 21 The Byzantine General Problem The Byzantine General Problem What assumptions were made 22 A1 Every message sent was delivered correctly What assumptions were made as we didn t see A1 Every message sent was delivered correctly A2 The receiver of the message knows who sent it as we didn t see 23 24 4 The Byzantine General Problem The Byzantine General Problem What assumptions were made A1 Every message sent was delivered correctly A2 The receiver of the message knows who sent it A3 All sites sent a message as we didn t see What assumptions were made A1 Every message sent was delivered correctly A2 The receiver of the message knows who sent it A3 The absence of a message can be detected so we might see No message for me a pre defined default value may be used 25 26 The Byzantine General Problem The Byzantine General Problem How many disloyal troops can we have and still reach consensus Pre determined general creates an attack plan 27 28 The Byzantine General Problem The Byzantine General Problem Round 1 Send out messages Record Round 2 Send out messages Record 29 30 5 The Byzantine General Problem The Byzantine General Problem Round 3 Send out messages Record Seems like 1 disloyal troop with 2 loyal troops works 31 32 The Byzantine General Problem The Byzantine General Problem but does it Round 1 Send out messages Record 33 34 The Byzantine General Problem The Byzantine General Problem Round 2 Send out messages Record Round 3 Send out messages Record 35 36 6 The Byzantine General Problem The Byzantine General Problem Round 4 Send out messages Record Round 5 Send out messages Record 37 38 The Byzantine General Problem The Byzantine General Problem Round 6 Send out messages Record Lamport shows by proof For a system of n 1 nodes there cannot exist more than n 3 faulty nodes Alternatively There must be more than 3m troops in any army with up to m traitors 39 The Byzantine General Problem The Byzantine General Problem General Proof Outline 40 Pair two loyal troops with each disloyal troop 41 General Proof Outline There must exist one more loyal troop to sway the balance of the majority 42 7 The Byzantine General Problem The Byzantine General Problem General Proof Outline But the proof only holds if the algorithm runs for m or more total rounds Up until now the node has been malicious But is that all A Byzantine failure is 1 4 An arbitrary failure of the node Adversarial assumption worst case 2 5 3 6 The adversary is as smart as the system Thus a system prone to Byzantine failures may not always suffer a Byzantine failure fail stop failures may also exist 43 The Byzantine General Problem The Byzantine General Problem Tough stuff But if we add one more assumption we can make the problem a lot easier 44 Returning to the problem that didn t work with unsigned messages A4 Messages are signed a A loyal general has a signature that cannot be forged b A signed message cannot be altered without detection c Anyone can verify the signature 45 46 The Byzantine General Problem The Byzantine General Problem Previously our general sent two order out But when the algorithm runs for a second round Conflicting Orders 47 48 8 The Byzantine General Problem The Two Generals Problem The authors find that by using signed messages A1 Every message sent was delivered correctly Any number of disloyal generals may exist in a system Reviewing our assumptions Problem is trivial if n m 2 All loyal generals will agree on a common result after m rounds The Two Generals Problem showed that two generals cannot ever reach consensus with the possibility of lost messages Developed by Akkoyunlu et al in 1975 49 The Byzantine General Problem Useful The core Byzantine problem is well studied and understood Works for systems where not all nodes can communicate with one another Clock synchronization problems have be solved in Byzantine prone systems 50 1 presents the case of 3 regular graphs In a system with a bound on adversarial nodes you must perform at least m rounds to reach consensus Unsigned Messages m n 1 3 Signed Messages m n Requires PKI or some similar system Interactive Consistency Algorithms Lamport 1986 51 Useful Consensus Protocol Goals Could you develop a practical replica server based upon 52 Liveness Safety Message loss reordering duplication Independent node failures PKI and collision resistant hashing Strong adversary Replicated service based on state machine Replicated service is linearizable Clients receive replies to requests As we examine 2 we will find out We need n 3f nodes 53 i e it appears centralized w atomic ops 2f 1 to act with confidence f
View Full Document
Unlocking...