Byz Problem Informal EIG Example Attributes Quiz TMR
The Byzantine Agreement – An Introduction
Radu Nicolescu Department of Computer Science University of Auckland
2 Sep 2020
1/30
Byz Problem Informal EIG Example Attributes Quiz TMR
1 The Byzantine agreement problem
2 Informal example
3 EIG tree
4 Example
5 Attributes
6 Quiz
7 Triple modular redundancy
2/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine agreement story
• Name is an allegory based on Byzantium’s tumultuous history…
• http://en.wikipedia.org/wiki/Byzantium
• http://en.wikipedia.org/wiki/Byzantine_Empire
4/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine agreement story
• N = 4 Byzantine armies, physically separated
• Generals start with their own initial decisions, 0 or 1
• They can communicate via N(N − 1)/2 = 6 reliable channels
• They must reach a common decision
• Problem: among them there may be F Byzantine traitors,
who may attempt to disrupt the agreement, by any means
• Deterministic agreement between loyal generals possible iff N ≥ 3F + 1 and communications are synchronous
5/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine agreement problem
• The N generals, basic story N = 4
• Complete graph KN (loopbacks possible),
with secure channels
• Generals’ initial choices can be different: attack or withdraw (database: commit or rollback; binary: 1 or 0)
• Agreement required on one of their initial choices
• Generals should either all attack or all withdraw
6/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine agreement problem
• However… among the N generals, there may be F traitors (faulty), thus only N − F are loyal (non-faulty)
• Typically: N = 4, F = 1 (or, N = 7, F = 2)
• In fact, the problem can be deterministically solved iff
N ≥ 3F + 1 (we’ll prove this later)
• We need two elves (loyals) for each orc plus one hobbit
(loyal): N ≥ F + 2F + 1 ,
• Algorithms: Pease, Shostak, Lamport (1980);
Lamport, Shostak, Pease (1982).
• Impossibility results: Fischer, Lynch, Paterson (1985) – FLP
7/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine failures
• A traitor can:
• behave correctly (!)
• stop cooperating (stop sending messages)
• send confusing messages (different messages to different directions)
• briefly: anything that could disrupt the agreement!
• The algorithm must cope with such extremely malevolent
adversaries
• The purpose is NOT to identify the traitors, but to ensure that the system continues to work properly (all loyal guys)
8/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine agreement conditions
• Termination: all non-faulty processes eventually decide • Agreement: no two non-faulty processes ever decide on
different values
• Validity: if all non-faulty processes start with the same initial value v ∈ V , then v is the only one possible decision value [STRONG]
• if the non-faulty processes start with different initial values, then the final decision could be any of these (as long as it is consistent)
9/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine agreement scenarios (N = 4)
Initial
Final
Notes
0000
0000
required
0001
0000
majority rule? NO, required (why?)
0011
vvvv
depending on a parameter v0
0111
1111
majority rule? NO, required (why?)
1111
1111
required
000*
000*
required
001*
0 0 0 * or 1 1 1 *
depending on parameter v0 and the orc
011*
0 0 0 * or 1 1 1 *
depending on parameter v0 and the orc
111*
111*
required
• The star (*) represents orc’s arbitrary or malevolent choices
• The algorithm we study – EIG – uses an internal parameter, v0, which (1) replaces missing or wrongly formatted messages, and (2) breaks ties
10/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Informal example
• The following agreement is required, between the elves: • Left: #2 and #3 should decide 0.
• Right: #1 and #2 should decide 1.
• Middle: #1 and #3 should reach a consistent decision.
• The orc processes have a perfect disrupting strategy (next)
12/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Informal example
• Consider that they send to each other their initial values:
• Process #3 cannot differentiate between the left and middle cases and should therefore take the same decision in both cases, i.e., 0.
• Process #1 cannot differentiate between the right and middle cases and should therefore take the same decision in both cases, i.e., 1.
• Thus, no common decision is possible for the middle case • Conclusion: 1 round is not enough…
13/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Informal example
• Consider that on the 2nd round the elves relay to each other the value received from the other process on the 1st round:
• Process #3 still cannot differentiate between the left and middle cases…
• Process #1 still cannot differentiate between the right and middle cases…
• Thus, no common decision is possible for the middle case
• Conclusion: 2 rounds are not enough… arguments can continue for any number of rounds…
14/30
Byz Problem Informal EIG Example Attributes Quiz TMR
EIG tree
• EIG = Exponential Information Gathering
• Here,F=1,N=3F+1=4,L=F+1=2 • Description in Lynch’s monograph
16/30
Byz Problem Informal EIG Example Attributes Quiz TMR
EIG tree
• Each non-faulty process maintains its own copy of the EIG tree
• The top-down val (α) attributes: first, the levels are filled
top-down, according to received messages
• The bottom-up newval (β) attributes: next, the levels are recomputed bottom-up, without messaging, according to a local majority rule
• On each branch, there is at least one node with a label ending in the ID of a non-faulty node
• The first such nodes (top-down) are connected by a red cut
• The nodes on or above the red cut are common: they have
the same newval values, in all non-faulty processes
• Thus the final decision is common, for all non-faulty processes
• Full description in Lynch’s monograph – also our demo
17/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Faulty process ι1 sends out conflicting messages
Process
ι1
ι2
ι3
ι4
Initial choice
?
0
1
1
Faulty
Yes
No
No
No
Round 1 messages
(1, x)
(2, 0)
(3, 1)
(4, 1)
Round 2 messages
(2.1, 0) (3.1, y) (4.1, 1)
(1.2, 0)
(3.2, 1) (4.2, 1)
(1.3, 0) (2.3, 0)
(4.3, 1)
(1.4, 1) (2.4, 0) (3.4, 1)
… Final decision
?
0
0
0
2 14 3
• x=0,y=1toprocessι2
• x=0,y=0toprocessι3 –tryalsox=1,y=0 • x=1,y=1toprocessι4
Non-faulty processes are always able to reach a common decision: either all 0, as here – or all 1
19/30
Byz Problem Informal EIG Example Attributes Quiz TMR
EIG trees for non-faulty processes
λ
0 (a) T42,2 0
1234
0011 0011
234134124123
001000111111 001000111111
λ
1
(b) T43,2 0
1234
0011 0011
234134124123
001000011111 001000011111
λ
1 (c) T4,2 0
1234
• α by top-down messaging (3,1)
Process
Initial choice
Faulty
Round 1 messages
Round 2 messages
… Final decision
ι1
?
Yes
(1, x)
(2.1, 0) (3.1, y) (4.1, 1)
?
ι2
0
No
(2, 0)
(1.2, 0)
(3.2, 1) (4.2, 1)
0
ι3
1
No
(3, 1)
(1.3, 0) (2.3, 0)
(4.3, 1)
0
ι4
1
No
(4, 1)
(1.4, 1) (2.4, 0) (3.4, 1)
0
•L:(initial)ι →ι,ι,ι 13234
(4.3,1) •L:(relay)ι →ι,ι,ι
1011 001123234
234134124123
001000111111 001000111111
• β by bottom-up local voting • common final decision
20/30
Byz Problem Informal EIG Example Attributes Quiz TMR
The top-down val() attribute
How val() are filled (example):
• val(2…) is about what #2 said
• val(2) is what #2 directly said
• val(21) is what #1 said that #2 said
• If #1 is lying about #2 in val(21), then #3 & #4 will “mask” this by val(23) & val(24)
• invalid or missing messages are assumed to be v0
22/30
Byz Problem Informal EIG Example Attributes Quiz TMR
The bottom-up newval() attribute
newval()
• computed new value
• no messaging anymore
• decision taken by a local majority voting procedure • or, v0, if there is no majority
• this “masks” failures
• if any – within the accepted limits (n ≥ 3f + 1)
23/30
Byz Problem Informal EIG Example Attributes Quiz TMR
The bottom-up newval() attribute
24/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine quiz
26/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine quiz: decision 0
27/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byzantine quiz: decision 1
28/30
Byz Problem Informal EIG Example Attributes Quiz TMR
Byz vs Triple modular redundancy (TMR)
30/30