The Byzantine Generals Problem Boon Thau Loo

The Byzantine Generals Problem

• Boon Thau Loo

• CS294-4

Overview

• Motivation

• Problem Definition

• Impossibility?

• Solutions (Oral and signed messages)

• Practical Use?

• Conclusions

Motivation

• Coping with failures in computer systems

• Failed component sends conflicting information to different parts of system.

• Agreement in the presence of faults.

• P2P Networks?

• Good nodes have to “agree to do the same thing”.
• Faulty nodes generate corrupted and misleading messages.
• Non-malicious: Software bugs, hardware failures, power failures
• Malicious reasons: Machine compromised.

Problem Definition

• Generals = Computer Components

• The abstract problem…

• Each division of Byzantine army is directed by its own general.
• There are n Generals, some of which are traitors.
• All armies are camped outside enemy castle, observing enemy.
• Communicate with each other by messengers.
• Requirements:
• G1: All loyal generals decide upon the same plan of action
• G2: A small number of traitors cannot cause the loyal generals to adopt a bad plan
• Note: We do not have to identify the traitors.

Naïve solution

• ith general sends v(i) to all other generals

• To deal with two requirements:

• All generals combine their information v(1), v(2), .., v(n) in the same way
• Majority (v(1), v(2), …, v(n)), ignore minority traitors

• Naïve solution does not work:

• Traitors may send different values to different generals.
• Loyal generals might get conflicting values from traitors

• Requirement: Any two loyal generals must use the same value of v(i) to decide on same plan of action.

Reduction of General Problem

• Insight: We can restrict ourselves to the problem of one general sending its order to others.

• Byzantine Generals Problem (BGP):

• A commanding general (commander) must send an order to his n-1 lieutenants.

• Interactive Consistency Conditions:

• IC1: All loyal lieutenants obey the same order.
• IC2: If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.

• Note: If General is loyal, IC2 => IC1.

• Original problem: each general sends his value v(i) by using the above solution, with other generals acting as lieutenants.

3-General Impossibly Example

• 3 generals, 1 traitor among them.

• Two messages: Attack or Retreat

• Shaded – Traitor

• L1 sees (A,R). Who is the traitor? C or L2?

• Fig 1: L1 has to attack to satisfy IC2.

• Fig 2: L1 attacks, L2 retreats. IC1 violated.

General Impossibility

• In general, no solutions with fewer than 3m+1 generals can cope with m traitors.

• Proof by contradiction.

• Assume there is a solution for 3m Albanians with m traitors.
• Reduce to 3-General problem.

Solution I – Oral Messages

• If there are 3m+1 generals, solution allows up to m traitors.

• Oral messages – the sending of content is entirely under the control of sender.

• Assumptions on oral messages:

• A1 – Each message that is sent is delivered correctly.
• A2 – The receiver of a message knows who sent it.
• A3 – The absence of a message can be detected.

• Assures:

• Traitors cannot interfere with communication as third party.
• Traitors cannot send fake messages
• Traitors cannot interfere by being silent.

• Default order to “retreat” for silent traitor.

Oral Messages (Cont)

• Algorithm OM(0)

• Commander send his value to every lieutenant.
• Each lieutenant (L) use the value received from commander, or RETREAT if no value is received.

• Algorithm OM(m), m>0

• Commander sends his value to every Lieutenant (vi)
• Each Lieutenant acts as commander for OM(m-1) and sends vi to the other n-2 lieutenants (or RETREAT)
• For each i, and each j<>i, let vj be the value lieutenant i receives from lieutenant j in step (2) using OM(m-1). Lieutenant i uses the value majority (v1, …, vn-1).
• Why j<>i? “Trust myself more than what others said I said.”

Restate Algorithm

• OM(M):

• Commander sends out command.
• Each lieutenant acts as commander in OM(m-1). Sends out command to other lieutenants.
• Use majority to compute value based on commands received by other lieutenants in OM(m-1)

• Revisit Interactive Consistency goals:

• IC1: All loyal lieutenants obey the same command.
• IC2: If the commanding general is loyal, then every loyal lieutenant obeys the command he sends.

Example (n=4, m=1)

Example (n=4, m=1)

Expensive Communication

• OM(m) invokes n-1 OM(m-1)

• OM(m-1) invokes n-2 OM(m-2)

• OM(m-2) invokes n-3 OM(m-3)

• …

• OM(m-k) will be called (n-1)…(n-k) times

• O(nm) – Expensive!

Solution II: Signed messages

• Previous algorithm allows a traitor to lie about the commander’s orders (command). We prevent that with signatures to simplify the problem.

• By simplifying the problem, we can cope with any number of traitors as long as their maximum number (m) is known.

• Additional Assumption A4:

• A loyal general’s signature cannot be forged.
• Anyone can verify authenticity of general’s signature.

• Use a function choice(…) to obtain a single order

• choice(V) = v if v if the only elem. in V
• choice(V) = RETREAT if V is empty

Signed Messages (Cont)

• Each lieutenant maintains a set V of properly signed orders received so far.

• The commander sends a signed order to lieutenants

• A lieutenant receives an order from someone (either from commander or other lieutenants),

• Verifies authenticity and puts it in V.
• If there are less than m distinct signatures on the order
• Augments orders with signature
• Relays messages to lieutenants who have not seen the order.

• When lieutenant receives no new messages, and use choice(V) as the desired action.

• If you want to protect against more traitors, increase m

Algorithm’s Intuition

• All loyal lieutenants compute the same set of V eventually, thus choice(V) is the same (IC1)

• If the commander is loyal, the algorithm works because all loyal lieutenants will have the properly signed orders by round 1 (IC2)

• What if the commander is not loyal?

Missing Communication Paths

• What if not all generals can reach all other generals directly?

• P-regular graph – Each node has p regular neighbors.

• 3m-regular graph has minimum of 3m+1 nodes

• Paper shows algorithm for variant of oral message algorithm – OM(m,p). Essentially same algorithm except that each lieutenant forwards orders to neighbors.

• Proofs that OM(m,3m) solves BGP for at most m traitors.

• I.e. if the communication graph is 3m-regular, and there are at most m traitors, the problem can still be solved.

Practical use of BGP?

• What does it take for majority voting to work?

• Input synchronization (order from commander) of non-faulty (loyal) processors to produce same outputs (decisions). (IC1)
• If input unit (commander) is non-faulty (loyal),all non-faulty processes use the value it provides as input (IC2)

• A1 – Every message sent by non-faulty process is delivered correctly.

• Failure of communication line cannot be distinguished from failure of nodes.
• OK because we still are tolerating m failures.

• A2 – A processor can determine origin of message

• A4 makes this obsolete.

Practical Use of BGP (Cont..)

• A3 – Absence of a message can be detected.

• Timeouts or synchronized clocks

• A4 – Unforgeable signatures. Anyone can verify authenticity of signature

• Message signed by i = (M, Si(M))
• If i is not faulty, no one can generate Si(M). Faulty processor used for generating signatures?
• Given M and X, anyone can verify if X=Si(M)

Concluding thoughts

• BGP solutions are expensive (communication overheads and signatures)

• Use of redundancy and voting to achieve reliability. What if >1/3 nodes (processors) are faulty?

• 3m+1 replicas for m failures. Is that expensive?

• Tradeoffs between reliability and performance (E.g. Oceanstore’s primary and secondary replicas)

• How would you determine m in a practical system?