Byzantine Generals Problem in Distributed Systems
Problem Formulation
Attack
Attack
Attack
Retreat
Retreat
Retreat
Retreat
Attack
Requirements
-
Consistency
-
Termination
-
Validity
1
2
Round 1: leader proposes to all
Round 2: all-to-all, commit upon f + 1 votes
(assume messages are signed)
Protocol: First Try
3
v
v’
v
v
’
Leader may equivocate
Check for equivocation before committing,
i.e., commit = f + 1 votes and no equivocation
Protocol: Faulty Leader (1)
4
Cannot violate consistency
But can hurt progress
v
v
v
Protocol: Faulty Leader (2)
or cause replicas to progress differently
5
propose
vote
n = 2f + 1
Replica 1
Replica 2
Replica 3
Leader 1
N
e
w
l
e
a
d
e
r
n
e
e
d
s
t
o
c
o
l
l
e
c
t
s
t
a
t
u
s
a
n
d
a
t
t
a
c
h
s
t
a
t
u
s
r
e
p
o
r
t
s
w
h
e
n
p
r
o
p
o
s
i
n
g
Leader 2
status
( v, status )
v
Protocol: Leader Change
6
Run (status, propose, commit) in iterations
Leader 2
status
status
propose
Protocol: Second Try
7
status
Leader can still cheat
Group 1 includes f faulty replicas
Make replica 2 commit on v
v
v
v
Protocol: Faulty Leader (3)
8
status
(v’, status)
v’
v
v’
Replica 2 committed on v, and vouches for it
New leader: “Replica 2 didn’t send status”
nil
Protocol: Faulty Leader (3)
9
status
v
v
v
notify
v
v
status
Want: 1 honest commit
= f + 1 honest vouch
An accept/notify round after commit
Cause and Solution
10
(status, propose, commit, notify) in iterations
Core Protocol
propose
vote
n = 2f + 1
Group 1
Replica 2
Group 3
Leader 1
status
notify
status
Leader 2
propose
When do Replicas Terminate?
status
v
v
v
notify
v
v
status
Terminate after receiving f+1 notify messages
11
Consistency
Suppose h is the first honest replica to commit on a value v*
in iteration k*,
-
1 honest commit = f + 1 honest accept [Ensured by the Notify round]
-
Byzantine replicas cannot commit on v’’ != v* in iteration k*
2. No other value v’ can be proposed in iterations k’ ≥ k*
1.
A replica h’ cannot commit on v’’ != v* in iteration k*
-
h’ must received f+1 commit messages on v’’
-
At least one of the f+1 messages is from an honest replica, say h’’
-
h’’ would have sent v’’ to h and h would detect equivocation, a
contradiction
12
Termination
Liveness/Termination: Honest leader
termination
status
(v, status)
v
v
v
nil
13
Adapting to Byzantine Broadcast
1.
How are leaders elected?
2.
What value does the first leader propose?
14
15
propose
vote
n = 2f + 1
Group 1
Replica 2
Group 3
Leader 1
status
notify
status
- Designated sender s with value v
- Validity? Agreement, termination are satisfied
- Introduce a pre-round
Byzantine Broadcast
Sender s
pre-round
v
v
v
16
propose
vote
n = 2f + 1
Group 1
Replica 2
Group 3
Leader 1
status
notify
status
Pre-round, (status, propose, vote, notify),
…
Assuming random leaders*, 2 iterations (8 rounds) in expectation,
Byzantine Broadcast
Sender s
pre-round
v
v
v
•
Round complexity
•
Message complexity
•
Byzantine Threshold
•
Type of adversary
17
Metrics
•
Round complexity: O(1) rounds, 10 rounds in expectation without
considering election
•
Message complexity: O(N
2
) signatures
•
Byzantine Threshold: Minority
•
Type of adversary: static
18
Metrics
•
Round complexity:
O(1) rounds, 10 rounds in expectation without
considering election
N rounds
•
Message complexity:
O(N
2
) signatures
O(N
2
f) messages
•
Byzantine Threshold:
Minority
to N-2 faults
•
Type of adversary: static
19
Dolev-Strong Protocol
20
The synchrony model has two requirements:
-
Bounded message delay
-
Locked-step execution
Replica 1
Replica 2
Synchrony in Practice?
21
new-day
Run every “day”:
-
Send “sync” if a day has passed locally
-
Upon f+1 “sync”, start new day and broadcast
sync
BFT Clock Synchronization
22
BFT Clock Synchronization
- Run every “day”:
-
Send “sync” if a day has passed locally
-
Upon f+1 “sync”, start new day and broadcast
-
|clk(i)
–
clk(j)| < d when a new day starts
-
|clk(i)-clk(j)| < d + t
-
Round time = d + (d + t)
Lemma (Informal):
For bounded message delay d, maximum clock drift b/w two
honest replicas in a “day” is t, then set round time = 2d + t.
Key Idea
P
a
x
o
s
Not Byzantine,
asynchronous
f
<
n/2
P
B
F
T
Byzantine,
asynchronous
f
<
n/3
quorum = 2f + 1
O
u
r
P
r
o
t
o
c
o
l
Byzantine,
synchronous
f
<
n/2
Quorum
intersection
at 1 node
Quorum
intersection
at f+1 nodes
Pre-commit quorum of f+1
Post-commit quorum of 2f+1
S
y
n
c
h
r
o
n
y
!
quorum = f + 1
23
"The Byzantine Generals Problem addresses how a group of generals, some of whom may be traitors, can reach a consensus on a battle plan while ensuring consistency, termination, and validity. Various protocols are explored to handle challenges such as faulty leaders, consistency violations, and cheating replicas in distributed systems."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Problem Formulation Byzantine Generals Problem Byzantine Generals Problem n n Byantine generals ( f f traitors) need to agree on a battle plan Attack Attack Requirements - Consistency - Termination - Validity Retreat Attack Attack Retreat Retreat Retreat 1
Protocol: First Try Round 1: leader proposes to all Round 2: all-to-all, commit upon f + 1 votes (assume messages are signed) Leader 1 Replica 1 Replica 2 Replica 3 n = 2f + 1 vote propose 2
Protocol: Faulty Leader (1) Leader may equivocate Check for equivocation before committing, i.e., commit = f + 1 votes and no equivocation Leader 1 Replica 1 v v Replica 2 v v Replica 3 n = 2f + 1 vote propose 3
Protocol: Faulty Leader (2) Cannot violate consistency But can hurt progress or cause replicas to progress differently Leader 1 Replica 1 Replica 2 v v v Replica 3 n = 2f + 1 vote propose 4
Protocol: Leader Change New leader needs to collect status reports when proposing status and attach status Leader 2 Leader 1 Replica 1 Replica 2 v Replica 3 n = 2f + 1 vote propose status 5
Protocol: Second Try Run (status, propose, commit) in iterations Leader 2 Leader 1 Replica 1 Replica 2 Replica 3 n = 2f + 1 propose vote propose status status 6
Protocol: Faulty Leader (3) Leader can still cheat Group 1 includes f faulty replicas Make replica 2 commit on v Leader 1 Group 1 v v v Replica 2 Group 3 n = 2f + 1 vote propose status 7
Protocol: Faulty Leader (3) Replica 2 committed on v, and vouches for it New leader: Replica 2 didn t send status Leader 1 Group 1 v Replica 2 v nil v Group 3 n = 2f + 1 vote propose status 8
Cause and Solution Want: 1 honest commit = f + 1 honest vouch An accept/notify round after commit Leader 1 Group 1 v v v v Replica 2 v Group 3 n = 2f + 1 notify vote propose status status 9
Core Protocol (status, propose, commit, notify) in iterations Leader 2 Leader 1 Group 1 Replica 2 Group 3 propose vote notify propose status status n = 2f + 1 10
When do Replicas Terminate? Terminate after receiving f+1 notify messages Leader 1 Group 1 v v v v Replica 2 v Group 3 n = 2f + 1 notify vote propose status status 11
Consistency Suppose h is the first honest replica to commit on a value v* in iteration k*, 1. A replica h cannot commit on v != v* in iteration k* - h must received f+1 commit messages on v - At least one of the f+1 messages is from an honest replica, say h - h would have sent v to h and h would detect equivocation, a contradiction 2. No other value v can be proposed in iterations k k* - 1 honest commit = f + 1 honest accept [Ensured by the Notify round] - Byzantine replicas cannot commit on v != v* in iteration k* 12
Termination Liveness/Termination: Honest leader termination Leader 3 Group 1 v Replica 2 v nil v Group 3 n = 2f + 1 vote propose status 13
Adapting to Byzantine Broadcast 1. How are leaders elected? 2. What value does the first leader propose? 14
Byzantine Broadcast - Designated sender s with value v - Validity? Agreement, termination are satisfied - Introduce a pre-round Sender s v v Leader 1 Group 1 v Replica 2 Group 3 vote notify propose status pre-round status n = 2f + 1 15
Byzantine Broadcast Pre-round, (status, propose, vote, notify), Assuming random leaders*, 2 iterations (8 rounds) in expectation, Sender s v v Leader 1 Group 1 v Replica 2 Group 3 vote notify propose status pre-round status n = 2f + 1 16
Metrics Round complexity Message complexity Byzantine Threshold Type of adversary 17
Metrics Round complexity: O(1) rounds, 10 rounds in expectation without considering election Message complexity: O(N2) signatures Byzantine Threshold: Minority Type of adversary: static 18
Dolev-Strong Protocol Round complexity: O(1) rounds, 10 rounds in expectation without considering election N rounds Message complexity: O(N2) signatures O(N2f) messages Byzantine Threshold: Minority to N-2 faults Type of adversary: static 19
Synchrony in Practice? The synchrony model has two requirements: - Bounded message delay - Locked-step execution Replica 1 Replica 2 20
BFT Clock Synchronization Run every day : - Send sync if a day has passed locally - Upon f+1 sync , start new day and broadcast Replica 1 Replica 2 Replica 3 n = 2f + 1 sync new-day 21
BFT Clock Synchronization - Run every day : - Send sync if a day has passed locally - Upon f+1 sync , start new day and broadcast - |clk(i) clk(j)| < d when a new day starts - |clk(i)-clk(j)| < d + t - Round time = d + (d + t) Lemma (Informal): For bounded message delay d, maximum clock drift b/w two honest replicas in a day is t, then set round time = 2d + t. 22
Key Idea Paxos Paxos Our Protocol Our Protocol Byzantine, synchronous f < n/2 PBFT PBFT Byzantine, asynchronous f < n/3 Not Byzantine, asynchronous f < n/2 quorum = f + 1 quorum = 2f + 1 Pre-commit quorum of f+1 Synchrony! Synchrony! Quorum intersection at 1 node Quorum intersection at f+1 nodes Post-commit quorum of 2f+1 23
