1Byzantine GeneralsUNIVERSITY of WISCONSIN-MADISONComputer Sciences DepartmentCS 739Distributed SystemsAndrea C. Arpaci-DusseauOne paper:• “The Byzantine Generals Problem”, by Lamport,Shostak, Pease, In ACM Transactions on ProgramingLanguages and Systems, July 1982MotivationBuild reliable systems in the presence of faultycomponentsCommon approach:• Have multiple (potentially faulty) components compute samefunction• Perform majority vote on outputs to get “right” resultC1C2C3majority(v1,v2,v3)f faulty, f+1 good components ==> 2f+1 total AssumptionGood (nonfaulty) components must use same input• Otherwise, can’t trust their output result eitherFor majority voting to work:1) All nonfaulty processors must use same input2) If input is nonfaulty, then all nonfaultyprocesses use the value it providesWhat is a Byzantine Failure?Three primary differences from Fail-Stop Failure1) Component can produce arbitrary output• Fail-stop: produces correct output or none2) Cannot always detect output is faulty• Fail-stop: can always detect that component has stopped3) Components may work together maliciously• No collusion across components2Byzantine GeneralsAlgorithm 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 planB) 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 planRephrase agreement conditions:A) All generals use same method for combining informationB) Decision is majority function of values v(1)...v(n)Key Step: Agree on inputsGenerals 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)’s2) If ith general is loyal, then the value he sends must be usedby every other general as v(i)Problem: How can each general send his value to n-1others?A commanding general must send an order to his n-1lieutenants such that:IC1) All loyal lieutenants obey same orderIC2) If commanding general is loyal, every loyal lieutenant obeysthe order he sendsInteractive Consistency conditionsImpossibility ResultWith only 3 generals, no solution can work with even 1traitor (given oral messages)commanderattackretreatL1 L2What should L1 do? Is commander or L2 the traitor???Option 1: Loyal CommandercommanderattackretreatL1 L2attackWhat must L1 do?By IC2: L1 must obey commander and attack3Option 2: Loyal L2commanderattackretreatL1 L2retreatWhat must L1 do?By IC1: L1 and L2 must obey same order --> L1 must retreatProblem: L1 can’t distinguish between 2 scenariosGeneral Impossibility ResultNo solution with fewer than 3m+1 generals cancope with m traitors< see paper for details >Oral MessagesAssumptionsA1) Every message is delivered correctlyA2) Receiver knows who sent messageA3) Absence of message can be detectedOral Message AlgorithmOM(0)• Commander sends his value to every lieutenantOM(m), m>0• Commander sends his value to every lieutenant• For each i, let vi be value Lieutenant i receivesfrom 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 Lieuti received from Lieut j. Lieut i computesmajority(v1,...,vn-1)4Example: Bad LieutenantScenario: m=1, n=4, traitor = L3CL1L3L2AAAOM(1):OM(0):???CL1L3L2AARRDecision?? L1 = m (A, A, R); L2 = m (A, A, R); Both attack!Example: Bad CommanderScenario: m=1, n=4, traitor = CCL1L3L2ARAOM(1):OM(0):???L1L3L2ARAADecision??L1=m(A, R, A); L2=m(A, R, A); L3=m(A,R,A); Attack!RABigger Example: Bad LieutenantsScenario: m=2, n=7, traitors=L5, L6CAAAL2L6L3L5L4L1AAAL2L6L3L5L4L1A A AA RRDecision???Messages?m(A,A,A,A,R,R) ==> All loyal lieutenants attack!Bigger Example: Bad Commander+Scenario: m=2, n=7, traitors=C, L6CL2L6L3L5L4L1RARAAxA,R,A,R,AA R RAADecision???L2L6L3L5L4L1Messages?5Decision with Bad Commander+L1: m(A,R,A,R,A,A) ==> AttackL2: m(R,R,A,R,A,R) ==> RetreatL3: m(A,R,A,R,A,A) ==> AttackL4: m(R,R,A,R,A,R) ==> RetreatL5: m(A,R,A,R,A,A) ==> AttackProblem: All loyal lieutenants do NOT choosesame actionNext Step of AlgorithmVerify that lieutenants tell each other the same thing• Requires rounds = m+1• OM(0): Msg from Lieut i of form: “L0 said v0, L1 said v1, etc...”What messages does L1 receive in this example?• 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 }All see same messages in OM(0) from L1,2,3,4, and 5m(A,R,A,R,A,-) ==> All attackSigned MessagesNew assumption: CryptographyA4) a. Loyal general’s signature cannot be forged andcontents cannot be alteredb. Anyone can verify authenticity of signatureSimplifies problem:• When lieutenant i passes on signed message from j, know that idid not lie about what j said• Lieutenants cannot do any harm alone (cannot forge loyalgeneral’s orders)• Only have to check for traitor commanderWith cryptographic primitives, can implement ByzantineAgreement 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 order1) Vi = v2) send (V:0:i) to allB) If receive (v:0:j:...:k) and v not in Vi1) Add v to Vi2) if (k<m) send (v:0:j:...:k:i) to all not in j...k3. When no more msgs, obey order of choose(Vi)6SM(1) Example: Bad CommanderScenario: m=1, n=3, bad commanderCL1L2A:0 R:0What next?L1L2A:0:L1R:0:L2V1={A,R} V2={R,A}Both L1 and L2 can trust orders are from CBoth apply same decision to {A,R}SM(2): Bad Commander+Scenario: m=2, n=4, bad commander and L3CL1L3L2A:0A:0xGoal? L1 and L2must make samedecisionL1L3L2A:0:L1A:0:L2A:0:L3R:0:L3L1L2R:0:L3:L1V1 = V2 = {A,R} ==> Same decisionOther VariationsHow to handle missing communication paths< see paper for details>AssumptionsA1) Every message sent by nonfaulty processor isdelivered correctly• Network failure ==> processor failure• Handle as less connectivity in graphA2) Processor can determine sender of message• Communication is over fixed, dedicated lines• Switched network???A3) Absence of message can be detected• Fixed max time to send message + synchronized clocks ==> Ifmsg not received in fixed time, use defaultA4) Processors sign msgs such that