The Byzantine Generals Problem Leslie Lamport, Robert Shostak, Marshall Pease

The Byzantine Generals Problem

• Leslie Lamport, Robert Shostak, Marshall Pease

• Presented by Radu Handorean

Byzantine Generals Problem (metaphor)

GBP – the Generals

• Loyal Generals

• Behave according to THE algorithm which should ensure that
• They decide upon the same plan (A)
• A small number of traitors shouldn’t be able to force a bad decision (B)

• Traitorous Generals

• Try to mess the final decision
• Send any info they want

GBP – the Generals

• (A) => Every loyal general must obtain the same v(1)…v(n)

• (B) => If the ith general is loyal => v(i) must be used by all (loyal) generals

Byzantine Generals Problem (formal)

• 0 .. N-1 processes in a complete graph

• Process 0 needs to send a value v to all others such that

• (IC1) If process 0 is non faulty then any non faulty process i receives v
• (IC2) If processes i and j are non faulty, they receive the same value

• Note: 0 is non faulty, then IC1=>IC2

Impossibility Results – Oral Msg

• Oral message – the content is entirely under the control of the sender

• No solution if more than 1/3 of the generals are traitorous

Traitorous Lieutenant

Traitorous General

Impossibility Results – Generalization

• No solution with fewer than 3m+1 generals for m traitors

• Proof by contradiction: reduce the problem to the 3 generals problem

• Assume 3m (let’s call them Albanians) or fewer generals can cope with m traitors
• Build the solution with Byzantine generals

Proof

• 1 Byzantine simulates ~1/3 Albanians

• 1 Byzantine simulates 1 Albanian general & m-1 Albanian lieutenants (m, m, respectively)
• Max m traitor Albanians
• IC1 & IC2 hold for Albanians (assumed)
• IC1 & IC2 hold for Byzantine (implied)
• IMPOSSIBLE SOLUTION

Solution with Oral Messages

• A1. Every msg. is delivered correctly

• A2. The receiver knows where the msg. comes from

• A3.The absence of a msg. can be detected

• A1&A2 – a traitor cannot interfere with a msg. between others
• A3 – a traitor cannot drop msg.

Oral Messages – Cont.

• No order from a traitorous commander => RETREAT by default

• OM(m) – alg. for 3m+1 generals with at most m traitors

• Use the majority function for decision

• Majority value if exists or RETREAT
• Median value if they are an ordered set

OM(0)

• (1) The commander sends his value to each lieutenant

• (2) Each lieutenant uses the value from the commander or RETREAT if the commander is silent

OM(m)

• (1) The commander sends his value to each lieutenant (vi)

• (2) Each L acts as commander for OM(m-1) and sends Vi to the other n-2 (or RETREAT)

• (3) For each i and j!=i, Li receives vj from Lj in (2) (or RETREAT); Li uses majority(v1..vn-1)

Example m=1, n=4, L traitor

Example m=1, n=4, L traitor

OM(m) - Proof of Correctness

• Lemma1: for any m, k, OM(m) has IC2 for more than 2k+m generals and at most k traitors

• IC2: if the commander is loyal, every loyal general obeys commander’s order

• Proof: induction on m

• OM(0) – trivial
• m>0
• Commander sends v to n-1 lieutenants

OM(m) – Proof - Cont.

• Each loyal general applies OM(m-1) with n-1 generals
• (*) n>2k+m => n-1>2k+(m-1)
• >each loyal Li gets vj=v from each loyal Lj
• At most k traitors and (*) =>a majotiry of n-1 lieutenants are loyal

OM(m) – Proof – Cont.

• Theorem: OM(m) satisfies IC1 and IC2 if there are more than 3m generals and at most m traitors

• Proof: induction on m

• OM(0) satisfies IC1 and IC2 (no traitors)
• Commander = loyal & k=m in Lemma => IC2 => IC1
• Commander = traitor => at most m-1 traitorous lieutenants

OM(m) – Proof – Cont.

• There are more than 3m generals => more than 3m-1 lieutenants
• 3m-1>3(m-1) & apply induction
• (OM(m-1) satisfies IC1 & IC2)
• => for each j, any 2 loyal Ls get the same value for vj in step 3
• => any 2 loyal Ls get the same array (v1...vn-1) in step 3 => the same majority(…) => IC1

Solution with Written Messages

• Generals send unforgeable signed messages

• Add A4 to A1-A3:

• A loyal G’s signature cannot be forged and any alteration can be detected
• Anyone can verify the auth of a G’s signature

• NO assumptions about a traitorous G’s signature

New Solution

• C sends signed orders to Ls

• Each L adds its signature and forwards the message, etc…

• 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
• Any choice() function must have these properties

Notations

• x:i = msg. x signed by G i

• v:j:i = msg. v signed by Gs j and I

• G0 = commander (C)

• Vi = set of properly signed orders received by Li

• Loyal C => Vi has only 1 element
• Do NOT confuse with the set of msg. !!! (many different msg can carry the same order)

SM(m)

• Initially Vi = empty for each I

• (1) C signs and send v to each L

• (2) For each i:

• (A) if Li receives v:0 and Vi=empty
• (i) Vi={v}
• (ii) Send v:0:i to all other Ls
• (B) if Li receives v:j1…:jk and v not in Vi
• (i) Add v to Vi
• (ii) if k

• (3) When Li receives no more msg., he obeys choice(Vi)

SM(1) - Example

SM(1) – Proof

• Theorem2: SM(m) solves GBP for at most m traitors

• C = loyal => sends v:0 to all Ls
• Every loyal L receives v in (2)
• No loyal L can receive v’:0 in (2B)
• Vi = {v} for all i
• Loyal Ls obey choice() in (3) => IC2 => IC1
• C = traitorous

SM(m) – Proof – Cont.

• C = traitorous
• Loyal Li and Lj obey the same order in (3) if Vi = Vj from (2)
• If Li receives v in (2A), it sends it to Lj in (2Aii)
• If Li adds v to Vi in (2B) => must receive a first message v:j1…:jk

SM(m) – Proof – Cont.

• If j is one of the jr, v must have already been added to Vi
• If not
• (1) k
• (2) k=m : since C=traitor= > max m-1 traitor Ls => at least 1 of j1…jm is loyal
• This loyal L must have sent v to j so j has that order

Missing Communication Paths

• The Generals’ graph is no longer complete

Definitions

• (a) {i1,…,ip} is a regular set of neighbors of I if

• Each ij is a neighbor of I
• For any k!=i there are paths gj,k from ij to k not passing through i s.t. any 2 such path only have k in common

• A graph G is p-regular if any node has a set of p regular neighbors

• Note: a 3m-regular graph has min 3m+1 nodes

OM(m,p)

• G must be p-regular

• (0) N = p-regular set of C’s neighbors

• C sends the order to every L in N

• For each i in N, Li receives vi from C or RETREAT; Li sends vi to every other Lk as follows:

OM(m,p) – Cont.

• (A) if m=1, it sends along gj,k
• (B) if m>1, it acts as commander for OM(m-1, p-1), after removing C

• For each k and i in N, k!=i, Lk receives vi from Li, or vi=RETREAT; Lk uses majority(vi1,…, vip), where N = {i1,…ip}

OM(m, 3m) – GBP

• O(m,3m) solves GBP for at most m traitors (proof below)

• Lemma1: for any m>0 and any p>=2k+m, OM(m,p) satisfies IC2 for at most m traitors

• m=1
• L obtains majority(v1..vp)
• At most k traitors and p>=2k+1 => more than half of the p paths –> loyal Ls -> if C is loyal then the majority() if his command
• m>1

Lemma2 – Cont.

• m>1
• Assume for m-1
• If C = loyal, each of the p Ls in N has the correct order
• p>2k -> a majority are loyal & each sends the correct order
• Each loyal L gets a majority of correct orders

GBP – Cont.

• Theorem 3: for any m>0 and any p>=3m, OM(m,p) solves GBP for max. m traitors

• Lemma 2 & k=m => IC2
• C = loyal then IC2 implies IC1
• C = traitorous
• m=1 => all Ls = loyal and gj,k do not pass through C
• m>1: induction since p>=3m implies p-1>=3(m-1)

Comments

• For 3m+1 generals, 3m-regularity = complete connectivity

• IC2 cannot be satisfied if a message C->L is “routed” by traitors

• IC1 cannot be satisfied if L1 and L2 can only communicate via traitors

• These assumptions are too strong

SM(m)

• If the subgraph of loyal Ls is connected =>SM(n-2) is a solution (n=# of Gs) regardless of # of traitors

• Definition: the diameter of a graph is the smallest # of edges to connect any 2 nodes

GBP - SM

• Theorem 4: If there are at most m traitors, and d=the diameter of loyal Ls subgraph, SM(m-d+1) solves GBP

• Proof: similar to Theorem 2

SO WHAT ???

• Use of redundancy and voting to achieve reliability

• Majority voting

• All non faulty processes produce the same result (from the same input - e.g. 2 non faulty processors read a clock)
• If the input unit (G) is non faulty, all non faulty (loyal) processes (Ls) use the provided value

SO WHAT – Cont. A1..A3(A4)

• A1 – every msg. sent by a non faulty proc. Is delivered correctly

• The failure of a communication line cannot be distinguished from the failure of a component => max m failures
• Real life effect: lowers connectivity, does not forge information

SO WHAT – Cont. A1..A3(A4)

• A2 – a processor can determine the origin of a msg.

• Most important is that a faulty proc. cannot impersonate a non faulty one
• In practice we should use IPC over fixed lines rather than fancy network switching
• A4 obsoletes A2, is satisfied

SO WHAT – Cont. A1..A3(A4)

• A3 – the absence of a message can be detected

• Use of time-outs:
• Fixed maximum time to produce and deliver a message
• Sender’s and receiver’s clock’s are reasonably synchronized

SO WHAT – Cont. A1..A3(A4)

• A4 – processors sign messages s.t. a non faulty processor cannot forged

• Signature = redundant info.
• Message signed by i = (M, Si(M))
• Si must satisfy
• If I is non faulty, no other processor can generate Si(M) – cannot be guaranteed
• Random multiplication
• Malicious intelligence
• Given M and X, any processor can verify X=Si(M)

DO YOU STILL HAVE QUESTIONS?