Paper Review: Fast-HotStuff: A Fast and Resilient HotStuff Protocol
In this post, I summarized the Fast-HotStuff paper. The authors of this paper are Mohammad Jalalzai from The University of British Columbia, Jianyu Niu, and Chen Feng.
The Fast-Hotstuff (FHS) is a new consensus algorithm for blockchain. It has the same properties that were proposed in HotStuff: linear view change complexity and responsiveness. FHS, on the other hand, has better latency due to the elimination of one phase in HotStuff. The FHS is resilient against certain attacks such as forking attacks and provides fairness proof-of-stake support. During primary failure at most two aggregated signatures (from N-F QCs) need to be verified instead of quadratic number of signatures.
The FHS basic idea is that the primary has to provide a highest Quorum certificate (QC) to prevent the byzantine primary from doing a forking attack. If replicas verified the QC successfully, then replicas can safely commit the block at the end of the second round.
FHS uses a signature-aggregation scheme when the primary failed instead of appending all replicas signatures in the proposed block. The primary has to convince voting replicas that it’s proposing a block that will extend the last block by using latest QC. The latest QC for view v-1 proposed with the proposal for view v into the block will verify by all replicas. In case of primary failure, FHS needs the proof for the latest QC in the form of (N-F QCs). The (N-F QCs) attached in the proposed block by the primary is for safety and liveness.
The algorithm in the nutshell:
1- The primary waits for new-view messages from N-F replicas. The new-view message contains the last prepareQC the replica knows. Then, the primary creates and signs a prepare message that contains aggregation QC from N-F replicas. Upon receiving it, replicas verify the aggregation QC and extracts HighQC.
2- The primary collects prepare votes from N-F replicas and builds PrepareQC. The primary broadcasts PrepareQC to all replicas in a pre-commit message. A replica responds with a pre-commit vote to the primary. Each replica checks if it has committed the block for the latest QC. Since the majority of replicas have voted for the latest QC, it is safe to commit it.
3- The primary collects pre-commit votes from N-F replicas and combines them into a PrecommitQC. As a replica receives and verifies the PrecommitQC, it executes the commands. The replica begins the next view.
The FHS is also pipelining the requests and proposing them in each phase. In both the basic and the pipelined, the primary proposes a block with QC if the primary is able to build a QC from a previous view while using a threshold signature scheme or a block with an AggQC using aggregated signatures if the previous primary has failed. A primary can only propose a block during view v if it is able to build a QC from N-F votes received during the view v-1 by using threshold signatures. Otherwise, the primary must receive N-F new-view messages from distinct replicas for view v. In this case, the primary during view v has to propose a block with aggregated QC or AggQC from N-F replicas. Each replica signs the new-view message using its private key. The signatures on the new-view are aggregated to generate a single aggregated signature in AggQC.
FHS is resilient to forking attacks because a primary cannot replace the N-F votes it has received for the previous block with an older QC to perform a forking attack. A primary has to provide the proof of highQC that it is holding. If a primary does not provide the proof for highQC or provides invalid proof, then other replicas will reject its proposal.
Replicas has O(n) signature verifications for AggQC. Each replica has to verify the aggregated signature of AggQC, then the replica has to loop through each QC inside AggQC and find the QC with the highest view and verify its aggregated signature.
The paper has a good evaluation section. It evaluates FHS and compares it to Hostuff performance in three cases:
- during happy path, FHS latency and throughput are better than HostStuff. Check fig 8, fig 9 part (a).
- Primary failed and FHS needs AggQC in its proposal.
- Forking attack has no impacts on FHS because it’s a QC proof.
