As the representaives of streamlined BFT consensus algorithms, Tendermint[1], Pala[2], Streamlet[3], and HotStuff[4] reseamble each other to a great extent. However, taking a close look at these algorithms, we can find they picks different routines in many aspects, such as inclusion of QC in blocks, echo mechanism, and so on.
In this blog, we make a detailed comparison between these representative algorihms.
Comparison
Our comparison results are shown in the following table. For the sake of consistency, we denote QC as the \(2f+1\) signatures for a block and epoch as the round/epoch charged by a proposer.
| Aspect | Tendermint | Pala | Streamlet | HotStuff |
|---|---|---|---|---|
| Pipeline | No | Yes | Yes | Yes |
| Lock* | Yes | Implicitly yes | No | Yes |
| Proposal | Repropose the block locked by it | Propose a new block extending from the locked (largest-epoch notarized) block | Propose a new block extending from the highest notarized block | Propose a new block extending from the highest notarized (prepareQC) block |
| Vote(safety) | Vote for the block it has locked before | Vote for the block extending from its locked (largest-epoch notarized) block | Vote for the block extending from its highest notarized block | Vote for the block extending from its locked (lockedQC) block |
| Vote(liveness)/unlock | Unlock once seeing a larger-epoch QC |
Unlock once seeing a larger-epoch QC |
Vote for a block extending from a larger-or-equal-height QC |
Vote for a block extending from a larger-epoch lockedQC |
QC in the block+ |
Yes | No | No | Yes |
| Echo# | No | Yes | Yes | No |
* Although the lock mechanism is not clarified by Pala explicitly, it is implicitly defined by the following specification: a replica only votes for the block extending from a larger-or-equal-epoch QC. Usually, it maintains its locally largest-epoch QC. Once seeing a new larger-or-equal-epoch QC, it will replace its maintained largest-epoch QC with the new one. The largest-epoch QC maintained by a replica will be only one at any time, which is considered to be locked on. As for Streamlet, it can vote for any block extending from a larger-or-equal-height QC. From another prospective, we can also consider Streamlet to lock on all the highest QCs, which may be multiple.
+, # We may find that the consensus with QC in the block does not need the echo mechanism. The reason is that a QC in the new block functions as echoing replicas' votes. If neither QC in the block nor the echo mechanism is adopted, the algorithm will lose the liveness property, which is detailed analyzed by Dr. Malkhi's blog.
Reference
- Buchman, E. "Tendermint: Byzantine fault tolerance in the age of blockchains." Doctoral dissertation, 2016.
- Chan, T. H., Pass, R., & Shi, E. "Pala: A simple partially synchronous blockchain." Cryptology ePrint Archive, 2018.
- Chan, B. Y., & Shi, E. "Streamlet: Textbook streamlined blockchains." In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies (AFT'20), pp. 1-11.
- Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., & Abraham, I. "HotStuff: BFT consensus with linearity and responsiveness." In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC'19), pp. 347-356.
- "What They Did not Teach you in Streamlet." https://dahliamalkhi.github.io/posts/2020/12/what-they-didnt-teach-you-in-streamlet/
- "Lecture 14: Blockchain protocols with finality: Streamlet and HotStuf." https://courses.grainger.illinois.edu/ece598pv/sp2021/lectureslides2021/ECE_598_PV_course_notes14.pdf