UNIVERSITY of WISCONSIN MADISON Computer Sciences Department CS 739 Distributed Systems Motivation Andrea C Arpaci Dusseau Build reliable systems in the presence of faulty components Byzantine Generals Common approach Have multiple potentially faulty components compute same function Perform majority vote on outputs to get right result One paper C1 The Byzantine Generals Problem by Lamport Shostak Pease In ACM Transactions on Programing Languages and Systems July 1982 C2 C3 majority v1 v2 v3 f faulty f 1 good components 2f 1 total Assumption What is a Byzantine Failure Good nonfaulty components must use same input Otherwise can t trust their output result either Three primary differences from Fail Stop Failure 1 Component can produce arbitrary output For majority voting to work 1 All nonfaulty processors must use same input 2 If input is nonfaulty then all nonfaulty processes use the value it provides Fail stop produces correct output or none 2 Cannot always detect output is faulty Fail stop can always detect that component has stopped 3 Components may work together maliciously No collusion across components 1 Byzantine Generals Algorithm to achieve agreement among loyal generals i e working components given m traitors i e faulty components Agreement such that A All loyal generals decide on same plan B Small number of traitors cannot cause loyal generals to adopt bad plan Terminology Let v i be information communicated by ith general Combine values v 1 v n to form plan Rephrase agreement conditions A All generals use same method for combining information B Decision is majority function of values v 1 v n Impossibility Result Key Step Agree on inputs Generals communicate v i values to one another 1 Every loyal general must obtain same v 1 v n 1 Any two loyal generals use same value of v i Traitor i will try to loyal generals into using different v i s 2 If ith general is loyal then the value he sends must be used by every other general as v i Problem How can each general send his value to n 1 others A commanding general must send an order to his n 1 lieutenants such that IC1 All loyal lieutenants obey same order IC2 If commanding general is loyal every loyal lieutenant obeys the order he sends Interactive Consistency conditions Option 1 Loyal Commander With only 3 generals no solution can work with even 1 traitor given oral messages commander L1 attack L1 retreat attack attack commander L2 retreat L2 What must L1 do By IC2 L1 must obey commander and attack What should L1 do Is commander or L2 the traitor 2 Option 2 Loyal L2 No solution with fewer than 3m 1 generals can cope with m traitors commander retreat attack L1 retreat General Impossibility Result see paper for details L2 What must L1 do By IC1 L1 and L2 must obey same order L1 must retreat Problem L1 can t distinguish between 2 scenarios Oral Messages Assumptions A1 Every message is delivered correctly A2 Receiver knows who sent message A3 Absence of message can be detected Oral Message Algorithm OM 0 Commander sends his value to every lieutenant OM m m 0 Commander sends his value to every lieutenant For each i let vi be value Lieutenant i receives from commander act as commander for OM m 1 and send vi to n 2 other lieutenants For each i and each j not i let vj be value Lieut i received from Lieut j Lieut i computes majority v1 vn 1 3 Example Bad Lieutenant Example Bad Commander Scenario m 1 n 4 traitor L3 C A OM 1 A A C A OM 1 L2 L1 Scenario m 1 n 4 traitor C L3 R L2 L1 C OM 0 L2 A L1 A R L1 m A A R L2 m A A R Both attack Decision Bigger Example Bad Lieutenants Scenario m 2 n 7 traitors L5 L6 A L1 A L3 L2 A L4 A Decision R A L3 A Decision L1 m A R A L2 m A R A L3 m A R A Attack Bigger Example Bad Commander Scenario m 2 n 7 traitors C L6 A L6 L5 C A A Messages L1 L2 A L1 R C A L3 A OM 0 L3 R A R L1 A L3 L2 R L4 x A L5 L6 Messages L2 A L3 A L4 A L5 R L6 R m A A A A R R All loyal lieutenants attack L1 A Decision L2 R L3 A L4 R L5 A L6 A R A R A 4 Decision with Bad Commander Next Step of Algorithm L1 m A R A R A A Attack Verify that lieutenants tell each other the same thing L2 m R R A R A R Retreat L3 m A R A R A A Attack What messages does L1 receive in this example Requires rounds m 1 OM 0 Msg from Lieut i of form L0 said v0 L1 said v1 etc OM 2 A OM 1 2R 3A 4R 5A 6A OM 0 2 3A 4R 5A 6R 3 2R 4R 5A 6A 4 2R 3A 5A 6R 5 2R 3A 4R 6A 6 total confusion L4 m R R A R A R Retreat L5 m A R A R A A Attack Problem All loyal lieutenants do NOT choose same action All see same messages in OM 0 from L1 2 3 4 and 5 m A R A R A All attack Signed Messages New assumption Cryptography A4 a Loyal general s signature cannot be forged and contents cannot be altered b Anyone can verify authenticity of signature Simplifies problem When lieutenant i passes on signed message from j know that i did not lie about what j said Lieutenants cannot do any harm alone cannot forge loyal general s orders Only have to check for traitor commander With cryptographic primitives can implement Byzantine Agreement with m 2 nodes using SM m Signed Messages Algorithm SM m 1 Commander signs v and sends to all as v 0 2 Each lieut i A If receive v 0 and no other order 1 Vi v 2 send V 0 i to all B If receive v 0 j k and v not in Vi 1 Add v to Vi 2 if k m send v 0 j k i to all not in j k 3 When no more msgs obey order of choose Vi 5 SM 1 Example Bad Commander Scenario m 1 n 3 bad commander A 0 C L2 A 0 L1 L2 L1 R 0 L2 V1 A R V2 R A Both L1 and L2 can trust orders are from C Both apply same decision to A R Other Variations How to handle missing communication paths see paper for details Scenario m 2 n 4 bad commander and L3 R 0 L1 What next SM 2 Bad Commander A 0 L1 C A 0 L2 x A 0 L1 A 0 L3 L3 L1 A 0 L2 L2 L3 Goal L1 and L2 must make same decision R 0 L3 L1 …