Divide & Scale: Formalization and Roadmap to Robust Sharding

Zeta Avarikioti, Antoine Desjardins, Lefteris Kokoris-Kogias, Roger WattenhoferSIROCCO 2023 · OpenReview

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

Abstract

Sharding distributed ledgers is a promising on-chain solution for scaling blockchains but lacks formal grounds, nurturing skepticism on whether such complex systems can scale blockchains securely. We fill this gap by introducing the first formal framework as well as a roadmap to robust sharding. In particular, we first define the properties sharded distributed ledgers should fulfill. We build upon and extend the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system. Using our model, we explore the limitations of sharding. We show that a sharded ledger with n participants cannot scale under a fully adaptive adversary, but it can scale up to m shards where $$n=c'm\log m$$ , under an epoch-adaptive adversary; the constant $$c'$$ encompasses the trade-off between security and scalability. This is possible only if the sharded ledgers create succinct proofs of the valid state updates at every epoch. We leverage our results to identify the sufficient components for robust sharding, which we incorporate in a protocol abstraction termed Divide & Scale. To demonstrate the power of our framework, we analyze the most prominent sharded blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties.
BibTeX
@inproceedings{avarikioti2023divide,
  author = {Zeta Avarikioti and Antoine Desjardins and Lefteris Kokoris-Kogias and Roger Wattenhofer},
  title = {{Divide \& Scale: Formalization and Roadmap to Robust Sharding}},
  booktitle = {SIROCCO},
  year = {2023},
  url = {https://openreview.net/forum?id=2iDfgCxBq9},
}
Figure