---
_id: '14744'
abstract:
- lang: eng
  text: "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.\r\nUsing 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."
acknowledgement: The work was partially supported by the Austrian Science Fund (FWF)
  through the project CoRaF (grant agreement 2020388).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Zeta
  full_name: Avarikioti, Zeta
  last_name: Avarikioti
- first_name: Antoine
  full_name: Desjardins, Antoine
  id: 06d0c166-aec1-11ee-a7c0-b96e840a602b
  last_name: Desjardins
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: Roger
  full_name: Wattenhofer, Roger
  last_name: Wattenhofer
citation:
  ama: 'Avarikioti Z, Desjardins A, Kokoris Kogias E, Wattenhofer R. Divide &
    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>'
  apa: '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>'
  chicago: '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>.'
  ieee: '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.'
  ista: '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.'
  mla: '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>.'
  short: 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.
conference:
  end_date: 2023-06-09
  location: Alcalá de Henares, Spain
  name: 'SIROCCO: Structural Information and Communication Complexity'
  start_date: 2023-06-06
date_created: 2024-01-08T12:56:46Z
date_published: 2023-06-01T00:00:00Z
date_updated: 2024-01-09T07:40:57Z
day: '01'
department:
- _id: ElKo
doi: 10.1007/978-3-031-32733-9_10
intvolume: '     13892'
language:
- iso: eng
month: '06'
oa_version: None
page: 199-245
publication: 30th International Colloquium on Structural Information and Communication
  Complexity
publication_identifier:
  eisbn:
  - '9783031327339'
  eissn:
  - 1611-3349
  isbn:
  - '9783031327322'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Divide & Scale: Formalization and roadmap to robust sharding'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13892
year: '2023'
...
---
_id: '13238'
abstract:
- lang: eng
  text: "We consider a natural problem dealing with weighted packet selection across
    a rechargeable link, which e.g., finds applications in cryptocurrency networks.
    The capacity of a link (u, v) is determined by how much nodes u and v allocate
    for this link. Specifically, the input is a finite ordered sequence of packets
    that arrive in both directions along a link. Given (u, v) and a packet of weight
    x going from u to v, node u can either accept or reject the packet. If u accepts
    the packet, the capacity on link (u, v) decreases by x. Correspondingly, v’s capacity
    on (u, v) increases by x. If a node rejects the packet, this will entail a cost
    affinely linear in the weight of the packet. A link is “rechargeable” in the sense
    that the total capacity of the link has to remain constant, but the allocation
    of capacity at the ends of the link can depend arbitrarily on the nodes’ decisions.
    The goal is to minimise the sum of the capacity injected into the link and the
    cost of rejecting packets. We show that the problem is NP-hard, but can be approximated
    efficiently with a ratio of (1+ε)⋅(1+3–√) for some arbitrary ε>0.\r\n."
acknowledgement: We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful
  discussions about different variants of the problem. This work is supported by the
  European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025,
  the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant
  470029389 (FlexNets), 2021–2024.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
- first_name: Michelle X
  full_name: Yeo, Michelle X
  id: 2D82B818-F248-11E8-B48F-1D18A9856A87
  last_name: Yeo
  orcid: 0009-0001-3676-4809
citation:
  ama: 'Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links
    in cryptocurrency networks: Complexity and approximation. In: <i>SIROCCO 2023:
    Structural Information and Communication Complexity </i>. Vol 13892. Springer
    Nature; 2023:576-594. doi:<a href="https://doi.org/10.1007/978-3-031-32733-9_26">10.1007/978-3-031-32733-9_26</a>'
  apa: 'Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2023). Weighted packet selection
    for rechargeable links in cryptocurrency networks: Complexity and approximation.
    In <i>SIROCCO 2023: Structural Information and Communication Complexity </i> (Vol.
    13892, pp. 576–594). Alcala de Henares, Spain: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-32733-9_26">https://doi.org/10.1007/978-3-031-32733-9_26</a>'
  chicago: 'Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection
    for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.”
    In <i>SIROCCO 2023: Structural Information and Communication Complexity </i>,
    13892:576–94. Springer Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-32733-9_26">https://doi.org/10.1007/978-3-031-32733-9_26</a>.'
  ieee: 'S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable
    links in cryptocurrency networks: Complexity and approximation,” in <i>SIROCCO
    2023: Structural Information and Communication Complexity </i>, Alcala de Henares,
    Spain, 2023, vol. 13892, pp. 576–594.'
  ista: 'Schmid S, Svoboda J, Yeo MX. 2023. Weighted packet selection for rechargeable
    links in cryptocurrency networks: Complexity and approximation. SIROCCO 2023:
    Structural Information and Communication Complexity . SIROCCO: Structural Information
    and Communication Complexity, LNCS, vol. 13892, 576–594.'
  mla: 'Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency
    Networks: Complexity and Approximation.” <i>SIROCCO 2023: Structural Information
    and Communication Complexity </i>, vol. 13892, Springer Nature, 2023, pp. 576–94,
    doi:<a href="https://doi.org/10.1007/978-3-031-32733-9_26">10.1007/978-3-031-32733-9_26</a>.'
  short: 'S. Schmid, J. Svoboda, M.X. Yeo, in:, SIROCCO 2023: Structural Information
    and Communication Complexity , Springer Nature, 2023, pp. 576–594.'
conference:
  end_date: 2023-06-09
  location: Alcala de Henares, Spain
  name: 'SIROCCO: Structural Information and Communication Complexity'
  start_date: 2023-06-06
date_created: 2023-07-16T22:01:12Z
date_published: 2023-05-25T00:00:00Z
date_updated: 2025-07-14T09:09:53Z
day: '25'
department:
- _id: KrPi
- _id: KrCh
doi: 10.1007/978-3-031-32733-9_26
ec_funded: 1
external_id:
  arxiv:
  - '2204.13459'
intvolume: '     13892'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2204.13459
month: '05'
oa: 1
oa_version: Preprint
page: 576-594
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 'SIROCCO 2023: Structural Information and Communication Complexity '
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031327322'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '14506'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: 'Weighted packet selection for rechargeable links in cryptocurrency networks:
  Complexity and approximation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13892
year: '2023'
...