Consensus in the Asynchronous
Hybrid Byzantine Model with
Optimal Resilience
Megumi AndoMoses Liskov{mando, mliskov}@mitre.org© 2011 The MITRE Corporation. All rights reserved

Byzantine fault tolerance Single adversary adaptively

corrupts nodes– Corrupted (“Byzantine”)
nodes send arbitrarymessages
 Asynchronous network model– Honest messages can bedelayed arbitrarily
 Lower bound: n > 3t

– n: number of nodes– t: corruption limit Critical problems:– reliable broadcast– consensus

2© 2011 The MITRE Corporation. All rights reserved

Crash tolerance and hybrid models
 In crash tolerance (fail stop)– Single adversary adaptively crashes nodes– Crashed nodes cannot send messages– Lower bound: n > 2t

3
© 2011 The MITRE Corporation. All rights reserved

Crash tolerance and hybrid models
 In crash tolerance (fail stop)– Single adversary adaptively crashes nodes– Crashed nodes cannot send messages– Lower bound: n > 2t
 Hybrid Byzantine model– Single adversary adaptively chooses to crash or corrupt nodes– Crashed nodes cannot send messages– Corrupted nodes send messages of adversary’s choice– Up to b corruptions, up to t total crashes or corruptions4© 2011 The MITRE Corporation. All rights reserved

Crash tolerance and hybrid models
 In crash tolerance (fail stop)– Single adversary adaptively crashes nodes– Crashed nodes cannot send messages– Lower bound: n > 2t
 Hybrid Byzantine model– Single adversary adaptively chooses to crash or corrupt nodes– Crashed nodes cannot send messages– Corrupted nodes send messages of adversary’s choice– Up to b corruptions, up to t total crashes or corruptions
 Our results:– Lower bound: n > 2t+b
– Optimal size protocols for reliable broadcast and consensus
5© 2011 The MITRE Corporation. All rights reservedPrinciples
 With n = 3t+1 nodes and up to t Byzantine:– Can wait for n-t responses in an asynchronous network– Of the ones we get responses from, at least t+1 are honest– t+1 honest nodes must be sufficient to force progress

6© 2011 The MITRE Corporation. All rights reservedPrinciples
 With n = 3t+1 nodes and up to t Byzantine:– Can wait for n-t responses in an asynchronous network– Of the ones we get responses from, at least t+1 are honest– t+1 honest nodes must be sufficient to force progress With n = 2t+b+1 nodes in the Hybrid Byzantine model:– Can still wait for n-t responses in an asynchronous network– Of them, at least t+1 were honest at the time
– But only b+1 must remain honest– Thus, b+1 honest nodes must be sufficient to force progress

7© 2011 The MITRE Corporation. All rights reservedConsensus protocol: approachApproach from Canetti and Rabin and earlier papers
x1x2x3...

xi

xi+1...

out

8© 2011 The MITRE Corporation. All rights reservedConsensus protocol: approach
Approach from Canetti and Rabin and earlier papers
x3x2

x1...

xi

xi+1...

out vote: protocol tovote
xi

yi
zi

determine clear
majority for avalue

9© 2011 The MITRE Corporation. All rights reservedConsensus protocol: approach
Approach from Canetti and Rabin and earlier papers
x3x2

x1

...

xi

xi+1...

out vote: protocol tovote

yizi

globalcoincxi

determine clear
majority for avalue
 global coin: acoin-flipping
protocol10© 2011 The MITRE Corporation. All rights reservedConsensus protocol: approach
Approach from Canetti and Rabin and earlier papers
x3x2

x1

...

xi+1xi...

out vote: protocol to

vote

yizi

xi
globalcoinc

if zi = 2
out=yi
if zi ≥ 1xi+1 = yielse
xi+1 = cxi+1

determine clear
majority for avalue
 global coin: acoin-flipping
protocol11© 2011 The MITRE Corporation. All rights reserved

Vote protocol: fully Byzantine
Protocol of Canetti-Rabin 1993: Let n ≥ 3t+1.
Player Pi with input xi:
1. a-cast (input, i, xi)
2. Complete n-t input a-casts; set vote vi to majority of input values.
3. a-cast (vote, i, vi)
4. Wait to complete n-t consistent vote a-casts; set revote rvi to majority of votevalues.
5. a-cast (re-vote, i, rvi)
6. Wait to complete n-t consistent re-vote a-casts.
7. If all votes agree on σ, output (σ,2). Else if all re-votes agree on σ, output (σ,1).
Otherwise, output (0,0).

Size of intersection (n-2t) of two honest nodes’ views guarantees
unanimity in one is a majority in the other: 2(t+1) > n-t.
n-2t = b+1 not large enough.
12© 2011 The MITRE Corporation. All rights reserved

Vote protocol: hybrid Byzantine
Our Protocol. Let n ≥ 2t + b + 1.
Player Pi with input xi:
1. a-cast (input, i, xi)
2. Complete n-t input a-casts; set vote vi to majority of input values.
3. a-cast (vote, i, vi)
4. Wait to complete n-t consistent vote a-casts; set revote rvi to majority of votevalues.
5. a-cast (re-vote, i, rvi)
6. Wait to complete n-t consistent re-vote a-casts.
7. If all votes agree on σ, output (σ,2). Else if all re-votes agree on σ, output (σ,1).
Otherwise, output (0,0).

13© 2011 The MITRE Corporation. All rights reserved

Vote protocol: hybrid Byzantine
Our Protocol. Let n ≥ 2t + b + 1.
Player Pi with input xi:
1. a-cast (input, i, xi)
2. Complete n-t input a-casts; set vote vi to majority of input values.
3. a-cast (vote, i, vi)

4. Wait to complete n-t consistent vote a-casts; set revote rvi to majority of votevalues.
5. a-cast (re-vote, i, rvi)
6. Wait to complete n-t consistent re-vote a-casts.
7. If all votes agree on σ, output (σ,2). Else if all re-votes agree on σ, output (σ,1).
Otherwise, output (0,0).

14© 2011 The MITRE Corporation. All rights reserved

Vote protocol: hybrid Byzantine
Our Protocol. Let n ≥ 2t + b + 1.
Player Pi with input xi:
1. a-cast (input, i, xi)
2. Complete n-t input a-casts; set vote vi to majority of input values.
3. a-cast (vote, i, vi)
4. Wait to complete n-t consistent vote a-casts; set Si to set of vote senders.
5. a-cast (set, i, Si)
6. Wait to complete n-t consistent set a-casts; set re-vote rvi to majority of votes frommembers of all sets.
7. a-cast (re-vote, i, rvi)
8. Wait to complete n-t consistent re-vote a-casts.
9. If all votes agree on σ, output (σ,2). Else if all re-votes agree on σ, output (σ,1).
Otherwise, output (0,0).

set messages guarantee the intersection of two honest nodes’
views has size at least n-t.

15
© 2011 The MITRE Corporation. All rights reserved