Source-linked AI summary
Flash: Efficient Dynamic Routing for Offchain Networks
Peng Wang, Hong Xu, Xin Jin, Tao Wang
TL;DR
Offchain routing must handle changing channel balances, while finding optimal paths can require probing for every payment. Flash uses different routing strategies for large and small payments, and improves network throughput by up to 2.3x compared with the state-of-the-art routing algorithm.
Problem
Dynamic routing must account for changing channel balances, but seeking optimal paths can require probing for every payment.
Source: §1 · p. 1Method
Flash uses modified max-flow routing to find capacity-sufficient paths for elephant payments and routes mice over a few previously computed paths.
Source: §1 · p. 2Results
Flash improves network throughput by up to 2.3x compared with the state-of-the-art routing algorithm.
Source: §1 · p. 2Takeaways & Limitations
Flash significantly outperforms existing solutions especially on success volume while maintaining low probing overhead.
Source: §7 · p. 13Flash assumes atomic multipath payments, whose mechanism design and implementation are beyond this paper.
Source: §3.1 · p. 5
Abstract
from arXiv · showhide
Offchain networks emerge as a promising solution to address the scalability challenge of blockchain. Participants directly make payments through a network of payment channels without the overhead of committing onchain transactions. Routing is critical to the performance of offchain networks. Existing solutions use either static routing with poor performance or dynamic routing with high overhead to obtain the dynamic channel balance information. In this paper, we propose Flash, a new dynamic routing solution that leverages the unique characteristics of transactions in offchain networks to strike a better tradeoff between path optimality and probing overhead. By studying the traces of real offchain networks, we find that the payment sizes are heavy-tailed, and most payments are highly recurrent. Flash thus differentiates the treatment of elephant payments from mice payments. It uses a modified max-flow algorithm for elephant payments to find paths with sufficient capacity, and strategically routes the payment across paths to minimize the transaction fees. Mice payments are directly sent by looking up a routing table with a few precomputed paths to reduce probing overhead. Testbed experiments and data-driven simulations show that Flash improves the success volume of payments by up to 2.3x compared to the state-of-the-art routing algorithm.
1 INTRODUCTION
Blockchain’s scalability limits motivate offchain networks, where routing must account for channel balances that change with each payment. Flash uses different routing strategies for large and small payments to balance path quality against probing overhead.
1 INTRODUCTION
- Offchain networks move payments through payment channels without committing every transaction to the blockchain, addressing blockchain’s scalability challenge.Blockchain scalability is limited by the bandwidth and processing needed to replicate state changes among participants.Source: §1 · p. 1
- Dynamic routing trades path optimality against probing overhead because channel balances change after each payment, potentially requiring a probe for every transaction.Offchain channels’ changing balances distinguish them from computer-network links with static capacity.Source: §1 · pp. 1–2
- Fewer than 10% of transactions contribute over 94% of transaction volume, and over 80% occur between existing participant pairs within 24 hours.These trace findings identify both elephant payments and recurring pairs that can reuse existing paths.Source: §1 · p. 2
- Flash probes candidate paths with a modified max-flow algorithm for elephant payments, distributing them to minimize fees, while mice use previously computed paths.Payments can be split across paths when needed.Source: §1 · p. 2
- Flash improves network throughput by up to 2.3x compared with the state-of-the-art routing algorithm in testbed experiments and trace-driven simulations.The paper also reports implementing a prototype of Flash.Source: §1 · p. 2
2 BACKGROUND AND MOTIVATION
Offchain networks route payments through payment channels, including indirect paths whose capacity is limited by their tightest channel balance. Measurements of Ripple and Bitcoin transactions reveal heavy-tailed payment sizes and recurring pairs, motivating differentiated routing and reuse of existing paths.
2.1 A Primer on Offchain Networks
- Payment channels support repeated off-chain payments between two parties, while a multi-hop payment requires a directed path with enough balance on every channel.HTLCs ensure either all channel balances on the path update or none do.Source: §2.1 · p. 3
2.2 Motivation
- The measurement study analyzes over 2.6 million Ripple transactions from 2013–2016 and over 103 million Bitcoin transactions from 2009–2018.Ripple is the only offchain network whose transaction data the authors report as publicly available.Source: §2.2 · p. 4
- Payment sizes are heavy-tailed: in Ripple, nearly 94.5% of volume comes from 10% of payments, while in Bitcoin, 10% contribute 94.7%.The median payment sizes are $4.8 USD for Ripple and 1.293 × 10^6 satoshis for Bitcoin.Source: §2.2 · p. 4
- Across Ripple’s 1306-day trace, the median daily share of recurring transactions is 86%, and each user’s top five recurring payments account for over 70% of daily transactions.Recurring transactions are defined by the same sender–receiver pair within a 24-hour period.Source: §2.2 · pp. 4–5
- A small routing table can store paths to recurring receivers, simplifying mice-payment path finding to lookups and reducing probing overhead.The authors motivate separate routing treatment: mice can reuse paths, while large payments warrant careful path selection and fee-aware scheduling.Source: §2.2 · pp. 4–5
3 DESIGN
Flash is a distributed online routing system that treats large and small payments differently to balance path quality against probing overhead. It assumes locally available network topology and atomic multipath payments, then uses capacity-aware routing for elephant payments and a lightweight routing table for mice.
3 DESIGN
- Flash processes payments online, using separate routing strategies for elephant and mice payments to balance performance and probing overhead.Elephant payments use capacity-aware path finding and fee-minimizing allocation; mice payments use precomputed paths and probe only when needed.Source: §3 · p. 5
3.1 Prerequisites
- Flash assumes each node locally stores and periodically updates network topology, and that multipath payments are atomic.The topology includes channel connectivity but not balances; atomicity ensures the receiver gets all partial payments or none.Source: §3.1 · p. 5
3.2 Routing Elephant Payments
- Flash adapts Edmonds-Karp to find and probe at most k paths sequentially, using probed channel capacities to estimate their flow.The algorithm uses breadth-first search over residual capacities and can stop when the found flow satisfies the payment demand; limiting the search to k paths reduces probing overhead compared with Edmonds-Karp’s O(|V||E|) iterations.Source: §3.2 · pp. 6–7
- For elephant payments, Flash allocates demand across feasible paths by minimizing total fees subject to demand and channel-capacity constraints.The objective is convex under the assumed convex fee functions; typical linear fees make it a linear program that standard solvers can handle quickly.Source: §3.2 · p. 7
3.3 Routing Mice Payments
- For mice payments, Flash reuses a few precomputed shortest paths from a routing table and randomly tries paths, probing only when needed.The table is recomputed when topology updates, and the evaluation uses m = 4 paths; at most m paths are probed before an unsatisfied payment fails.Source: §3.3 · p. 7
4 SIMULATION
The simulation evaluates Flash on Ripple and Lightning topologies under varying network capacities and transaction loads. Flash combines elephant-payment routing across capacity-sufficient paths with a few precomputed paths for mice, aiming to balance payment performance and probing overhead.
4.2 Overall Performance and Overhead
- Flash’s success volume is up to 4.5x higher than Shortest Path, 5x higher than SpeedyMurmurs, and 2.3x higher than Spider across Ripple and Lightning.Its success ratio is about 20% better than Shortest Path and SpeedyMurmurs; Flash and Spider perform similarly on this metric.Source: Figure 6 · p. 8, §4.2 · p. 9
- With more transactions, Flash’s success-volume gains reach 4.7x over Shortest Path, 6.6x over SpeedyMurmurs, and 2.6x over Spider.All schemes’ success ratios degrade as transaction volume rises; Flash’s gains increase with load.Source: Figure 7 · p. 8, §4.2 · p. 9
4.1 Methodology
- The simulation uses Ripple and Lightning topologies, sampled transaction volumes and sender-receiver pairs, and compares Flash with Spider, SpeedyMurmurs, and Shortest Path.Flash uses m = 4 paths for mice and k = 20 for elephants by default; success ratio, success volume, and probing messages are averaged over five runs.Source: §4.1 · p. 8
4.2 Overall Performance and Overhead
- Flash saves 43% of probing messages in Ripple and 37% in Lightning compared with Spider.Flash uses at most four paths for most mice payments and probes another path only when the payment cannot be delivered in full.Source: Figure 8 · p. 9, §4.2 · p. 9
4.3 Flash Microbenchmarks
- Flash reduces average transaction cost by around 40% in Ripple and Lightning compared with routing without fee minimization.The comparison uses unit fees across all payments, with fees assigned randomly to channels.Source: Figure 9 · p. 9, §4.3 · pp. 9–10
- Success volume for mice payments stays stable until mice account for 80%–90% of payments, supporting a threshold set at 90%.Treating more payments as mice reduces probing overhead, with only marginally lower mice success volume in that range.Source: Figure 10 · p. 10, §4.3 · p. 10
- With six precomputed paths per receiver, mice-routing success volume is within 15% of the m = 0 upper bound, with at least ∼12x less probing overhead.Performance stabilizes when m exceeds 6; the reported trend uses the Ripple trace, with similar trends in Lightning.Source: Figure 11 · p. 10, §4.3 · p. 10
5 TESTBED EVALUATION
The testbed evaluates a simplified Golang prototype on two Watts–Strogatz topologies with 50 and 100 nodes. Flash delivers greater success volume than Spider and shorter processing delays, while its success ratio is lower than Spider’s.
5.1 Implementation
- The prototype implements source routing, probing, and atomic payment processing, using a two-phase commit to finalize a multipath payment only when all sub-payments succeed.It is a simplified Golang system using TCP and omits topology-gossip mechanisms and HTLC security.Source: §5.1 · pp. 10–11
5.3 Results
- Flash’s success volume is 42.5% and 34.4% higher than Spider’s on average in the 50-node and 100-node topologies, respectively.Flash’s success ratio is 5.6% and 8.8% lower than Spider’s, but 36.3% and 14.8% higher than Shortest Path’s, respectively.Source: Figure 12 · p. 11, Figure 13 · p. 11, §5.3 · p. 12
- Flash’s average processing delay is 19.4% and 19.2% smaller than Spider’s in the 50-node and 100-node topologies, respectively.For mice payments, Flash is 26.4% and 26% faster than Spider in those topologies.Source: Figure 12 · p. 11, Figure 13 · p. 11, §5.3 · p. 12
5.2 Experiment Setup
- The testbed uses 50- and 100-node Watts–Strogatz graphs, 10,000 Ripple-trace-sized transactions, and five independent runs per scheme.Flash uses a threshold classifying 90% of transactions as mice, k = 20 elephant paths, and m = 4 mice paths; results use min-mean-max bars.Source: §5.2 · p. 12
6 RELATED WORK
Prior offchain routing includes static path-finding approaches and centralized dynamic algorithms. Flash differentiates elephant and mice payments, balancing path optimality against probing overhead while accounting for offchain and data-center network differences.
6 RELATED WORK
- The Lightning design draft uses a BGP-like system with a global routing table; Flare limits local neighbor state and exchanges neighbor information to construct paths.Flare also supplements its network view with randomly selected beacon nodes.Source: §6 · p. 12
- SilentWhispers routes through landmarks, which can lengthen paths, while SpeedyMurmurs uses node coordinates to find shortcuts that reduce average path lengths.Source: §6 · p. 12
- Revive and Spider account for dynamic channel balances with centralized offline routing, but centralized schemes have high probing overhead and do not work for decentralized offchain networks.Source: §6 · p. 12
- Flash differentiates elephant and mice payments to balance path optimality against probing overhead, while noting that offchain networks differ from data-center networks in topology and channel-balance dynamics.The paper identifies congestion-aware load balancing and fine-grained routing as potential sources of insight for offchain routing.Source: §6 · p. 12
7 CONCLUSION
Flash uses payment characteristics observed in real offchain networks to route elephant and mice payments differently. Trace-driven simulations and a prototype show improved performance, especially in success volume, with low probing overhead.
7 CONCLUSION
- Flash significantly outperforms existing solutions, especially on success volume, while maintaining low probing overhead.Source: §7 · p. 13
- Real offchain-network traces show that payment sizes are heavy-tailed and most payments recur; Flash treats elephant and mice payments differently.Source: §7 · p. 13
- Flash uses a modified max-flow algorithm to find sufficient path capacity for elephant payments and a routing table of a few shortest paths for mice payments.The mice-payment routing table reduces probing overhead.Source: §7 · p. 13