Universally Composable Transaction Order Fairness: Refined Definitions and Adaptive Security

While consistency and liveness are the defining properties of ledger consensus, fair ordering has emerged as an independent consideration whose importance is underscored by the observation of real world transaction inclusion strategies that manipulate fairness such as Miner Extractable Value. Receiver-order fairness is a fine-grain notion of fairness that determines the order of any two submitted transactions based on the two sequences of reception timestamps for the two transactions across all nodes in the network. Given this information, ledger serialization can be viewed as the social choice problem of producing the most agreeable transaction order based on the "preferences" of the miners or validators. In this work, our contribution is three-fold: (i) We put forward a formal Universally Composable definition for order fairness that encompasses receiver order fairness as well as input causality. (ii) We design a novel ledger protocol that preserves input causality and receiver order fairness. (iii) We capture in our composable definition and construction the role that transaction fees play when dealing with fairness.

Our protocol is based on a novel YOSO-style approach that allows encrypting transactions for a short period of time. Notably, the communication complexity required to decrypt the transactions is independent of the number of encrypted transactions. To the best our our knowledge, we are the first to provide a YOSO-style approach with such asymptotic complexity while relying on standard cryptographic assumptions.