Optimising Order-Fairness in Blockchains using Ordering Linearizability

Abstract

The world of digital finance was forever reshaped by the release of Bitcoin, seen as a symphony of cryptographic and distributed systems principles orchestrated together to provide a coherent machine for permissionless, peer-to-peer payments. This singular event led to the emergence of a new paradigm where a ledger of digital payments could be upheld by completely decentralized participants of a protocol that could freely join and leave, and contrasted immensely against traditional centralized finance models. The success of this new paradigm brought great attention to its underlying technology, State Machine Replication (SMR), but exposed a shortcoming in the way transactions were ordered in SMR protocols. Although a slight detail, the shortcomings of ordering were misused by malicious actors to reorder transactions and exploit hundreds of millions of profit from unsuspecting users.

To mitigate the risk of these shortcomings, the idea of order-fairness was introduced to constrain the output of SMR so that the final ordering of transactions reflects the ordering observed by all participating processes. Ordering linearizability is one ordering technique that achieves such a result. Specifically, with ordering linearizability, processes assign ordering indicators to transactions they observe, ordering the output using the indicators that are upper-bounded and lower-bounded by ordering indicators assigned by correct processes. However, ordering linearizability is not sufficient to prevent all reordering attacks. Furthermore, its implementation induces additional costs compared to standard SMR and displays sub-optimal time and communication complexity. This dissertation builds upon ordering linearizability and introduces SMR protocols that improve resilience to reordering attacks, reduce the additional costs induced by adding order-fairness, and fill the gaps present in the formulation of ordering linearizability.