conference paper published yes Zeta Avarikioti author Antoine Desjardins author 06d0c166-aec1-11ee-a7c0-b96e840a602b Eleftherios Kokoris Kogias author f5983044-d7ef-11ea-ac6d-fd1430a26d30 Roger Wattenhofer author ElKo department SIROCCO: Structural Information and Communication Complexity 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. Springer Nature2023Alcalá de Henares, Spain eng 0302-9743 1611-3349 9783031327322 00129278260001010.1007/978-3-031-32733-9_10 13892199-245 Avarikioti Z, Desjardins A, Kokoris Kogias E, Wattenhofer R. Divide &#38; Scale: Formalization and roadmap to robust sharding. In: <i>30th International Colloquium on Structural Information and Communication Complexity</i>. Vol 13892. Springer Nature; 2023:199-245. doi:<a href="https://doi.org/10.1007/978-3-031-32733-9_10">10.1007/978-3-031-32733-9_10</a> Avarikioti, Z., Desjardins, A., Kokoris Kogias, E., &#38; Wattenhofer, R. (2023). Divide &#38; Scale: Formalization and roadmap to robust sharding. In <i>30th International Colloquium on Structural Information and Communication Complexity</i> (Vol. 13892, pp. 199–245). Alcalá de Henares, Spain: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-32733-9_10">https://doi.org/10.1007/978-3-031-32733-9_10</a> Z. Avarikioti, A. Desjardins, E. Kokoris Kogias, and R. Wattenhofer, “Divide &#38; Scale: Formalization and roadmap to robust sharding,” in <i>30th International Colloquium on Structural Information and Communication Complexity</i>, Alcalá de Henares, Spain, 2023, vol. 13892, pp. 199–245. Avarikioti Z, Desjardins A, Kokoris Kogias E, Wattenhofer R. 2023. Divide &#38; Scale: Formalization and roadmap to robust sharding. 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 13892, 199–245. Z. Avarikioti, A. Desjardins, E. Kokoris Kogias, R. Wattenhofer, in:, 30th International Colloquium on Structural Information and Communication Complexity, Springer Nature, 2023, pp. 199–245. Avarikioti, Zeta, et al. “Divide &#38; Scale: Formalization and Roadmap to Robust Sharding.” <i>30th International Colloquium on Structural Information and Communication Complexity</i>, vol. 13892, Springer Nature, 2023, pp. 199–245, doi:<a href="https://doi.org/10.1007/978-3-031-32733-9_10">10.1007/978-3-031-32733-9_10</a>. Avarikioti, Zeta, Antoine Desjardins, Eleftherios Kokoris Kogias, and Roger Wattenhofer. “Divide &#38; Scale: Formalization and Roadmap to Robust Sharding.” In <i>30th International Colloquium on Structural Information and Communication Complexity</i>, 13892:199–245. Springer Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-32733-9_10">https://doi.org/10.1007/978-3-031-32733-9_10</a>. 147442024-01-08T12:56:46Z2025-09-09T14:10:46Z