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.
I. A Unified Model of Parallel-Block Blockchains
A unified model of the parallel-block blockchain systems consists of four ingredients:
- Epoch: the system is run by consecutive epoches
- Parallel block creation & dissemination: multiple blocks are created and disseminated in parallel
- Block selection: in each epoch, a certain number of blocks must be selected by different peers consistently
- Block sorting: sort the selected blocks
A schematic diagram for this model is also shown by the following figure: 
The most challenging task in the four ingredients is the block selection mechanism. To be more specific, since the selection is done by each replica independently, how to guarantee the consistency of selection results between different replicas?
Almost all the blockchains adopt a simple mechanism to sort the selected blocks. For example, it can take the lexicographical order of block hashes to do the sorting.
II. Implementation Scheme by OHIE
OHIE introduces the concept of parallel chains, each of which generates a legitimate block in an epoch. Note that there may be multiple blocks generated by the same chain in an epoch, but only one of these blocks is legitimate.
OHIE adopts a simple block selection mechanism, which selects all the legitimate blocks in each chain. Since different replicas maintain the same legitimate blocks, the selection of all the legitimate blocks will also be the same. A schematic diagram for OHIE is shown as follows: 
However, OHIE runs into a new problem: what if a chain grows slowly? In this situation, there may be less than n legitimate blocks in an epoch at that time, where n represents the number of chains. One solution is to wait until the slow chain grows. However, this can be quite inefficient. OHIE raises a novel notion of "virtual height", which implies the vacancies in some chains for an epoch. If there are vacancies in m chains for an epoch, a replica only needs to select the remaining n−m legitimate blocks directly. This can accelerate the processing of this epoch.
Besides, OHIE takes the chain ids of blocks to do the sorting.
III. Implementation Scheme by Occam
Occam dynamically adjusts the number of blocks to be selected in an epoch, according to the transaction demand in the network. For example, if a replica needs to select n blocks in epoch k, it may need to select 2n or n/2 blocks in epoch k+1. A schematic diagram for Occam is shown as follows: 
However, as far as I understand it, Occam cannot guarantee each replica to select the same blocks. In this regard, Occam cannot guarantee the safety property.
IV. A Generalized Implementation Scheme by HoneybadgerBFT
Although HoneybadgerBFT is aimed at a different network assumption (asynchronous v.s. synchronous) and system model (permissioned v.s. permissionless) than OHIE/Occam, it can also be unified by our model.
Exactly, HoneybadgerBFT makes use of RBC initialized by n replicas to implement the parallel block creation & dissemination. Besides, it utilizes n ABA instances to implement the block selection, where an ABA instance decides if a corresponding block will be selected. A schematic diagram for HoneybadgerBFT is shown as follows: 
V. Our Simpler Implementation Scheme
Under the above model, we can even devise a simpler parallel-block blockchain system, whose schematic diagram is shown as follows: 
The biggest innovation of this design is the usage of a PoW chain (i.e., selection chain) to do the block selection. Although it is simple, it seems to work well.
Reference
- Yu, H., Nikolić, I., Hou, R., & Saxena, P. "OHIE: Blockchain scaling made simple." In Proceedings of the IEEE Symposium on Security and Privacy (SP'20) pp. 90-105.
- Xu, J., Cheng, Y., Wang, C., & Jia, X. "Occam: A Secure and Adaptive Scaling Scheme for Permissionless Blockchain." In Proceedings of the IEEE 41st International Conference on Distributed Computing Systems (ICDCS'21), pp. 618-628.
- Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D. "The honey badger of BFT protocols." In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS'16), pp. 31-42.