CS Paper Radar

How Much Must a Private Mempool Hide? Exact Leakage Thresholds for Sandwich Attacks

Tingyi Lin, Jiazhuo Li, Ruoran Lai

cs.GT cs.CRq-fin.TR ·submitted 2026-09-25 15:15 UTC · v2
publishedtheory

Abstract

Private and encrypted mempools hide pending transactions to stop sandwich attacks and other forms of maximal extractable value (MEV), but what they hide is rarely everything: a transaction's pair, direction, and a coarse range for its size can still leak. How much leakage makes sandwiching pay? We answer exactly for a fee-free constant-product automated market maker, the pricing rule behind Uniswap v2. Traders observe an interval containing the victim's size and bid in a first-price auction for the right to sandwich it, and the winning front-run must keep the victim's trade executable at every size in the interval. The answer turns on the smallest size consistent with the leak. It alone determines the feasible front-runs, the largest feasible front-run is optimal for pointwise, expected, and worst-case profit alike, and the guaranteed profit has a closed form. When execution is costly, a privacy layer that wants to rule out sandwiches profitable at every consistent size may therefore reveal anything about the size except a lower bound above an explicit threshold; the upper end of the range is irrelevant. With two or more symmetric traders, every pure-strategy perfect Bayesian equilibrium of the auction hands the entire expected net rent to the auctioneer. If the direction is hidden too, no non-contingent first leg front-runs both possible directions, while post-trade arbitrage can survive even perfect pre-trade hiding.

Comment
Accepted at NeurIPS 2026
Journal ref
https://neurips.cc/virtual/2026/loc/atlanta/poster/148297

Closest papers

Nearest neighbours by meaning across the whole index.

When One Leak Pays Forever: Context Binding and the Price of Deterring Collusion

cs.GT cs.CRecon.TH ·2026-09-29 ·Tingyi Lin, Shawn Yu, Ruoran Lai, Huanxi Zhang
published similarity 0.67
Abstract · Accepted at NeurIPS 2026

A coalition that deviates once can profit many times when what it sells keeps working. In a threshold-encrypted mempool, a leading defense against maximal extractable value (MEV), a quorum of the decryption committee that sells its decryption capability to a front-runner exposes every later block that the capability still decrypts. We ask how large a penalty, such as slashable stake, deters this kind of collusion. In our repeated game, a single leak by any coalition in a monotone family of authorized coalitions (for example, any $k$ of the $n$ committee members) unlocks a set of future rounds, costs a one-time penalty, and ends the coalition's participation. We show that every dynamic deviation reduces to choosing a leak time, so deterrence holds if and only if each coalition's penalty covers the largest discounted value that a single leak reaches. Without discounting, over $T$ rounds of unit value full reuse needs a penalty of $T$ while binding each leak to its own round needs $1$, so no penalty that is constant in the horizon deters unbounded reuse; a reuse window of $w$ rounds costs at most $w$ times the largest per-round value. The cheapest profile of per-party stakes that deters every coalition solves a covering linear program. For blockchain design, per-epoch keys cut the required stake from the value of a key's lifetime to the value of one epoch; we calibrate the gap on Ethereum front-running data and place Ferveo and Shutter in the model. The analysis extends to sealed-bid auctions, multi-authority voting, and federated learning under a shared key.

0.29

Provisional Reachability: Containing Agents by Making Every Crossing Revocable

cs.CR cs.NI ·2026-09-18 ·Yoshiaki Takashita
unusual similarity 0.58
Abstract · 35 pages. Companion papers: arXiv:2609.18145, arXiv:2609.19720. Code and records included as ancillary files

A companion paper found that what a defender must block over time has units: bits per period [Takashita, 2026a]. This paper sets it. Hold every crossing in escrow for one period, audit each held item independently with probability r, and revoke the window if any audit catches something. An adversary crossing k times, each carrying c bits, expects kc(1-r)^k, maximised at k* = 1/ln(1/(1-r)), a bound of L(r) ~ c/(er) per window. The bound is a supremum over the adversary's choice, so the scheme may be public; simulation matches it to 7.7 standard errors. It is a rate, not a total: escrow alone still lets the secret assemble in every run. But if the secret decays at a fraction mu of held bits per period, holdings converge to g/mu at any horizon, so an L-bit secret is unreachable once mu > g/L -- an error threshold in Eigen's sense, sharp where the closed form puts it (100% of runs assemble at 0.9mu*, 0% at 2mu*, over 20,000 windows). Deception that needs the adversary to reason badly fails: a surface whose names lie left accuracy at 18 of 18, and 100% at three reader strengths. Withholding reference works, and differently: no reader would commit at all. Keying the entry points hides 0.10 bits of what a module does; keying the denotation hides 2.64 of 3.00 at chance accuracy, while 100% of readers still call it ordinary Python. Variance must be removed from the audit rate, where loot is convex in r, and added to the activation budget, where survival is multiplicative: extinction 70% to 100% at a fixed mean. End to end the stack takes the leak from 100,000 to 59 bits, a factor of 1,704, leaving 12% of legitimate work standing; keying the window to the caller restores that to 100% at no cost in leakage, at the price of a bound that is per principal. Of 65 read-only tools, escrow leaves 2,400 bits per call: a factor of 10, not infinity.

0.33

A Sharp Additive Bound for the Threshold Rule in Repeated Rent-or-Buy

cs.DS ·2026-11-03 ·Vasco Schiavo
similarity 0.57
Abstract · 16 pages

Motivated by context management in LLM agents, we study a repeated rent-or-buy model with schedule-independent history growth and a fixed reset price $K$, a discrete form of dynamic TCP acknowledgment: every call pays as rent the history accumulated since the last reset, and a reset clears it. The classical threshold rule is $2$-competitive, and no deterministic rule guarantees a smaller ratio. We show that, measured additively, its loss is governed by the changes in the growth: if the growth is constant on $P$ runs, the threshold rule, knowing neither the runs nor the horizon, pays at most $(2P-1)K$ more than the optimal schedule chosen with hindsight, and the coefficient $2P-1$ is sharp. If the growth is only within a factor $1+\varepsilon$ of $P$ runs, the bound holds up to a factor $1+\varepsilon$ and an extra $\varepsilon K$. The proof is a potential argument built from the relative value functions of the single-rate problems. On two runs no deterministic rule guarantees a loss below $2K$. A rule that also resets when the growth decreases guarantees $2K$, while the threshold rule can lose arbitrarily close to $3K$.

0.30

Uniform-Price Mechanism Design for Automated Market Makers

cs.GT ·2026-10-16 ·Zhike Peng
published similarity 0.54
Abstract · 22 pages. Full version of a paper accepted at IJTCS-FAW 2026

Automated market makers (AMMs) are central to decentralized exchanges, but their reserve curves make mechanism design different from classical double auctions. We study a batch double auction with buyers, sellers, and a liquidity-nondecreasing AMM: post-trade reserves must have weakly larger product than the initial reserves. Each user has two-dimensional private information: a unit value and a demand or supply quantity. User trades clear at one uniform price subject to AMM feasibility. The objective is user-side trading volume, benchmarked against the optimal feasible individually rational (IR) uniform-price allocation. We give a randomized uniform-price mechanism based on binary quantity buckets. It randomly chooses one of three clearing modes: peer-to-peer matching, AMM sales to buyers, and seller sales to the AMM. Every deterministic realization of the mechanism is ex-post feasible and satisfies IR and weak quantity incentive compatibility: conditional on any quantity report, truthful unit-value reporting is dominant whenever it gives a non-negative utility, no unit-value deviation gives a positive utility if the truthful one doesn't, and users cannot benefit by under-reporting the quantity together with their truthful unit value. Let $V^\ast$ be the optimal feasible IR uniform-price volume without incentive constraints, and let $γ=\bar q/\underline q$, where $\bar q$ and $\underline q$ are the quantity-domain bounds. For $γ\ge1$, the mechanism achieves an expected trading volume of $ Ω(1/(1+\logγ)^2)V^\ast - O(\bar q). $ We also show that full incentive compatibility over the two-dimensional type space forces a worst-case approximation ratio of $O(1/γ)$ at every prescribed initial reserve ratio, even when both AMM reserves are scaled by an arbitrarily large common factor and the optimal volume $V^\ast$ is arbitrarily large relative to $\bar q$.

0.36

Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting

cs.CR ·2026-09-06 ·Guangjie Liu, Guang Cheng, Weiwei Liu
theory similarity 0.54
Abstract

The Side-Channel Existence Theorem proves $I(X;Y)>0$ in the binary, undefended setting, but is confined to pairwise arguments and ignores active defenses. We extend it to $k$ classes via the per-class decomposition $I(X;Y)=\sum_iπ_i D_{\mathrm{KL}}(P_{Y|i}\|P_Y)$, with defense cost modelled by per-class Wasserstein-1 constraints $\sup_x W_1(Q_x^D,P_x)\le B$. Three results follow: (1) a summation-form MI lower bound over all active classes; (2) a cascade critical cost theorem and a per-class budget corollary, nonzero where the uniform-budget bound vanishes; (3) an accuracy corollary $\mathrm{Acc}^*\ge 2^{I_0}/k>1/k$. On a 95-class website fingerprinting dataset the measured MI has a strictly positive $95\%$ confidence lower bound under every defense tested. Against the strongest pairwise baseline---a convex program over all $\binom{k}{2}$ triangle constraints, also $Θ(1)$ in $k$ under the same non-vanishing-gap conditions---the summation form is only $1.45\times$ stronger, so the case for the per-class decomposition is structural: only it gives each class a critical cost and a cascade. FRONT's apparent $122\times$ gap is inflated mainly by threshold exclusion rather than the inequality chain: on the active classes it is $21\times$, within $1.4\times$ of the $15\times$ measured undefended. Measuring the chain's two steps separately bounds the collapse onto one Lipschitz statistic below by $28\times$, against a divergence step measured at $1.5\times$. Undefended OVR distinguishability predicts post-defense per-class leakage at Spearman $ρ=0.62$--$0.77$, the transfer the certification procedure relies on. The framework carries over unchanged to a 100-class QUIC/TCP pair.

0.26

Can Rényi Accountants Beat Lossless Accountants for DP-SGD?

cs.LG cs.CRcs.DScs.IT+1 ·2026-10-12 ·Jinho Bok
similarity 0.54
Abstract · 41 pages

Recent frameworks in differential privacy (DP), such as privacy loss distributions and $f$-DP, provide lossless representations of the privacy leakage of mechanisms. These approaches are often considered to yield tighter $(\varepsilon, δ)$-DP guarantees than those obtained from relaxed notions such as Rényi DP. But is that always the case? We study this question for differentially private stochastic gradient descent (DP-SGD) with fixed-size batches under replace adjacency. Our key observation is that in this setting, privacy accounting based on Rényi DP can use a pair of worst-case distributions (i.e., a dominating pair) that differs from the one used in the lossless frameworks. In particular, we characterize the worst-case distributions as two-dimensional Gaussian mixtures and derive an improved Rényi DP bound for DP-SGD. Numerical and asymptotic comparisons show that across various hyperparameter settings, a Rényi DP accountant based on the new bound can yield better privacy guarantees than those obtained from the lossless frameworks.

0.25

When Privacy Moves ML-Mediated Decisions On Device: Information and Incentive Misalignment in Auctions

cs.GT cs.DCcs.LG ·2026-09-27 ·Dipankar Sarkar
code/data similarity 0.53
Abstract · 14 pages, 1 figure, 3 tables. Previously submitted to the Economics for Machine Learning (EconML) workshop at NeurIPS 2026. Code and data: h…

Moving ML-mediated decision making onto privacy-preserving clients decentralises the economic decision along with the inference. Shared budget constraints then depend on information that cannot be globally current, creating an information-structure failure that conventional pacing is not designed to solve. We study this information misalignment in an auction-logic-faithful on-device simulation with 36 campaigns and 50 devices. Accounting is in dimensionless integer score units; no currency semantics are claimed. Across 30 paired demand paths, proportional Even pacing overspends 17.77% after one tick of staleness and 1,669.31% after 50 ticks under the original 20-times budget pressure. The effect does not depend on that severe a budget: at two-times pressure, 50-tick overspend remains 106.95%. A visible-budget no-sale guard makes zero-lag compliance exact at this score-unit granularity, yet leaves 11.88% overspend at one tick because other devices' debits remain invisible. A declared bursty, heterogeneous-device sweep retains a strictly increasing mean lag curve. We derive a finite-window expected excess-debit bound under conditional charge caps and find positive paired slack in every bounded-value cell. A second, incentive misalignment arises when the ML/pacing score transformation is allowed to change payment units: 98.23% of rival auctions at one tick admit a profitable deviation. An executable implementation-level counterexample isolates the runner-up's multiplier in the winner's price. Critical-base-bid payment is per-auction DSIC conditional on current multipliers, but does not establish dynamic truthfulness and does not repair base-value ranking disagreement.

0.44

Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

cs.GT ·2026-10-11 ·Haolong Li, Fangxiao Wang, Xiaowei Wu
similarity 0.52
Abstract

We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevocably assign her a subset of the unallocated chores. We focus on the notion of maximin share (MMS) and measure the fairness of the realized allocation $X$ by the ex-post MMS approximation ratio $ρ(X)$. We measure an algorithm's performance by its expected ratio, and also the guarantees that hold with high probability. For binary additive costs, we achieve an expected ex-post MMS ratio of $3/2+o(1)$, and show that every randomized online algorithm has an expected ratio of at least $3/2-o(1)$. For every $n$, the expected ratio is at most $1.755$. A variant of our algorithm guarantees an approximation ratio of $2$ with high probability, which is optimal. % For general additive costs, we present a weighted-rounding algorithm that achieves an expected ratio of $2+o(1)$, which also holds with high probability. The expected ratio is at most $2.594$ for every $n$. We also show that similar algorithms extend to additive goods, achieving a constant expected ex-post MMS ratio and guaranteeing every agent an $x$-fraction of her MMS with probability at least $1-85x^2$ for every $x\le1/15$.

0.39