Welcome to the resource topic for 2024/545
Title:
Optimal Asynchronous Byzantine Consensus with Fair Separability
Authors: Vincent Gramoli, Zhenliang Lu, Qiang Tang, Pouriya Zarbafian
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 (\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.
ePrint: https://eprint.iacr.org/2024/545
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .