[Resource Topic] 2024/206: Kronos: A Robust Sharding Blockchain Consensus with Optimal Communication Overhead

Welcome to the resource topic for 2024/206

Kronos: A Robust Sharding Blockchain Consensus with Optimal Communication Overhead

Authors: Andi Liu, Yizhong Liu, Zhuocheng Pan, Yinuo Li, Jianwei Liu, Yuan Lu


Sharding enhances blockchain scalability by dividing the network into shards, each managing specific unspent transaction outputs or accounts. As an introduced new transaction type, cross-shard transactions pose a critical challenge to the security and efficiency of sharding blockchains. Current solutions, however, either prioritize security with assumptions and substantial investments, or focus on reducing overhead and overlooking security considerations.

In this paper, we present Kronos, a generic and efficient sharding blockchain consensus ensuring robust security. At the core of Kronos, we introduce a ‘‘buffer’’ mechanism for atomic cross-shard transaction processing. Shard members collectively maintain a buffer to manage cross-shard inputs, ensuring that a transaction is committed only if all inputs are available, and no fund is transferred for invalid requests. While ensuring security including atomicity, Kronos processes transactions with optimal intra-shard communication overhead. A valid cross-shard transaction, involving x input shards and y output shards, is processed with a minimal intra-shard communication overhead factor of x+y. Additionally, we propose a reduction for transaction invalidity proof generation to simple and fast multicasting, leading to atomic rejection without executing full-fledged Byzantine fault tolerance (BFT) protocol in optimistic scenarios. Moreover, Kronos adopts a newly designed ‘‘batch’’ mechanism, reducing inter-shard message complexity for cross-shard transactions from \mathcal{O}(\lambda) to \mathcal{O}((m \text{log} m/b)\lambda) without sacrificing responsiveness (where m denotes number of shards, b denotes the batch size of intra-shard consensus, and \lambda is security parameter).

Kronos operates without dependence on any time or client honesty assumption, serving as a plug-in sharding blockchain consensus supporting applications in diverse network environments including asynchronous ones. We implement Kronos using two prominent BFT protocols: asynchronous Speeding Dumbo (NDSS’22) and partial synchronous HotStuff (PODC’19). Extensive experiments (over up to 1000 AWS EC2 nodes across 4 AWS regions) demonstrate Kronos achieving a substantial throughput of $68.6$ktx/sec with $1.7$sec latency. Compared with state-of-the-art solutions, Kronos outperforms in all cases, achieving up to a 42 \times improvement in throughput and a 50\% reduction in latency when cross-shard transactions dominate the workload.

ePrint: https://eprint.iacr.org/2024/206

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .