Paper 2024/545
Optimal Asynchronous Byzantine Consensus with Fair Separability
Abstract
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 (
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2024-04-08: approved
- 2024-04-08: received
- See all versions
- Short URL
- https://ia.cr/2024/545
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/545, 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}, url = {https://eprint.iacr.org/2024/545} }