Paper 2020/269

Order-Fairness for Byzantine Consensus

Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels

Abstract

Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties: consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in leader-based protocols (almost all protocols used today), malicious leaders can directly choose the final transaction ordering. To rectify this problem, we propose a third consensus property: transaction order-fairness. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We provide several natural definitions for order-fairness and analyze the assumptions necessary to realize them. We also propose a new class of consensus protocols called Aequitas. Aequitas protocols are the first to achieve order-fairness in addition to consistency and liveness. They can be realized in a black-box way using existing broadcast and agreement primitives (or indeed using any consensus protocol), and work in both synchronous and asynchronous network models.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in Crypto 2020
Keywords
Byzantine consensusfair ordering
Contact author(s)
mahimna @ cs cornell edu
History
2020-08-09: last of 2 revisions
2020-03-04: received
See all versions
Short URL
https://ia.cr/2020/269
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/269,
      author = {Mahimna Kelkar and Fan Zhang and Steven Goldfeder and Ari Juels},
      title = {Order-Fairness for Byzantine Consensus},
      howpublished = {Cryptology ePrint Archive, Paper 2020/269},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/269}},
      url = {https://eprint.iacr.org/2020/269}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.