Byzantine Generals Problem Anthony Soo Kaim

Byzantine Generals Problem

• Anthony Soo Kaim

• Ryan Chu

• Stephen Wu

Overview

• The Problem

• Two Solutions

• Oral Messages
• Signed Messages

• Missing Communication Paths

• Reliable Systems

• Conclusion

The Problem

Background

• Important to have reliable computer systems

• Two solutions to ensuring a reliable system

• Having components that never fail
• Ensure proper handling of cases where components fail

• Byzantine Generals Problem

Problem

• Divisions of the Byzantine army camped outside the walls of an enemy city.

• Each division is led by a general.

• Generals decide on a common plan of action.

Problem – Types of Generals

• There are two types of generals

• Loyal Generals
• Traitor Generals

Problem – Conditions

• Two conditions must be met:

• All loyal generals decide upon the same plan of action.
• A small number of traitors cannot cause the loyal generals to adopt a bad plan.

Problem – Not a Bad Plan

• A plan that is not bad is defined in the following way:

• Each general sends his observation to all other generals.
• Let v(i) be the message communicated by the ith general.
• The combination of the v(i) for i = 1, …, n messages received determine a plan that is not bad.

Problem – Example Not a Bad Plan

• General 2 receives ATTACK, ATTACK.

• General 3 receives ATTACK, ATTACK.

• So Not a Bad Plan is to ATTACK

Problem – Not a Bad Plan Flaw

• Assumed that every general communicates the same v(i) to every other general.

• A traitor general can send different v(i) messages to different generals.

Problem – Example Flaw

• General 2 receives ATTACK, ATTACK.

• General 3 receives RETREAT, ATTACK.

• Is Not a Bad Plan to ATTACK or RETREAT?

Problem – New Conditions

• The new conditions are:

• Any two loyal generals use the same value of v(i).
• If the ith general is loyal, then the value that he sends must be used by every loyal general as the value of v(i).

Byzantine Generals Problem

• A commander general giving orders to his lieutenant generals.

• Byzantine Generals Problem – A commanding general must send an order to his n-1 lieutenant generals such that:

• IC1. All loyal lieutenants obey the same order.
• IC2. If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.
• These are called the interactive consistency conditions.

Impossibility Results

• When will the Byzantine Generals Problem fail?

• The problem will fail if 1/3 or more of the generals are traitors.

Impossibility Results – Example

• L1 received the commands ATTACK, RETREAT

• L1 doesn’t know which general is a traitor.

Impossibility Results – Example 2

• L1 again received the commands ATTACK, RETREAT

• L1 doesn’t know which general is a traitor.

Impossibility Results Generalization

• No solution when:

• Fewer than 3m + 1 generals;
• m = number of traitor generals

Impossibility Results - Application

• Utilized in clock synchronization as described in Dolev et al. [1986]

• N > 3f

• N = number of clocks
• f = number of clocks that are faulty

• Same as the Byzantine Problem!

A Solution with Oral Messages

Solution with Oral Messages

• Assumptions:

• A1: Every 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.

Solution with OM – Definition

• majority(v1, …, vn-1)

• If the majority of the values vi equal v, then majority(v1, …, vn-1) is v.
• If a majority doesn’t exist, then the function evaluates to RETREAT.

Solution with OM – Algorithm

• Case where m = 0 (No traitors)

• Algorithm OM(0)

• The commander sends his value to every lieutenant.
• Each lieutenant uses the value he receives from the commander, or uses the value RETREAT if he receives no value.

Solution with OM – Algorithm

• Algorithm OM(m), m > 0

• The commander sends his value to every lieutenant.
• For each i, let vi be the value lieutenant i receives from the commander, or else be RETREAT if he receives no value. Lieutenant i acts as the commander in Algorithm OM(m-1) to send the value vi to each of the n – 2 other lieutenants.
• For each i, and each j ≠ i, let vj be the value lieutenant i received from lieutenant j in step 2 (using OM(m-1)), or else RETREAT if he received no value. Lieutenant i uses the value majority(v1, …, vn-1).

Solution with OM – Example

• n=4 generals; m=1 traitors

• L2 calculates majority(ATTACK, ATTACK, RETREAT) = ATTACK

Solution with OM – Example

• n=4 generals; m=1 traitors

• L1, L2, L3 calculate majority(x, y, z)

Proof of algorithm OM(m)

• Lemma 1. For any m and k, OM(m) satisfies IC2 if there are more than 2k + m generals and at most k traitors

• Proof by induction on m:

• Step 1: loyal commander sends v to all n – 1 lieutenants.
• Step 2: each loyal lieutenant applies OM(m – 1) with n – 1 generals.
• By hypothesis, we have n – 1 > 2k + (m – 1) ≥ 2k.
• k traitors at most, so a majority of the n – 1 lieutenants are loyal. Each loyal lieutenant has vi = v for a majority of the n – 1 values, and therefore majority(…) = v

Proof of algorithm OM(m)

• Theorem 1. For any m, OM(m) satisfies conditions IC1 and IC2 if there are more than 3m generals and at most m traitors

• Proof by induction on m:

• For no traitors, OM(0) satisfies IC1 and IC2. Assume validity for OM(m – 1) and prove OM(m) for m > 0.
• Loyal commander: k = m from Lemma 1, so OM(m) satisfies IC2.
• Traitorous commander: must also show IC1 is met:
• m – 1 lieutenants will be traitors. There are more than 3m generals and 3m – 1 lieutenants, and 3m – 1 > 3(m – 1), so OM(m – 1) satisfies IC1

A Solution with Signed Messages

Solution with Signed Messages

• Simplify the problem by allowing generals to send unforgeable, signed messages

• New assumption A4:

• A loyal general’s signature cannot be forged, and any alteration of the contents of his signed messages can be detected.
• Anyone can verify the authenticity of a general’s signature.

Solution with Signed Messages

• New function: choice(V), takes in a set of orders and returns a single order. Requirements:

• If V contains a single element v, choice(V) = v
• choice(empty set) = retreat

• Notation for signed messages:

• x : i denotes the value x is signed by General i
• v : j : i denotes v is signed by j, and v : j is signed by i
• Each lieutenant maintains a set Vi, containing the set of properly signed orders he has received so far

Algorithm SM(m)

• Commander signs and sends v to every lieutenant.

• For each i:

• If i receives a message v : 0 from the commander and he has not yet received any order, then Vi = {v} and he sends message v : 0 : i to every other lieutenant.
• If i receives a message v : 0 : ji … jk and v is not in Vi, then add v to Vi. If k < m, then send the message v : 0 : ji … jk : i to every lieutenant other than ji … jk

• For each i:

• when lieutenant i will receive no more messages, he obeys order choice(Vi).

• Algorithm SM(1); the commander is a traitor

Proof of algorithm SM(m)

• Theorem 2. For any m, SM(m) solves the Byzantine Generals Problem if there are at most m traitors.

• Loyal commander: sends v : 0 to all lieutenants, which cannot be forged. A loyal lt will receive only v : 0

• Vi will contain only v, showing IC2

• Traitorous commander: prove IC1 by showing if i puts order v into Vi in step 2, then j must also put order v into Vj in step 2.

• i receives message v : 0 : j1 : … : jk. Is j one of the ji?

• If not, one of j1 … jk must be loyal, who sent j the value v

Missing Communication Paths

Missing Communication Paths

• New restriction: physical barriers that may restrict sending. The generals now form the nodes of a simple, finite, undirected graph

• A set of nodes {i1, …, ip} is a regular set of neighbors of node i if: each ij is a neighbor of i, and
• for any general k different from i, there exist paths pj,k from ij to k not passing through i such that any two different paths pj,k have no node in common other than k
• G is said to be p-regular if every node has a regular set of neighbors consisting of p distinct nodes

P-regular graphs

Algorithm OM(m, p)

• Choose regular set of neighbors N of the commander consisting of p lieutenants

• Commander sends his value to every lieutenant in N

• For each i in N, lieutenant i receives value vi from the commander, or else RETREAT if he receives no value. i sends vi to every other lieutenant k as follows:

• m = 1: send the value along the path pi,k
• m > 1: act as the commander in OM(m – 1, p -1), with the original commander removed from graph G

• For each k and i in N with i ≠ k, let vi be the value Lieutenant k received from i in step 2, or RETREAT if he received no value. Lieutenant k uses the value majority(vi1, …, vip), where N = {i1, …, ip}

Proof of algorithm OM(m, p)

• Similar to the proof for OM(m)

• Lemma 2. For any m > 0 and any p ≥ 2k + m, OM(m, p) satisfies IC2 if there are at most k traitors

• Theorem 3: For any m > 0 and any p ≥ 3m, OM(m, p) solves the Byzantine Generals Problem if there are at most m traitors

Missing paths for Signed Messages

• Oral message solution is overly restrictive

• We can extend signed messages more easily!

• Theorem 4. For any m and d, if there are at most m traitors and the sub-graph of loyal generals has diameter d, then SM(m + d – 1) solves the Byzantine Generals Problem.

• Corollary. If the graph of loyal generals is connected, then SM(n – 2) solves the Byzantine Generals Problem.

Reliable Systems

Implementation of Reliable Systems

• How to implement?

• Intrinsically reliable circuit components
• Redundancy – use multiple processors
• Each processor computes same result
• Majority vote to obtain one result
• Examples
• Protect against failure of a single chip
• Missile defense system

Majority Voting

• Assumption: all nonfaulty processors produce the same output

• True as long as all use same input
• Problem: processors can receive different input values.
• Any single input value comes from a single physical component
• Malfunctioning component can give different values
• Non-faulty component can give different values if read while value is changing

Conditions for a Reliable System

• All nonfaulty processors must use the same input value (so they produce the same output)
• If the input unit is nonfaulty, then all nonfaulty processes use the value it provides as input (so they produce the correct output)

• Really just IC1 and IC2.

• Commander  Input unit
• Lieutenants  Processors
• Loyal  Nonfaulty

A Hardware Solution

• A hardware solution for the input problem?

• Tempting, but unfeasible
• Example: make all processors read from one wire
• Faulty input unit could send marginal signal
• Different processors could interpret as a 0 or a 1
• No way to guarantee same value is used without having processors communicate among themselves

Faulty Input Units

• What about faulty input units?

• Byzantine General’s solution can only guarantee same value is used
• If input is important, use redundant input units
• Redundant inputs cannot achieve reliability in itself

Nonfaulty Input Units

• What if a nonfaulty input unit gives different values because it is read while the value is changing?

• Still want processors to obtain reasonable input values
• Take the choice and majority functions to be the median function
• Assume reasonable range of input values  value obtained by processors is within the range of input values provided

Reliable Computing Systems

• How do we apply the solutions OM(m) and SM(m) to computing systems?

• “Easy” to implement the algorithm in a processor

• Problem is in implementing the message passing system

• Need to meet assumptions A1 – A4

Assumption A1

• A1: Every message sent by a nonfaulty processor is delivered correctly.

• For OM(m), communication line failure indistinguishable from processor failure

• Works with up to m failures (processor or communication line)

Assumption A1

• SM(m) is insensitive to communication line failure

• Assumes a failed connection cannot result in the forgery of a signed message
• Communication line failure equivalent to removing the line
• Reduces connectivity of graph

Assumption A2

• A2: A processor can determine the originator of the message received.

• Means a faulty processor cannot impersonate a nonfaulty one

• If we assume messages are signed, we can get rid of this assumption

Assumption A3

• A3: The absence of a message can be detected.

• Use timeouts

• Requires two assumptions:
• Fixed max time needed for the generation and transmission of a message
• The sender and receiver have clocks that are synchronized to within some fixed maximum error

Assumption A3 – Using Timeouts

• Any message sent should be received by time: T + τ + µ

• µ: max generation and transmission delay
• τ: max difference between clocks
• T: time at which processor begins to generate message

• Ex. For SM(m), a processor must wait until time T0 + k(τ + µ)

• T0 : Time at which commander sends message
• k: number of signatures on message

Assumption A4

• A4: Processors can sign their messages in such a way that a nonfaulty processor’s signature cannot be forged.

• What is a signature?

• Redundant information Si(M)
• Generated by process i from a message M
• A message signed by i is sent with the signature:
• (M, Si(M))

Assumption A4

• Vulnerable to “replay” attacks

• Use sequence numbers to guarantee uniqueness

• To meet parts (a) and (b) of A4, Si must have the following two properties:

• If processor i is nonfaulty, the no faulty processor can generate Si(M)
• Given M and X, any process can determine if X = Si(M)

Assumption A4 – Function Si

• Property (a) is impossible to guarantee

• We can make the probability of violation as small as we want (… and as reliable as we want)
• How? Depends on types of faults we expect…
• Random Malfunction
• Make Si a “randomizing” function
• Malicious Intelligence
• Ex. A hacker trying to disrupt the system
• Becomes a cryptography problem

Conclusion

Complexity

• Solutions OM and SM are expensive in both time and number of messages required

• Both require message paths of length up to m + 1
• This is optimal.
• For graphs not completely connected, require paths with length up to m + d
• d: diameter of the subgraph of loyal generals
• Both require up to (n – 1)(n – 2) … (n – m – 1) messages to be sent.
• Can be reduced by combining messages.

Conclusion

• Achieving reliability in the face of arbitrary malfunctioning is a difficult problem

• Solution inherently expensive

• Can reduce cost by making assumptions of type of failure that can occur
• Reduces reliability