Byzantine GeneralsMotivationAssumptionWhat is a Byzantine Failure?Slide 5Key Step: Agree on inputsImpossibility ResultOption 1: Loyal CommanderOption 2: Loyal L2General Impossibility ResultOral MessagesOral Message AlgorithmExample: Bad LieutenantExample: Bad CommanderBigger Example: Bad LieutenantsBigger Example: Bad Commander+Decision with Bad Commander+Next Step of AlgorithmSigned MessagesSigned Messages Algorithm: SM(m)SM(1) Example: Bad CommanderSM(2): Bad Commander+Other VariationsAssumptionsImportance of AssumptionsByzantine GeneralsUNIVERSITY of WISCONSIN-MADISONComputer Sciences DepartmentCS 739Distributed SystemsAndrea C. Arpaci-DusseauOne paper:• “The Byzantine Generals Problem”, by Lamport, Shostak, Pease, In ACM Transactions on Programing Languages and Systems, July 1982MotivationBuild reliable systems in the presence of faulty componentsCommon approach:•Have multiple (potentially faulty) components compute same function•Perform majority vote on outputs to get “right” resultC1C2C3majority(v1,v2,v3)f faulty, f+1 good components ==> 2f+1 totalAssumptionGood (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 nonfaulty processes 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 componentsByzantine 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 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 orderIC2) If commanding general is loyal, every loyal lieutenant obeys the order he sendsInteractive Consistency conditionsImpossibility ResultWith only 3 generals, no solution can work with even 1 traitor (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 attackOption 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 can cope 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 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)Example: 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?Decision 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 choose same 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 and contents cannot be alteredb. Anyone can verify authenticity of signatureSimplifies 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 commanderWith 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 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)SM(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 L2 must make same decisionL1L3L2A:0:L1A:0:L2A:0:L3R:0:L3L1L2R:0:L3:L1V1 = V2 = {A,R} ==> Same decisionOther VariationsHow