Sync StopFail EIGStop Side ByzAuth
Fault Tolerant Consensus – Wrapup I
Radu Nicolescu Department of Computer Science University of Auckland
16 Oct 2020
1/19
Sync StopFail EIGStop Side ByzAuth
1 Synchronous network model
2 Stopping failures
3 EIGStop
4 Side by side
5 Byzantine agreement with authentication
2/19
Sync StopFail EIGStop Side ByzAuth
Synchronous network model
• All these algorithms are still based on the synchronous network model
• Even the simple stopping failure cannot be deterministically solved in the asynchronous network model
• FLP – Fischer, Lynch and Patterson
Impossibility of Asynchronous Distributed Consensus with a
Single Faulty Process
• Solutions for the asynchronous model use randomisation, failure detectors (partially synchronous model)
4/19
Sync StopFail EIGStop Side ByzAuth
Stopping failures model
• Much simplified version of the Byzantine agreement
• A failed process can only stop sending messages, forever
(no intermittent failures, recovery not considered)
• No possibility to send confusing messages
(i.e. different messages to different directions)
• TheproblemcanbesolvedforanyF ≤N−1, (notonlywhen3F ≤N−1)
6/19
Sync StopFail EIGStop Side ByzAuth
The Stopping agreement conditions – vs Byz
• 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
• If the processes start with different initial values, then the final decision could be any of these (as long as it is consistent)
7/19
Sync StopFail EIGStop Side ByzAuth
EIGStop
• EIG tree as in the EIGByz, F + 1 messaging rounds
• recall: F can be as high as N −1 (not at most (N −1)/3)
• Top-down val()’s as in the EIGByz, i.e. via messaging
• No bottom-up newval() attributes
• Final decision: set W of all non-null val()’s in EIG tree • all values at all levels! not just leaves
• nulls discarded! not assumed v0
• If W is singleton, W = {v}, then the decision is v
• Otherwise, if W is mixed, W = {0, 1}, then the decision is v0 • no voting! no tie breaking
9/19
Sync StopFail EIGStop Side ByzAuth
EIGStop example – assuming v0 = 1; nulls as –
• Process #1 : init 0; decision v0 = 1
• Process #2 : init 0; decision v0 = 1
• Process #3 : init 1; no decision;
fails after sending one 1st round message, to #1
P#1 0
001 0-0-1-
P#2 0
00- 0-0-1-
P#3 1
— ——
10/19
Sync StopFail EIGStop Side ByzAuth
EIGStop example – assuming v0 = 1; nulls as –
• Process #1 : init 0; decision 0
• Process #2 : init 0; decision 0
• Process #3 : init 1; no decision;
fails before sending any 1st round message
P#1 0
00- 0-0—
P#2 0
00- 0-0—
P#3 1
— ——
11/19
Sync StopFail EIGStop Side ByzAuth
EIGStop example – assuming v0 = 1; nulls as –
• WHAT IF scenario – NOT supported by this EIGStop protocol What if P#3 fails before sending any 1st round out-message
but would be allowed to recover and decide
• NO agreement
• Process #1 : init 0; decision 0
• Process #2 : init 0; decision 0
• Process #3 : init 1; decision v0 = 1;
P#1 0
00- 0000–
P#1 0
00- 0000–
P#3 1
001 0000–
12/19
Sync StopFail EIGStop Side ByzAuth
OptEIGStop
• Each process sends out only two messages
• First: its initial choice, to all the processes
• Second: a different value, to all the processes
• The first time it learns about a different value • Arbitrary choice, if there are more
13/19
Sync StopFail EIGStop Side ByzAuth
EIGStop vs EIGByz vs 3PC – assuming v0 = 0
• X indicates a faulty process, which fails from start, before sending any 1st round message
Initial
EIGStop
EIGByz
3PC
0000
0
0
0
0001
0
0
0
0011
0
0
0
0111
0
1
0
1111
1
1
1
000X
0
0
0
001X
0
0
0
011X
0
0
0
111X
1
1
0
15/19
Sync StopFail EIGStop Side ByzAuth
EIGStop vs EIGByz vs 3PC – assuming v0 = 1
• X indicates a faulty process, which fails from start, before sending any 1st round message
Initial
EIGStop
EIGByz
3PC
0000
0
0
0
0001
1
0
0
0011
1
1
0
0111
1
1
0
1111
1
1
1
000X
0
0
0
001X
1
1
0
011X
1
1
0
111X
1
1
0
16/19
Sync StopFail EIGStop Side ByzAuth
Complexity
• EIGStop
• Rounds: f + 1
• Messages: O((f + 1)n2) messages
• OptEIGStop messages: O(2n2) messages
• EIGByz – Additional requirement: n > 3f • Rounds: f + 1
• Messages: O((f + 1)n2) messages
• 3PC:
• Rounds: O(f + 1)
• Messages: O(fn) messages
17/19
Sync StopFail EIGStop Side ByzAuth
Byzantine agreement with authentication
• Assume that each process digitally signs its messages in a total safe way, e.g. based on a reliable unbreakable PKI/DSA…
• Is this reasonable?
• Problem with certificate weaknesses: What if a powerful
Byzantine faulty process is able to forge such signatures?
• Problem with authority: What if the certification authority itself is hacked or even turns into a Byzantine process?
• Anyway, assuming that such digital signatures are totally safe, Byzantine faulty nodes are not able to wreak much more havoc than a stopped process
• EIGStop can be adapted to solve the (slightly different) Byzantine agreement with authentication
• Faster/better/more general algorithms possible…
19/19