Paper 2023/1253

Ordering Transactions with Bounded Unfairness: Definitions, Complexity and Constructions

Aggelos Kiayias, University of Edinburgh, IOG
Nikos Leonardos, National and Kapodistrian University of Athens
Yu Shen, University of Edinburgh

An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were proposed in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize the input transactions, a natural objective is to minimize the distance (in terms of number of transactions) between any pair of unfairly ordered transactions in the output ledger — a concept we call bounded unfairness. In state machine replication (SMR) parlance this asks for minimizing the number of unfair state updates occurring before the processing of any request. This unfairness minimization objective gives rise to a natural class of parametric order fairness definitions that has not been studied before. As we observe, previous realizable relaxations of order fairness do not yield good unfairness bounds. Achieving optimal order fairness in the sense of bounded unfairness turns out to be connected to the graph theoretic properties of the underlying transaction dependency graph and specifically the bandwidth metric of strongly connected components in this graph. This gives rise to a specific instance of the definition that we call “directed bandwidth order-fairness” which we show that it captures the best possible that any ledger protocol can achieve in terms of bounding unfairness. We prove ordering transactions in this fashion is NP-hard and non-approximable for any constant ratio. Towards realizing the property, we put forth a new distributed ledger protocol called Taxis that achieves directed bandwidth order-fairness. We present two variations, one that matches the property perfectly but (necessarily) lacks in performance and liveness, and another that achieves liveness and better complexity while offering a slightly relaxed version of the property. Finally, we comment on applications of our work to social choice, a direction which we believe to be of independent interest.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
blockchainstate machine replicationfair ordering
Contact author(s)
aggelos kiayias @ ed ac uk
nikos leonardos @ gmail com
shenyu tcv @ gmail com
2024-04-08: revised
2023-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aggelos Kiayias and Nikos Leonardos and Yu Shen},
      title = {Ordering Transactions with Bounded Unfairness: Definitions, Complexity and Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1253},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.