Byzantine Fault Tolerance: Protocols, Forensics, and Research
BFT Protocol Forensics
Kartik Nayak
Peiyao Sheng, Gerui Wang, Sreeram Kannan, Pramod Viswanath
State Machine Replication
A group of servers provide
the same interface as a
single non-faulty server even if some of the servers
are Byzantine faulty
(Safety) Any two non-faulty servers do not learn
different sequence of values
(Liveness)
A value proposed by a client will be
eventually executed by every non-faulty server
cmd
i
cmd
j
BFT Protocol Research
•
40 years of research
•
Byzantine Agreement:
•
Byzantine threshold:
t < n
•
Actual number of faults:
f
•
Safety and liveness:
f ≤ t
Tolerate
more
faults
Better
efficiency
Q: What happens when f > t?
BFT Protocol Forensics
•
What happens when
f > t
?
•
Safety and/or liveness can be violated
•
Forensic support:
provide irrefutable evidence of bad
behavior
•
Is it always possible?
•
What does it take to obtain such evidence?
for d > n-2t
BFT Protocol Forensics
Actual number of Byzantine parties (f)
n-t
t
Safe and live
Forensic support
(d = t+1)
No forensic support
d: Number of Byzantine replicas detected
Existing Works on Forensic Support for BFT
•
Multiple previous works
•
PeerReview, Casper, Polygraph, Grandpa BFT, …
•
To design protocols with forensic support (accountability)
•
Our goal: Analyze existing protocols based on
•
Number of Byzantine replicas detected
(d)
•
Number of witnesses
•
Distributedness
(k)
Today’s Talk
Byzantine parties held culpable (
d)
Honest parties involved (k
)
HotStuff
d = t + 1
k = 1
Algorand BA
d = 0
k = n - f (all honest parties)
HotStuff
•
Partially synchronous protocol, tolerates 1/3
rd
Byzantine
faults
[YMRGA’19]
propose(v, hQC)
vote2(v)
vote3(v)
precommitQC(v)
commitQC(v)
Messages in some view e
(2t+1 votes)
HotStuff: Key Invariant
vote3(v)
: “locked on
v
; will not vote differently”
propose(v, hQC)
vote1(v)
vote2(v)
vote3(v)
prepareQC(v)
precommitQC(v)
commitQC(v)
Messages in some view e
HotStuff: Key Invariant
vote3(v):
“locked on
v
; will not vote differently unless it is safe”
propose(v, hQC)
vote1(v)
vote2(v)
vote3(v)
prepareQC(v)
precommitQC(v)
commitQC(v)
Messages in some view e
hQC: highest prepareQC
known to leader
“it is safe”:
hQC
shared by leader is from a higher view
An Attack Across Views
No commits in these views
. . .
Q: Which parties are Byzantine?
No commits in these views
Hint:
D
is not, it did not
vote3(v)
. . .
Observe:
vote2
,
vote3
do not matter
Claim:
B
and
C
are culpable.
Claim: B and C are culpable
A
C
B
D
View e
commitQC(v)
“Party i commits v”
View e’
No commits in these views
Propose(v’, hQC)
commitQC(v’)
“Party j commits v’ ”
A: False,
hQC
can be a
prepareQC
on
v’
in some view
> e
vote3(v)
Holds for all views
> e
except the first one where
prepareQC
was formed
Identifying Culpable Replicas (Across Views)
A
C
B
D
View e
commitQC(v)
“Party i commits v”
View e’
Propose(v’, hQC)
commitQC(v’)
“Party j commits v’ ”
View e*
Propose(v’, hQC)
not vote1
vote1
vote1
vote1
vote3(v)
We’re locked on v
in view e
prepareQC(v’)
We are locked on
v’ or our locks
are older than e
e*
:
first higher view
prepareQC
for a different value was formed
(hQC from a lower view)
Identifying Culpable Replicas (Across Views)
•
Culpable replicas: Intersection of
commitQC(v)
and parties
forming the first
prepareQC(v’)
Q: Who has access to the first
prepareQC(v’)
formed in
e*
?
A: If
v’
was committed,
2t+1-f
honest parties hold
prepareQC(v’)
-
Many witnesses
Identifying Culpable Replicas (Across Views)
•
Culpable replicas: Intersection of
commitQC(v)
and parties
forming the first
prepareQC(v’)
Q: How do we know
e*
was the first such view?
A: Implementation details matter
-
Depending on information included with
vote1(v’)
, we can have
(a)
Single witness identifying
t+1
Byzantine replicas
(b)
Require multiple witnesses
(c)
Have no forensic support even after obtaining all honest
transcripts
Today’s Talk
Byzantine parties held culpable (
d)
Honest parties involved (k
)
HotStuff
d = t + 1
k = 1
Algorand BA
d = 0
k = n - f (all honest parties)
Algorand BA
•
Synchronous protocol, tolerating 1/3 faults
[CM’16]
•
Byzantine Agreement on a binary value
Algorand BA
•
Propagate local value
b
•
Receive values within a synchronous step:
•
#(0)
> 2t
, update
b
= 0 (terminate if step 1)
•
#(1)
> 2t
, update
b
= 1 (terminate if step 2)
•
Else
•
Step 1: set
b
= 0
•
Step 2: set
b
= 1
•
Step 3: set
b
= common coin
Step 1
Step 2
Step 3
Safety intuition
(f ≤ t)
: Suppose a party commits
b
= 0
-
All
(> 2t)
honest parties have
b
= 0
-
Honest parties never change their value to
b
= 1
Safety Violation when f > t: World 1
•
Propagate local value
b
•
Receive values within a synchronous step:
•
#(0)
> 2t
, update
b
= 0
•
#(1)
> 2t
, update
b
= 1
•
Else
•
Step 1: set
b
= 0
•
Step 2: set
b
= 1
•
Step 3: set
b
= common coin
Step 1
Step 2
Step 3
Safety intuition
(f ≤ t)
: Suppose a party commits
b
= 0
-
All
(> 2t)
honest parties have
b
= 0
-
Honest parties never change their value to
b
= 1
f > t
≤ 2t
can
Byzantine do not send 0
Honest parties switch to b = 1
World 1 Culprits: Parties who did not send b
•
Propagate local value
b
•
Receive values within a synchronous step:
•
#(0)
> 2t
, update
b
= 0
•
#(1)
> 2t
, update
b
= 1
•
Else
•
Step 1: set
b
= 0
•
Step 2: set
b
= 1
•
Step 3: set
b
= common coin
Step 1
Step 2
Step 3
Safety intuition
(f ≤ t)
: Suppose a party commits
b
= 0
-
All
(> 2t)
honest parties have
b
= 0
-
Honest parties never change their value to
b
= 1
f > t
≤ 2t
can
Byzantine do not send 0
Honest parties switch to b = 1
World 2 Culprits: Parties who switched to b = 1
•
Propagate local value
b
•
Receive values within a synchronous step:
•
#(0)
> 2t
, update
b
= 0
•
#(1)
> 2t
, update
b
= 1
•
Else
•
Step 1: set
b
= 0
•
Step 2: set
b
= 1
•
Step 3: set
b
= common coin
Step 1
Step 2
Step 3
Safety intuition
(f ≤ t)
: Suppose a party commits
b
= 0
-
All
(> 2t)
honest parties have
b
= 0
-
Honest parties never change their value to
b
= 1
f > t
≤ 2t
can
Byzantine do not send 0
Honest parties switch to b = 1
All parties send 0
Byzantine parties switch to b = 1
Summary
•
Two protocols: HotStuff and Algorand BA
•
HotStuff has strong forensic support
•
Algorand BA does not have any forensic support
•
Implementation details matter
•
Our paper:
•
PBFT, VABA
•
Implement forensic client on DiemBFT
•
Generic impossibility results
Explore the realm of Byzantine fault tolerance through protocols like State Machine Replication and HotStuff, discussing safety, liveness, forensic support, and the impact of Byzantine faults. Dive into decades of research on achieving fault tolerance and examining forensic support in the face of Byzantine behavior.
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
BFT Protocol Forensics Kartik Nayak Peiyao Sheng, Gerui Wang, Sreeram Kannan, Pramod Viswanath
State Machine Replication A group of servers provide the same interface as a single non-faulty server even if some of the servers are Byzantine faulty (Safety) Any two non-faulty servers do not learn different sequence of values (Liveness) A value proposed by a client will be eventually executed by every non-faulty server cmdj cmdi
BFT Protocol Research 40 years of research Tolerate more faults Better efficiency Byzantine Agreement: Byzantine threshold: t < n Actual number of faults: f Safety and liveness: f t
BFT Protocol Forensics What happens when f > t? Safety and/or liveness can be violated Forensic support: provide irrefutable evidence of bad behavior Is it always possible? What does it take to obtain such evidence?
BFT Protocol Forensics Safe and live No forensic support Forensic support (d = t+1) for d > n-2t t n-t Actual number of Byzantine parties (f) d: Number of Byzantine replicas detected
Existing Works on Forensic Support for BFT Multiple previous works PeerReview, Casper, Polygraph, Grandpa BFT, To design protocols with forensic support (accountability) Our goal: Analyze existing protocols based on Number of Byzantine replicas detected (d) Number of witnesses Distributedness (k)
Todays Talk Algorand BA d = 0 k = n - f (all honest parties) Honest parties involved (k) HotStuff d = t + 1 k = 1 Byzantine parties held culpable (d)
HotStuff Partially synchronous protocol, tolerates 1/3rd Byzantine faults [YMRGA 19] (2t+1 votes) prepareQC(v) precommitQC(v) commitQC(v) propose(v, hQC) vote1(v) vote2(v) vote3(v) Messages in some view e
HotStuff: Key Invariant vote3(v): locked on v; will not vote differently prepareQC(v) precommitQC(v) commitQC commitQC(v) (v) propose(v, hQC) vote1(v) vote2(v) vote3(v) vote3(v) Messages in some view e
HotStuff: Key Invariant vote3(v): locked on v; will not vote differently unless it is safe it is safe : hQC shared by leader is from a higher view prepareQC(v) precommitQC(v) commitQC(v) propose(v, hQC) hQC: highest prepareQC known to leader vote1(v) vote2(v) vote3(v) Messages in some view e
An Attack Across Views commitQC(v) Party i commits v commitQC(v ) Party j commits v Propose(v , hQC) vote3(v) A A A A B B B B No commits in these views C C C C D D D D View e . . . View e
Q: Which parties are Byzantine? Hint: D is not, it did not vote3(v) Observe: vote2, vote3 do not matter Claim: B and C are culpable. commitQC(v) Party i commits v commitQC(v ) Party j commits v Propose(v , hQC) vote3(v) A A A A B B B B No commits in these views C C C C D D D D View e . . . View e
Claim: B and C are culpable A: False, hQC can be a prepareQC on v in some view > e Holds for all views > e except the first one where prepareQC was formed commitQC(v) Party i commits v commitQC(v ) Party j commits v Propose(v , hQC) vote3(v) A A A A B B B B No commits in these views C C C C D D D D View e View e
Identifying Culpable Replicas (Across Views) e*: first higher view prepareQC for a different value was formed We re locked on v in view e commitQC(v) Party i commits v (hQC from a lower view) commitQC(v ) Party j commits v Propose(v , hQC) prepareQC(v ) Propose(v , hQC) not vote1 A vote3(v) A vote1 B B We are locked on v or our locks are older than e vote1 C C vote1 D D View e* View e View e
Identifying Culpable Replicas (Across Views) Culpable replicas: Intersection of commitQC(v) and parties forming the first prepareQC(v ) Q: Who has access to the first prepareQC(v ) formed in e*? A: If v was committed, 2t+1-f honest parties hold prepareQC(v ) - Many witnesses
Identifying Culpable Replicas (Across Views) Culpable replicas: Intersection of commitQC(v) and parties forming the first prepareQC(v ) Q: How do we know e* was the first such view? A: Implementation details matter - Depending on information included with vote1(v ), we can have (a) Single witness identifying t+1 Byzantine replicas (b) Require multiple witnesses (c) Have no forensic support even after obtaining all honest transcripts
Todays Talk Algorand BA d = 0 k = n - f (all honest parties) Honest parties involved (k) HotStuff d = t + 1 k = 1 Byzantine parties held culpable (d)
Algorand BA Synchronous protocol, tolerating 1/3 faults [CM 16] Byzantine Agreement on a binary value
Algorand BA Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 (terminate if step 1) #(1) > 2t, update b = 1 (terminate if step 2) Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Step 1 Step 2 Step 3 Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1
Safety Violation when f > t: World 1 Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 #(1) > 2t, update b = 1 Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Byzantine do not send 0 Step 1 Step 2 Step 3 Honest parties switch to b = 1 f > t Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1 can 2t
World 1 Culprits: Parties who did not send b Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 #(1) > 2t, update b = 1 Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Byzantine do not send 0 Step 1 Step 2 Step 3 Honest parties switch to b = 1 f > t Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1 can 2t
World 2 Culprits: Parties who switched to b = 1 Propagate local value b Receive values within a synchronous step: #(0) > 2t, update b = 0 #(1) > 2t, update b = 1 Else Step 1: set b = 0 Step 2: set b = 1 Step 3: set b = common coin Byzantine do not send 0 All parties send 0 Step 1 Step 2 Byzantine parties switch to b = 1 Step 3 Honest parties switch to b = 1 f > t Safety intuition (f t): Suppose a party commits b = 0 - All (> 2t) honest parties have b = 0 - Honest parties never change their value to b = 1 can 2t
Summary Two protocols: HotStuff and Algorand BA HotStuff has strong forensic support Algorand BA does not have any forensic support Implementation details matter Our paper: PBFT, VABA Implement forensic client on DiemBFT Generic impossibility results
