CS Paper Radar

Breaking Cycles for Scalable Fair Ordering in Blockchain Systems

Jinchun He, Wangjie Qiu, Yizhong Liu, Shengda Zhuo, Kwok-Yan Lam

cs.DC ·submitted 2026-09-01 07:37 UTC · v1

Abstract

In blockchain systems, transaction order directly determines financial outcomes: unfair ordering enables front-running and sandwich attacks that have extracted over \$686M from Ethereum users. Current fair-ordering protocols aggregate pairwise receive-order evidence from replicas. Under contention or adversarial manipulation, however, Condorcet cycles force them into global strongly connected component (SCC) condensation, causing delays, coarse batches, and scaling failures. We present FlashOrder, a deterministic fair-ordering engine that localizes cyclic ambiguity before it propagates across the batch. FlashOrder embeds pairwise preferences into one-dimensional canonical positions, clusters nearby transactions with a partition hypergraph, and performs hierarchical inter- and intra-cluster serialization, replacing batch-wide SCC condensation with localized sorting and aggregation. Evaluated against Themis (CCS '23) and Rashnu (VLDB '24) on a libhotstuff-based prototype, FlashOrder achieves up to 10.5$\times$ higher throughput than Themis and 4.8$\times$ higher than Rashnu, with the latency gap widening as network scales. In controlled adversarial simulation, it reduces maximum rank displacement by 88.7\%, and under Condorcet attacks it sustains 12.0$\times$ and 9.7$\times$ higher throughput than Themis and Rashnu on average. These results show that localizing cyclic ambiguity yields stronger fairness at substantially higher throughput.

Closest papers

Nearest neighbours by meaning across the whole index.

Lantern: Finding Committable Transactions via Back-Propagation on DAGs

cs.DC cs.DBcs.PF ·2026-09-03 ·Denglong Li, Gerui Wang, Tian Guan, Mingchao Wan
code/data similarity 0.69
Abstract

Existing concurrency control protocols either introduce nondeterminism, resulting in a serial execution-replay dependency between primary and replica nodes, or rely on impractical prior knowledge of transaction read-write sets. In this paper, we present Lantern, a deterministic concurrency control protocol tailored for high-performance transaction processing systems operating without prior knowledge. The key insight of Lantern is that all zero-out-degree transaction vertices in the local dependency graph can be safely committed in ascending order using an overwrite-permissive strategy. We further introduce a novel Back-Propagation mechanism that iteratively propagates dependency states from sink to source vertices to identify additional committable transactions. We also propose Conflict-Free Batch Selection (CFBS) for read-modify-write intensive scenarios. We integrate Lantern into the open-source blockchain platform ChainMaker. Extensive evaluations on YCSB and SmallBank benchmarks demonstrate that Lantern achieves up to a 4.2x throughput speedup over Aria and improves the throughput of ChainMaker's execution layer by at least 2.2x.

0.21

Tight Characterizations of AMM Mechanism Design under Weak Efficiency

cs.GT ·2026-10-27 ·Chengkai Zhang, Lirong Xia, Elaine Shi, Mengqian Zhang, Qishen Han +1 more
theory similarity 0.63
Abstract · Abstract shortened to comply with arXiv's character limit

Miner extractable value (MEV) poses a persistent challenge for blockchain ecosystems. It arises from the fact that a block builder can exploit its unilateral control over transaction inclusion and ordering to extract profit, potentially at users' expense. Recent work has explored consensus-aided mechanism design to mitigate MEV. This approach combines generic consensus-layer guarantees with application-layer mechanisms that use these guarantees to address application-specific MEV problems. Prior work exemplifies this approach for automated market makers (AMMs). When the consensus layer offers fair sequencing, which orders transactions according to their arrival times, their proposed mechanism achieves incentive compatibility (IC) and weak local efficiency (wLE). Informally, IC rules out profitable strategic deviations by users and builders. Meanwhile, wLE ensures that after execution, any order willing to trade at the initial price cannot benefit from further trade with the pool at the ending marginal price. In this work, we resolve the main open question left by prior works: whether IC and wLE can be achieved under plain consensus (e.g., current Ethereum) without fair sequencing. We prove that no deterministic, anonymous batch AMM can achieve both properties. The impossibility holds even when the consensus layer guarantees censorship resilience and block space is unlimited, establishing the first separation between censorship resilience and fair sequencing in the context of decentralized mechanism design. Our impossibility proof combines three strategic capabilities: creating Sybil identities, over-reporting budgets, and misreporting values. We further show the tightness of our impossibility result: removing any one from the strategy space restores feasibility under censorship resilience. Specifically, we construct a mechanism achieving IC and wLE for each restricted setting.

0.21

Flamingo: On Load Balancing in DAG-based Consensus Protocols

cs.DC cs.DB ·2026-09-23 ·Zhen Ping Khor, Garvit Gupta, Mohammad Javad Amiri, Boon Thau Loo
similarity 0.63
Abstract

Distributed data management systems deployed in untrusted environments rely on Byzantine Fault-Tolerant (BFT) consensus protocols to tolerate malicious failures. DAG-based BFT protocols improve throughput by letting validators disseminate transactions concurrently and by scaling execution across multiple workers. However, imbalances in workload or resource capacity can still degrade performance significantly. This paper presents Flamingo, a load-balancing protocol for certified DAG-based BFT protocols that addresses imbalance at both the ordering and execution layers. At the ordering layer, Flamingo periodically migrates client accounts away from overloaded validators, adapting to skewed submissions and heterogeneous validator capacity while preserving correctness under Byzantine faults, with migrations taking effect only through the committed log. At the execution layer, Flamingo redistributes committed transactions across executor workers using a deterministic, order-preserving scheduler that balances load and minimizes cross-worker data movement, without centralized coordination or costly distributed commit. Built on top of Narwhal and Tusk, our prototype shows that Flamingo recovers throughput and latency under workload skew, validator heterogeneity, and shifting hotspots, adds negligible overhead when the system is balanced, and needs load balancing in both layers, since resolving only one shifts the bottleneck to the other.

0.17

RegionFence: Adaptive Concurrency Control for Blockchain Parallel Transaction Execution

cs.DC ·2026-11-01 ·Jiaying Feng, Linpeng Jia, Yi Sun
similarity 0.61
Abstract · Submitted to the Proceedings of the VLDB Volume 20 (for VLDB 2027)

Smart contracts have turned blockchains into general platforms, and their throughput is increasingly limited by transaction execution. Parallel execution can relieve this bottleneck. However, most existing engines apply a single policy within a block, typically optimistic (OCC) or pessimistic (PCC) concurrency control, and thus re-execute or delay whole transactions. Although some database studies have proposed hybrid and adaptive mechanisms, these mechanisms cannot be applied directly to blockchains because the block fixes the serial order, accesses emerge only at run time, and real workloads vary widely. We propose RegionFence, an adaptive concurrency control mechanism for blockchain parallel transaction execution, based on three key designs. First, we propose regions to refine the granularity of control from whole transactions to the parts that touch contended keys. Second, we design fences to decide at run time how each region handles a conflict. Third, we introduce intra-block and inter-block online learning to anticipate likely conflicts. At the same time, the system still produces the same result as serial execution in consensus order. We implement RegionFence in go-ethereum and evaluate it on real Ethereum mainnet blocks from different periods of the past five years. Experimental results show that RegionFence achieves an overall speedup of 9.2x over single-core execution on 64 cores and outperforms OCC by 2.9-5.4x and PCC by 3.9-9.4x in speedup across these periods.

0.18

GridSMR: Causal Compression for Sharded Blockchains

cs.DC ·2026-10-01 ·Shir Cohen, Adam Alon, Raz Omessi, Amir Sarid, Dana Shamir +1 more
similarity 0.61
Abstract

We present GridSMR, a sharded blockchain that scales execution horizontally while allowing dependent cross-shard operations to progress within a single block. Existing sharded systems typically place coordination between dependent cross-shard steps, making latency grow with causal depth. GridSMR localizes atomicity to individual accounts and executes cross-account work asynchronously. Using an execute-before-agree architecture, dependent operations execute across shards as they become available, while consensus later validates and commits the resulting schedule. This enables Causal Compression: cross-shard latency need not grow with the causal depth of a computation. GridSMR scales single-validator execution to 1.07M requests/s and four-validator execution to 193K committed requests/s, while reducing 16-hop causal-chain latency by 8.2x versus deferred execution.

0.22

Mitigating Front-Running Attacks through Fair and Resilient Transaction Dissemination

cs.DC ·2026-09-21 ·Wassim Yahyaoui, Joachim Bruneau-Queyreix, Jérémie Decouchant, Marcus Völp
publishedhighly cited similarity 0.61
Abstract

In modern blockchains, efficient, fair, and faulttolerant information dissemination is critical for performance and security. Several stages of the transaction lifecycle are affected, from the creation and dissemination of transactions to the dissemination of blocks in the consensus layer. Mempool protocols, such as L{Ø}, already address some of modern blockchains' security threats. However, others remain unless fairness is embedded most fundamentally in the dissemination layer used by these protocols to share transactions and blocks and to reconcile mempools. This paper introduces HERMES, a novel dissemination protocol for mempools that leverages robust minimal structures to optimize data propagation, balance load, and ensure fairness despite faults and Byzantine actors. Specifically, we address front-running attacks by randomizing the choice of an overlay structure while forcing nodes to prove adherence to the mempools' dissemination policies and the random choice made. Experimental results show significant performance improvements compared to traditional broadcast protocols for both permissioned and permissionless blockchains.

0.57

On the Robustness of Gossip Protocols in Modern Blockchains

cs.CR ·2026-10-15 ·Wenting Li, Jannik Albrecht, Frederik Armknecht, Ghassan Karame
top venue similarity 0.60
Abstract · Accepted at IEEE Symposium on Security and Privacy (IEEE SP), 2027

Modern platforms such as Ethereum and Polkadot nowadays execute Byzantine fault-tolerant consensus protocols over large validator committees, often comprising hundreds of nodes. At this scale, complete graph topologies for connecting nodes are impractical, leading systems to adopt various gossip mechanisms, often in an ad hoc manner. In this paper, we study the robustness of widely deployed gossip protocols used in committee-based blockchains against realistic network adversaries. We show, both analytically and through extensive empirical measurements, that the graph parameters commonly chosen to instantiate random graphs are insufficient to guarantee that enough honest nodes receive consensus messages for quorum formation in existing protocols. Motivated by this finding, we empirically assess the robustness of Bitcoin's Erdős-Rényi (ER) graphs, Polkadot's grid topology, Ethereum's GossipSub, and Solana's chunk- and tree-based disseminations. Our results reveal surprising tradeoffs: Solana's dynamic trees are bandwidth-efficient in benign settings but fragile under adaptive attacks; Polkadot's grid achieves strong robustness at the cost of high bandwidth overhead; GossipSub is both bandwidth-efficient and resilient to adaptive adversaries, yet highly sensitive to parameter choices; and ER graphs provide a strong robustness-efficiency tradeoff, e.g., when the (average) fanout degree exceeds 15 for networks up to 5000 nodes.

0.29

Prefix Sharing Is a Sorting Problem

cs.DS cs.CL ·2026-09-12 ·Rong He
theorycode/data similarity 0.59
Abstract · 16 pages. v2: Corrected the spanning-tree lower-bound implementation and retrieval summary statistics; clarified the scope of empirical opti…

LLM serving reuses KV cache by exact prefix match, so when a prompt is assembled from a set of reusable pieces -- retrieved passages, tool definitions, few-shot exemplars -- the order chosen for those pieces determines how much computation can be shared. Every deployed system fixes that order by a single global convention. We prove this is optimal only when requests contain at most two pieces, and asymptotically wrong in general. Our main result is a structure theorem: the minimum prefix-trie cost equals min_H sum_x w(x) t_x(H) over binary hierarchies H on the requests, where t_x(H) is the canonical decomposition size of the set of requests needing chunk x. Choosing chunk orders is therefore equivalent to choosing one hierarchy over requests. The identity yields an O(3^m) exact algorithm, identifies the two-chunk case as minimum vertex cover, and shows that on the leave-one-out family the optimum is the minimum external path length of a binary tree -- the merge-sort recursion -- so a global order pays Theta(n^2) against a true cost of Theta(n log n). Agglomerative clustering by common intersection is a tight 1/2-approximation for the achievable saving. On BM25 retrieval traces over three BEIR corpora the resulting layout reduces prefill by 17-36% against production RAG ordering, and the margin widens with retrieval depth as the theory predicts. Serving requests in the hierarchy's DFS order finally lets a cache holding one request's context attain the unbounded-cache optimum exactly, so cache capacity and reorder window act as substitutes.

0.28