# Sedna: Sharding transactions in multiple concurrent proposer blockchains

Crypto.world

> MCP consensus removes the single-leader bottleneck, but it leaves open a practical question: how does a user get their transaction to enough proposers to avoid censorship without paying to send the…

**arXiv**: 2512.17045

**Published**: 2025-12-18

**Authors**: Alejandro Ranchal-Pedrosa, Benjamin Marsh, Lefteris Kokoris-Kogias, Alberto Sonnino

## AI summary

Sedna: Sharding transactions in multiple concurrent proposer blockchains

## Overview

**Research area:** Blockchain consensus and transaction dissemination — specifically, how users should deliver transactions to proposers in multiple concurrent proposer (MCP) blockchains, using rateless/erasure coding to reduce bandwidth while preserving censorship resistance and pre-inclusion privacy.

**Technical level:** Advanced. The paper combines formal protocol specification, cryptographic reductions (EUF-CMA signatures, commitment binding/hiding, collision-resistant hashing), coding theory (MDS, LT/Raptor/RaptorQ), and closed-form liveness bounds; it assumes familiarity with Byzantine fault tolerance and partially synchronous network models.

**Scope (one sentence):** The paper specifies, proves, and analytically evaluates a user-facing submission layer that replaces full transaction replication to proposers with commitment-bound bundles of verifiable rateless-coded symbols, without modifying the underlying consensus.

## What This Paper Is About

MCP consensus removes the single-leader bottleneck, but it leaves open a practical question: how does a user get their transaction to enough proposers to avoid censorship without paying to send the whole payload many times over? Today users either replicate the full transaction widely — which the paper says can cut goodput by 80% to tolerate just 5 censoring proposers — or target few proposers and accept weak censorship and latency guarantees, all while exposing the payload to MEV. Sedna's goal is to give each sender a per-transaction dial that navigates a trilemma among censorship resistance, low latency, and reasonable cost, using coded symbols that hide the payload until enough of them are finalized to decode.

## Key Contributions

1. **A user-facing submission protocol.** Sedna commits to a payload, derives `txID = H(H_pre ∥ C)`, and emits an unbounded stream of small signed coded symbols. These are packaged into addressed bundles and privately delivered to a sampled set of validator "lanes," with decode-to-include semantics and deterministic ordering by `(ht_incl(txID), txID)` under lazy execution, while retaining pay-for-bytes admission.
2. **Correctness proofs.** The paper proves header/commitment non-malleability and deterministic resolution of symbol indices, and shows monotone decoding yields a unique payload from any `K` verified symbols for honestly encoded transactions, except with negligible decoding failure probability `δ_code`.
3. **Liveness and censorship-resistance bounds.** It derives per-slot inclusion bounds and gives closed-form, conservative prescriptions for how many lanes to contact and how many symbols to place per bundle to hit a target failure probability `δ` against an assumed effective censor mass `c_e`.
4. **Privacy formalization plus cost analysis.** It formalizes "until-decode" confidentiality, bounding pre-decode leakage to the bits in revealed symbols and the public header, quantifies an adversary's early-decode probability under passive eavesdropping, and computes exact byte costs (including header and per-symbol metadata) compared against naive replication and fixed-rate MDS coding.

## Main Findings

- **Efficiency versus naive replication.** Analysis shows the protocol approaches the information-theoretic lower bound for bandwidth overhead, yielding a **2–3× efficiency improvement** over naive replication for medium-to-large payloads under typical censorship assumptions, with the gap **widening as payload size increases**.
- **The asymptotic overhead floor.** For large payloads the byte overhead approaches **(1+ε)/(1−c_e/n)**, where ε 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 deterministic coding up to the `(1+ε)` factor and is far below the `m`-fold cost of naive replication.
- **The baseline cost of naive replication.** Deterministically tolerating `c` censoring proposers requires contacting at least `c+1` validators, so the replication factor is `c+1` — a worst-case goodput decrease of that factor, e.g. 80% to tolerate 5 censoring proposers.
- **What `c_e` actually is.** For `c ≤ f`, the adversary cannot selectively censor lanes outside its control, so `c_e = c`. For `c > f`, the adversary can also stall correct lanes, giving `c_e = n − (2f+1) + c` in the `n = 3f+1` model where finalization needs `⌊(n+f)/2⌋ + 1 = 2f+1` votes; `c_e = n` for `c > 2f`, so the strongest tolerable adversary is `c = 2f`.
- **The decode threshold.** `K = ⌈(1+ε) · S/ℓ_sym⌉`, with ε small (e.g., 5%) and `δ_code` the residual failure probability of the chosen code family (LT/Raptor/RaptorQ).
- **Deterministic ordering.** Because finality fixes the ledger prefix, the deduplicated symbol set, the decoder output, and hence `ht_incl(txID)` are all fixed, so the lexicographic order on `(ht_incl(txID), txID)` is a deterministic function of the finalized ledger (Theorem 1).
- **Equivocation is handled without proofs.** A malicious sender can sign conflicting symbols for the same index across lanes, but per-index deduplication (scanning by height, then lane index, then intra-block position) fixes one value per `(txID, j)`. Decoding then typically fails or yields an invalid transaction, which is discarded while bandwidth fees remain charged — so equivocation is economically irrational rather than cryptographically prevented.
- **Verification is deliberately shallow.** Validators check hash consistency, header signature, the accounting/fees predicate, and the bundle signature — four checks — but do **not** verify that symbols are correctly encoded against the commitment. Malformed symbols are handled economically, replacing AVID-style correctness proofs with deterrence.
- **Three variants.** Sedna is analyzed in naive, fixed-rate MDS, and rateless forms, and the paper identifies the parameter regimes in which each is bandwidth-optimal.

## Methodology in Plain English

The authors start from an observation about deployment reality: MCP systems in production either push duplication costs onto the system or onto users. Sui, Aptos and Red-Belly absorb duplication (the paper notes Sui transactions are naturally duplicated up to 5 times); Hedera charges users for all duplication but cannot fully protect the system under asynchronous execution; Filecoin stays trustless with an average replication factor of 3–4 and some messages duplicated as much as 9 times.

Against that backdrop, the design work is a substitution: instead of sending the whole transaction to many proposers, send small coded pieces of it. The sender commits to the payload first, so the identifier is fixed before any dispersion; then each bundle carries a signed set of index–symbol pairs addressed to one lane. Because the code is rateless, the sender can keep producing new symbols and can adapt how many lanes to use based on how quickly early symbols land on-chain. Inclusion happens only when enough distinct verified symbols appear in finalized history to decode, at which point the commitment opening is checked and the transaction executes.

The formal work builds three layers on top of that design: safety lemmas (deterministic resolution, non-malleability, unique decode) that reduce to standard assumptions about hashing, signatures and commitments; liveness bounds derived under a partially synchronous model with an unknown GST, where liveness holds after GST and safety holds always; and a privacy argument that treats symbols as pseudorandom linear combinations, so `r` symbols reveal at most `r · ℓ_sym` bits. The cost analysis computes exact byte costs including headers and per-symbol metadata, then takes asymptotics to show the approach to the `(1+ε)/(1−c_e/n)` floor.

The evaluation in Section 7 is described as covering representative design points, but the truncated content provided here does not report the specific testbed, dataset sizes, or benchmark names used, so those are not summarized.

## Why This Matters

**Impact on research.** Prior work established that censorship-resistant consensus costs latency — 4 rounds in synchrony and 5 in partial synchrony, exactly two rounds more than classic leader-based Byzantine Broadcast — and the MCP framework achieves those bounds. Sedna addresses the orthogonal, previously under-specified dimension: the *bandwidth* price a user pays to reach enough proposers. It also reframes erasure coding, which in data-availability systems is typically applied post-proposal, as a user-side dissemination primitive, and it relaxes AVID's requirement that the dealer commit to the entire bundle up front by leaning on signature-based verification, per-index deduplication, and consensus-defined decoding.

**Real-world applications:**

- **Latency-sensitive trading.** Applications where a brief delay is economically equivalent to censorship, because the delay itself is exploitable as MEV.
- **MEV mitigation for MCP chains.** Until-decode privacy shrinks the window in which an adversary can front-run, sandwich, or strategically reorder based on a visible mempool entry.
- **Fee and goodput budgeting for high-throughput chains.** Senders pick lane count and bundle size per transaction to meet a target failure probability `δ`, rather than living with a system-wide deduplication parameter.
- **Censorship-resistant submission without trusted relays.** Replacing the prevalent pattern of trusted RPC servers that enforce a system's deduplication target.

**Industry relevance.** The protocol requires no consensus modifications, which the authors present as enabling incremental deployment on existing MCP networks. The trilemma framing is explicitly commercial: goodput impact is equated with pricing, and the question of whether the system or the user absorbs duplication cost is a live design divergence among deployed networks.

## Future Directions

- **Parameter selection under real adversaries.** The liveness prescriptions assume an effective censor mass `c_e`, but the paper concedes that an adversary's concrete power to censor lanes outside its direct control depends on the specific consensus implementation — calibrating `c_e` empirically per deployment is left open.
- **Sender-side adaptivity.** The rateless variant lets a sender adjust lane count based on how fast initial symbols finalize; how to schedule that adaptation optimally against latency and fee targets is a natural next problem.
- **Economic parameterization.** Correct encoding is enforced by charging bandwidth fees rather than by proofs; setting those fees so that garbage submission and equivocation are reliably unprofitable is an open design question.
- **Integration with existing deduplication and relay infrastructure.** How Sedna composes with system-wide deduplication targets, trusted RPC relaying, and single-leader mitigations such as PBS and private order-flow channels is not resolved here.

## Target Audience

Protocol designers and consensus researchers working on MCP and censorship-resistant dissemination; applied cryptographers interested in verifiable information dispersal and rateless codes; MEV researchers studying pre-inclusion leakage; and engineering teams at MCP-based networks who must decide whether users or the system pay for transaction duplication. Readers need comfort with Byzantine fault tolerance, coding theory, and reduction-based proofs; the paper is not an introductory treatment.

## Authors’ 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…

[The full abstract on arXiv](https://arxiv.org/abs/2512.17045)

[Read the original paper](https://arxiv.org/abs/2512.17045)

---

Canonical: https://crypto.world/paper/sedna-sharding-transactions-in-multiple-concurrent-proposer-blockchains-2512.17045
