Fair Ordering via Social Choice Theory

Control of the ordering of transactions in modern blockchains can be extremely profitable. Rather than allow one central actor to control this revenue source, recent research has studied mechanisms for decentralizing the process of computing an ordering among multiple, distributed replicas. This problem is akin to the classic problem from social choice theory of aggregating ordinal votes, applied to a streaming setting. Prior work proposes a ``$\gamma$-batch-order-fairness'' requirement on the aggregate ordering. Under this requirement, the ordering should be divisible into contiguous batches, and when a $\gamma$ fraction of replicas receive $tx$ before $tx^\prime$, then $tx^\prime$ cannot be in an earlier batch than $tx$. We extend this definition to formalize the notion that these batches should have minimal size, thereby giving the first notion of order fairness that cannot be vacuously satisfied (by arbitrarily large batches) and that can be satisfied in the presence of faulty replicas. We then show that the Ranked Pairs aggregation method produces an ordering that satisfies our fairness definition for every choice of parameter $\gamma$ simultaneously and for any number of faulty replicas (where fairness guarantees linearly degrade as the fraction of faulty replicas increases). We then instantiate our protocol in the streaming setting. Careful analysis of the interactions between ordering dependencies enables our protocol to simulate Ranked Pairs voting in this setting, and adjustments to ordering algorithm give a protocol that (under synchronous network assumptions) always appends a transaction to the output ordering after a bounded amount of time.