Sedna: Sharding transactions in multiple concurrent proposer blockchains

Alejandro Ranchal-Pedrosa, Benjamin Marsh, Lefteris Kokoris-Kogias, Alberto Sonnino · 2025

Read Sedna: Sharding transactions in multiple concurrent proposer blockchains by Alejandro Ranchal-Pedrosa, Benjamin Marsh, Lefteris Kokoris-Kogias, Alberto Sonnino (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-17045.txt.

Introduction

Alejandro Ranchal-Pedrosa and coauthors present Sedna, a protocol for sending transactions in blockchains with many concurrent proposers. Multi-proposer consensus kills the single-leader bottleneck, but users still face a trilemma among censorship resistance, low latency, and cost.

Copying full transactions to many proposers wastes throughput and exposes payloads to front-running. Sedna instead ships coded symbol bundles to subsets of proposers in private, with execution in a set order once enough symbols finalize to decode. Proofs give liveness and privacy until decode. Bandwidth overhead nears the theoretical floor, a two to three times gain over plain copying, and no consensus change is needed.

Catalog record

CREATORAlejandro Ranchal-Pedrosa, Benjamin Marsh, Lefteris Kokoris-Kogias, Alberto Sonnino
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-17045

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sedna: Sharding transactions in multiple concurrent proposer blockchains Alejandro Ranchal-Pedrosa, Benjamin Marsh, Lefteris Kokoris-Kogias, Alberto Sonnino Abstract Modern blockchains increasingly adopt multi-proposer (MCP) consensus to remove single-leader bottlenecks and improve censorship resistance. However, MCP alone does not resolve how users should disseminate transactions to proposers. Today, users either naively replicate full transactions to many proposers, sacrificing goodput and exposing payloads to MEV, or target few proposers and accept weak censorship and latency guarantees. This yields a practical trilemma among censorship resistance, low latency, and reasonable cost (in fees or system goodput). We present Sedna, a user-facing protocol that replaces naive transaction replication with verifiable, rateless coding. Users privately deliver addressed symbol bundles to subsets of proposers; execution follows a deterministic order once enough symbols are finalized to decode. We prove Sedna guarantees liveness and until-decode privacy , significantly reducing MEV exposure. Analytically, the protocol approaches the information-theoretic lower bound for bandwidth overhead, yielding a 2 2 – 3 × 3\times efficiency improvement over naive replication. Sedna requires no consensus modifications, enabling incremental deployment. 1 Introduction Multiple concurrent proposer (MCP) consensus mitigates single leader bottlenecks by allowing many validators to propose per slot. This improves bandwidth utilization and removes the acute impact of a slow or offline leader. Yet MCP alone does not settle how a user should disseminate their transaction to proposers, and dissemination plays a key role in the user’s experience of latency, price, and censorship exposure. An important argument for blockchain systems to resort to MCP instead of single proposer consensus protocols is the native tolerance to censorship by a subset of the proposers. In MCP, it is straight-forward for users to send the same transaction to a number of the proposers and obtain censorship resistance through naive replication, whereas the closest approximation of this approach in single proposer systems involves the user sending the same transaction iteratively to the next proposer until it is included. It is also well-known that this replication comes at a significant impact on goodput: if all users want to deterministically tolerate censorship from c proposers without it incurring a cost on latency, they each need to send their respective transactions to at least c+1 validators, incurring a worst-case goodput decrease by the replication factor of c+1 (e.g., a decrease of 80\% in goodput to tolerate just 5 censoring proposers). Some systems enforce deduplication by tuning a global parameter that navigates the trade-off between censorship resistance and goodput for all transactions. Beyond system-wide deduplication efforts, a final trade-off remains: how much of the replication bandwidth cost the system absorbs (i.e., how vulnerable it becomes to DoS attacks on goodput) versus how much users pay themselves (i.e., how costly censorship resistance becomes for them). In this sense, goodput impacts can be equated to pricing considerations for users. It is for this reason that we speak of a trilemma of three user-facing properties : censorship resistance (in that the transaction eventually gets included), low latency (in that the transaction gets included as soon as there is capacity for it), and reasonable pricing (either in goodput or economic terms, and whether incurred to the system or user). MEV and dissemination latency. Some users or systems may tolerate losing one of the three properties for specific transactions, but many applications (e.g., trading) require all three, because latency effectively counts as censorship: a brief delay can wipe out an opportunity even if the transaction eventually lands on-chain. Even short delays before inclusion are economically exploitable as MEV. Under MCP, the lever extends from in-block ordering to who first learns a transaction and when . Replicating broadly increases leakage surface; targeting a single proposer is cheaper but trivially censorable. Our goal is to minimize pre-inclusion leakage while keeping byte cost low. Our approach. We present Sedna, a dissemination protocol that replaces whole-transaction replication with verifiable, ratelessly coded symbols addressed to a subset of proposers (“lanes”). The sender commits to the payload, derives a transaction identifier \mathsf{txID} , and generates an unbounded stream of small coded symbols, each tied to the transaction via signatures. These symbols are packaged into addressed bundles and privately delivered to a sampled set of lanes. Inclusion occurs as soon as enough distinct verified symbols for \mathsf{txID} appear in finalized history to reconstruct the payload; at that point the payload is decoded and the transaction is executed. Order is deterministic : transactions are sorted by (\mathrm{ht}_{\mathrm{incl}}(\mathsf{txID}),\mathsf{txID}) , where \mathrm{ht}_{\mathrm{incl}}(\mathsf{txID}) is the first height at which decoding succeeds and the commitment opening verifies. Crucially, Sedna is entirely user-facing: each sender independently selects encoding parameters to navigate the trilemma according to their transaction’s specific requirements, without any protocol-level changes to the underlying MCP consensus. Benefits. For large payloads, the byte overhead of Sedna approaches \frac{1+\varepsilon}{1-c_{e}/n}, where \varepsilon>0 is the small coding overhead of the rateless scheme (e.g., 5\% ), n is the number of proposers, and c_{e} is the effective number of censoring proposers the user wishes to tolerate. This matches the information-theoretic lower bound for any deterministic coding scheme up to the (1+\varepsilon) factor, and is far below the m -fold cost of naive replication. Our evaluation demonstrates that for medium-to-large payloads, Sedna reduces bandwidth overhead by a factor of 2 – 3\times compared to naive replication under typical censorship assumptions, with the gap widening as payload size increases. A user selects how many lanes to contact and how many symbols to place in each bundle so as to meet a target per-slot failure probability \delta . Because symbols are verifiable and payload-hiding until decode, Sedna provides until-decode privacy such the adversary’s early decode probability remains near zero for properly chosen parameters, substantially reducing the pre-inclusion MEV surface compared to transparent mempool dissemination. For completeness, we also analyze two simpler submission variants, naive replication and fixed-rate MDS coding, and identify the parameter regimes where each approach is bandwidth-optimal. Contributions. • Protocol. We introduce Sedna, a user-facing submission layer for MCP that replaces whole-transaction replication with commitment-bound, addressed bundles of verifiable coded symbols; it realizes decode-to-include semantics and a deterministic execution order in a lazy-execution setting, while retaining pay-for-bytes admission. • Correctness. We prove header/commitment non-malleability and deterministic resolution of symbol indices, and show that monotone decoding yields a unique payload from any K verified symbols for honestly encoded transactions (where K is the decode threshold) except with negligible decoding failure probability \delta_{\mathrm{code}} . • Liveness and censorship resistance. We derive per-slot inclusion bounds and give closed-form, conservative prescriptions for how many lanes to contact (and how many symbols to place per bundle) to achieve a target failure probability \delta against an assumed effective censor mass c_{e} . • Privacy (and MEV). We formalize “until - decode” confidentiality, proving that pre - decode leakage is bounded to the bits contained in revealed symbols and the public header, and we quantify an adversary’s early - decode probability (including passive eavesdropping). We discuss how these bounds reduce the pre - inclusion MEV surface and interact with deterministic ordering by (\mathrm{ht}_{\mathrm{incl}}(\mathsf{txID}),\mathsf{txID}) . • Cost and comparisons. We compute exact byte costs including header and per-symbol metadata, derive asymptotic overhead floors approaching \tfrac{1+\varepsilon}{1-c_{e}/n} , and compare Sedna to naive replication and fixed-rate MDS coding, identifying parameter regimes where each approach is bandwidth-optimal,

Read the complete text