Paper 2020/406

Hybrid-BFT: Optimistically Responsive Synchronous Consensus with Optimal Latency or Resilience

Atsuki Momose, Jason Paul Cruz, and Yuichi Kaji

Abstract

Optimistic responsiveness was introduced to shorten the latency of a synchronous Byzantine consensus protocol that is inherently lower bounded by the pessimistic bound on the network delay Δ. It states that a protocol makes a decision with latency on the order of actual network delay δ if the number of actual faults is significantly smaller than f, which is the worst-case allowed. In this paper, we investigate if a Byzantine consensus can simultaneously achieve (i) optimistic responsiveness, and (ii) optimal latency of Δ+O(δ) in the presence of f faults. To do this, we provide a tight upper bound on the number of actual faults by showing matching feasibility and infeasibility results. Furthermore, we present a simple leader-based Byzantine fault-tolerant (BFT) replication protocol as a practical application. Even while being able to rotate leaders after every decision, our protocol simultaneously achieves average latency of (i) under optimistic condition and (ii) (or ) in the presence of faults, which is more than a factor of two better than current state-of-the-art rotating-leader BFT protocols.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
BFTbroadcastByzantine consensusoptimistic responsiveness
Contact author(s)
momose @ sqlab jp
History
2020-09-07: last of 5 revisions
2020-04-13: received
See all versions
Short URL
https://ia.cr/2020/406
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/406,
      author = {Atsuki Momose and Jason Paul Cruz and Yuichi Kaji},
      title = {Hybrid-{BFT}: Optimistically Responsive Synchronous Consensus with Optimal Latency or Resilience},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/406},
      year = {2020},
      url = {https://eprint.iacr.org/2020/406}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.