PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiple Concurrent Proposers: Why and How

Pranav Garimidi, Joachim Neu, Max Resnick

arXiv:2509.23984v1cs.CRcs.DC

TL;DR

Single-proposer control over transaction inclusion enables MEV, while on-chain auctions require protection from both censorship and premature bid visibility. The paper proposes MCP, which provides these properties with one network round-trip of additional latency after optimizations.

  • Problem

    A single proposer’s control over transaction inclusion and ordering enables MEV, and on-chain auctions can fail when proposers censor bids or see them before confirmation.

    Source: §1 · pp. 1–2

  • Method

    MCP has multiple proposers submit transaction batches for the same slot, with a relay committee mediating between them and the consensus leader.

    Source: §3.1 · p. 20

  • Results

    One network round-trip of additional latency after optimizations lets MCP provide censorship resistance and hiding while remaining safe and live.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Transactions submitted to honest nodes receive immediate inclusion while their contents remain concealed until the consensus decision is final.

    Source: §1 · p. 2

    MCP does not obscure transactions from the proposer; repeated adverse behavior may lead users to switch proposers in a competitive environment.

    Source: Hiding · p. 21

Abstract

from arXiv · show

Traditional single-proposer blockchains suffer from miner extractable value (MEV), where validators exploit their serial monopoly on transaction inclusion and ordering to extract rents from users. While there have been many developments at the application layer to reduce the impact of MEV, these approaches largely require auctions as a subcomponent. Running auctions efficiently on chain requires two key properties of the underlying consensus protocol: selective-censorship resistance and hiding. These properties guarantee that an adversary can neither selectively delay transactions nor see their contents before they are confirmed. We propose a multiple concurrent proposer (MCP) protocol offering exactly these properties.

1 Introduction

The paper frames single-proposer control over transaction inclusion as a source of MEV and motivates consensus guarantees against both censorship and bid visibility. It presents MCP as a lightweight addition to PBFT-style consensus that provides censorship resistance and hiding.

1 Introduction

  • A single proposer’s monopoly over transaction inclusion and ordering enables MEV extraction, distorts markets, undermines fair access, and constrains viable on-chain applications.The paper identifies this market structure as the underlying cause that existing MEV countermeasures have not satisfactorily addressed.Source: §1 · p. 1
  • MCP adds censorship resistance and hiding to standard PBFT-style consensus as a lightweight gadget, with only one network round-trip of additional latency after optimizations.The paper proves the construction safe and live.Source: §1 · p. 2

1.1 Three Examples

  • Censorship alone can break a first-price auction: Bob can censor Alice’s bid and win with a near-zero bid, whether or not he sees her bid.The example motivates selective-censorship resistance as a distinct requirement.Source: §1.1 · p. 3
  • When Bob can see Alice’s bid, even without censorship, adverse selection can unravel the auction; hiding her bid prevents that same equilibrium, though the remaining last-look effect persists.Under a geometric Brownian motion price process, prior work finds auction revenue converges to v_tA as Bob’s time advantage tends to zero [54].Source: §1.1 · p. 4

1.2 Related Work

  • Fair-ordering protocols face limits from Condorcet cycles and transaction-created cycles, while encryption and batching do not remove a proposer’s power over inclusion.Batching can leave auctions vulnerable to censorship, and encrypted transactions may be bypassed for time-sensitive bids.Source: §1.2 · p. 5
  • DAG-based and leaderless protocols may still permit selective censorship or short-term confirmation delays, and the described DAG protocols do not provide hiding.The passage distinguishes eventual inclusion from confirmation at the next possible opportunity.Source: §1.2 · pp. 6–7

2.1 Cryptographic Primitives

This section presents the cryptographic primitives and security framework used by the scheme, including signatures, commitments, and hiding erasure-correcting codes. It also proves a hiding guarantee for a construction combining vector commitments with hiding erasure-correcting codes under the stated parameter conditions.

2.1 Cryptographic Primitives

  • The primitive definitions use a PPT adversary, security parameter κ, and finite field F with |F| ≥ 2κ.Source: §2.1 · p. 7

2.1.1 Signatures

  • Signatures comprise key generation, signing, and verification, and a good scheme is correct and existentially unforgeable; BLS is one example.Unforgeability means a PPT adversary cannot produce a valid signature for a message it did not query for signing, except with negligible probability.Source: §2.1.1 · pp. 7–8

2.1.2 Vector Commitments

  • A hiding Merkle-tree vector commitment hashes each value with per-position randomness, uses the root as commitment, and opens positions with the value, randomness, and Merkle path.The construction satisfies correctness, binding, position binding, and hiding in the random oracle model.Source: §2.1.2 · pp. 10, 12

2.1.3 Hiding Erasure-Correcting Codes

  • The HECC construction is correctible from any K + T distinct shreds, while any T shreds reveal no information about the encoded message.It is instantiated using Reed–Solomon coding with T random field elements appended to the message before encoding.Source: §2.1.3 · pp. 13–14

2.1.4 Combining Vector Commitments and Hiding Erasure-Correcting Codes

  • With HECC-encoded masking randomness, any K + T distinct shreds are uniformly random over F^(K+T), supporting the protocol’s vector-commitment hiding requirement.The protocol requires commitments to remain hiding when an adversary knows at most T openings; Lemma 3 establishes uniformity for K + T shreds.Source: §2.1.4 · p. 14
  • With K,T > 0 and L = N, V = R = F, Lemma 4 gives every PPT adversary’s success probability negligible in κ in the hiding game with up to T distinct openings.The challenger commits to one of two supplied vectors using an HECC encoding of random values.Source: §2.1.4 · p. 15
  • Because up to T observed shreds leave any unopened shred uniform, and a PPT adversary’s chance of querying the relevant random-oracle input is negligible, the Merkle hashes have identical distributions for either vector.The proof bounds the query event by q/|F| ≤ q/2^κ = negl(κ); conditioned on its not occurring, unopened leaves and thus all tree hashes, including the commitment, are indistinguishable.Source: §2.1.4 · p. 16

2.2 Setting, Adversary, Network

The paper assumes a permissioned setting with computationally bounded adversaries and a partially synchronous network. Nodes have synchronized clocks, and the adversary statically corrupts nodes and controls message delays.

2.2 Setting, Adversary, Network

  • The paper adopts a standard permissioned setting with a computationally bounded adversary and partial synchrony.This is presented as an exposition choice.Source: §2.2 · p. 16
  • The setting has n identified nodes, synchronized real-time clocks, and protocol slots that index logical steps.Nodes receive environment inputs and communicate through the protocol.Source: §2.2 · p. 16
  • A PPT adversary statically corrupts f nodes before protocol randomness is drawn and can make them deviate arbitrarily.Honest nodes follow the protocol; the adversary also determines message delays.Source: §2.2 · p. 16
  • The network is partially synchronous: before GST delays are arbitrary, and after GST they are bounded by the known Δ.After GST, messages sent by an honest node by time t reach all honest nodes by max(t, GST) + Δ.Source: §2.2 · p. 16

2.3 Consensus Basics

The paper defines atomic broadcast through consistent logs and eventual transaction inclusion, then equips consensus with slots, leaders, and proposal times. This interface supports leader-driven liveness guarantees.

2.3.1 Safety and Liveness of Atomic Broadcast

  • Atomic broadcast requires honest nodes’ logs to remain consistent and every transaction submitted to an honest node to eventually appear in every honest node’s log.The paper calls these properties safety and liveness, respectively.Source: §2.3.1 · p. 17
  • Security requires safety and liveness in partially synchronous executions with f/n ≤ τ, except with negligible probability.The resilience threshold is τ.Source: §2.3.1 · p. 17

2.3.2 Slightly Enriched Interface

  • Consensus proceeds in slots with a designated leader and fixed proposal time; confirmed payloads are annotated with their slot numbers.The interface is a syntactic refinement of atomic broadcast; candidate protocols can be adapted to it.Source: §2.3.2 · pp. 17–18
  • By each slot’s proposal time, its leader submits a payload; the protocol emits confirmed payloads by slot, or ⊥ when none is confirmed.The interface also permits regular proposal times and non-decreasing confirmed slot numbers.Source: §2.3.2 · pp. 17–18
  • After GST plus cΔ, an honest slot leader’s timely proposal is eventually included under leader-driven liveness.The guarantee applies when the leader invokes the input no later than the slot’s proposal time.Source: §2.3.2 · p. 18

2.4 Economic Consensus Properties

The paper adds selective-censorship resistance and hiding to traditional consensus properties: transactions should be confirmed at the next opportunity, while their contents remain unknown until inclusion and position are decided. MCP uses multiple proposers and relays to support these properties.

2.4 Economic Consensus Properties

  • Selective-censorship resistance and hiding target timely transaction inclusion and concealment of pending contents until the adversary can no longer act on them.The paper motivates both as economically relevant consensus properties beyond traditional safety and liveness.Source: §2.4 · p. 18

2.4.1 Selective-Censorship Resistance

  • At a slot after GST, either no transactions are confirmed in that slot or all transactions submitted to honest nodes by its proposal time are included by then.Thus, to censor any transaction in a slot, the adversary must censor all transactions for that slot.Source: §2.4.1 · p. 18

2.4.2 Hiding

  • Hiding means the adversary cannot learn honest nodes’ input transactions before they enter the protocol’s valency.Valency captures decisions that are inevitable under every future adversarial strategy, even if honest nodes have not yet recognized them.Source: §2.4.2 · p. 19

2.4.3 Practical Considerations of Selective-Censorship Resistance and Hiding

  • The model treats nodes as both transaction-input entities and consensus participants, rather than modeling users or RPCs/block builders.Unlike encrypted mempools, this hiding guarantee does not keep transactions private from all nodes; it leaves room for block-space filtering and fee checks.Source: §2.4.3 · p. 19
  • Hiding alone is insufficient: without selective-censorship resistance, an adversary can pressure users to route transactions through it, exposing their flow.The paper notes that users can route through multiple nodes to choose nodes that respect their privacy.Source: §2.4.3 · p. 19
  • MCP has four phases: proposers send transaction batches as shreds to relays, relays attest to the leader, the leader submits a block to consensus, and relays broadcast shreds for reconstruction.All nodes decode available batches and output the transactions.Source: §2.4.3 · p. 20

3.1 Philosophy & Overview

MCP replaces a single slot leader’s transaction batch with batches from multiple concurrent proposers, mediated by relays. Relay attestations constrain selective censorship, while encoded shreds conceal batch contents until consensus confirms inclusion.

3.1 Philosophy & Overview

  • Multiple proposers submit transaction batches for the same slot, and a relay committee mediates between them and the consensus leader.Unlike a single leader proposing all transactions, MCP has nodes submit separate batches.Source: §3.1 · p. 20

Selective-Censorship Resistance

  • A valid block must include attestations from many relays, forcing inclusion of enough honest attestations to confirm all honest proposals during synchrony.The leader can censor a target batch only by proposing no block at all.Source: Selective-Censorship Resistance · p. 21

Hiding

  • HECC-encoded shreds reveal no batch information to adversarial relays, and honest relays release shreds only after consensus confirms inclusion.Thus, nodes other than the originating proposer cannot observe or adapt to transaction contents before confirmation.Source: Hiding · p. 21
  • MCP does not hide transactions from their originating proposer; repeated interaction and competition may let users switch proposers acting against their interests.The stated mitigation concerns adverse selection by proposers in repeated interactions.Source: Hiding · p. 21

3.2 Detailed Description

The MCP gadget augments an underlying consensus protocol with per-slot proposer, relay, consensus, and reconstruction phases. Its setup and thresholds govern which batches are attested, included, and reconstructed.

3.2 Detailed Description

  • The MCP gadget composes with a standard consensus protocol that satisfies the enriched interface, and its construction has four phases per slot.The phases are proposer, relay, consensus, and reconstruction.Source: §3.2 · p. 22

3.2.1 Setup (Alg. 3, ln. 1)

  • Setup samples proposers and relays for each slot and assumes an underlying consensus leader and proposal time.The detailed description also specifies shared cryptographic parameters and keys.Source: §3.2.1 · p. 22

3.2.2 Proposer Phase (Alg. 3, ln. 8)

  • Proposers batch pending transactions, HECC-encode them into relay-specific shreds, and privately send each relay its shred with a commitment and opening proof.The writeup assumes batches can be arbitrarily large and include all transactions a proposer hears about, ignoring block-size limits and transaction fees.Source: §3.2.2 · pp. 22–23

3.2.3 Relay Phase (Alg. 3, ln. 20)

  • Relays verify and store received shreds, then attest to their receipt by sending the leader signed commitments without revealing the shreds.The attestation certifies receipt, verification, and storage while revealing no information about the individual shred.Source: §3.2.3 · p. 25

3.2.4 Consensus Phase (Alg. 3, ln. 30)

  • The consensus leader validates relay and proposer signatures, assembles the attestations into a block, signs it, and submits it to the underlying consensus protocol.Source: §3.2.4 · p. 25

3.2.5 Reconstruction Phase (Alg. 4, ln. 7)

  • After consensus, nodes deem a batch available when enough relays attest to the same commitment without conflicting commitments, then release shreds for reconstruction.Nodes decode batches from at least γnrelay valid shreds, check consistency against the commitment, and deterministically order valid reconstructed transactions.Source: §3.2.5 · pp. 25–26

4 Analysis

The analysis specifies parameter conditions for MCP’s guarantees and proves safety, selective-censorship resistance, liveness, and hiding under stated assumptions. The instantiated parameters target resilience 1/5.

4.1 Parameter Choices

  • For target resilience τ = 1/5, the instantiation sets µ = 4/5, φ = 3/5, and γ = 2/5; liveness, censorship resistance, and hiding require parameter inequalities tied to relay resilience.The analysis assumes nprop = n, nrelay = Θ(n), and an underlying consensus protocol secure with resilience 1/5 and satisfying leader-driven liveness.Source: §4.1 · pp. 26–27

4.2 Safety

  • Assuming the underlying protocol is secure with resilience n/5, MCP is safe: honest nodes reconstruct identical batches or discard them, yielding consistent logs.Safety holds even when the sampled relay set has more than nrelay/5 Byzantine relays, though liveness may then fail.Source: §4.2 · pp. 27–28

4.3 Selective-Censorship Resistance

  • With fewer than nrelay/5 Byzantine relays, MCP is selectively censorship resistant; an adversary can censor only indiscriminately by withholding a valid block.In that case the adversary cannot include its own transactions in the slot, and users can resubmit in the next slot.Source: §4.3 · p. 29

4.4 Liveness

  • If the underlying protocol is secure with resilience n/5 and satisfies leader-driven liveness, MCP is live with overwhelming probability and also satisfies leader-driven liveness.Source: §4.4 · p. 30

4.5 Hiding

  • Under the stated consensus and HECC parameters, MCP is hiding with overwhelming probability; adversarial relays’ shreds do not reveal whether a batch contains either challenge transaction.The adversary learns transaction contents only after an honest relay releases shreds, which occurs after the slot’s block is confirmed.Source: §4.5 · pp. 31–32

5 Discussion

MCP’s liveness, selective-censorship resistance, and hiding have probabilistic tradeoffs shaped by relay thresholds and parameter choices. The discussion also describes liveness recovery, proposer allocation, and a relay optimization, while noting a safety caveat for the recovery gadget.

5.1 Tradeoffs in Probabilistic Guarantees

  • Safety always holds, but liveness, selective-censorship resistance, and hiding hold with overwhelming probability only when fewer than nrelay/5 relays are adversarial in a slot.The analyzed parameterization is vulnerable to an outsized adversarial relay sample when nrelay is low.Source: §5.1 · p. 32
  • Favoring liveness by adjusting φ or T can leave selective-censorship resistance or hiding vulnerable to occasional failure against a weaker adversary.The per-slot fault probabilities are computed from the binomial number of Byzantine relays and the relevant thresholds.Source: §5.1 · p. 32
  • Roughly 1 in 109 per slot is the probability of either a potential liveness failure or a potential selective-censorship failure with the stated parameters.The passage equates this to once every 10 years at 400-millisecond slot times; hiding can be broken fairly often when f = T.Source: §5.1 · p. 32
  • The heatmap varies the liveness-fault probability with Byzantine fraction f and relay count nrelay, for φ = 0.6 and γ = 0.3.Red rectangles mark the highest f for each relay count that maintains probability at most 1 : 109.Source: §5.1 · p. 33

5.2 Recovering Liveness

  • A batch-skip certificate lets nodes agree that an unavailable batch can be skipped while atomic broadcast continues making progress independently of reconstruction.If enough shreds arrive, an honest node can reconstruct and forward the batch; otherwise, nodes can eventually agree to skip it.Source: §5.2 · pp. 33–34
  • Recovery can use full rollback or isolated skip; isolated skip preserves reconstructible later slots but may create bursty bandwidth needs to release delayed batches.Full rollback discards blocks proposed from the failed slot through issuance of the skip certificate, including batches that might have been reconstructed.Source: §5.2 · p. 34

5.3 Choosing Proposers and Allocating Blockspace

  • MCP’s communication overhead scales with aggregate blocksize, so adding proposers costs only an extra commitment per proposer and associated signature verifications.Batches must be capped for feasible reconstruction and timely confirmation; stake-weighted eligibility is one proposed selection rule, with blockspace proportional to stake.Source: §5.3 · p. 34

5.4 Localized Relay Optimization

  • Localized relays can save one of the protocol’s five rounds by privately forwarding shreds among a validator’s relays before they broadcast after the required conditions are met.The described batch-skip gadget can be unsafe if some nodes reconstruct a batch while others vote to skip; additional reconstruction-certification votes add communication and latency.Source: §5.4 · p. 34

Related papers

Loading 2509.23984v1…