PaperlayerView exact revision on arXiv

Source-linked AI summary

Flexible Byzantine Fault Tolerance

Dahlia Malkhi, Kartik Nayak, Ling Ren

arXiv:1904.10067v2cs.CRcs.DC

TL;DR

Classic BFT protocols are tailored to fixed fault and timing assumptions, limiting how one protocol serves clients with different beliefs. Flexible BFT separates replica protocol execution from client commit rules and introduces a mixed Byzantine/alive-but-corrupt fault model. It supports combined-fault thresholds beyond existing bounds while enabling clients with correct, diverse assumptions to use the same protocol.

  • Problem

    Classic BFT designs bind protocols to particular fault and timing assumptions, and may lose safety and liveness when deployment conditions differ.

    Source: §1 · p. 1

  • Method

    Flexible BFT combines alive-but-corrupt faults with a replica protocol separated from client commit rules, using network-speed execution and flexible quorum roles.

    Source: §1 · p. 2, §4.2 · p. 7

  • Results

    Combined Byzantine and alive-but-corrupt tolerance exceeds 1/3 in partial synchrony and 1/2 in synchrony, while the Byzantine fraction remains below those respective bounds.

    Source: §1 · p. 2, §8 · p. 17

  • Takeaways & Limitations

    Clients with different fault thresholds and timing beliefs can use the same protocol and, when their assumptions are correct, commit consistently.

    Source: §1 · pp. 2–3

    The liveness proof assumes all clients have correct commit rules; the fault model does not specify what alive-but-corrupt replicas do when they can violate safety for some clients.

    Source: §8 · p. 17

Abstract

from arXiv · show

This paper introduces Flexible BFT, a new approach for BFT consensus solution design revolving around two pillars, stronger resilience and diversity. The first pillar, stronger resilience, involves a new fault model called alive-but-corrupt faults. Alive-but-corrupt replicas may arbitrarily deviate from the protocol in an attempt to break safety of the protocol. However, if they cannot break safety, they will not try to prevent liveness of the protocol. Combining alive-but-corrupt faults into the model, Flexible BFT is resilient to higher corruption levels than possible in a pure Byzantine fault model. The second pillar, diversity, designs consensus solutions whose protocol transcript is used to draw different commit decisions under diverse beliefs. With this separation, the same Flexible BFT solution supports synchronous and asynchronous beliefs, as well as varying resilience threshold combinations of Byzantine and alive-but-corrupt faults. At a technical level, Flexible BFT achieves the above results using two new ideas. First, it introduces a synchronous BFT protocol in which only the commit step requires to know the network delay bound and thus replicas execute the protocol without any synchrony assumption. Second, it introduces a notion called Flexible Byzantine Quorums by dissecting the roles of different quorums in existing consensus protocols.

1 Introduction

Classic BFT designs bind replicas and clients to one fault and timing model, while Flexible BFT separates protocol design from client assumptions. This supports stronger combined-fault resilience and lets clients with different beliefs use the same protocol.

1 Introduction

  • Classic BFT protocols are tailored to one set of fault and timing assumptions, and can fail when deployment conditions differ.The paper notes that optimal-resilience partially synchronous protocols lose safety and liveness above 1/3 Byzantine faults, while synchronous ones do so above 1/2 or when the synchrony bound is violated.Source: §1 · p. 1
  • Alive-but-corrupt replicas attack safety but, if unable to break it, do not try to prevent liveness, enabling combined-fault tolerance beyond existing Byzantine bounds.The paper reports combinations exceeding 1/3 in partial synchrony and 1/2 in synchrony while keeping Byzantine faults below the respective bounds.Source: §1 · pp. 2–3
  • Flexible BFT lets clients with different fault thresholds and timing beliefs interpret one protocol transcript and commit under their own assumptions.The guarantees apply when clients' assumptions are correct; clients with correct but different assumptions agree on the committed value.Source: §1 · pp. 1–2
  • Clients can adjust their assumptions, such as requiring more votes for a high-value transaction or after observing conflicting votes or long delays.A client that believes in synchrony may adopt a more conservative delay bound or switch to partial synchrony after abnormally long delays.Source: §1 · p. 2
  • A client may commit before another client, but clients with correct assumptions commit consistently; commits made under incorrect assumptions may later be reverted.The paper compares this recovery behavior to a Bitcoin client increasing the confirmations it requires after a competing longer fork appears.Source: §1 · p. 2
  • A network-speed replica protocol leaves committing to clients, while Flexible Byzantine Quorums separate replica protocol quorums from client commit quorums.The synchronous protocol requires synchrony only for the client commit step; the quorum design assigns distinct quorum sizes to replica protocol actions and client decisions.Source: §1 · pp. 2–3

2 Modeling Flexible BFT

Flexible BFT models a replicated service in which clients and replicas have distinct roles, and clients may interpret the protocol transcript using different assumptions. Its guarantees concern safety and liveness for learners whose assumptions are correct.

2 Modeling Flexible BFT

  • The service uses n replicas to provide clients with a single server interface and a shared totally ordered sequence of values.Clients act as proposers and learners, while replicas act as acceptors.Source: §2 · pp. 3–4
  • In the model, proposers send values, acceptors add them to the sequence, and learners decide what to execute from the protocol transcript.The sequence is called a blockchain, and learners execute it on a state machine.Source: §2 · p. 3
  • The standard properties are safety—learners learn the same sequence—and liveness—each proposed value is eventually executed by every learner.Source: §2 · p. 3
  • Flexible BFT permits learners with different assumptions to interpret the transcript differently, while correct-assumption learners still learn the same sequence and eventually execute proposed values.Source: §2 · p. 3
  • Byzantine replicas may behave arbitrarily, whereas alive-but-corrupt replicas attack safety but help liveness if they cannot break safety; the adversary is static.The safety proof treats alive-but-corrupt replicas like Byzantine replicas, and the liveness proof treats them like honest replicas.Source: §2 · p. 4
  • The model assumes hash functions, digital signatures, a public-key infrastructure, pair-wise replica channels, and clocks advancing at the same rate.Source: §2 · p. 4

3 Synchronous BFT with Network Speed Replicas - Overview

The synchronous protocol lets replicas run without blocking waits or a synchrony assumption, while clients use their own delay bounds to commit. Its quorum and locking conditions support safety and liveness under combined Byzantine and alive-but-corrupt faults.

3 Synchronous BFT with Network Speed Replicas - Overview

  • Replicas execute at network speed without blocking waits or relying on synchrony, while client commit rules use synchrony bounds; combined Byzantine and alive-but-corrupt faults can exceed one half.The Byzantine fault ratio remains below one half.Source: §3 · p. 5
  • Each view has a leader propose a value, replicas vote when it is safe, and a certificate locks replicas on that value.Replicas switch views after equivocation or a proposal timeout; Figure 1 depicts the protocol overview.Source: §3 · pp. 4–5, Figure 1 · p. 4
  • A client commits only after replicas report a certificate and no equivocation or view change occurs during the 2∆ interval after certification.∆ is the maximum message delay the client believes in.Source: §3 · p. 5
  • Safety follows when quorum honesty prevents another value from being certified and locks honest replicas; liveness follows when quorum availability lets an honest or alive-but-corrupt leader drive consensus.The safety argument uses an undisturbed period after a replica locks on the value; the liveness argument assumes faulty leaders are blamed and a view change eventually reaches an honest or alive-but-corrupt leader.Source: §3 · p. 5
  • With Byzantine fraction B and alive-but-corrupt fraction P, quorum honesty requires B + P < qr, while availability requires B ≤ 1 − qr, allowing varying combinations when qr > 1/2.Without alive-but-corrupt faults, quorum honesty requires B < qr and availability requires B ≤ 1 − qr.Source: §3 · p. 5
  • Clients may choose their own message-delay bounds because the replica protocol does not rely on a synchrony bound.A client using a correct bound enjoys safety.Source: §3 · p. 6

4 Flexible Byzantine Quorums for Partial Synchrony - Overview

Flexible Byzantine Quorums separate quorum roles so safety and liveness can be analyzed under different fault thresholds. This lets clients use different commit rules over the same replica protocol.

4 Flexible Byzantine Quorums for Partial Synchrony - Overview

  • The design generalizes partially synchronous BFT quorums to support higher fault tolerance and diverse clients, while this overview sets aside termination.Source: §4 · p. 6

4.1 Background: Quorums in PBFT

  • In PBFT, 2/3-sized quorums support safety through honest intersection and liveness through availability of an all-honest quorum.The stated quorum size is slightly above 2/3 in the precise 2f +1 out of 3f +1 formulation.Source: §4.1 · p. 6

4.2 Flexible Byzantine Quorums

  • Flexible BFT assigns separate quorums to locking, unlocking, certificate uniqueness, and client commit safety.The paper names these qlck, qulck, qunq, and qcmt, respectively.Source: §4.2 · p. 7
  • For safety across views, every unlocking quorum must intersect every commit quorum in at least one honest replica.This requires the faulty fraction to be less than qulck + qcmt −1.Source: §4.2 · p. 7
  • Safety holds below min(qunq + qlck −1, qcmt + qulck −1), while liveness holds when Byzantine faults are at most 1 −max(qunq, qcmt, qlck, qulck).Balanced quorum sizes are optimal for these bounds.Source: §4.2 · p. 7
  • With qr = 0.7 and qc = 0.8, the protocol can tolerate 0.2 Byzantine faults plus 0.3 alive-but-corrupt faults.The example uses the model where alive-but-corrupt replicas attack safety but not liveness.Source: §4.2 · p. 8
  • Clients with different fault assumptions can use the same replica protocol by choosing different commit thresholds.A larger qc seeks stronger safety against dishonest replicas while trading liveness; a smaller qc suits clients expecting more liveness attacks.Source: §4.2 · p. 8

5 Flexible BFT Protocol

Flexible BFT replicas certify blocks while clients commit under their own fault and timing assumptions. Its protocol combines replica-side quorum rules with distinct client commit rules.

5 Flexible BFT Protocol

  • The protocol supports partial-synchrony clients choosing qc and synchrony clients choosing ∆, while replicas execute with qr.Voting rounds can be pipelined.Source: §5 · p. 8

5.1 Notation

  • A block contains a proposed value and a hash of its predecessor; certificates contain qr replica signatures and rank by view, then height.The first block has no predecessor.Source: §5.1 · p. 8

5.2 Replica Protocol

  • Replicas certify chained blocks using qr votes; after a view change, the new leader proposes from the highest-certified block in the collected status.Replicas blame leaders for malicious behavior or lack of progress and enter a view change.Source: §5.2 · pp. 9–10

5.3 Client Commit Rules

  • Client commit rules use block-vote counts for partial synchrony or an undisturbed 2∆ period for synchrony.These are the two client types supported by the protocol.Source: §5.3.1 · p. 10, §5.3.2 · p. 11

5.3.1 Clients with Partial-Synchrony Assumptions (CR1)

  • Under CR1, a block and its immediate successor each need qc votes in the same view, and safety holds below qc + qr − 1 faulty replicas.The fault count includes Byzantine and alive-but-corrupt replicas.Source: §5.3.1 · p. 10

5.3.2 Client with Synchrony Assumptions (CR2)

  • With a correct synchrony bound ∆ and fewer than qr faulty replicas, CR2 commits are safe after an undisturbed 2∆ period.A replica reports no equivocation or view change during that period.Source: §5.3.2 · p. 11

5.4 Safety and Liveness

  • Correct commit rules ensure that clients commit the same block at each height and keep committing new blocks.The liveness argument treats alive-but-corrupt replicas as honest once safety is established.Source: §5.4 · pp. 12–13

5.5 Efficiency

  • Synchronous clients incur 2∆ plus a few network-speed rounds, while partial-synchrony clients need two voting rounds; broadcasts cost O(n^2) messages.The latency comparisons are to synchronous state-of-the-art protocols and PBFT, respectively.Source: §5.5 · p. 13

6 Discussion

Flexible BFT lets clients choose fault and synchrony assumptions while using a shared protocol, with supported trade-offs determined partly by the administrator’s qr. Its discussion explains how client assumptions and qr choices affect safety and liveness, and how resilience and diversity can also be provided separately.

6.2 Comparing Different qr Choices

  • The administrator chooses qr, which determines the client assumptions the protocol supports; Figure 6 compares client support across qr choices.Clients choose qc and ∆ for committing blocks.Source: §6 · p. 13, §6.2 · p. 14, Figure 6 · p. 15

6.1 Client Assumptions Supported by qr

  • Partial-synchrony clients can trade Byzantine tolerance for total-fault tolerance along the supported line, while correctly timed synchronous clients can tolerate 1/3 Byzantine and 2/3 total faults.For partial synchrony, moving toward fewer Byzantine faults permits more total faults; synchronous tolerance depends on the client choosing a correct ∆.Source: §6.1 · p. 14
  • Incorrect fault or synchrony assumptions can cost safety or liveness; a client may need to revert unsafe commits, adjust its threshold, or switch to a synchronous rule.A synchronous client choosing too small a ∆ may see a conflicting value certified; if the true fault model lies in the synchronous region, no partially synchronous rule is both safe and live.Source: §6.1 · p. 14

6.2 Comparing Different qr Choices

  • For partial-synchrony clients, qr ≥ 2/3 dominates qr < 2/3, while increasing qr trades greater safety tolerance for reduced Byzantine liveness tolerance.For qr ≥ 2/3 or synchronous clients, no qr is Pareto optimal; the choice represents a safety–liveness trade-off.Source: §6.2 · p. 14

6.3 Separating Alive-but-corrupt Resilience from Diversity

  • Stronger alive-but-corrupt resilience and client diversity can be provided separately, although a uniform setting that raises total-fault tolerance sacrifices Byzantine tolerance for all clients.In the diverse setting, clients may instead choose their own fault assumptions, including the classic Byzantine model; without alive-but-corrupt faults, the identified diversity for partial-synchrony clients is limited.Source: §6.3 · p. 15

7 Related Work

The related-work discussion compares Flexible BFT’s resilience and client diversity with existing protocols, and situates its quorum and mixed-fault ideas alongside prior work. It also identifies an open challenge in incentive analysis for the alive-but-corrupt model.

Resilience

  • Figure 7 compares Byzantine resilience on the x-axis with total alive-but-corrupt resilience on the y-axis, placing Flexible BFT client beliefs alongside existing protocol thresholds.Existing partially synchronous protocols are represented at (1/3, 1/3), and synchronous protocols at (1/2, 1/2); some protocols use two commit rules without client diversity.Source: §7 · pp. 15–16, Figure 7 · p. 16

Diverse client beliefs

  • Prior diversity examples include Bitcoin’s differing confirmation thresholds, XFT’s two client types, and Stellar’s client-selected quorums; Flexible BFT instead varies alive-but-corrupt and synchrony assumptions.The paper describes the Stellar and Flexible BFT approaches as largely orthogonal and complementary.Source: §7 · p. 16

Flexible Paxos

  • Flexible Byzantine Quorum Intersection is presented as the Byzantine and alive-but-corrupt counterpart to Flexible Paxos’s cross-view quorum intersection, extended to support diverse client assumptions.Flexible Paxos observes that Paxos needs intersection across views, but not within a view.Source: §7 · p. 16

Mixed fault model

  • Unlike BAR’s rational-replica model, alive-but-corrupt replicas may collude without the stated BAR constraints, and analyzing incentives for this model remains open.The paper says Flexible BFT does not rely on deterrence for good behavior and addresses synchronous as well as partial-synchrony settings.Source: §7 · p. 16

8 Conclusion and Future Work

Flexible BFT combines a protocol for diverse client assumptions with stronger combined-fault tolerance, using distinct technical approaches for synchronous and partial-synchrony settings. Its liveness proof and clock assumptions leave specific conditions for future work.

Conclusion

  • Flexible BFT supports clients with different assumptions on one ledger and tolerates combined Byzantine and alive-but-corrupt faults exceeding 1/2 under synchrony and 1/3 under partial synchrony.The conclusion combines a synchronous network-speed protocol, whose commit rule alone uses the synchrony assumption, with Flexible Byzantine Quorums for partial synchrony.Source: §8 · p. 17

Future Work

  • The liveness proof assumes all clients have correct commit rules, and the protocol assumes replicas’ clocks advance at the same rate.The authors identify rational-model analysis and support for clock drift as future work.Source: §8 · p. 17
Loading 1904.10067v2…