Source-linked AI summary
DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks
Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, David Tse
TL;DR
Variable bandwidth in wide-area networks can make slow block downloads hold up BFT consensus. DispersedLedger separates agreement on block commitments from full block retrieval, allowing nodes to retrieve at their own pace. In a 16-city deployment, it reports 2× better throughput and 74% lower latency than HoneyBadger.
Problem
Bandwidth variability across nodes and over time can cause slow downloads to hold up progress in BFT protocols, reducing throughput below average network capacity.
Source: §1 · p. 1Method
DispersedLedger agrees on an ordered log of block commitments and uses verifiable information dispersal so nodes can retrieve blocks asynchronously at their own pace.
Source: §1 · p. 1Results
2× better throughput and 74% lower latency than HoneyBadger in a wide-area deployment across 16 major cities.
Source: §7 · p. 12Takeaways & Limitations
The approach decouples agreement from bandwidth-intensive block downloads, allowing nodes to make progress at different retrieval speeds.
Source: §1 · pp. 1–2Server-sent spam harms DispersedLedger and HoneyBadger equally and is bounded by the fraction of Byzantine servers (f/N).
Source: §4.5 · p. 9
Abstract
from arXiv · showhide
The success of blockchains has sparked interest in large-scale deployments of Byzantine fault tolerant (BFT) consensus protocols over wide area networks. A central feature of such networks is variable communication bandwidth across nodes and across time. We present DispersedLedger, an asynchronous BFT protocol that provides near-optimal throughput in the presence of such variable network bandwidth. The core idea of DispersedLedger is to enable nodes to propose, order, and agree on blocks of transactions without having to download their full content. By enabling nodes to agree on an ordered log of blocks, with a guarantee that each block is available within the network and unmalleable, DispersedLedger decouples bandwidth-intensive block downloads at different nodes, allowing each to make progress at its own pace. We build a full system prototype and evaluate it on real-world and emulated networks. Our results on a geo-distributed wide-area deployment across the Internet shows that DispersedLedger achieves 2x better throughput and 74% reduction in latency compared to HoneyBadger, the state-of-the-art asynchronous protocol.
1 Introduction
Bandwidth variability makes slow block downloads a bottleneck for BFT consensus in large WANs. DispersedLedger separates agreement on block commitments from block retrieval, so nodes can retrieve at their own pace while preserving block availability; its evaluation reports higher throughput and lower latency than HoneyBadger.
1 Introduction
- In each epoch, BFT progress is gated by the (f +1)th slowest node, so slow downloads prevent faster nodes from fully using their bandwidth.This straggler effect also applies to asynchronous BFT protocols that require a super-majority to download and vote.Source: §1 · p. 1
- DispersedLedger first agrees on an ordered log of small block commitments, then lets each node download and execute blocks at its own pace.Fast nodes can progress if they have the minimal bandwidth needed to participate in agreement.Source: §1 · pp. 1–2
- Verifiable information dispersal ensures committed blocks remain available for later retrieval; nodes vote once dispersal is observed rather than waiting to download blocks.An unavailable committed block could otherwise halt the system.Source: §1 · p. 2
- AVID-M is proposed as an asynchronous VID protocol, and DispersedLedger also addresses censorship and practical issues including retrieval traffic, lagging nodes, and spam transactions.The introduction reports AVID-M communication cost 1–2 orders of magnitude better for small blocks and clusters of more than a few servers.Source: §1 · p. 2
- Across 16 cities, DispersedLedger achieves 36 MB/s throughput and 800 ms latency, with 105% higher throughput and 74% lower latency than HoneyBadger.The latency is reported as stable across a wide range of load.Source: §1 · p. 2
2 Background and Related Work
This section defines the BFT replication setting and its trust assumptions, reviews verifiable information dispersal and asynchronous BFT protocols, and states the system’s security model.
2.1 The BFT Problem
- BFT replicates a total-ordered transaction log across servers despite up to f Byzantine servers; this paper assumes consortium-style organizations and clients that trust their organization’s servers.The stated properties are agreement, total order, and validity.Source: §2.1 · pp. 2–3
2.2 Verifiable Information Dispersal
- VID disperses data across servers for later retrieval; AVID-M reduces per-message overhead from AVID-FP’s 37N bytes to one 32-byte hash, independent of cluster size.The section says AVID-FP’s overhead makes it unsuitable for small blocks and clusters of more than a few nodes.Source: §2.2 · p. 3
2.3 Asynchronous BFT protocols
- DispersedLedger assumes an asynchronous network and uses randomization to tolerate up to f Byzantine servers among 3f +1; HoneyBadger achieves O(N) communication cost per committed transaction bit with batching.HoneyBadger’s structure uses parallel Binary Byzantine Agreement instances to select proposed blocks for commitment.Source: §2.3 · p. 3
2.4 Security Model
- The security model assumes an asynchronous network, a fixed set of N nodes with at most f Byzantine nodes and N ≥3f +1, and authenticated messages using publicly known keys.Source: §2.4 · p. 3
3 AVID-M: An Efficient VID Protocol
AVID-M reduces dispersal overhead by committing to a compact summary of encoded chunks and checking encoding consistency during retrieval. Its protocol coordinates chunk storage and retrieval while providing the stated verifiable-information-dispersal properties.
3.1 Problem Statement
- A VID instance must provide termination, agreement, availability, and correctness, including consistent retrieval and recovery of B after a lone correct client disperses it.These properties specify when dispersal completes and what correct clients can retrieve.Source: §3.1 · p. 4
3.2 Overview of AVID-M
- Earlier AVID protocols checked encoding during dispersal, but downloading chunks or fingerprints from correct peers limited scalability; AVID-FP cross-checksum overhead grows quadratically with N.At N > 40 and |B| = 100 KB, each AVID-FP node downloads more than a full block.Source: §3.2 · p. 4
- AVID-M commits to possibly inconsistent chunks with a constant-sized commitment, so servers agree on the commitment while clients verify the re-encoded block during retrieval.The short commitment replaces AVID-FP's O(N)-sized cross-checksums in server messages.Source: §3.2 · p. 4
- At N = 128, every AVID-M node downloads as much as 1/32 of a block, versus 1.2× the full block for AVID-FP; AVID-M's per-node cost is O(|B|/N+λN).The figure reports N = 128 as the biggest cluster size in the evaluation.Source: Figure 2 · p. 4, §3.2 · p. 4
3.3 AVID-M Protocol
- The client erasure-encodes the block, builds a Merkle tree, and sends each server a chunk with its root and proof; servers exchange GotChunk and Ready messages to complete dispersal.N − f GotChunk announcements establish that at least N − 2f correct servers have received chunks under the root.Source: §3.3 · p. 4
- During retrieval, a client requests chunks, decodes after collecting N − 2f under one root, then re-encodes and checks the root so correct clients return consistent data or the same error string.The re-encoding check addresses differing decodings from different chunk subsets.Source: §3.3 · pp. 5–6
4 DispersedLedger Design
DispersedLedger separates block dispersal and commitment from later retrieval, then uses inter-node linking to recover correct blocks omitted by per-epoch agreement. Its design also specifies correctness guarantees and operational tradeoffs for retrieval, slow nodes, and spam.
4.1 Overview
- Dispersal and agreement proceed without full-block downloads, allowing each node to retrieve blocks lazily and adjust retrieval to its bandwidth.Nodes agree on an ordered log of commitments, while block retrieval can occur concurrently with future proposals and dispersals.Source: §4.1 · p. 6
4.2 Single Epoch Protocol
- BA commits only blocks whose VID has completed; after N−f BA instances output 1, nodes finish the remaining instances and retrieve committed blocks in order.Each epoch assigns one VID and one BA instance to each proposing node.Source: §4.2 · pp. 6–7
4.3 Inter-node Linking
- Inter-node linking uses completed-VID reports in BA-committed blocks to identify and deliver correct blocks omitted by BA, with nodes computing the same delivery set and order.The protocol chooses a conservative reported completion value so linked blocks remain available for retrieval.Source: §4.3 · pp. 7–8
4.4 Correctness of DispersedLedger
- The correctness argument establishes agreement and total order for BA-committed and inter-node-linked blocks, and eventual delivery of correct transactions and blocks.The argument relies on BA agreement and VID correctness and availability properties.Source: §4.4 · p. 8
4.5 Practical Considerations
- Retrieval can run across epochs in parallel while delivery remains serial; designers trade average bandwidth over time T against how far behind nodes may fall.Dispersal traffic is prioritized over retrieval; server-sent spam harms DispersedLedger and HoneyBadger equally, while DL-Coupled proposes empty blocks when retrieval lags.Source: §4.5 · pp. 8–9
- Server-sent spam cannot be filtered before download, while DL-Coupled lets nodes verify transactions before proposing them by using empty blocks when behind.The authors report that the overhead of empty blocks is minor and that DL-Coupled retains most performance benefits.Source: §4.5 · p. 9
5 Implementation
The implementation models DispersedLedger as nested automata and uses connection-level prioritization and adaptive batching to manage network traffic.
Implementation
- The 8,000-line Go implementation composes BA, VID, DLEpoch, and DL automata, using Reed-Solomon coding and embedded key-value storage for blocks and chunks.DLEpoch nests N VID and BA instances; DL combines multiple epochs with inter-node linking.Source: §5 · p. 9
Traffic prioritization
- Two connections per node pair prioritize dispersal over retrieval by making the high-priority connection behave like T connections; the implementation sets T =30.High-priority traffic accounts for 1/20 to 1/10 of handled traffic in most cases.Source: §5 · p. 9
Traffic prioritization and rate control
- Retrieval uses separate QUIC streams and serves the lowest epoch first, while Nagle-based batching proposes blocks after 100 ms or 150 KB accumulates.The implementation uses these thresholds in its evaluation experiments.Source: §5 · pp. 9–10
6 Evaluation
The evaluation compares DispersedLedger (DL) with HoneyBadger (HB) and HoneyBadger-Link across geo-distributed and controlled networks, testing throughput, latency, and scalability. DL improves throughput over HB in the Internet deployment, stays robust to bandwidth fluctuation, and its throughput declines only slightly as cluster size grows.
6.1 Experimental Setup
- AWS EC2 tests used 16-city, unthrottled WAN and controlled 100 ms-delay networks with independently varying ingress and egress bandwidth.Each node ran on a 16-core, 16 GB RAM instance; the controlled setup used Mahimahi and Poisson transaction arrivals.Source: §6.1 · p. 10
6.2 Performance over the Internet
- 105% better average throughput than HoneyBadger on the geo-distributed testbed; Figure 8 reports throughput for each server and protocol.DispersedLedger also achieves 41% better throughput than HoneyBadger with linking.Source: Figure 8 · p. 10, §6.2 · pp. 10–11
- DL-Coupled is 12% slower than DL on average, yet averages 80% and 23% higher throughput than HB and HB-Link, respectively.DL-Coupled limits transaction proposals to nodes up-to-date with retrievals, addressing spamming attacks.Source: §6.2 · p. 11
- As offered load increases from 2 MB/s to 23 MB/s, DispersedLedger median latency increases only from 730 ms to 830 ms; at 6 MB/s, its 99th-percentile latency is 1000 ms across servers.At 6 MB/s, HoneyBadger’s 99th-percentile latency ranges from 1500 ms to 4500 ms. DispersedLedger tail latency at Mumbai and Ohio stays low until very high load.Source: §6.2 · p. 11
6.3 Controlled experiments
- With independent bandwidth variation over time, DL throughput stays the same, while HB and HB-Link throughput drops by 20% and 25%, respectively.Under spatial variation, HB and HB-Link are capped by the fifth-slowest server, while DL throughput at each server is proportional to its available bandwidth.Source: §6.3 · p. 12, Figure 11 · p. 12
6.4 Scalability
- Throughput drops only slightly as cluster size grows eightfold from 16 to 128 nodes; larger blocks improve throughput by amortizing VID and BA costs.Larger blocks also reduce the dispersal-traffic fraction, while increasing cluster size lowers its lower bound.Source: Figure 12 · p. 12, §6.4 · p. 12, Figure 13 · p. 12
7 Conclusion
DispersedLedger decouples agreement from bandwidth-intensive block downloads to provide near-optimal throughput under fluctuating bandwidth. Across a 16-city wide-area deployment, it achieves 2× better throughput and 74% lower latency than HoneyBadger.
7 Conclusion
- DispersedLedger decouples agreement from bandwidth-intensive block downloads and provides near-optimal throughput under fluctuating bandwidth.The prototype was evaluated on two real-Internet testbeds and in a controlled emulated setting.Source: §7 · p. 12
A.1 Latency metric
The section compares confirmation latency counted across all transactions with latency counted only for local transactions. The authors choose the local-only metric because overloaded nodes’ transactions worsen tail latency for non-overloaded HoneyBadger nodes.
A.1 Latency metric
- Counting only local transactions avoids the tail-latency increase that overloaded nodes’ transactions cause for non-overloaded HoneyBadger servers.This effect motivates the authors’ choice of latency metric.Source: §A.1 · p. 14
- DispersedLedger’s median and tail latency are unchanged whether latency counts all transactions or only local transactions.Both systems run near capacity in this comparison.Source: §A.1 · p. 14
- For HoneyBadger, counting all transactions lowers overloaded servers’ median latency but worsens tail latency for non-overloaded servers.The overloaded servers may confirm transactions from other nodes while their own transactions remain uncommitted.Source: §A.1 · p. 14
A.2 Throughput on another testbed over the internet
On the Vultr testbed, DispersedLedger achieves at least 50% higher throughput than HoneyBadger. Figure 15 reports per-server throughput for the compared protocols.
A.2 Throughput on another testbed over the internet
- The Vultr deployment used the $80/month plan with 6 CPU cores, 16 GB RAM, 320 GB SSD, and a 1 Gbps NIC.At the time of the experiment, Vultr had 15 locations across the globe.Source: §A.2 · p. 14
- At least 50% higher throughput over HoneyBadger is reported for DispersedLedger on the Vultr testbed.Figure 15 shows throughput per server.Source: Figure 15 · p. 15, §A.2 · p. 15
- Figure 15 compares per-server throughput for HoneyBadger, HoneyBadger with inter-node linking, and DispersedLedger.The figure caption abbreviates these protocols as HB, HB-Link, and New, respectively.Source: Figure 15 · p. 15
A.3 Example trace of temporal variation
The section identifies Figure 16 as an example synthetic bandwidth trace used in the temporal variation scenario.
A.3 Example trace of temporal variation
- The bandwidth trace is an example input for the temporal variation experiment.The passage identifies it as synthetic.Source: §A.3 · p. 15
- Figure 16 presents an example bandwidth trace used in the temporal variation scenario.The trace is synthetic.Source: Figure 16 · p. 15, §A.3 · p. 15
- Figure 16 is the visual reference for the synthetic trace used in that scenario.The caption and accompanying prose identify the figure and its experimental use.Source: Figure 16 · p. 15, §A.3 · p. 15
B Correctness proof of AVID-M
The AVID-M correctness argument establishes termination, agreement on a common chunk root, and availability of retrievable data. It then shows clients reconstruct the same block, and recover the dispersed block when only one client initiates dispersal.
B Correctness proof of AVID-M
- If one correct client invokes Disperse on a VID instance, all correct servers eventually complete dispersal; the algorithm’s steps eventually finish.The termination condition excludes another client invoking Disperse on that same instance.Source: B Correctness proof of AVID-M · pp. 15–16
- Once any correct server completes, all correct servers eventually complete and set ChunkRoot to the same value.Completion requires 2f + 1 Ready messages, and the proof uses the N ≥ 3f + 1 fault-tolerance condition.Source: B Correctness proof of AVID-M · p. 16
- After completion, a correct client invoking Retrieve eventually reconstructs a block from N−2f valid chunks.At least N−2f correct servers send chunks with valid proofs under the common root.Source: B Correctness proof of AVID-M · p. 16
- Any two correct clients that finish Retrieve set ChunkRoot to the same value.The proof relies on completed servers agreeing on their chunk root.Source: B Correctness proof of AVID-M · pp. 16–17
- For any array of N chunks, either all N−2f-chunk subsets decode to the same block, or re-encoding a decoded subset yields a different Merkle root.This dichotomy lets clients detect an inconsistent encoding.Source: B Correctness proof of AVID-M · p. 17
- Correct clients reconstruct the same block; when one correct client alone invokes Disperse(B), they reconstruct B.If decoding detects inconsistent encoding, clients return the same “BAD_UPLOADER” block.Source: B Correctness proof of AVID-M · pp. 17–18
- In the algorithm, each proposed block includes transactions and an observation of completed prior VID instances.The i-th server invokes Disperse on its block for epoch e.Source: B Correctness proof of AVID-M · p. 18
- Figure 17 marks the inter-node-linking changes to the single-epoch algorithm in blue.The figure’s caption identifies the comparison as the algorithm with versus without inter-node linking.Source: Figure 17 · p. 18
C Specification of the full DispersedLedger protocol with Inter-node Linking
Figure 17 shows how the single-epoch protocol is modified to use inter-node linking.
C Specification of the full DispersedLedger protocol with Inter-node Linking
- Figure 17 marks in blue the additions made to the single-epoch protocol for inter-node linking.The figure describes the protocol modification; blue indicates the added parts.Source: C Specification of the full… · p. 18
D Correctness proof of DispersedLedger
The correctness proof establishes that correct nodes finish epochs, deliver valid blocks, and deliver the same block sequence in the same order. It derives these guarantees from Byzantine agreement and verifiable information dispersal properties.
D Correctness proof of DispersedLedger
- If a correct node includes an index in its selected set, the corresponding VID has completed at some correct node.BA validity implies a correct node invoked Input(1) only after seeing the VID complete.Source: D Correctness proof of DispersedLedger · p. 18
- At least N−f binary-agreement instances eventually Output(1) at all correct nodes.Assuming fewer, the remaining instances can neither Output(0) nor remain unterminated, contradicting BA validity and termination.Source: D Correctness proof of DispersedLedger · pp. 18–19
- Each estimation is bounded above and below by observations made by correct nodes.The proof uses the (f + 1)th-largest observation and the N > 3f condition to rule out estimates beyond correct-node observations.Source: D Correctness proof of DispersedLedger · p. 19
- Every correct node eventually finishes each epoch, so the algorithm is well-defined.The proof proceeds step by step, using eventual BA outputs and completion of required retrieves.Source: D Correctness proof of DispersedLedger · p. 19
- All blocks proposed by correct nodes are eventually delivered by all correct nodes.The proof connects completed dispersal with epoch estimates and the delivery steps.Source: D Correctness proof of DispersedLedger · p. 19
- Two correct nodes deliver the same sequence of blocks, establishing agreement and total order.The proof uses induction across epochs and deterministic retrieval and sorting, including for inter-node linking.Source: D Correctness proof of DispersedLedger · pp. 19–20