Seafooler's Blog
0%

What Benefits Can Blockchain Structure Bring To Consensus?

Posted on In

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?

A block can contain multiple number of requests. To make a better comparison between consensuses with/without blockchain structures, we assume a block contains only one request.

I. Voting Mechanism Accompanied By Blockchain Structures

First, let us review the voting mechanism accompanied by the blockchain structures. Almost all the consensus adopting blockchain structures stipulate the voting mechanism as follows:

A replica votes for a request (\(r\)) only if all the ancestral requests led by \(r\) are consistent with its locked requests.

The locked request denotes the request being judged as committed by the replica, which has been talked about in a previous blog. With this voting mechanism, if a request (\(r\)) is locked, all the ancestral requests led by \(r\) are locked too. Further, if \(r\) is committed, all the ancestral requests led by \(r\) are committed.

II. Blockchain Structures Can Reduce the Overhead

A. High overhead in PBFT

Review that in PBFT, when the view is changed, all the indexes after low-water mark must be processed again in the process of view change or in the new view.

These indexes are processed independently in PBFT, since the opinion for one request has nothing to do with the opinion for another request. Broadcasting and later processing of these messages can bring large communication and computation overhead.

B. Opinion with hash value can represent opinions for preceding indexes

With the blockchain structures, especially the hash values, these overheads can be reduced largely.

1. Reduction of communication overhead

Particularly, an opinion for an index \(i\) can also represent all the opinions for the preceding indexes (\(< i\)). Therefore, a replica only needs to broadcast the opinion for its largest locked index/request. Thus, the communication overhead is reduced.

2. Reduction of computation overhead

When a replica (\(rep_j\)) receives a blockchain-structure opinion from another replica (\(rep_k\)), it will compare the index in the opinion with its local index. If the former index is larger than the latter, it will first fetch the lacking data from other replicas.

Then, the hash value contained in the opinion will be compared with \(rep_j\)'s local hash value at the same index. If two values are equal, \(rep_j\) can consider that \(rep_k\) expresses the opinions for all the preceding indexes.

If everything goes well, one comparison of hash values is enough, which reduces the computation overhead.

3. Reduction of storage overhead

If a block also contains the digest of currect executing status, the committed/executed requests and corresponding can be discarded, thus reducing the storage overhead. The status digest contained in a block resembles a checkpoint in PBFT, and the status digest contained in a committed block resembles a stable checkpoint in PBFT.

However, it seems that almost all the consensus algorithms adopting blockchain structures consider the "storage overhead" as unimportant. Thus, there is no a mechanism of storage reduction or garbage collection in these algorithms.

III. Blockchain Structures Can Eliminate the Checkpoint Mechanism

Although getting few attentions by the readers, checkpoint mechanism plays an important role in PBFT. As talked about in this blog, checkpoint mechanism is used to reduce the storage, communication, and computation overhead.

As a contrast, the blockchain structures can also reduce these overhead, even largerly. Therefore, with the blockchain structures, checkpoint mechanism can be eliminated.

In fact, if the digest of currect executing status is contained in a block, we can think that each committed block also generates a stable checkpoint. In this regard, the stable checkpoint can be considered as an additional product of the normal consensus, whose overhead is negligible.

Reference

  1. Castro, M., & Liskov, B. "Practical byzantine fault tolerance." In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI'99), pp. 173-186.
  2. Buchman, E. "Tendermint: Byzantine fault tolerance in the age of blockchains." Doctoral dissertation, 2016.
  3. 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.
  4. Chan, T. H., Pass, R., & Shi, E. "Pala: A simple partially synchronous blockchain." Cryptology ePrint Archive, 2018.
  5. 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.