Hi everyone, our work on FRP-25 is completed. This post provides a summary of our work on computing Arbitrum’s burst period and creating an ordering policy that mitigates drawbacks of classic First-Come-First-Served (FCFS) ordering in rollups. The full paper—which discusses our results in more detail—will be published later and shared on the forum for feedback and review:
Contributions
We proposed an algorithm to mitigate negative issues associated with MEV extraction on rollup chains using the FCFS ordering policy—particularly, adversarial attempts to manipulate sequencer orderings (via transaction spamming), and unfair ordering owing to variances in network latency experienced by users. The proposed algorithm is based on the concept of a fairness granularity estimate through a statistical approach. We also conducted experiments to assess the proposed algorithm’s accuracy in fairly ordering transactions.
The burst period—defined as the average interval between two network transactions—has been previously identified as a suitable indicator for the fairness granularity on FCFS chains like Arbitrum by Sysxun et al. Our main contribution is calculating Arbitrum’s burst period more formally (vs. using informal heuristics) and employing historical data to arrive at an estimate that reflects real-world network conditions.
The fairness granularity is a crucial aspect of our algorithm’s fairness property: it defines the interval during which transactions received by a sequencer are assumed to occur simultaneously. For context: the algorithm is implemented in a centralized (single-sequencer) with the following key details:
- The sequencer divides a batch of transactions received within the sequencing timeline into granularity intervals (aka., slots).
- Transactions in each interval are considered to happen at the same time.
- A specific selection mechanism is adopted to determine priority of transactions within each slot.
Determining the optimal granularity interval requires striking a balance between fairness and efficiency in transaction ordering: an extremely small fairness granularity resembles classic FCFS ordering (and displays similar drawbacks), while an excessively large granularity parameter leads to a time-consuming ordering process within intervals.
Experiments and results
Accurate estimation of Arbitrum’s burst period is hindered by the imprecise nature of block timestamps (which are represented as Unix seconds) and the centralized nature of the sequencer node. To address these limitations, we created a synthetic dataset with precise receive-times for transactions (in milliseconds) using a statistical distribution model.
The statistical distribution model employed parameters calculated based on Arbitrum’s average blocktime dataset, and we used it to generate one million records of transactions with their corresponding receive-times. Thereafter, we calculated the average interval between transactions in the generated dataset to estimate the burst period (in milliseconds) for Arbitrum.
Evaluation/conclusion
We adopted a similar evaluation methodology as adopted by Kelkar et al. in their work on the Themis fair-ordering protocol. Here, we focus on measuring how closely the final transaction ordering derived from our algorithm aligns with the ideal ordering, which is derived by arranging transactions based on (client-side) generation times instead of (sequencer-side) receive-times.
More concretely, the evaluation procedure involves comparing the final sequence of transactions with their original order at the time of generation for transaction pairs. This allows us to quantify the degree of deviation from the ideal ordering and assess the accuracy of the proposed algorithm in maintaining chronological order of transactions.
In the evaluation, our algorithm achieved an accuracy of ~70% for the Arbitrum One network. This suggests that over 70% of transaction pairs are sequenced based on their generation times—meaning they align with the ideal order—even in scenarios involving transactions with varying network delays.
The fair ordering algorithm is adaptable to other blockchains but requires specific granularity calculations for each network. While it doesn’t eliminate issues associated with classic FCFS-based ordering issues entirely, it mitigates them significantly and improves fairness in transaction ordering across network latency scenarios. The algorithm can also be applied in a distributed setting for each sequencer to create its local ordering and send it to the leader (who aggregates ordering preferences from replica nodes to create a final ordering).