Seafooler's Blog

In the previous blog, we have talked about the safety of chained HotStuff.

In this post, we go on talking about its responsiveness.

In the classical paper The Byzantine Generals Problem, Lamport et al. proposed two recursive protocols to achieve the Byzantine consensus, namely oral message protocol and signed message protocol. Although the authors have proved the correctness of the protocols, the proof seems to be not intuitive enough.

In this blog, we try to prove the oral message protocol by myself. Particularly, I will attach the figures to make the proof more readable.

As for the chained HotStuff, there are two commitment rules for a block: three-chain or two-chain+QC. Three-chain rule is easy for understanding, while two-chain+QC is not.

In this blog, we want to figure out why the commitement rule can be relaxed from a three-chain to a two-chain+QC? Or in other words, why a two-chain+QC can guarantee the safety, where three-chain can be considered as a special case of two-chain+QC?

Many thanks to all, especially my wife. On this Christmas Eve, my loved baby girl comes to this world.

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.

Inspired by the blockchain data structures, lots of streamlined BFT (Byzantine Fault Tolerant) consensus algorithms have been proposed recently, including Tendermint[1], Pili[2], Pala[3], HotStuff[4], and Streamlet[5]. Among them, two extremely-simple ones are quite similar and even born from the same research group (i.e., Prof. Elaine Shi). Streamlet is claimed to be an improved variant of Pala, which seems to be simpler.

In this blog, we try to make a comparison between Pala and Streamlet. Note that we only consider the basic Pala, which takes a democracy-favoring proposer rotation approach, similar to Streamlet. Furthermore, we want to figure out how can Streamlet simplify the consensus and are the improvements made at any costs?

在HotStuff的PODC版本论文和Arxiv版本论文中，多次将不同共识协议的活性(liveness)和响应度(responsiveness)进行比较。此外，一些博客和其他相关论文中也有关于liveness问题和responsiveness问题的叙述。其中涉及到两点叙述：

1. Tendermint中在leader切换的时候需要等待一个最大的网络延迟\(\Delta\)，导致Tendermint无法做到optimistic responsiveness
2. 如果Tendermint在leader切换的时候不等待\(\Delta\)，将导致Tendermint中无法进行有效共识，从而破坏协议的liveness。

但笔者在看这两点叙述的时候，总感觉论文作者和博主没有将问题讲透，看得云里雾里的。可能大佬们觉得这两点叙述很容易理解，甚至是一些一点就该通的常识。

为了真正弄懂以上两点叙述，笔者查阅了大量资料，并将自己的一些理解整理在这篇博客中。这篇博客需要读者对共识算法已经有了一定的理解。

In recent years, more and more blockchain systems are proposed to improve the system performance. One of the significant directions taken by these works is to parallelize the block creation and dissemination, with OHIE [1] and Occam [2] as representatives.

In this blog, we try to raise a model to unify these new blockchain systems. Also, we are surprised to find that this model can even unify a class of asynchronous blockchain systems, such as HoneybadgerBFT [3].

At the end of this blog, we further propose a simpler blockchain system under this model.

While I was reading the HoneybadgerBFT paper, a question came to me is that "Reliable Broadcast (RBC) seems to implement the functions of a consensus algorithm already, why an extra phase of Asynchronous Binary Agreement (ABA) is needed"?

In this blog, we will try to answer this question.

The birth of blockchain brings a new option when designing a consensus algorithm, that the requests can be packaged as blocks and blocks can be linked with the hash values. Almost all the newly born consensus algorithms, such as Tendermint, HotStuff, Pala, and Streamlet, adopt the blockchain structures.

A question is that what benefits can the blockchain structure bring to the consensus design? Or in other words, what problem can the blockchain structures deal with? Besides, another relevant question is that how does the consensus (e.g., PBFT) without adopting the blockchain strucuture deal with the same problem?