PaperlayerView exact revision on arXiv

Source-linked AI summary

Bandwidth Fee Mechanisms for Certified Transaction Dissemination

Eleftheria Fassman, Mahimna Kelkar, Benjamin Marsh, Ke Wu

arXiv:2610.00697v1cs.GT

TL;DR

The paper addresses how to price transaction bandwidth used before consensus, when execution-based fees may not reflect dissemination costs. It models certified dissemination and analyzes incentive limits and pricing mechanisms; it proves coalition-impossibility results and studies bandwidth pricing dynamics under stated assumptions.

  • Problem

    Transactions use bandwidth before consensus, while execution-based fees may not charge transactions that are excluded or fail execution.

    Source: §1 · p. 3

  • Method

    The paper studies certified-dissemination pricing through BFMs, analyzing transcript-based mechanisms and validator incentives around transaction forwarding.

    Source: §1 · p. 3, §2.2 · p. 10, §2.3 · p. 13

  • Results

    No non-trivial transcript-based BFM satisfies 2-VIC, and no non-trivial BFM simultaneously achieves UIC, 1-VIC, and 1-SCP.

    Source: §5.1 · p. 23, §5.2 · p. 25

  • Takeaways & Limitations

    In transcript-based BFMs, two validators can delegate signing to create an apparently valid certificate without transferring data and save bandwidth costs.

    Source: §2.2 · p. 10

    The dynamic analysis assumes one-time validator reports and honest later execution; decentralized routing and farsighted multi-round incentives remain open.

    Source: §1.2 · p. 8

Abstract

from arXiv · show

We study bandwidth fee mechanisms (BFMs) for pricing threshold-certified transaction dissemination before consensus. Analogous to transaction fee mechanisms for computation, BFMs price blockchain communication, which is especially relevant when dissemination is separated from consensus and execution. We model BFMs as two-sided procurement auctions between users submitting transactions and validators receiving and forwarding them. Any validator may serve as a transaction's source and forward it to a threshold of attesters. The model accounts for receipt from the user and subsequent transfers between validators, while abstracting away unrestricted multi-hop gossip and network topology. We establish limits on myopic incentive compatibility: no nontrivial transcript-based BFM prevents profitable collusion between two validators, and no nontrivial BFM simultaneously satisfies incentive compatibility for individual users, individual validators, and coalitions of one validator and one user. On the feasibility side, we give a greedy-route posted-price mechanism that is incentive compatible for every individual user and validator. We also study bandwidth pricing across blocks. Assuming honest validator execution, we propose an EIP-1559-style price-update rule whose fluid approximation has a unique fixed point that is locally stable for sufficiently small step sizes. In large markets, prices starting near this point remain nearby with high probability over any fixed time horizon.

1 Introduction

Transactions consume bandwidth before consensus, but execution-based fees may not charge for that use; the paper introduces certified-dissemination pricing and studies its incentive limits, feasible mechanisms, and dynamics. [No citations requested?]

1 Introduction

  • Transactions may consume bandwidth without paying for it when they are not finalized or execution fails, even though protocol nodes bear propagation costs.This mismatch is especially relevant when dissemination is separated from consensus and execution.Source: §1 · p. 3

1.1 Our Contributions

  • The planner model assigns each transaction to a source and attesters, authenticates intended routes with public assignments, and leaves validators free to deviate during dissemination.The model abstracts away multi-hop paths, topology, latency, and link congestion.Source: §1.1 · p. 4
  • No non-trivial transcript-based BFM resists two-validator collusion, and no non-trivial BFM simultaneously achieves UIC, 1-VIC, and (1, 1)-SCP.Delegated signing can produce a certificate without the corresponding data transfer; the validator-user impossibility applies when cost functions are strictly increasing and positive for positive work.Source: §1.1 · p. 5
  • The greedy-route posted-price mechanism achieves UIC and 1-VIC, sacrificing coalition resistance to protect against unilateral deviations.Its capacity-limited approximation guarantee applies when the final allocation is capacity-maximal.Source: §1.1 · pp. 5–6
  • The proposed fee update has a unique positive-price fluid fixed point that is locally stable for sufficiently small steps, with nearby stochastic states tracking it over fixed horizons in large markets.The dynamic analysis assumes one-time validator reports and honest execution in later rounds.Source: §1.1 · p. 6

1.2 Additional Related Work and Future Directions

  • The paper identifies decentralized routing, farsighted multi-round incentives, and added primitives for coalition resilience as open directions.The dynamic analysis assumes validators report once and execute assignments honestly in subsequent rounds.Source: §1.2 · p. 8

2 Technical Overview

The technical overview develops bandwidth fee mechanisms for certified transaction dissemination, modeling validators’ routing of transactions to attesters and analyzing their incentives. It covers coalition impossibilities, a greedy-route posted-price mechanism and its approximation guarantee, and an EIP-1559-style bandwidth-price update with analysis of its fluid operating point’s stability.

2.1 Model Overview

  • The model assigns each transaction a source and k attesters, with validator capacity and cost reports, user bids, payments, and validator rewards determining dissemination.Incentives are evaluated for myopic players acting in a single round; users value finalization, while validators incur costs for bandwidth used.Source: §2.1 · pp. 8–9

2.2 Impossibility against Coalitions

  • No non-trivial transcript-based BFM resists collusion by two validators, who can share signing keys and avoid transmission costs while producing an apparently honest certificate.This deviation is profitable when transmitting one unit of data has positive cost.Source: §2.2 · p. 10
  • No non-trivial BFM simultaneously achieves UIC, 1-VIC, and (1, 1)-SCP when validator costs are strictly positive for positive bandwidth and strictly increasing.The proof reduces to the MPC-assisted TFM impossibility in, which forces zero validator utility and enables a validator to profit by overreporting cost.Source: §2.2 · pp. 10–11

2.3 Greedy-Route BFM

  • The mechanism charges eligible transactions a fixed base fee b, rewards completed validator work at rate τ < b, and scans routes in a fixed order subject to capacity and budget limits.It processes eligible transactions in a fixed, non-manipulable priority order and can run in streaming fashion.Source: §2.3 · pp. 11–12
  • The greedy-route mechanism satisfies UIC and 1-VIC for m ≥ 3 and 0 < τ < b, because a fake transaction can generate at most b in new rewards but costs b.Routes are scanned in fixed order and accepted only when validator capacities and the incremental reward budget constraint are respected.Source: §2.3 · p. 12
  • The greedy-route BFM is 1-VIC: validators cannot profit by deviating in dissemination, injecting fake bids, or misreporting their costs or bandwidth.The proof rules out components of arbitrary joint validator deviations sequentially.Source: §2.3 · pp. 13–14
  • When every optimal route is blocked by a validator at capacity, G_τ ≥ OPT_τ/(2k + 1) − (k + 1)m/(2k + 1) with infinitely many eligible bids.The comparison is against the optimal allocation for fixed base fee b and reward parameter τ.Source: §2.3 · p. 14
  • The paper gives no approximation guarantee in the cost-congested regime, where fixed route ordering can reject transactions that a different ordering might accept.A guarantee there requires cost-aware route ordering that still incentivizes truthful validator reporting.Source: §2.3 · p. 14

2.4 Dynamic Price Update

  • With validator reports and τ fixed, honest execution, and slack route budgets near the operating point, the base fee rises above half of available supply consumption and falls below it.The price rule uses a step size d; used bandwidth is subtracted immediately, while a fraction α of the gap to maximum capacity recovers before the next round.Source: §2.4 · pp. 14–15
  • When arrivals can sustain a positive price, the fluid system has a unique positive-price fixed point: x* = 2α/(2α + 1) and F(b*) = 1 − αqλ/(2α + 1).At this point, consumption equals the target and recovered bandwidth replenishes consumption.Source: §2.4 · p. 15
  • With sufficiently small step size, the price-supply fixed point is locally stable, and large-market dynamics started nearby remain near it with high probability over any fixed horizon.If the step size is too large, the linearized dynamics instead oscillate away from the fixed point.Source: §2.4 · p. 15

3 Background and Preliminaries

The background defines proof-of-availability (PoA) as a threshold certificate of transaction availability, distinct from consensus commitment. It also sets out the network assumptions and basic stochastic-process terminology used later.

3.1 Consensus and Proof-of-Availability

  • A PoA certificate records a source and at least k attesters; it makes a transaction available and admissible for consensus, not committed.Consensus decides which certified transactions enter the finalized ledger; only then does a transaction count as committed.Source: §3.1 · pp. 16, 18
  • PoA guarantees public verification and accountability by identifying the source and actual attesters in each valid certificate.The mechanism can base rewards on observed certified work rather than the planned route alone.Source: §3.1 · p. 17
  • With k > t, every valid certificate includes an honest attester, supporting post-GST retrieval; honest sources can collect certificates when at least k honest attesters have sufficient bandwidth.The soundness claim relies on unforgeable signatures and honest attesters storing data; the post-GST delivery assumption supports liveness.Source: §3.1 · pp. 16–17

3.2 Preliminary on Markov Process

  • A Markov process’s future depends only on its current state, while a fixed point remains unchanged under the update and is locally stable when nearby trajectories converge to it.A time-homogeneous Markov chain has transition probabilities that do not depend on the time step.Source: §3.2 · pp. 18–19

4 Models and Definitions

The model treats bandwidth pricing as a single-round game in which a central planner assigns transaction routes using reports from users and validators. It defines incentive compatibility for individual players and coalitions against deviations from truthful behavior.

4.1 Single-Round Bandwidth Fee Game with Centralized Planner

  • A trusted planner receives transactions and validator reports, then assigns each accepted transaction to a source and k attesters for dissemination.The source receives the transaction through the planner and forwards it to the attesters; validators’ bandwidth costs and capacities are not directly observable.Source: §4.1 · pp. 19–20
  • Users have private values, while validators have private capacities and costs modeled as ci·gi(x), with the cost shape gi publicly known.Transaction size is normalized to one bandwidth unit; an attester incurs receive cost even if it does not later sign.Source: §4.1 · pp. 19, 21
  • A BFM specifies allocation, user payments, and validator rewards; it also assumes feasible routes, individual rationality, and budget feasibility.Users pay only for committed transactions, and total validator rewards cannot exceed total user payments.Source: §4.1 · pp. 20–21

4.2 Incentive Compatibilities

  • Incentive compatibility requires that a coalition cannot gain by deviating from its honest strategy; the definitions distinguish user, validator, and side-contract guarantees.Users may submit multiple bids, validators may misreport or deviate from assigned dissemination, and coalitions coordinate member strategies.Source: §4.1 · p. 21, §4.2 · p. 22

5 Impossibility of Coalition Resilience

The section establishes two limits on coalition resilience: transcript-based mechanisms cannot prevent profitable collusion between two validators, and no non-trivial planner BFM satisfies user, individual-validator, and one-validator–one-user incentive compatibility together.

5.1 Validator-Coalition Impossibility under Delegated Signing.

  • No non-trivial transcript-based BFM is 2-VIC: two validators can delegate signing, preserve the public transcript and rewards, yet avoid the transfer’s bandwidth cost.The resulting deviation is strictly profitable; no non-trivial transcript-based BFM is (2, d)-SCP for any d ≥ 1.Source: §5.1 · pp. 22–23
  • Preventing this validator-collusion strategy requires assumptions or tools that prevent internal key sharing or verify physical data receipts.The certificates identify source and attesters, but a transcript-based mechanism cannot verify which physical validator transferred the data.Source: §5.1 · pp. 22–23

5.2 Impossibility under Validator-User Coalitions

  • The reduction fixes validators’ types and honest dissemination, treating accepted transactions as finite block space and validator net utility as revenue.The argument uses the implication that honest validator utility must be zero even when nontriviality gives a positive-probability assignment.Source: §5.2 · pp. 24–25
  • No non-trivial planner BFM simultaneously achieves UIC, 1-VIC, and 1-SCP.The proof reduces the BFM to an MPC-assisted transaction fee mechanism, where those guarantees cannot all hold.Source: §5.2 · pp. 24–25

6 Greedy-Route Posted-Price Mechanism

This section presents a greedy-route posted-price mechanism that charges a fixed base fee and rewards validators for verifiable work. It establishes UIC and 1-VIC for m ≥ 3 and 0 < τ < b, optimal truthful bandwidth reporting for validators, a greedy-throughput approximation guarantee under capacity congestion, and a polynomial-time implementation of the greedy route scan.

6.1 The Mechanism

  • The planner greedily assigns eligible transactions to routes in a predetermined order, subject to validator bandwidth capacities and budget feasibility.Each route specifies one source validator and a set of k attesters; committed transactions pay b, and validators receive τ per unit of verifiable work.Source: §6.1 · pp. 26–27, §6 · p. 26

6.2 Incentive Compatibility of Greedy-Route Posted-Price Mechanism

  • For any m ≥ 3 and 0 < τ < b, the posted-price mechanism achieves UIC and 1-VIC.The mechanism uses base fee b and reward parameter τ, with 0 < τ < b.Source: §6 · p. 26, §6.2 · p. 28
  • A user cannot profit by injecting eligible fake transactions: they cannot improve the real transaction’s priority, and finalized fakes pay b.Under an insertion-monotone priority rule, fake transactions cannot increase the probability of allocation for the user’s real transaction; truthful bidding follows from the standard posted-price auction.Source: §6.2 · p. 28
  • Validator 1-VIC covers joint deviations in dissemination, fake-bid injection, cost reporting, and capacity reporting, using successive reductions to honest behavior.At each reduction, the component under consideration can be replaced by its honest version without increasing utility, conditional on arbitrary choices of the other components.Source: §6.2 · pp. 28–29
  • Injecting fake transactions is not profitable because any additional validator reward is at most ∆·b, while finalized fake transactions pay at least ∆·b.Misbehavior during dissemination is also no better than honest behavior for a fixed assignment, validator report, and fake-bid set.Source: §6.2 · pp. 29–30
  • Misreporting a validator’s cost function is not profitable: reports below τ may assign costly work, while reports at or above τ yield the same allocation as truthful reporting.The cost report is used to determine whether the validator receives any workload.Source: §6.2 · p. 30
  • Neither underreporting nor overreporting bandwidth capacity improves a validator’s utility over truthful bandwidth reporting.The overreporting argument considers both excess assigned work, which risks crashing or earning no reward, and overreporting within true capacity.Source: §6.2 · p. 31

6.3 Approximation in the Capacity-Limited Regime

  • For a capacity-maximal final greedy allocation, Gτ ≥ OPTτ/(2k + 1) − (k + 1)m/(2k + 1); when OPTτ ≫ m, greedy-route BFM is a (2k + 1)-approximation.Source: §6.3 · p. 32
  • In the fully cost-congested regime, a fixed route order has no meaningful approximation guarantee independent of cost profiles; a cost-aware, truth-incentivizing ordering remains needed.A route rejected for budget reasons need not be blocked by residual capacity, so the capacity-based analysis does not apply.Source: §6.3 · p. 33
  • Arbitrary-size transactions preserve the mechanism’s incentive properties, but the approximation constant depends on the largest transaction size.The incentive proofs require nonnegative additive workload increments and strictly increasing gi, rather than unit-sized transactions.Source: §6.3 · p. 33

6.4 Polynomial-Time Implementation of the Greedy Route Scan

  • The implementation exactly reproduces the greedy allocation in O(Nm^2k) time and O(mk) working space, without enumerating routes.The bounds assume constant-time evaluation of each gi and constant-time arithmetic and comparisons.Source: §6.4 · pp. 34, 36
  • The route scan requires no convexity assumption on the public shape functions gi and retains its forward-only pointer behavior.A route rejected for budget reasons may become feasible as workloads grow, but the mechanism does not revisit it.Source: §6.4 · p. 36

7 Multi-Block Price Dynamics

The section models how posted prices and available bandwidth evolve across rounds, then analyzes the fluid system’s fixed point, stability, and finite-horizon stochastic behavior. In large markets, processes starting near a locally stable fixed point remain nearby with high probability over any fixed horizon.

7 Multi-Block Price Dynamics

  • The multi-block rule follows an EIP-1559-style rationale: price changes with prior-round usage while validators’ available bandwidth recovers over time.The analysis assumes validators report true capacity and cost initially, then implement dissemination honestly.Source: §7 · pp. 36–37

7.4 Implications for the Stochastic Process

  • In large markets, stochastic dynamics started near a locally stable fluid fixed point remain nearby with high probability over any fixed horizon; this result does not address long-run behavior.The tracking result assumes the fluid trajectory stays away from zero available supply.Source: §7 · p. 37, §7.4 · p. 43

7.1 The Stochastic Supply-Price Process

  • The stochastic state tracks normalized available bandwidth and the base fee; eligible-user arrivals determine consumption, used bandwidth recovers, and the fee adjusts against a half-supply target.The process is time-homogeneous Markov; the analytical model allows real-valued available bandwidth.Source: §7.1 · pp. 37–38

7.2 Fluid Approximation

  • The fluid approximation replaces random eligible-user counts with their mean before capacity truncation, so its expected consumption can overestimate stochastic consumption.Finite-horizon tracking holds when the fluid trajectory stays away from the zero-supply boundary.Source: §7.2 · pp. 39–40

7.3 Fixed Point and Local Stability of the Fluid Approximation

  • If λ > αq(2α+1) and F is strictly increasing, the fluid system has a unique positive-price fixed point, locally stable for sufficiently small d and unstable beyond dcrit.The local stability result assumes differentiability near the fixed point and a neighborhood where the capacity constraint is slack.Source: §7.3 · pp. 41–42

8 Numerical Evaluation

The numerical evaluation tests fluid-model predictions against indivisible simulations and probes recovery, market size, stability, capacity, and a route-level instance. Baseline paths track the fixed point, while price stability degrades above the step-size threshold.

8.1 Experimental setup

  • The baseline uses k=2 (q=5), Θmax=10000, Uniform[1, 2] values, λ=0.15, α=0.25, and d=0.05; discretization error is bounded by one transaction.The normalized one-step discrepancy is less than q/Θmax and vanishes under the large-market normalization; this is not a stronger stochastic convergence theorem.Source: §8.1 · p. 44

8.2 Baseline tracking and fixed-point behavior

  • Stochastic trajectories fluctuate around the fixed point while the fluid trajectory approaches it smoothly, supporting the fixed point as the stochastic operating point rather than an absorbing state.At the tested parameter scale, the indivisible simulation accurately implements the fluid model rather than introducing separate drift.Source: §8.2 · pp. 44–45, Figure 1 · p. 45

8.3 Recovery-rate and market-size sensitivity

  • Post-burn-in averages track the fixed-point predictions across five recovery rates; faster recovery supports higher steady-state throughput while consumption stays near half of available bandwidth.Table 1 and Figure 2 compare the predictions with simulated averages.Source: §8.3 · p. 45, Table 1 · p. 46, Figure 2 · p. 46
  • Normalized post-burn-in errors shrink as Θmax grows across the tested market sizes, consistent with finite-horizon large-market scaling but not proving the limiting result.The sweep varies Θmax over 500, 1000, 5000, 10000, and 50000 while holding k, λ, α, and d fixed.Source: §8.3 · p. 46, Figure 3 · p. 47

8.4 Step size and local stability

  • At d=0.35 the boundary already shows an RMSE jump; above it, local linearization is unstable and RMSE roughly doubles to triples relative to the boundary case.The uniform baseline has dcrit=0.35; representative traces at d=0.65 oscillate, unlike the d=0.05 and d=0.35 paths.Source: §8.4 · pp. 47–48, Figure 4 · p. 47, Table 2 · p. 48

8.5 Capacity binding and Jensen gap

  • At baseline, the capacity cap is about 18.2 Poisson standard deviations above the mean, making binding negligible and the Jensen gap numerically zero; Θmax=100 exposes truncation.The Θmax=100 setting is a deliberately small tight-cap stress case, not the baseline regime.Source: §8.5 · p. 48, Table 3 · p. 49

8.6 Concrete route instance

  • With m=20, k=2, and q=5, the capacity-only greedy scan matches the full mechanism and accepts 2000 transactions; this is an aggregate-realizability witness, not a universal validation.The instance has a slack budget, so every capacity-feasible route is also budget-feasible.Source: §8.6 · p. 49

A MPC-Assisted Transaction Fee Mechanisms

This section recalls the MPC-assisted TFM model of, representing the validators’ MPC protocol as an ideal functionality that faithfully implements the TFM.

A MPC-Assisted Transaction Fee Mechanisms

  • The model abstracts an MPC protocol among validators, originally miners in, as an ideal functionality FMPC that implements the TFM faithfully.The recalled setting is for finite block size.Source: A MPC-Assisted Transaction Fee… · p. 52

A.1 The MPC-Assisted TFM Game

The MPC-assisted TFM game specifies allocation, payment, and validator-revenue rules, then has an ideal functionality execute those rules on submitted bids. Validators cannot alter the resulting allocation once bids are fixed.

A.2 The MPC-Assisted TFM Game

  • An MPC-assisted TFM specifies three possibly randomized rules: allocation, payment, and validator revenue, for a fixed block-size parameter Θ.The game proceeds through bid submission, allocation, payment, and revenue distribution by FMPC.Source: §A.1 · p. 52
  • FMPC selects at most Θ bids, charges unconfirmed bids zero, and distributes validator revenue subject to total revenue not exceeding payments from confirmed bids.Source: §A.1 · p. 52
  • Because FMPC enforces allocation, payment, and revenue rules, validators cannot choose block contents after seeing bids; their remaining strategic power is submitting fake bids through identities.Source: §A.1 · p. 52

A.2 Strategy Space and Utility

The strategy space distinguishes truthful single-identity users from strategic users and validators who may use multiple identities. Utilities and incentive guarantees are defined for individuals and coalitions.

A.3 Strategy Space and Utility

  • An honest user with value vi bids vi through one identity, while a strategic user may abstain, misreport, or submit multiple bids but cannot impersonate an honest identity.Source: §A.2 · p. 52
  • Strategic validators may submit fake bids through arbitrary identities, but under they cannot choose which bids are allocated once the bid vector is fixed.Source: §A.2 · p. 52
  • A confirmed user’s utility is vi−pi, an unconfirmed user’s is zero, a validator’s is its revenue, and coalition utility is the sum of member utilities.[SCW23] defines UIC, MIC, and (ρ, c)-SCP as prohibitions on profitable deviations by individual users, validator coalitions, and mixed coalitions, respectively.Source: §A.2 · p. 52

A.3 MPC-Assisted Impossibility Theorems

For MPC-assisted TFMs, ex-post user incentive compatibility, validator-coalition incentive compatibility, and validator-user coalition strategy-proofness together force validator revenue to zero. The passage also explains how congestion can let colluding users improve confirmation chances, constraining mechanisms that provide positive utility under finite block space.

A.3 MPC-Assisted Impossibility Theorems

  • Ex-post UIC, MIC against a ρ-sized validator coalition, and SCP against a (ρ, 1)-sized validator-user coalition force zero validator revenue in MPC-assisted TFMs.The theorem states this for every bid vector; the induced mechanism likewise has zero revenue on every fixed input when the corresponding properties hold there.Source: §A.3 · p. 53
  • Non-trivial utility means positive expected utility for some participant under some input distribution.Source: §A.3 · p. 53
  • With finite block space, a two-user coalition can exploit congestion by changing one user’s bid to improve the other’s confirmation probability, which strict two-user SCP rules out alongside positive utility.The passage describes this intuition after validator revenue is forced to zero.Source: §A.3 · p. 53
Loading 2610.00697v1…