Paper 2024/545

Optimal Asynchronous Byzantine Consensus with Fair Separability

Vincent Gramoli, University of Sydney, Redbelly Network
Zhenliang Lu, University of Sydney
Qiang Tang, University of Sydney
Pouriya Zarbafian, University of Sydney

Despite ensuring both consistency and liveness, state machine replication protocols remain vulnerable to adversaries who manipulate the transaction order. To address this, researchers have proposed order-fairness techniques that rely either on building dependency graphs between transactions, or on assigning sequence numbers to transactions. Existing protocols that handle dependency graphs suffer from sub-optimal performance, resilience, or security. On the other hand, Pompe (OSDI '20) introduced the novel ordering notion of ordering linearizability that uses sequence numbers. However, Pompe's ordering only applies to committed transactions, opening the door to order-fairness violation when there are network delays, and vulnerability to performance downgrade when there are Byzantine attackers. A stronger notion, fair separability, was introduced to require ordering on all observed transactions. However, no implementation of fair separability exists. In this paper, we introduce a protocol for state machine replication with fair separability ($\mathsf{SMRFS}$); moreover, our protocol has communication complexity $\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$, while previous works have cubic communication. To the best of our knowledge, $\mathsf{SMRFS}$ is the first protocol to achieve fair separability, and the first implementation of fair ordering that has optimal communication complexity and optimal Byzantine resilience.

Available format(s)
Cryptographic protocols
Publication info
State Machine ReplicationAsynchronous Byzantine ConsensusFair SeparabilityOrder FairnessOptimal
Contact author(s)
vincent gramoli @ redbelly network
zhenliang lu @ sydney edu au
qiang tang @ sydney edu au
pouriya zarbafian @ sydney edu au
2024-04-08: approved
2024-04-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vincent Gramoli and Zhenliang Lu and Qiang Tang and Pouriya Zarbafian},
      title = {Optimal Asynchronous Byzantine Consensus with Fair Separability},
      howpublished = {Cryptology ePrint Archive, Paper 2024/545},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.