The Next 700 BFT Protocols

We present Abstract (ABortable STate mAChine replicaTion), a new abstraction for designing and reconfiguring generalized replicated state machines that are, unlike traditional state machines, allowed to
abort
executing a client’s request if “something goes wrong.”
Abstract can be used to considerably simplify the incremental development of efficient Byzantine fault-tolerant state machine replication (
BFT
) protocols that are notorious for being difficult to develop. In short, we treat a
BFT
protocol as a composition of Abstract instances. Each instance is developed and analyzed independently and optimized for specific system conditions. We illustrate the power of Abstract through several interesting examples.
We first show how Abstract can yield benefits of a state-of-the-art
BFT
protocol in a less painful and error-prone manner. Namely, we develop
AZyzzyva
, a new protocol that mimics the celebrated best-case behavior of Zyzzyva using less than 35% of the Zyzzyva code. To cover worst-case situations, our abstraction enables one to use in
AZyzzyva
any existing
BFT
protocol.
We then present
Aliph
, a new
BFT
protocol that outperforms previous
BFT
protocols in terms of both latency (by up to 360%) and throughput (by up to 30%). Finally, we present
R-Aliph
, an implementation of
Aliph
that is
robust
, that is, whose performance degrades gracefully in the presence of Byzantine replicas and Byzantine clients.