How The Hotstuff Protocol is NOT Secure?

Each participant stores a tree of pending commands locally, in addition to the state variables viewNumber (starting at 1, stores the highest QC it voted to pre-commit), and prepareQC (starts at nil), lockedQC (starts at nil, stores the highest QC it voted to commit). When a “new-view” or round starts, a public function determines the leader from the current participants.

Each participant sends its

prepareQC

Key Innovations in HotStuff from Previous Solutions

The star communication network allows HotStuff BFT/LibraBFT to achieve consensus with reduced communication complexity but increased round complexity. The key innovations to note are that: 

1. HotStuff participants send signed messages to the leader participant in a p2p channel (the star topology communication network). 
2. Using threshold digital signature schemes, HotStuff achieves linear authenticator complexity regardless of whether the leader is correct or faulty.

Perhaps most relevant: PaceMaker is a functionality the original HotStuff paper proposed to achieve round synchronization, but the paper lacked explicit implementation details.

Therefore we can look at how LibraBFT implemented it: When a participant gives up on a round, it broadcasts a timeout message with the round-entry certificate.

They expect this to bring all (honest) participants to round r within a bound for transmission delay. Upon collection of a quorum of participants’ timeout messages, a timeout certificate is formed, and round synchronization is achieved. 

The Importance of A Reliable Leader

The importance of message propagation is especially highlighted in the vulnerabilities for the HotStuff BFT protocol, since it lacks an explicit decision message propagation process. The trouble arises when the leader fails to reliably broadcast decide messages in HotStuff. Consider the following scenario:

According to the protocol, the leader is tasked with extending the path to (a0 -> a1 -> … -> at -> b). Suppose that the execution continues without a hitch, and we continue on the next view v+1.

We expect the leader to propagate the commands to all participants, who should all execute the commands associated with extending both leaf nodes b and c.

The HotStuff BFT protocol states that “in practice, a recipient who falls behind can catch up by fetching missing nodes from other replicas.” That means that, at the end of view v+1, the participant who falls behind could fetch the prepareQC corresponding to (a0 -> a1 -> … -> at -> b -> c).

However, this participant that’s trying to catch up has no way of knowing whether all the participants actually executed the commands (i.e. whether the leader propagated the commands for node b to everyone, to 1 node, or to some subset).

According to the HotStuff BFT protocol, the node on the tree only contains the hash of the parent node, and the client command. As a result, the leaf node maintained by each participant contains no information about whether the command has been executed. 

In the end, this analysis demonstrates that the original overview of HotStuff leaves the participants on a network vulnerable to inconsistency. The lesson here is that it’s important to consider including whether a given command has been executed in the tree node itself.