AOAB: Optimal and Fair Ordering of Financial Transactions

In recent years, opportunistic traders have extracted hundreds of millions of dollars from blockchains by reordering financial transactions. The problem stems from the fact that blockchains implement a state machine replication that orders transactions in any consistent order, regardless of the order in which these transactions were received. Existing attempts at enforcing the order perceived by honest participants suffer from cyclic dependencies or message delays. In this paper, we propose the Asynchronous Ordered Atomic Broadcast (AOAB) protocol. It does not suffer from cyclic dependencies or message delays because (i) it assigns an absolute timestamp to transactions, and (ii) it tolerates unbounded message delays. Besides being the first protocol to solve this problem, AOAB is communication-optimal and resilience-optimal. In particular, AOAB makes use of threshold signatures and information dissemination to reach a communication complexity of
$\mathcal{O}(n\ell+\lambda n^{2})$
, where
$n$
is the number of processes,
$\ell$
is the input (transaction) size and
$\lambda$
is the security parameter. This is optimal when
$\ell\geq\lambda n$
,