Kronos: A Secure and Generic Sharding Blockchain Consensus with Optimized Overhead

Kronos: A Secure and Generic Sharding Blockchain Consensus with Optimized Overhead

Speakers: Yizhong Liu

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=4HtbPBdtRG0

Overview

This talk introduces Kronos, a novel sharding blockchain consensus protocol designed to address the critical scalability and security challenges inherent in existing sharded blockchain architectures. Presented by Yizhong Liu, Kronos aims to provide a generic, secure, and efficient solution for handling cross-shard transactions, which are a major bottleneck for blockchain networks seeking to achieve high transaction throughput. The work is particularly significant given the increasing volume and value of multi-input transactions on platforms like Ethereum, estimated at billions of dollars, and the observation that cross-shard transactions quickly dominate transaction types as the number of shards grows beyond a modest threshold (e.g., 16 shards).

The core problem Kronos tackles lies in maintaining atomicity—the "all or nothing" principle—for transactions spanning multiple shards, while simultaneously optimizing communication overhead and ensuring resilience against malicious actors and network failures. Existing solutions, such as two-phase commit protocols, suffer from high computational overhead due to multiple Byzantine Fault Tolerant (BFT) protocol runs and are vulnerable to "silence attacks" in asynchronous networks. Kronos proposes a new mechanism that significantly reduces BFT overhead and introduces a resilient cross-shard certification method, making it a crucial advancement for the future of scalable and secure blockchain systems.

Background

▶ Watch: Introduction to blockchain scalability and sharding (0:00)

Traditional blockchain designs, while providing strong security and decentralization, inherently suffer from poor scalability. As the number of nodes in the network increases, all nodes must participate in the consensus process to finalize transactions, leading to a bottleneck in throughput. To combat this limitation, sharding was proposed in 2016 as a method to partition the network's state and processing load across multiple independent "shards." In a sharded system, nodes within a specific shard are responsible for processing transactions relevant to that shard, theoretically improving overall scalability.

However, sharding introduces new complexities, particularly concerning transactions that involve assets or data residing in different shards. These are known as cross-shard transactions, distinct from intra-shard transactions which are confined to a single shard. As the network scales, the proportion of cross-shard transactions rapidly increases. Simulations suggest that once a blockchain exceeds 16 shards, cross-shard transactions can account for over 90% of all activity. This prevalence, coupled with the high financial value often associated with multi-input transactions (e.g., crowdfunding, estimated at $1 billion on Ethereum in 2024), makes their secure and efficient handling paramount.

The primary security and consistency challenge with cross-shard transactions is ensuring atomicity. This means that either all components of a multi-shard transaction are successfully committed, or none are. Partial commitment can lead to inconsistent states, double-spending, or loss of funds. For instance, if a transaction involves inputs from Shard 1 and Shard 2, and an output to Shard 3, all inputs must be successfully spent and the output correctly received, or the entire transaction must be aborted without any state changes.

Existing approaches to achieving atomicity in sharded blockchains often rely on variations of two-phase commit (2PC) protocols. In a typical 2PC, a transaction proceeds through a preparation phase (where involved shards lock the relevant assets) and a commit phase (where the locks are converted to spent assets and the transaction is finalized). While conceptually sound, 2PC protocols incur significant overhead because each involved shard typically needs to run its own Byzantine Fault Tolerant (BFT) consensus protocol in both phases. This "cannot remove any of this BFT run without compromising atomicity" principle makes 2PC computationally expensive. Furthermore, 2PC is vulnerable to silence attacks in asynchronous networks, where a malicious node can intentionally withhold messages, preventing the transaction from progressing and potentially leading to a deadlock or inconsistent state.

Another critical aspect is the mechanism for cross-shard certification, which dictates how shards communicate confirmation of transactions. Two primary models exist:

1. Leader-to-Leader Communication: Each shard designates a leader node responsible for communicating with leaders of other shards. This approach is communication-optimal (only one node per shard communicates) but introduces a single point of failure and trust. A malicious leader can selectively block or alter messages, compromising the integrity of cross-shard transactions.
2. End-to-End Communication: All nodes in an input shard communicate directly with all nodes in an output shard. While more resilient to individual node failures, this approach suffers from an O(N^2) communication complexity, where N is the number of nodes in a shard, making it highly inefficient and unscalable.

The need for a solution that is generic (works in both synchronous and asynchronous networks), secure (ensures atomicity and resists malicious actors), efficient (low overhead), and optimized in terms of communication cost is evident. Kronos emerges as a response to these pressing requirements.

Key Findings

▶ Watch: Limitations of current two-phase commit (2PC) solutions (3:15)

Kronos presents several significant contributions to the field of sharded blockchain consensus, primarily focused on enhancing security, efficiency, and scalability for cross-shard transactions. The key findings and innovations include:

• Optimized Atomicity for Cross-Shard Transactions: Kronos achieves strong atomicity—the "all or nothing" principle—for complex multi-shard transactions while drastically reducing the computational overhead compared to traditional two-phase commit (2PC) protocols. Specifically, input shards in Kronos only require one BFT run, as opposed to two BFT runs in 2PC, for valid transactions.
• Resilience Against Silence Attacks and Malicious Leaders: The protocol is explicitly designed to withstand silence attacks in asynchronous networks, a critical vulnerability of 2PC. Furthermore, its cross-shard communication mechanism mitigates the risks associated with malicious leaders by distributing verification responsibilities.
• Generic Applicability: Kronos is engineered to operate effectively in both synchronous and asynchronous network environments, offering a flexible solution for diverse blockchain deployments.
• Novel Cross-Shard Batch Certification: A highly optimized and reliable method for cross-shard communication is introduced. This mechanism leverages erasure codes and Merkle trees to ensure that all receiving nodes can verify and reconstruct transaction confirmations efficiently, even if some parts of the communication are lost or corrupted. This approach minimizes communication complexity while maintaining high reliability.
• Efficient Handling of Invalid Transactions: Kronos includes a fast rejection mechanism for invalid transactions (e.g., due to unavailable coins). In the "happy path" scenario, where an honest node can quickly compute an "invalidity proof of rejection," other shards can abort the transaction before running expensive BFT protocols, saving significant resources.
• Superior Performance Metrics: Experimental evaluations demonstrate that Kronos achieves significantly higher throughput and lower latency compared to 2PC-based solutions and other sharding blockchains like AHL and ByzChart. This empirical validation underscores its practical efficiency gains.

Technical Deep Dive

▶ Watch: Different cross-shard communication approaches and their flaws (4:55)

Kronos's design is a sophisticated blend of optimized BFT consensus, novel cross-shard communication, and intelligent transaction buffering to ensure atomicity and efficiency. The protocol fundamentally re-architects how cross-shard transactions are processed, moving away from the costly two-phase commit model.

The core idea is to process transaction inputs and outputs separately, using a buffered approach at the receiving end, and to optimize the cross-shard communication channel.

Valid Transaction Flow

Let's trace a valid cross-shard transaction where client A and B want to spend blue and purple coins from their respective input shards (S1 and S2) to a payee (P) in an output shard (S3).

1. Initiation: Clients A and B submit a request, along with signed transaction information, to the pay shard (S3). At this stage, the pay shard cannot verify the availability of funds; it merely receives the request.
2. Request Forwarding: The pay shard (S3) then forwards this transaction request to the involved input shards (S1 and S2). These requests are placed in a queue for validation within each input shard.
3. Input Shard BFT Execution: Each input shard (S1 and S2) independently runs its own Byzantine Fault Tolerant (BFT) protocol to validate the transaction inputs. If the coins are available and the transaction is legitimate, the input shard commits a "spending transaction" to its local ledger, marking the blue or purple coins as spent. This is a critical departure from 2PC, as only one BFT run is required per input shard for this phase.
4. Cross-Shard Batch Certification: After the BFT run in an input shard successfully secures the transaction, this confirmation needs to be reliably communicated to the output shard (S3). Kronos employs a specialized reliable cross-shard batch certification mechanism for this:

• Grouping and Erasure Coding: Transactions that have been secured in an input shard are grouped based on their target output shard. For each output shard, erasure codes (e.g., Reed-Solomon codes) are used to construct blocks of data. Erasure codes allow the original data to be reconstructed even if a certain fraction of the encoded blocks are lost or corrupted, providing resilience.
• Merkle Tree Construction: These erasure-coded blocks become the leaves of a Merkle tree. A Merkle tree allows for efficient verification of data integrity.
• Optimized Communication: Each node within the input shard is responsible for sending only one of these erasure-coded blocks to all receiving nodes in the output shard. Crucially, this block is accompanied by a Merkle proof (the "off-path" hashes required to verify the block's inclusion in the Merkle tree). This optimization significantly reduces the O(N^2) communication complexity of end-to-end models.
• Receiver-Side Verification and Reconstruction: Upon receiving these blocks and Merkle proofs, nodes in the output shard (S3) can verify the integrity of the data and, using the erasure codes, reconstruct the full set of transaction confirmations, even if some nodes fail to send their blocks or if network partitions occur.

1. Output Shard Buffering and Finalization: Instead of immediately finalizing the transaction, the output shard (S3) maintains a buffer where it waits for all necessary confirmations from the input shards to be securely received and reconstructed. Once all input shards have confirmed their respective parts of the transaction in the buffer, the output shard runs its own BFT protocol to finalize the transaction, committing the receipt of funds to its ledger. This final BFT run ensures that the output state is consistent and agreed upon by the output shard.

In summary, for a valid transaction, Kronos requires only one BFT run per input shard, plus one final BFT run in the output shard. This contrasts sharply with 2PC, which would typically require two BFT runs in each input shard (one for preparation, one for commit) and potentially one in the output shard.

Invalid Transaction Flow

Kronos also efficiently handles invalid transactions, minimizing wasted computational effort. There are two primary sub-scenarios for invalidity:

1. Unavailable Coins (Malicious Client):

• If an input shard discovers that the coins specified by a client (e.g., client D) are not available or have already been spent, it generates an invalidity proof of rejection.
• This proof is then broadcast to all other shards involved in the transaction (other input shards and the output shard).
• Happy Path: This is the most likely and efficient scenario. Because computing this proof by at least one honest node is generally much faster than running a distributed BFT protocol, other shards often receive the proof before they initiate or complete their own BFT runs for that transaction. Upon receiving the proof, these shards immediately abort the transaction and reject the payment request, preventing any further processing and saving BFT costs. The output shard, having nothing in its buffer for this transaction, also simply rejects it.
• Unhappy Path: In a less likely scenario, another input shard might have already completed its BFT run and secured its part of the transaction before receiving the invalidity proof. In this case, that input shard would need to run an additional BFT protocol to refund the transaction (i.e., revert the spending action). The output shard, however, would still reject the transaction as it would not have received all necessary input confirmations.

This proactive rejection mechanism for invalid transactions significantly reduces the computational burden and improves the overall efficiency of the sharded system.

Demo / Proof of Concept

▶ Watch: Introducing Kronos: a secure, generic, and optimized solution (6:10)

The talk directly references the availability of a GitHub repository containing the code and details of an artifact evaluation, confirming that Kronos has been implemented and rigorously tested. While a live demonstration was not explicitly described in the transcript, the speaker presented comprehensive experimental results derived from this implementation and evaluation.

The performance evaluation specifically compared Kronos against existing solutions, including traditional two-phase commit (2PC) protocols and other sharding blockchain designs like AHL and ByzChart. The results indicated a substantial improvement across key performance metrics:

• Throughput: Kronos demonstrated "very high throughput," achieving a "significant improvement" over 2PC-based solutions. This indicates its ability to process a much larger volume of transactions per unit of time.
• Latency: The protocol exhibited "very low latency," which was "significantly less" than that of 2PC and comparable sharding protocols. Low latency is crucial for user experience and the responsiveness of decentralized applications.

These empirical findings validate Kronos's claims of optimized overhead and efficiency, showcasing its practical viability and superior performance in handling the complex demands of cross-shard transactions within a sharded blockchain environment.

Defensive Implications

▶ Watch: Kronos's protocol for handling valid cross-shard transactions (6:50)

Kronos introduces several critical defensive implications for blockchain architects, developers, and network operators striving to build more secure and scalable decentralized systems.

1. Enhanced Atomicity and Consistency: By providing a robust mechanism for ensuring atomicity in cross-shard transactions, Kronos significantly reduces the risk of inconsistent ledger states, double-spending, or partial transaction commitments. Defenders can rely on Kronos to maintain the integrity of multi-shard operations, which is paramount for financial applications and complex smart contracts.
2. Mitigation of Silence Attacks: The protocol's design explicitly addresses the vulnerability of two-phase commit protocols to silence attacks in asynchronous networks. This means that even if malicious nodes attempt to withhold messages, Kronos can continue to make progress or gracefully abort transactions, preventing deadlocks and ensuring system liveness. This resilience is a major defensive advantage in real-world, potentially adversarial network environments.
3. Resistance to Malicious Leaders: The novel cross-shard batch certification mechanism, which distributes communication and verification responsibilities using erasure codes and Merkle trees, inherently prevents a single malicious leader from compromising cross-shard communication. Unlike leader-to-leader models, where a compromised leader can selectively censor or manipulate messages, Kronos ensures that enough information is disseminated for honest nodes to reconstruct and verify transaction proofs, even if some nodes are malicious.
4. Optimized Resource Utilization: The reduction in BFT runs for input shards (from two to one per valid transaction) and the fast rejection mechanism for invalid transactions translate directly into optimized resource utilization. This means less computational power, bandwidth, and time are consumed for transaction processing, making the blockchain more efficient and potentially reducing operational costs for validators and network participants.
5. Foundation for Scalable dApps: For developers building decentralized applications (dApps) that require high throughput and involve complex interactions across different parts of a sharded state, Kronos offers a secure and performant underlying consensus layer. This allows dApp developers to design more ambitious applications without being constrained by the scalability and atomicity limitations of previous sharding approaches.
6. Guidance for Protocol Design: Kronos's innovations in cross-shard communication (erasure codes, Merkle trees, distributed proofs) provide a blueprint for future sharding protocol designs. Defenders and researchers can leverage these techniques to develop even more robust and efficient inter-shard messaging systems.

In essence, Kronos empowers defenders to build and operate sharded blockchains with greater confidence in their security, consistency, and performance, even under adversarial conditions and high transaction loads.

Key Takeaways

• Kronos addresses critical scalability limitations of blockchains through secure and efficient sharding. It specifically targets the challenges of cross-shard transactions, which dominate activity in large sharded networks.
• The protocol ensures strong atomicity for cross-shard transactions while significantly reducing overhead. It achieves this by requiring only one BFT run per input shard for valid transactions, a notable improvement over two-phase commit protocols.
• Kronos is resilient against common attacks like silence attacks and malicious leaders. Its design is generic, supporting both synchronous and asynchronous network environments, making it highly adaptable.
• A novel cross-shard batch certification mechanism optimizes communication. This system leverages erasure codes and Merkle trees to reliably and efficiently transmit transaction confirmations across shards, distributing verification and minimizing communication complexity.
• Invalid transactions are handled efficiently with a fast rejection mechanism. This prevents unnecessary BFT computations, saving resources and improving overall system throughput.
• Experimental results confirm Kronos's superior performance. The protocol demonstrates significantly higher throughput and lower latency compared to existing sharding solutions and two-phase commit approaches.

About the Speaker(s)

The talk was presented by Yizhong Liu at the NDSS Symposium. Yizhong Liu is the speaker for this paper, "Kronos: A Secure and Generic Sharding Blockchain Consensus with Optimized Overhead." It was mentioned that a student co-author, who was expected to be present, could not attend due to visa issues. No further biographical details were provided in the transcript or metadata.