PaperlayerView exact revision on arXiv

Source-linked AI summary

Mir-BFT: High-Throughput Robust BFT for Decentralized Networks

Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, Marko Vukolić

arXiv:1906.05552v3cs.DC

TL;DR

Leader-based BFT faces scaling challenges, while parallel leaders can introduce request duplication and censoring concerns. Mir partitions and rotates request assignments across parallel leaders and reports more than 60000 signed 500-byte requests per second on 100 WAN nodes.

  • Problem

    BFT performance at medium-sized WAN scales is a research focus, while countering request censoring requires allowing at least f + 1 leaders to propose a request.

    Source: §1 · pp. 1–2

  • Method

    Mir multiplexes parallel PBFT instances into one total order, partitioning the request hash space among leaders and rotating assignments.

    Source: §11 · p. 24

  • Results

    More than 60000 signed 500-byte requests/s on 100 WAN nodes, with Mir outperforming state-of-the-art protocols.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Mir combines parallel leaders that thwart censoring and request-duplication performance attacks with signature verification sharding to achieve high throughput at scale.

    Source: §11 · p. 24

    The model assumes adversaries cannot break the cryptographic primitives, including PKI and cryptographic hashes.

    Source: §2 · p. 3

Abstract

from arXiv · show

This paper presents Mir-BFT, a robust Byzantine fault-tolerant (BFT) total order broadcast protocol aimed at maximizing throughput on wide-area networks (WANs), targeting deployments in decentralized networks, such as permissioned and Proof-of-Stake permissionless blockchain systems. Mir-BFT is the first BFT protocol that allows multiple leaders to propose request batches independently (i.e., parallel leaders), in a way that precludes request duplication attacks by malicious (Byzantine) clients, by rotating the assignment of a partitioned request hash space to leaders. As this mechanism removes a single-leader bandwidth bottleneck and exposes a computation bottleneck related to authenticating clients even on a WAN, our protocol further boosts throughput using a client signature verification sharding optimization. Our evaluation shows that Mir-BFT outperforms state-of-the-art and orders more than 60000 signed Bitcoin-sized (500-byte) transactions per second on a widely distributed 100 nodes, 1 Gbps WAN setup, with typical latencies of few seconds. We also evaluate Mir-BFT under different crash and Byzantine faults, demonstrating its performance robustness. Mir-BFT relies on classical BFT protocol constructs, which simplifies reasoning about its correctness. Specifically, Mir-BFT is a generalization of the celebrated and scrutinized PBFT protocol. In a nutshell, Mir-BFT follows PBFT "safety-wise", with changes needed to accommodate novel features restricted to PBFT liveness.

1 Introduction

Mir addresses the scaling limits of leader-based BFT and the duplication risk introduced by parallel leaders. It combines parallel proposals with request-space partitioning and rotation, and reports high throughput on a 100-node WAN.

1 Introduction

  • A single leader’s O(n) work makes it a bottleneck as node count grows, while parallel leaders can duplicate requests and waste resources.With up to O(n) parallel leaders, duplication attacks may induce O(n)-fold duplication of requests.Source: §1 · p. 2
  • Mir partitions request hashes across leaders to prevent duplicate proposals, then rotates assignments across epochs to address censoring.It also shards client signature verification to reduce CPU overhead.Source: §1 · pp. 2–3
  • More than 60000 signed 500-byte requests/s on 100 WAN nodes, with 3x Chain’s throughput and over an order of magnitude more than other state-of-the-art single-leader protocols.The paper reports typical latencies of a few seconds in this setup.Source: §1 · p. 3
  • Mir generalizes PBFT, following it safety-wise while restricting changes for new features to liveness, which the authors say simplifies correctness reasoning.The paper also evaluates Mir in clusters and under different faults.Source: §1 · pp. 2–3

2 System Model

The system model specifies fault, cryptographic, and communication assumptions for BFT total-order broadcast, along with service properties. Mir enforces no duplication during agreement rather than ordering duplicates first.

2 System Model

  • The model assumes eventual synchrony, at most f Byzantine nodes with n ≥ 3f + 1, and that adversaries cannot break the cryptographic primitives.Any number of clients may be Byzantine; nodes communicate over authenticated point-to-point channels.Source: §2 · p. 3
  • The broadcast service is specified through validity, total-order agreement, no duplication, and liveness properties.The supplied passages state the property labels and fragments of their definitions.Source: §2 · p. 3
  • Mir enforces no duplication during agreement instead of ordering duplicates and filtering them afterward, which the paper describes as bandwidth-wasting.No duplication is identified as standard for total-order broadcast.Source: §2 · p. 3

3 PBFT and its Bottlenecks

PBFT’s primary proposes and sequences requests, making PRE-PREPARE a WAN bottleneck. Prepare and commit use metadata-only all-to-all rounds, while view changes and state-management protocols handle faults and log maintenance.

3 PBFT and its Bottlenecks

  • The primary’s PRE-PREPARE proposal is typically a network bottleneck on WANs.Other nodes validate the request upon receiving it.Source: §3 · p. 3
  • PREPARE and COMMIT are all-to-all rounds that use parallel links and carry metadata; nodes progress after matching quorums of n − f ≥ 2f + 1.A node commits after receiving a quorum of matching COMMIT messages.Source: §3 · p. 4
  • When a primary is faulty or a quorum is unavailable, nodes time out and initiate a view change in which a round-robin new primary re-proposes potentially committed requests.PBFT also uses checkpointing and state transfer for log and state compaction.Source: §3 · p. 4

4 Mir Overview

Mir multiplexes PBFT-style operation across parallel leaders while assigning requests and sequence numbers to avoid conflicts. Bucket rotation addresses censoring, while signatures, batching, and watermarks support request authentication and throughput.

4 Mir Overview

  • Mir uses request signatures instead of PBFT’s MAC vectors, but signature verification can become a CPU bottleneck, addressed through signature verification sharding.The cited passage gives the authentication change and its motivation.Source: §4 · p. 4
  • Mir reuses request and batch watermarks to facilitate concurrent proposals by multiple leaders.Requests are processed in batches, a standard PBFT throughput improvement.Source: §4 · pp. 4–5
  • Mir assigns sequence numbers to epoch leaders in round-robin order so they can propose batches simultaneously without conflicts; ungracious changes correspond to PBFT view changes.Epochs also end gracefully after a configured number of committed batches, except stable epochs with all nodes as leaders.Source: §4 · p. 5
  • More elaborate epoch-length and leader-set strategies using execution history, fault patterns, voting, randomness, or stake are outside the paper’s scope.Source: §4 · p. 5
  • A simplistic multi-leader design can suffer Θ(n)-factor throughput loss when clients retransmit requests to avoid censoring or malicious clients duplicate them.The paper distinguishes duplication attacks from denial-of-service attacks involving many unique requests.Source: §4 · p. 5
  • Mir partitions the request hash space into buckets assigned to one leader each, preventing duplicate proposals; periodic redistribution ensures each bucket is assigned to a correct leader infinitely often.Redistribution occurs at epoch changes and after a configured number of batches in stable epochs.Source: §4 · pp. 5–6

5 Mir Implementation Details

Mir supports concurrent client requests and distributes batch proposals across leaders using assigned sequence numbers and request buckets. In the common case, leaders propose batches while replicas check them for ordering, duplication, bucket ownership, and signature validity.

5.1 The Client

  • Clients can keep multiple requests in flight using timestamp watermarks, and may initially send each request to f + 1 nodes before retrying more broadly after a timeout.Requests carry monotonically increasing timestamps within a sliding window; clients periodically resend until the request commits at at least f + 1 nodes.Source: §5.1 · p. 6

5.2 Sequence Numbers and Buckets

  • Mir assigns sequence numbers to epoch leaders round-robin from the primary and assigns each leader request buckets, with periodic bucket rotation in stable epochs.The primary selects preferred buckets starting from the bucket containing its oldest pending request; leaders wait for in-flight batches to commit before proposing from newly assigned buckets.Source: §5.2 · pp. 6–7, Figure 3 · p. 7

5.3 Common Case Operation

  • Leaders hash each request’s client identifier and timestamp to a FIFO bucket, then propose batches from their active buckets when enough requests accumulate or a timer expires.If the timer expires with no available requests, a leader sends an empty batch to guarantee progress under low load.Source: §5.3 · p. 7
  • Replicas accept a batch only if its sequence number and leader are valid and its requests are not already preprepared, within client watermarks, in the leader’s active buckets, and signature-valid.The no-duplication check enforces P3, while signature verification supports Validity (P1); after acceptance, the protocol proceeds as in PBFT.Source: §5.3 · p. 7

5.4 Epoch Change

Epochs end either after their sequence numbers are exhausted or after a timeout triggers an epoch change. The transition uses PBFT-style view-change machinery and restores uncommitted requests so they can be proposed again.

5.4 Epoch Change

  • An epoch ends graciously when its sequence numbers are exhausted, or ungraciously when a node’s epoch-change timer expires; temporary disagreement about transitions does not violate liveness.Inconsistent transitions may temporarily prevent commits in the next epoch, but are eventually resolved in subsequent epochs.Source: §5.4 · pp. 7–8

5.4.1 Epoch Change Subprotocol

  • After a timeout, a node sends an EPOCH-CHANGE message to the next epoch’s primary, which constructs a NEW-EPOCH message using PBFT-style view-change procedures.Before entering the new epoch, correct nodes return uncommitted requests absent from NEW-EPOCH to their bucket queues and mark them not preprepared, allowing them to be proposed again.Source: §5.4.1 · p. 8

5.4.2 Starting a New Epoch

  • The next epoch’s primary reliably broadcasts its leader set and preferred buckets, and nodes wait for this configuration before participating.In a gracious transition, nodes also wait until they locally commit all in-flight batches from the preceding epoch.Source: §5.4.2 · p. 8

5.5 Checkpointing (Garbage Collection)

Mir uses checkpoints to prune protocol logs and advance client watermarks. It shards signature verification in stable epochs and supports reconnection through state transfer from a stable checkpoint.

5.5 Checkpointing (Garbage Collection)

  • At checkpoints, replicas collect 2f + 1 matching checkpoint messages to establish a stable checkpoint and discard older common-case messages from their logs.Checkpoint hashes cover batches since the preceding checkpoint; client low watermarks also advance when all requests below a delivered timestamp have been delivered.Source: §5.5 · p. 8

5.6 Signature Verification Sharding (SVS)

  • Signature verification sharding assigns f + 1 verifiers per batch, and replicas wait for verifier PREPARE messages before sending COMMIT.At least one verifier is correct, preserving Validity; because one faulty verifier can block commitment, Mir applies sharding only in stable epochs and disables it when the leader set shrinks.Source: §5.6 · pp. 8–9

5.7 State Transfer

  • A reconnecting node obtains the current epoch configuration, latest stable checkpoint, and intervening batches, using HELLO messages to request missing state.A node can fetch missing batches from one checkpoint signer and receive hash confirmations from f additional nodes.Source: §5.7 · p. 9
  • State-transfer traffic is reduced by delaying active participation until the next stable checkpoint and exchanging client-timestamp Merkle roots before fetching needed timestamps.Source: §5.7 · p. 9

5.8 Membership Reconfiguration

Membership changes take effect at checkpoints, while optional persistence supports recovery after crashes. Mir’s implementation also parallelizes batch processing and network connections.

5.8 Membership Reconfiguration

  • Configuration requests are totally ordered but take effect only after the checkpoint following the one at which they were ordered.This delay avoids nondeterminism because nodes may commit requests at different times.Source: §5.8 · p. 9

5.9 Durability (Persisting State)

  • By default, Mir does not persist state or message logs, so a crashed node waits for the next stable checkpoint to restore correct state; optional persistence supports recovery after a crash.The authors note that simultaneous faults exceeding f may be more likely with small node counts and offer persistence as an option.Source: §5.9 · p. 9
  • In a four-node LAN test with small transactions, durability left total throughput unchanged but increased average request latency by roughly 300ms.The authors attribute the throughput result mainly to batching, Mir’s parallel architecture, and the computation-intensive workload.Source: §5.9 · p. 9

5.10 Implementation Architecture

  • Mir’s Go implementation uses a separate thread per batch during common-case processing and parallelizes computation-intensive tasks such as signature verification and hashing.A manager thread handles ungracious epoch changes, sequential batch delivery, and checkpointing.Source: §5.10 · pp. 9–10
  • Independent network connections between node pairs are critical for boosting WAN performance beyond apparent bandwidth limits from a single TCP/TLS connection.Client requests also use an independent connection, allowing receipt to continue during epoch changes.Source: §5.10 · p. 10

6 Pseudocode

The pseudocode presents PBFT’s common message flow and Mir’s extensions for parallel leaders, bucketed request handling, epochs, and request deduplication.

6 Pseudocode

  • The section first presents PBFT pseudocode to show the common-case message flow shared by PBFT and Mir.The supplied PBFT pseudocode includes request reception, primary proposals, prepare and commit quorums, delivery, and view change.Source: §6 · pp. 10–11
  • The pseudocode omits batching and a batch timeout; the text says batching replaces requests with batches and adds validity checks across batch contents.At low load, the timeout keeps leaders sending batches, including empty ones, to drive checkpoints and avoid epoch-change timeouts.Source: §6 · p. 10
  • Mir initializes request buckets and epoch configuration, then assigns bucket ownership among the epoch’s leaders.The initial configuration gives all nodes leader status and assigns primary buckets.Source: §6 · p. 11
  • Mir verifies client requests, maps each request to a bucket using its timestamp and client key, and avoids queuing a duplicate timestamp-and-client pair.The pseudocode also excludes requests already pre-prepared.Source: §6 · p. 12
  • Leaders propose requests from active buckets through PRE-PREPARE, PREPARE, and COMMIT, then deliver committed requests in sequence order.A request is removed from its bucket after commitment.Source: §6 · p. 12
  • Epoch changes update the leader set and bucket assignments, while bucket rotations activate further requests for leaders to propose.The pseudocode uses PBFT view change and reliable broadcast for epoch configuration.Source: §6 · p. 12

7 Mir Correctness

The correctness section establishes Mir’s total-order-broadcast properties, with particular attention to liveness and the effect of signature verification sharding. Its arguments rely on PBFT for key safety and liveness steps.

7.1 Validity (P1)

  • A committed request must have been broadcast by a client, both with and without signature verification sharding (SVS).Without SVS, the proof derives enough correct signature verifications from the COMMIT and PREPARE quorums; with SVS, at least one correct verifier is among the f + 1 verifier nodes.Source: §7.1 · p. 13

7.2 Agreement (Total Order) (P2)

  • Mir’s agreement proof reduces common-case and ungracious-epoch-change safety to PBFT, while signed stable checkpoints support the state-transfer case.The proof also rules out the first correct commit of a batch through state transfer.Source: §7.2 · p. 13

7.3 No Duplication (P3)

  • A correct node cannot commit the same request at two sequence numbers; Mir’s pre-prepare checks and per-bucket synchronization prevent duplicate requests from being prepared.The SVS optimization does not affect this no-duplication property.Source: §7.3 · pp. 13–14

7.4 Totality (P4)

  • If a correct node commits a request, every correct node eventually commits it, using agreement and the lemma that every correct node eventually commits each committed sequence number.The proof handles sequence numbers that enter a stable checkpoint through state transfer and those that do not through watermark-window exhaustion and PBFT liveness.Source: §7.4 · p. 14

7.5 Liveness (P5)

  • If a correct client broadcasts a request, some correct node eventually commits it, across executions with finite or infinite epochs.For infinite epochs, the proof uses eventual request receipt and preferred requests in epochs with correct primaries; after GST, a correct leader’s proposal can commit within 3δ + rd if no view change intervenes.Source: §7.5 · pp. 15–16

8 LTO: Optimization for large requests

Light Total Order (LTO) targets network-bound systems with large requests, where request payloads constrain leader bandwidth but are not needed to establish order. It orders request hashes while retaining totality for those hashes.

8 LTO: Optimization for large requests

  • In network-bound settings, leader bandwidth for PRE-PREPARE messages drives maximum throughput, while request hashes can establish total order without carrying payloads.The passage notes that some systems still require payloads at every node, while others separate ordering from execution.Source: §8 · p. 16
  • LTO requires totality for each request hash rather than the full request and is offered as an optional throughput optimization.The optimization applies only in stable epochs.Source: §8 · p. 16
  • Mir’s evaluation table is identified as listing the configuration parameters used in the evaluation.The supplied caption does not specify individual parameters or table comparisons.Source: Table 3 · p. 17

9 Evaluation

The evaluation measures Mir’s throughput and latency across WAN and datacenter deployments, optimization variants, duplicate-request scenarios, and crash and Byzantine faults. Across these settings, the results show WAN scalability and performance under the tested faults, while exposing trade-offs from payload size, authentication, and bucket rotation.

9 Evaluation

  • Evaluation uses 500-byte requests representative of Bitcoin transactions and 3,500-byte requests typical of Hyperledger Fabric, with throughput measured just below saturation.The WAN deployment spans 16 datacenters across four continents and scales to 100 nodes; beyond 16 nodes, nodes are collocated in already-used datacenters.Source: §9 · p. 17, §9.1 · p. 17

9.1 Scalability on a WAN

  • At n=100, Mir maintains more than 60k req/s (3x Chain throughput); at n=4, it delivers 82.5k throughput (roughly 4x Chain).The WAN experiments compare Mir with PBFT, Chain, and Honeybadger; Figure 4 also presents a separate HotStuff comparison.Source: Figure 4 · p. 18, §9.1 · p. 18
  • With 3,500-byte requests and no signature verification sharding, Mir reaches 7k req/s at n=100; LTO raises this to about 12.5k req/s, a 70% improvement.At n=4, LTO reaches 40k req/s, roughly 40% above Mir without LTO; LTO replicates payloads to f + 1 nodes in a stable epoch while others agree on request hashes.Source: §9.1 · p. 19, Figure 6 · p. 19

9.2 Scalability in a Cluster/Datacenter

  • In a single datacenter, Chain peaks at roughly 130k req/s versus Mir’s 83k req/s, but adding signatures to Chain drops its throughput below Mir’s more than 80k req/s.The comparison attributes Chain’s higher peak to its use of MAC vectors rather than client signatures.Source: §9.2 · pp. 19–20, Figure 7 · p. 20

9.5 Performance Under Faults

  • Leader failures trigger configuration changes, while a WAN straggler delaying each batch by 15 seconds is detected and removed almost immediately; throughput averages 18k req/s versus a 24.8k baseline.On LAN, a 2-second straggler delay leaves the leader in the set for over 600 sequence numbers; average throughput is 15.7k req/s versus a 28.1k baseline.Source: §9.5 · pp. 20–21

9.3 Impact of optimizations and bucket rotation.

  • At n=16, bucket rotation costs about 3% throughput for small requests and 9.5% for large ones versus no rotation; signature sharding raises throughput to 74k req/s, or 33.5k req/s with LTO.Across Mir variants, latency is roughly 1–2 seconds at low load and 3–5 seconds near saturation; PBFT latency is 600–800 ms but it saturates at much lower load.Source: §9.3 · p. 20, Figure 8 · p. 21

9.4 Benefits of Duplication Prevention

  • Without duplication prevention, goodput falls 61% or 72% at n=4 and as much as 97% or 99% at n=100, depending on whether clients submit to f + 1 nodes or all nodes.The comparison is against Mir without signature sharding and demonstrates the performance cost of duplicate requests from parallel leaders.Source: §9.4 · p. 20, Figure 9 · p. 21

9.5 Performance Under Faults

  • With up to five Byzantine leaders censoring requests in a 16-node WAN, mean latency stays below 4.6 seconds under 100% censorship and below 2.2 seconds under 25% censorship.Shortening bucket rotation to 128 batches reduces mean latency by up to 44% and tail latency by up to 49%, at an approximately 10% peak-throughput cost.Source: §9.5 · pp. 20–21

10 Related Work

Related work spans parallel-leader replication, newer single-leader protocols, asynchronous BFT, and blockchain deployments. Mir is positioned as combining robust duplicate prevention with a PBFT-derived design.

10 Related Work

  • Mir generalizes PBFT, whose single leader creates a network bottleneck, while combining Aardvark-style robustness with parallel leaders and duplicate prevention.Recent blockchain-context multi-leader proposals [25] do not address request duplication and devise new protocols from scratch.Source: §10 · pp. 21–23
  • Mencius, EPaxos, and BFT-Mencius pursue latency benefits through nearby-node request mapping, but retransmission exposes BFT-Mencius to duplicate-request attacks.Mir instead assigns request buckets to nodes and redistributes that assignment over time to address censoring, while accepting that it does not optimize best-case latency.Source: §10 · pp. 22–23
  • HotStuff and SBFT reduce common-case messages to O(n), while Mir's parallel leaders avoid HotStuff's single-leader bandwidth bottleneck.Combining linear message complexity with parallel leaders is proposed as future work.Source: §10 · p. 23
  • Mir variants based on Zyzzyva's latency-efficient communication pattern are conceivable, and Mir remains compatible with Aliph's modular optimistic-BFT approach.Mir holds its ground against BFT Chain in clusters and considerably outperforms it in WANs.Source: §10 · p. 23
  • Mir significantly outperforms Honeybadger in their shared WAN-scale setting, while trading eventual synchrony for Honeybadger's asynchronous guarantees except with negligible probability.Honeybadger's random request sampling yielded goodput around 20% of nominal throughput in the reported evaluation.Source: §10 · p. 23
  • Mir is proposed as an in-committee protocol for systems such as Algorand and as an option for permissioned blockchains such as Hyperledger Fabric [11].ByzCoin's separation of transaction verification from block mining is described as orthogonal to Mir.Source: §10 · p. 23
  • Unlike Stellar's SCP [43], which uses asymmetric quorums and different trust and liveness assumptions, Mir demonstrates high throughput with classical symmetric quorums.The cited production configuration of Stellar had a reported liveness violation with failures of two specific nodes.Source: §10 · p. 24
  • Mir's request-verification approach is complementary to sharding protocols, which still require ordering within a shard or total ordering across shards.Monoxide offers weaker eventual atomicity across shards and scalability dependent on transaction-payload semantics.Source: §10 · p. 24

11 Conclusions

Mir combines parallel PBFT instances with rotating request-hash assignments to prevent duplicate proposals and censoring attacks. Signature verification sharding reduces CPU overhead, and the protocol achieves high throughput at scale while retaining PBFT-based reasoning about correctness.

11 Conclusions

  • Signature verification sharding reduces CPU overhead, helping Mir achieve unprecedented throughput at scale on wide-area networks and outperform state-of-the-art protocols.Source: §11 · p. 24
  • Mir multiplexes parallel PBFT instances into one totally ordered log, using partitioned and rotating request-hash assignments to prevent duplicate proposals and censoring attacks.Rotation eventually assigns each request to a correct leader.Source: §11 · p. 24
  • Because Mir builds on well-understood PBFT, the authors say its correctness is easy to reason about.Source: §11 · p. 24

Related papers

Loading 1906.05552v3…