International Association
for Cryptologic Research

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.