Paper 2020/1300
Byzantine Ordered Consensus without Byzantine Oligarchy
Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi
Abstract
The specific order of commands agreed upon when running state machine replication (SMR) is immaterial to fault-tolerance: all that is required is for all correct deterministic replicas to follow it. In the permissioned blockchains that rely on Byzantine fault tolerant (BFT) SMR, however, nodes have a stake in the specific sequence that ledger records, as well as in preventing other parties from manipulating the sequencing to their advantage. The traditional specification of SMR correctness, however, has no language to express these concerns. This paper introduces Byzantine ordered consensus, a new primitive that augments the correctness specification of BFT SMR to include specific guarantees on the total orders it produces; and a new architecture for BFT SMR that, by factoring out ordering from consensus, can enforce these guarantees and prevent Byzantine nodes from controlling ordering decisions (a Byzantine oligarchy). These contributions are instantiated in Pompe, a BFT SMR protocol that is guaranteed to order commands in a way that respects a natural extension of linearizability.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. USENIX Operating Systems Design and Implementation (OSDI) 2020
- Keywords
- Byzantine consensusorderingBFTordering linearizabilityconsensus
- Contact author(s)
-
srinath @ microsoft com
yz2327 @ cornell edu
cheqi @ microsoft com
lidongz @ microsoft com
la13 @ cornell edu - History
- 2020-10-19: received
- Short URL
- https://ia.cr/2020/1300
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1300,
author = {Yunhao Zhang and Srinath Setty and Qi Chen and Lidong Zhou and Lorenzo Alvisi},
title = {Byzantine Ordered Consensus without Byzantine Oligarchy},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1300},
year = {2020},
url = {https://eprint.iacr.org/2020/1300}
}
