Motivation Build reliable systems in presence of faulty components Common approach: - Send request (or input) to some “f-tolerant” server
- Have multiple (potentially faulty) components compute same function
- Perform majority vote on outputs to get “right” result
What is a Byzantine Failure? Three primary differences from Fail-Stop Failure - Component can produce arbitrary output
- Fail-stop: produces correct output or none
- Cannot always detect output is faulty
- Fail-stop: can always detect that component has stopped
- Components may work together maliciously
With fail-stop failures: How many components are needed to be f-tolerant??
Assumption for F-tolerant Servers Good (non-faulty) components must use same input - Otherwise, can’t trust their output result either
For majority voting to work: All non-faulty processors must use same input If input is non-faulty, then all non-faulty processes use the value it provides Must agree on value of input
Byzantine Generals Algorithm to achieve agreement among “loyal generals” (i.e., working components) given m “traitors” (i.e., faulty components) Agreement such that: - All loyal generals decide on same plan (important even when input is faulty! Why?)
- Small number of traitors cannot cause loyal generals to adopt “bad plan”
Terminology - Let v(i) be information communicated (I.e., input observed) by ith general
- Each general combines values v(1)...v(n) to form plan
Agreement Conditions Rephrase agreement conditions: - Loyal generals decide on same plan if All loyal generals use same method for combining information (and see same inputs)
- Small number of traitors can’t hurt loyal generals if Use robust function for decision, such as majority function of values v(1)...v(n)
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 trick 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)
How can each general send his value to n-1 others? A commanding general must send an order (order: Use v(i) as my value) 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
Impossibility Result With only 3 generals, no solution can work with even 1 traitor (given oral messages)
Option 1: Loyal Commander
Option 2: Loyal L2
General Impossibility Result No solution with fewer than 3m+1 generals can cope with m traitors < see paper for details >
Oral Messages Assumptions A1) Every message sent is delivered correctly A2) Receiver knows who sent message - What scenarios is this true for?
A3) Absence of message can be detected
Oral Message Algorithm 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)
OM(0) - Commander sends his value to every lieutenant
Example: Bad Lieutenant Scenario: m=1, n=4, traitor = L3
Example: Bad Commander Scenario: m=1, n=4, traitor = C
Bigger Example: Bad Lieutenants Scenario: m=2, n=3m+1=7, traitors=L5, L6
Bigger Example: Bad Commander+ Scenario: m=2, n=7, traitors=C, L6
Decision with Bad Commander+ L1: m(A,R,A,R,A,A) ==> Attack L2: m(A,R,A,R,A,R) ==> Retreat L3: m(A,R,A,R,A,A) ==> Attack L4: m(A,R,A,R,A,R) ==> Retreat L5: m(A,R,A,R,A,A) ==> Attack Problem: All loyal lieutenants do NOT choose same action
Next Step of Algorithm Verify 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 (doesn’t know 6 is traitor)
- 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 5 m(A,R,A,R,A,-) ==> All attack
Signed Messages Problem: Traitors can lie about what others said; how can we remove that ability? New assumption: Signed messages (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, receiver knows 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) Commander signs v and sends to all as (v:0) 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 3. When no more msgs, obey order of choice(Vi)
SM(1) Example: Bad Commander Scenario: m=1, n=m+2=3, bad commander
SM(2): Bad Commander+ Scenario: m=2, n=m+2=4, bad commander and L3
Other Variations How to handle missing communication paths < see paper for details>
Assumptions A1) Every message sent by nonfaulty processor is delivered correctly A2) 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 ==> If msg not received in fixed time, use default
A4) Processors sign msgs such that nonfaulty signatures cannot be forged - Use randomizing function or cryptography to make liklihood of forgery very small
Importance of Assumptions “Separating Agreement from Execution for Byzantine Fault Tolerant Services” - SOSP’03 Goal: Reduce replication costs - 3f+1 agreement replicas
- 2g+1 execution replicas
- Costly part to replicate
- Often uses different software versions
- Potentially long running time
To provide A2, protocol assumes cryptographic primitives, such that one can be sure “i said v” in switched environment What is the problem??
Conclusions Problem: To implement a fault-tolerant service with coordinated replicas, must agree on inputs Byzantine failures make agreement challenging - Produce arbitrary output, can’t detect, collude
User different agreement protocol depending on assumptions - Oral messages: Need 3f+1 nodes to tolerate f failures
- Difficult because traitors can lie about what others said
- Signed messages: Need f+2 nodes
- Easier because traitors can only lie about other traitors
Byzantine Werewolves - Two groups: Werewolves and villagers
- Multiple rounds of night and day
- Night: Werewolves kill a villager
- Day: All vote on who to kill…hopefully a werewolf
Werewolves trick villages into bad decisions (killing one of their own) - Werewolves lie, act in collision
Werewolves have more information than villagers (I.e., who is a werewolf) - Traditional: Only 1 village “seer” has any info
- My variant: Every villager can ask one question per round
- Traditional: More psychological…
Byzantine-Werewolf Game Rules Everyone secretly assigned as werewolf or villager - 3 werewolves, rest are “seeing” villagers
- I am moderator
Night round: - “Close your eyes”; make noises to hide activity
- “Werewolves, open your eyes”: 3 can see who is who
- “Werewolves, pick someone to kill” (Not first round)
- Silently agree on villager to kill by pointing
- “Werewolves, close your eyes”
- For all: “NAME, open your eyes” “Pick someone to ask about”
- Useless for Werewolves, but hides their identity…
- Point to another player
- Moderator signs thumbs up for werewolf, down for villager
- “NAME, close your eyes”
Rules: Day Time Day Time: “Everyone open your eyes; its daytime” - “NAME, you have been killed by the werewolves!”
- They are now out of the game
- Agreement time: Everyone talks and votes on who should be “decommissioned”
- Villagers try to decommission werewolf
- Werewolves try to trick villagers with bad info
- Pairwise communication
- Variant: Signed messages; leave a note with everyone telling them what you know; can show this note to others
- When you’ve made up your mind, tell moderator
- Moderator: Uses majority voting to determine who is decommissioned “Okay, NAME is dead”
- Person is out of game (can’t talk anymore) and shows card
Repeat cycle until All werewolves dead OR werewolves >= villagers
Dostları ilə paylaş: |