CHERUBIM: A Secure and Highly Parallel Cross-Shard Consensus Using Quadruple Pipelined Two-Phase Commit for Sharding Blockchains

Due to the promising scalability property, sharding technology has gained widespread attention. It improves the transaction throughput of blockchain systems but also introduces cross-shard transactions. Current two-phase commit (2PC) protocols process different cross-shard transactions sequentially, resulting in significant system overhead and low throughput. Besides, current sharding blockchains rely on Byzantine fault tolerance (BFT) as a black box, lacking specific designs to efficiently handle cross-shard proposals. Moreover, cross-shard communication complexity is high, and transaction processing parallelism is low. In this paper, we first propose P-2PC, a general framework to process cross-shard transactions of different phases in a pipelined way, suitable for most sharding blockchains. Further, we design Cherubim with improved quadruple 2PC, 4P-2PC. By combining P-2PC with an intra-shard pipelined BFT, 4P-2PC achieves both intra-shard and cross-shard pipelined processing. Combined with a newly designed batch processing method, each shard processes 4 transaction batches simultaneously through 1 round of calculation and communication, compared to 4 rounds in previous work. In particular, Cherubim seamlessly integrates a multi-signature algorithm supporting further aggregation, reducing communication complexity. Furthermore, we evaluate our work through theoretical analysis and implementation, proving that Cherubim has a communication complexity linear to the node number. We also propose horizontal and vertical consensus parallelism degrees to evaluate the parallelism ability. Compared to the state-of-the-art solutions, the evaluation demonstrates that Cherubim achieves a transaction throughput improvement of at least $2.28 \times $.