International Association for Cryptologic Research

International Association
for Cryptologic Research


Order-Fairness for Byzantine Consensus

Mahimna Kelkar , Cornell Tech, Cornell University, IC3
Fan Zhang , Cornell Tech, Cornell University, IC3
Steven Goldfeder , Cornell Tech, Cornell University, IC3
Ari Juels , Cornell Tech, Cornell University, IC3
DOI: 10.1007/978-3-030-56877-1_16 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
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 usually satisfy two properties: {\em consistency} and {\em 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 {\em 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: {\em transaction order-fairness}. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We also 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.
Video from CRYPTO 2020
  title={Order-Fairness for Byzantine Consensus},
  author={Mahimna Kelkar and Fan Zhang and Steven Goldfeder and Ari Juels},