Source-linked AI summary
Revisiting Fast Practical Byzantine Fault Tolerance
Ittai Abraham, Guy Gueta, Dahlia Malkhi, Lorenzo Alvisi, Rama Kotla, Jean-Philippe Martin
TL;DR
Optimistic Byzantine replication seeks fast common-case progress, but this note finds that key protocols do not handle optimism correctly. It analyzes simple view-change scenarios and demonstrates safety violations in Zyzzyva and a liveness failure in FaB, with the problems appearing in the first log slot.
Problem
Several key works in the optimistic strand do not handle optimism correctly, despite aiming to provide a fast common case.
Source: §1 · p. 1Method
The note uses relatively simple scenarios involving four replicas and one or two view changes to demonstrate protocol failures.
Source: §1 · p. 1Results
The scenarios expose Zyzzyva safety violations and a FaB liveness failure, with the problems appearing in the first log slot.
Source: §1 · p. 1Takeaways & Limitations
Other fast Byzantine replication solutions are less fast when their optimistic track is not fully intertwined with a regular protocol.
Source: §1 · p. 1The analysis assumes state-machine replication with n replicas, f Byzantine faults, and authenticated, reliable asynchronous communication.
Source: Preliminaries · p. 2
Abstract
from arXiv · showhide
In this note, we observe a safety violation in Zyzzyva and a liveness violation in FaB. To demonstrate these issues, we require relatively simple scenarios, involving only four replicas, and one or two view changes. In all of them, the problem is manifested already in the first log slot.
1 Introduction
Optimistic Byzantine replication seeks a fast common case and falls back to a backup protocol when failures occur. This note reports safety violations in Zyzzyva and a liveness violation in FaB, while observing that the broader challenge of Byzantine Fast Paxos remains open.
1 Introduction
- Optimistic protocols target a fast common case without link or server failures, then fall back to a backup implementation with strong progress guarantees.This is the focus of one strand of efforts to improve PBFT efficiency.Source: §1 · p. 1
- Four-replica scenarios with one or two view changes expose Zyzzyva safety violations and FaB liveness failure in the first log slot.The note says the scenarios are relatively simple and require only one or two view changes.Source: §1 · p. 1
- Other fast Byzantine replication solutions are less fast because their optimistic track is not fully intertwined with a regular protocol.Source: §1 · p. 1
- The note says the challenge of Byzantine Fast Paxos remains open: simultaneously achieving optimal step-complexity and resilience, safety against fewer than a third Byzantine failures, and progress during partial synchrony.Source: §1 · p. 1
- The authors say their full solution will appear in a follow-up report.Source: §1 · p. 1
Preliminaries
The preliminaries frame the work as state-machine replication among replicas and clients, with authenticated, reliable asynchronous communication. The protocol decides a growing log of client requests subject to agreement, validity, and liveness.
Preliminaries
- The setting is state-machine replication with n replicas, f of which may be Byzantine faulty, and authenticated, reliable asynchronous communication among nodes.A message sent from a correct node to another correct node is signed and eventually arrives.Source: Preliminaries · p. 2
- At the core of state-machine replication is deciding on a growing log of operation requests from clients.Source: Preliminaries · p. 2
- Agreement requires any two correct replicas that commit at the same log position to decide the same value.Source: Preliminaries · p. 2
- Validity requires a committed decision to have been requested and signed.The supplied statement is truncated after “by.”Source: Preliminaries · p. 2
- Liveness requires that a correct client's request eventually leads replicas to commit some decision when the system is eventually partially synchronous.Source: Preliminaries · p. 2
View Change
The protocols use ranked views with a single leader per view, and leader replacement must safely carry forward prior values. The preliminaries distinguish benign and Byzantine mechanisms for choosing those values and for preserving decisions across views.
View Change
- The framework ranks proposals explicitly by view number, with replicas starting in an initial view and accepting requests only in their current view.Source: View Change · p. 2
- A view has one designated leader, and this approach preserves safety despite arbitrary communication delays while providing progress during synchrony.Source: View Change · p. 2
- A view change occurs when enough replicas suspect the leader; replicas advance on timer expiry or suggestions from f + 1 replicas, balancing stalled progress against capricious changes.Liveness relies on a constant fraction of views having a correct leader whose communication with correct replicas is timely.Source: View Change · p. 2
- New leaders must adopt prior leader values because a previous leader may already have committed a decision.Source: View Change · p. 2
- Benign protocols choose the value with the maximal view number from n − f replicas, while Byzantine settings use enlarged quorums whose intersection includes a correct node.PBFT also requires a correct node to prove a decision value to a new leader.Source: View Change · p. 2
- PBFT uses prepare messages from n − f nodes to ensure uniqueness, then forms a commit-certificate from n − f prepare messages so a correct node can prove a decision to a new leader.Source: View Change · pp. 2–3
Sacrificing Resilience
FaB, Zyzzyva, and Q/U avoid PBFT's extra phase by sacrificing resilience and using n = 5f + 1.
Sacrificing Resilience
- FaB, Zyzzyva, and Q/U use n = 5f + 1, sacrificing some resilience to avoid PBFT's extra phase.The intersection between a potential decision quorum and a view-change quorum has 2f + 1 correct nodes, enough for uniqueness and value transfer.Source: Sacrificing Resilience · p. 3
Kursawe’s Solution
Kursawe’s technique transforms a suitable Asynchronous Byzantine Agreement protocol into consensus with an optimistic fast path. Its fallback does not reuse fast-track prepares, and the technique covers only single-shot consensus, not state replication.
Kursawe’s Solution
- Kursawe’s black-box technique transforms a sufficiently strong-validity ABA protocol into consensus with an optimistic fast path.The paper describes this as addressing a more limited scope.Source: Kursawe’s Solution · p. 3
- In the fast track, a node decides when all nodes prepare an identical value; otherwise, the fallback invokes Byzantine agreement using prepare values as inputs.The agreement protocol must satisfy Byzantine validity: if all correct nodes start with the same input, the decision must match it.Source: Kursawe’s Solution · p. 3
- The fallback does not reuse prepare steps already performed in the fast track, so it is not optimal.The framework is described as correct, but its recovery does not use that earlier work.Source: Kursawe’s Solution · p. 3
- The technique solves single-shot consensus only and does not address state replication or execution.Source: Kursawe’s Solution · p. 3
FaB
FaB incorporates fast-track prepares into recovery and extends the failure model through a parameterized system size. Opening up recovery to achieve these enhancements resulted in an omission highlighted by the paper.
FaB
- FaB uses fast-track prepare messages in recovery, giving recovery the same overall cost as standard PBFT.Source: FaB · p. 3
- FaB parameterizes the failure model as n = 3f + 2t + 1, achieving fast termination despite up to t non-leader Byzantine failures while preserving safety against f.Source: FaB · p. 3
- Achieving these enhancements required opening the recovery agreement protocol rather than treating it as a black box, and that integration resulted in the omission identified in the paper.Source: FaB · p. 3
Zyzzyva
Zyzzyva extends FaB’s approach to state replication and speculative execution, but its view-change protocol does not provide safety against a faulty leader.
Zyzzyva
- Zyzzyva borrows FaB’s efficient intertwining of the optimistic fast track and recovery track.Source: Zyzzyva · p. 3
- Unlike FaB’s single-shot consensus, Zyzzyva provides state replication and uses speculative state-update execution for a high-throughput pipeline.Source: Zyzzyva · p. 3
- Zyzzyva’s view-change protocol fails to provide safety against a faulty leader.Source: Zyzzyva · p. 3
Upright
UpRight aims to build an engineering-strength Byzantine fault-tolerant engine and adopts prior solutions, but does not provide a full algorithm description.
Upright
- UpRight aims to build an engineering-strength BFT engine.Source: Upright · p. 3
- The UpRight paper does not provide a full description of its algorithm.Source: Upright · p. 3
- Instead, UpRight indicates that it adopts the Zyzzyva view-change protocol and FaB’s parameterized failure model.Source: Upright · p. 3
The Next 700 BFT Protocols
AZyzzyva combines Zyzzyva’s speculative fast path with a recovery protocol such as PBFT, avoiding the safety violations discussed here at the cost of a slower recovery path and delayed return to Zlight.
The Next 700 BFT Protocols
- AZyzzyva combines Zlight’s speculative fast path with a recovery protocol such as PBFT, switching regimes when Zlight stops making progress.It executes PBFT for a fixed number k of log slots after switching views.Source: The Next 700 BFT Protocols · p. 4
- AZyzzyva is not vulnerable to the safety violations of Zyzzyva exposed in this paper.Source: The Next 700 BFT Protocols · p. 4
- Compared with Zyzzyva’s two-phase recovery, AZyzzyva requires more recovery steps and waits for a k-slot commit decision before returning to Zlight.Source: The Next 700 BFT Protocols · p. 4
2 Revisiting the Zyzzyva View-Change
This section examines how Zyzzyva’s view-change rules can violate safety, focusing on choices between commit-certificates. Two four-replica scenarios illustrate the risks across views.
2.1 Introduction
- Zyzzyva’s rules for combining fast-track and two-phase evidence can violate safety, including preferring a commit-certificate over f + 1 prepares.The omission is subtle: without leader equivocation, a commit-certificate will not conflict with fast paths of higher views.Source: §2.1 · p. 5
2.2 A Skeletal Overview of Zyzzyva
- View-change gathers local states from 2f + 1 replicas; a valid commit-certificate selects the longest request-log, while f + 1 view-change messages with the same request-log extend the selected log.Source: §2.2 · p. 6
2.3 Breaking Safety: First Scenario
- In a four-replica scenario with one Byzantine replica, b becomes successfully committed at log position 1; replicas then undo b and successfully commit a at that position, reaching conflicting decisions across three views.Source: §2.3 · pp. 7–8
2.4 Breaking Safety: Second Scenario
- Prioritizing the longest commit-certificate is not always correct; in the second four-replica, three-view scenario, b1 commits at log position 1.The scenario uses four operation requests to construct commit-certificates of different lengths.Source: §2.4 · pp. 8–9
- After further messages are delayed, i3 collects view-change messages from itself, i1, and i4; i4 reports cert2 for (b1) and local log (b1, b2), while Byzantine i1 may join either report or send an empty log.Source: §2.4 · p. 9
- Leader i3 chooses cert1, the commit-certificate with the longest request-log, adopts (a1, a2), and sends that request-log in a new-view message.Source: §2.4 · p. 9
- Replicas accept i3’s new-view message, zero their local logs, undo b1 as needed, and commit a1 at log position 1.They speculatively execute a1 and send the result after accepting the message.Source: §2.4 · p. 9
3 Revisiting the FaB View-Change
Parameterized FaB’s progress certificate can fail to vouch for any value, leaving new leaders unable to make a valid proposal. A four-replica scenario shows how conflicting prepare and commit evidence produces this stuck state.
3.1 Introduction
- FaB offers FaB5 with n = 5f + 1 replicas and PFaB with n = 3f + 2t + 1; Zyzzyva borrows FaB’s optimistic fast track and adds view-numbers to prevent FaB’s stuck situation.In Parameterized FaB, the progress certificate may vouch for no value, causing the protocol to get stuck.Source: §3.2 · p. 10, §3.1 · p. 10
3.2 A Skeletal Overview of the FaB Protocol Family
- PFaB combines a two-step fast track, guaranteed during synchrony with a correct leader and up to t Byzantine replicas, with a PBFT-adapted recovery track.Unlike FaB5, PFaB may not guarantee fast progress during synchrony when the actual failure count exceeds t, although it remains safe despite up to f Byzantine failures.Source: §3.2 · p. 11
- PFaB inherits FaB’s progress-certificate approach, but its replica messages carry both the last prepared value and the last commit-certificate.A certificate vouches for a value only when it has neither a conflicting prepare value appearing in f+t+1 messages nor a conflicting commit-certificate.Source: §3.2 · p. 11
3.3 Getting Stuck
- PFaB can have f + t + 1 new-view messages for one prepare value and a commit-certificate for another, leaving no value vouched for and no valid proposal.The paper notes that PFaB’s Lemma 7 argument that every progress certificate vouches for at least one value contains a mistake.Source: §3.3 · pp. 11–12
- With f = 1, t = 0, and four replicas, a Byzantine leader proposes A to some replicas and B to another, then delayed messages trigger a view change.The new leader’s quorum includes B as a prepare value and A with a commit-certificate, so the progress certificate vouches for neither value.Source: §3.3 · pp. 11–12