Brief Announcement: Delay-Optimal Transaction Order Fairness
Zhuo Cai, Amir Kafshdar Goharshady · 2026
Order-fair consensus aims to prevent a leader or block producer from exploiting transaction order, a concern amplified by front-running and MEV in decentralized finance. Existing order-fairness notions avoid some impossibilities by batching cyclic dependencies or by allowing bounded displacement, but these relaxations do not distinguish a tiny timing inversion from a large physical time gap. We revisit approximate-order-fairness (AOF), originally introduced and dismissed as too weak or impossible in prior work, in a synchronous model where parties can timestamp transaction arrivals using physical time. We show that time-aware AOF has a nontrivial feasible region: if a fraction φ of nodes receive tx at least before tx', then tx can be forced before tx' whenever > Δsync/k and φ > 1 - h/k, where h is the honest fraction and Δsync is the honest dissemination bound. We also give matching-style infeasibility constructions showing why smaller delays or lower thresholds permit Condorcet cycles. Finally, we outline how a HotStuff-style consensus layer can agree on timestamp reports while a deterministic ordering function enforces the strongest acyclic AOF constraints available in the observed execution.