1 of 46

HotStuff:

BFT Consensus in the Lens of Blockchain

Authors: Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham

Presented by: Haobin Ni

1

2 of 46

Why this paper?

2

3 of 46

Impact

3

4 of 46

Contribution

  • A new solution to a classic problem

​

  • Simplicity

​

  • Flexibility
    • Generalizes to a framework for BFT consensus

4

5 of 46

Other Protocols through the lens

5

6 of 46

Connection

Maofan (Ted) Yin

6

7 of 46

Background

What is BFT Consensus?

7

8 of 46

What is consensus?

Processes:

Decision:

or

8

9 of 46

What is consensus?

9

10 of 46

What is consensus?

10

11 of 46

What is consensus?

11

12 of 46

What is consensus?

  • For each of n processes:
    1. Input: initial value v
    2. [Execute the protocol]
    3. Output: decision d

​

  • Goal
    • Safety: all processes decide the same value
    • Liveness: all processes decide in bounded time

12

13 of 46

What is consensus?

13

14 of 46

Byzantine Fault

14

15 of 46

Byzantine Fault

  • Up to f processes may be faulty
    • Faulty processes can deviate arbitrarily from the protocol

​

  • Safety: all correct processes decide the same value

15

16 of 46

3f+1 Lower Bound

  • At least 3f+1 processes are needed to tolerate f faulty processes.
    • Resilient consensus protocols [PODC’83]

16

17 of 46

Related Work

  • Well-known protocols
    • Crash fault-tolerant consensus: Paxos, Raft
    • Byzantine fault-tolerant consensus: PBFT, Zyzzyva, BOSCO
    • Blockchains: Nakamoto (Bitcoin), Avalanche

​

  • Applications of consensus
    • Antiquity, Derecho, Charlotte, …

17

18 of 46

State machine replication (SMR)

  • Single-value consensus: make one decision

​

  • State machine replication: make a sequence of decisions
    • The State Machine Approach: A Tutorial
    • Useful for build fault-tolerant systems

18

19 of 46

The saddest moment, Mickens 2013

19

20 of 46

The HotStuff Lens

A protocol framework

20

21 of 46

Voting

21

22 of 46

Voting

22

23 of 46

Unanimous Quorum

23

24 of 46

Unanimous Quorum

  1. Any two sets of 3 votes must have an overlap of 2 votes, thus at least 1 honest vote
  2. Honest processes only vote for a single value
  3. The two quorums have the same value

=

24

25 of 46

Unanimous Quorum

  • Any two sets of 2f+1 votes must have an overlap of f+1 votes, thus at least 1 honest vote
  • Honest processes only vote for a single value
  • The two quorums have the same value

25

n=3f+1

|B|=2f+1

|A|=2f+1

|A∩B|>=f+1

|A∩B-F|>=1

26 of 46

Multiple Rounds of Voting

26

1

0

2

3

…

Skip

Skip

27 of 46

The Problem

27

Skip

Mismatch!

28 of 46

The HotStuff Lens

  1. Use multiple rounds of voting

​

  • Add information about previous rounds to the content of voting
    • Can vote differently based on these information
    • Like a blockchain with each round as a block

​

  • Decide when certain patterns are observed

28

29 of 46

Other Protocols through the lens

29

30 of 46

HotStuff

BFT Consensus meets Blockchain

30

31 of 46

Quorum Chain

  • Extra information: a pointer to the latest known unanimous quorum
    • Use threshold signatures to make it verifiable

31

b0

b1

b2

b3

32 of 46

Quorum Chain

  • Vote differently: Only vote when proposed pointer is newer

32

b0

b1

b2

b3

33 of 46

Time to observe some pattern!

33

34 of 46

One Chain

  • An unanimous quorum of b0
    • Update latest known quorum

​

  • Guarantees agreement on the content of b0
    • if knows b0 to be successful

34

b0

b1

35 of 46

Two Chain

  • An unanimous quorum for b1 which contains an unanimous quorum for b0

​

  • Guarantee future quorum chains do not “jump” over all b0, b1, and b2

35

b0

b1

b2

36 of 46

Two Chain

  • In this case, the quorum for b1 and b3 has an honest intersection
  • But voting for b1 updates latest known quorum to b0 (One chain), voting for b3 is against the voting rule!

36

b0

b1

b2

b3

37 of 46

Three Chain

  • Safe to decide b0!

​

  • Guarantee all future quorum chains contains b0

37

b0

b1

b2

b3

38 of 46

Three Chain

  • Two chain (b0-b1-b2): b3’s chain goes through either b0, b1, or b2
    • Other nodes may observe a different b3!
  • One chain (b2-b3): b2’s pointer points to b1
  • => b3’s quorum chain, if exists, goes through b0
    • Induction for later quorums

38

b0

b1

b2

b3

39 of 46

Three time’s a charm!

39

“

40 of 46

Summary

  • Protocol: Multiple rounds of voting, decide the quorum chain of b0 if observed three chain

​

  • Three chain’s property => Safety

​

  • Liveness: after GST, three chain is guaranteed to happen with honest leaders

40

41 of 46

Results

41

42 of 46

Theoretical Results

  • Linearity
    • The communication cost is linear to number of processes

​

  • Optimistic responsiveness
    • Decide as fast as the network propagates, on a good day

42

43 of 46

Comparison

43

Protocol

Correct Leader

Leader Failure

f Leader Failures

Responsive

DLS

O(n4)

O(n4)

O(n4)

​

PBFT

O(n2)

O(n3)

O(fn3)

✓

SBFT

O(n)

O(n2)

O(fn2)

✓

Tendermint/Casper

O(n2)

O(n2)

O(fn2)

​

Tendermint/Casper*

O(n)

O(n)

O(fn)

​

HotStuff

O(n)

O(n)

O(fn)

✓

44 of 46

Evaluation

44

45 of 46

Conclusion

  • The HotStuff lens: a framework for consensus

​

  • [Chained] HotStuff protocol: three chain rules

​

  • HotStuff is cool stuff!

​

45

46 of 46

Questions?

46