Cryptology ePrint Archive: Report 2020/269

Order-Fairness for Byzantine Consensus

Mahimna Kelkar and Fan Zhang and 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.

Category / Keywords: foundations / Byzantine consensus, fair ordering

Date: received 27 Feb 2020, last revised 6 Mar 2020

Contact author: mahimna at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20200306:194827 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]