TL;DR
This paper introduces the first formal framework for analyzing sharded blockchains, defining key properties like consistency and scalability. It reveals fundamental limitations, showing that robust sharding against adaptive adversaries is only possible under specific conditions, and proposes a modular protocol abstraction called "Divide & Scale" to achieve it.
What Problem Does This Paper Address?
Blockchains face a significant scalability challenge, and sharding is a promising on-chain solution. However, the field has lacked a formal, rigorous definition of what constitutes a "robust sharded ledger." This absence leads to skepticism about whether sharding can truly scale blockchains securely, as existing protocols often define their own goals, making direct comparisons difficult. This paper aims to bridge this gap by providing a formal framework to define, analyze, and compare sharding techniques, ultimately identifying the necessary components for robust sharding and its inherent limitations.
Methods
The authors build upon existing work on robust transaction ledgers (like the Bitcoin backbone protocol) and extend it to the sharded context. They introduce a formal model that defines four key properties for sharded ledgers:
- Persistence: Agreement on transaction order.
- Consistency: Atomic execution of cross-shard transactions (all-or-nothing).
- Liveness: Transactions are eventually processed.
- Scalability: The system's ability to increase transaction throughput without a proportional increase in resources per party.
They then analyze the limitations of sharding under different adversarial models, particularly focusing on adaptive adversaries. A key contribution is the identification of seven essential components for robust sharding, which are then used to construct a protocol abstraction named "Divide & Scale." The paper also defines metrics like "throughput factor" to quantitatively evaluate sharding protocols.
Datasets
Not discussed in the paper. The analysis is theoretical and relies on formal models and proofs rather than empirical datasets.
Key Insights and Ideas
- Formalizing Sharding: The paper provides the first formal framework for sharded ledgers, enabling rigorous analysis and comparison.
- Inherent Limitations: Robust sharding against fully adaptive adversaries is impossible. Scalability is achievable only up to a certain number of shards ($m$) related to the total number of participants ($n$) by $n = c'm \log m$, under an epoch-adaptive adversary.
- Security vs. Scalability Trade-off: The constant $c'$ in the scalability bound highlights a fundamental trade-off between security (adversary resilience) and the number of shards.
- Essential Components: The paper identifies seven critical components for robust sharding, including consensus per shard, cross-shard communication, Sybil resistance, state partitioning, node assignment to shards, randomness generation, and verifiable state compaction.
- Importance of State Compaction: Verifiable state compaction is crucial for long-term scalability, preventing bootstrap costs from becoming a bottleneck.
- Critique of Existing Protocols: The framework is used to analyze prominent sharding protocols (Elastico, Monoxide, OmniLedger, RapidChain), revealing where they fall short of the defined properties.
Key Results
- No Scaling with Fully Adaptive Adversary: A sharded ledger with $n$ participants cannot scale under a fully adaptive adversary.
- Scalability Bound: Under an epoch-adaptive adversary, sharding can scale up to $m$ shards where $n = c'm \log m$.
- Protocol Abstraction: The "Divide & Scale" protocol abstraction is proposed, incorporating the identified sufficient components for robust sharding.
- Analysis of Existing Protocols:
- Elastico fails consistency and scalability.
- Monoxide fails scalability.
- OmniLedger satisfies persistence, consistency, and scalability but fails liveness (though a fix is proposed).
- RapidChain satisfies the properties but only under a weaker adversarial model.
Limitations and Future Work
- Adversarial Models: The analysis primarily focuses on slowly-adaptive adversaries. The paper acknowledges that more restrictive corruption sets (e.g., ensuring at least one honest node per shard) might allow for sharding against adaptive adversaries with additional tools like fraud proofs.
- Synchronous Network Assumption: The analysis is largely conducted under a synchronous network model, which is a simplification.
- Practical Considerations: While the framework provides asymptotic bounds, practical performance improvements of deployed protocols are noted but not fully captured by the theoretical model.
- Future Work: The authors suggest that their framework can be used to prove the security of future sharding protocols and aspire for it to become a standard tool in the field. They also highlight the importance of further research into practical aspects like efficient cross-shard communication and robust state compaction.
Summary updated