PaperlayerView exact revision on arXiv

Source-linked AI summary

High Throughput Cryptocurrency Routing in Payment Channel Networks

Vibhaalakshmi Sivaraman, Shaileshh Bojja Venkatakrishnan, Kathy Ruan, Parimarjan Negi, Lei Yang, Radhika Mittal, Mohammad Alizadeh, Giulia Fanti

arXiv:1809.05088v5cs.NI

TL;DR

PCNs face throughput limits because payments require sufficiently funded paths and one-way flows deplete channel balances, while atomic routing makes large transfers harder to complete. Spider packetizes transactions and applies multipath congestion control to balance channel use. It routes over 95% of balanced-demand transactions using less than 25% of LND’s required capacity and supports 4x more transactions than the state of the art on imbalanced demands.

  • Problem

    PCN throughput is limited by insufficiently funded routes, directional channel depletion, and atomic payment routing.

  • Method

    Spider splits transactions into independently routed units and uses multipath congestion control to balance channel utilization over paths and time.

  • Results

    Spider achieves nearly 100% throughput on circulation demands and supports 4x more transactions than the state of the art on the PCN under DAG demands.

  • Takeaways & Limitations

    Spider reduces reliance on on-chain intervention for deadlocked PCNs while maintaining high throughput across circulation and imbalanced demands.

  • Takeaways & Limitations

    Spider relies on correct router queue-buildup signaling, while incentive compatibility for rogue routers and privacy implications of queue-delay relaying remain unanalyzed.

Abstract

from arXiv · show

Despite growing adoption of cryptocurrencies, making fast payments at scale remains a challenge. Payment channel networks (PCNs) such as the Lightning Network have emerged as a viable scaling solution. However, completing payments on PCNs is challenging: payments must be routed on paths with sufficient funds. As payments flow over a single channel (link) in the same direction, the channel eventually becomes depleted and cannot support further payments in that direction; hence, naive routing schemes like shortest-path routing can deplete key payment channels and paralyze the system. Today's PCNs also route payments atomically, worsening the problem. In this paper, we present Spider, a routing solution that "packetizes" transactions and uses a multi-path transport protocol to achieve high-throughput routing in PCNs. Packetization allows Spider to complete even large transactions on low-capacity payment channels over time, while the multi-path congestion control protocol ensures balanced utilization of channels and fairness across flows. Extensive simulations comparing Spider with state-of-the-art approaches shows that Spider requires less than 25% of the funds to successfully route over 95% of transactions on balanced traffic demands, and offloads 4x more transactions onto the PCN on imbalanced demands.

1 Introduction

Cryptocurrency scalability remains limited, motivating payment channel networks that enable off-chain transfers but require careful routing to sustain throughput. Spider addresses these challenges by packetizing payments and using multipath congestion control to balance channels and improve routing performance.

  • Bitcoin processes 7 transactions per second and Ethereum 15 transactions/second, compared with VISA’s 1,700 transactions per second.
  • Payment channel networks route transactions through intermediaries without requiring blockchain consensus for every transaction.Bitcoin’s Lightning Network and Ethereum’s Raiden are examples of PCNs.
  • High transaction throughput is necessary for routers to offset collateral opportunity costs and provide an appealing payment service.A payment succeeds only when every channel on its route has sufficient funds.
  • Existing routing protocols reduce throughput by atomically routing complete transactions and failing when no sufficiently funded path exists, while also allowing channels to become imbalanced.
  • Spider packetizes transactions across paths and time, then uses one-bit congestion signals to adjust outstanding transaction-units and promote balanced channel use.Its congestion-control design is adapted to payment channels, whose usable capacity depends on directional fund flows.
  • Spider’s contributions include formalizing balanced routing, designing a packet-switched architecture and multipath transport protocol, and validating the design through simulation and an LND implementation.

2 Background

Payment channels escrow funds for private bilateral transfers, while payment channel networks connect non-neighboring users through intermediary relays. Their operation depends on bidirectional balances, funded paths, and cryptographic settlement mechanisms.

  • A bidirectional payment channel lets Alice and Bob exchange funds using signed balance messages before optionally settling the latest state on-chain.Opening the channel requires a jointly created transaction that escrows funds for a fixed time.
  • A payment-channel route must have sufficient funds on every channel, so only the path through Charlie can support the illustrated 3-token transfer.
  • Payment channel networks route transfers through intermediate nodes that relay payments and receive routing fees.A cryptographic hash lock ensures intermediate transfers become valid only after the recipient knows a private key.
  • Hashed Timelock Contracts secure routed payments, with Spider assuming the sender generates the secret key.

3 Challenges in Payment Channel Networks

PCN throughput is constrained by route concentration, directional channel imbalance, atomic sending, and deadlocks. Packetization helps address atomicity, but effective throughput also requires time multiplexing and congestion control.

  • Shortest-path routing can concentrate traffic on one channel while leaving alternate channels under-utilized.In the illustrated topology, both directions use channel c, congesting it while channels a and b carry less traffic.
  • Directional fund flow eventually exhausts a channel’s usable balance, forcing costly and slow on-chain replenishment before payments can continue.Balanced routing instead divides traffic across directions to prevent channel imbalance.
  • Most PCNs send transactions instantaneously and atomically, so a transaction fails when no complete path has enough available balance.
  • Packetization splits payments into smaller units multiplexed across paths and time, but independent completion and congestion control are needed for throughput gains.Simply splitting units that must all complete together does not sufficiently improve success under contention.
  • DAG-like payment patterns can create deadlocks in which an intermediary’s depleted balance prevents otherwise feasible transfers between endpoints.
  • Routing, rate control, and deadlock effects are intertwined, so packet switching alone provides limited benefit without corresponding routing and rate-control mechanisms.
  • PCN channel capacity depends on reverse-direction transaction rates because sustained one-way flow requires regular fund replenishment.

4 Packet-Switched PCN

Spider uses packet switching to divide payments into independently routed units and queues them at routers when channels temporarily lack forwarding funds. This lets later incoming funds release queued units instead of immediately failing the transaction.

  • Spider splits each transaction into independently routed transaction-units bounded by a maximum-transaction-unit value.The units can be sent over different paths and at different times.
  • Spider routers queue transaction-units when a channel lacks funds and forward them as funds arrive from the opposite side.This differs from current PCN implementations, where a transaction fails immediately when it cannot be forwarded.

5 Modeling Routing

This section models PCN routing as a utility-maximization problem constrained by channel capacity and balance. It shows that circulation demands can be routed efficiently, whereas DAG demands cannot be balanced indefinitely without replenishment, and describes a decentralized price-based algorithm with practical challenges.

  • 5 Modeling Routing: PCN routing seeks high aggregate throughput and fair allocation while keeping latency below that of on-chain transactions.The model assumes the underlying communication network is not the bottleneck.
  • 5 Modeling Routing: Channel capacity limits flow according to escrowed funds and confirmation latency, while mismatched directional rates eventually exhaust usable funds.If x_u,v exceeds x_v,u over time, funds accumulate at v and the u-to-v direction becomes unusable.
  • 5 Modeling Routing: Logarithmic source utility yields proportionally fair rate allocations that prevent any individual sender’s payments from being completely throttled.The optimization maximizes overall utility subject to the routing constraints.
  • 5.1 Implications for Throughput: Circulation demands can be routed efficiently, but DAG demands cannot be balanced indefinitely without periodic replenishment of channel credits.The circulation component can be routed when capacity is sufficient, whereas the DAG component shifts tokens until a channel becomes unusable.
  • 5.2 Design: The decentralized algorithm updates channel prices from congestion, imbalance, arrival rates, available balance, and queued transaction-units, then uses path prices to adjust sender rates.Price variables represent capacity and imbalance constraints, and end-hosts adapt path rates using the resulting prices.
  • 5.2.3 Challenges: The price-based approach may converge slowly, require coordination between both routers, be sensitive to parameters, and create bursts without windows and active queue control.These practical difficulties motivate the later design based on windows and queue control.

6 Design

Spider packetizes payments, queues transaction-units when channels lack funds, and uses multipath congestion control to balance utilization across paths. Routers mark delayed packets, while senders adjust per-path windows and can cancel incomplete payments by deadline.

  • 6 Design: Spider queues transaction-units when a channel lacks funds, revealing either capacity overload or directional imbalance.Queue growth indicates that a capacity or balance constraint is being violated.
  • 6.1 Intuition: Congestion control throttles both directions under capacity overload and reduces the faster direction under imbalance until queued funds drain.In the imbalanced case, the higher arrival rate is reduced to match the rate at which new funds become available.
  • 6.1 Intuition: Routers mark packets whose queue delay exceeds threshold T, and senders adjust path windows using marked acknowledgments.Routers preserve an existing mark and forward acknowledgments so end-hosts can interpret congestion feedback.
  • 6 Design: Spider combines packetized non-atomic payments with multipath routing so large payments can be delivered as independently routed transaction-units.Senders choose a set of k paths, and each transaction-unit is assigned a route before transmission.
  • 6.2 End-host Design: End-hosts maintain a window w_p for each path and transmit a new transaction-unit only when that path’s pending units do not exceed its window.The windows bound outstanding transaction-units separately on candidate paths.
  • 6 Design: If a payment misses its application deadline, the sender cancels it and removes queued transaction-units from paths to the receiver.Transaction-units that already arrive cannot be unlocked because the sender retains the secret key.
  • 6.4 Analysis: Under a fluid approximation, Spider’s converged rates satisfy the optimization problem’s KKT conditions and are optimal for parallel networks.The result maps converged flow rates and marking fractions to the optimization problem’s primal and dual variables.

7 Evaluation

Spider is evaluated through simulation and prototype validation across synthetic and Lightning Network topologies, traffic patterns, and routing designs. It generally improves throughput and success ratio, but DAG demand can induce persistent deadlocks.

  • Experimental Setup: The evaluation combines an event-based PCN simulator, prototype validation, three topologies, circulation demands, DAG mixtures, and design-choice experiments.The simulator models endhosts, routers, messages, channel balances, and routing decisions; the prototype validates simulator results against LND and Spider.
  • Circulation Payment Graph Performance: Spider routes more than 95% of circulation transactions using less than 25% of the capacity required by LND.At lower capacities, Spider completes 2–3× more transactions than LND by responding to queue buildup and maintaining channel balance.
  • Transaction Size Effects: Spider’s largest transactions incur at most 2 seconds of additional delay versus LND, alongside a 20% increase in overall success ratio at mean channel size 16880e.LND latency also rises because it retries transactions, whereas Spider reuses capacity from smaller channels over time.
  • Effect of DAGs: Adding DAG demand prevents schemes from reaching the theoretical circulation-throughput bound and can leave circulation throughput below 100% after DAG traffic is removed.The experiments vary DAG demand from 5% to 40%; in scale-free and Lightning topologies, the DAG causes a persistent deadlock.
  • Effect of DAGs: With rebalancing, Spider achieves 90% success ratio when routers rebalance every 10,000e routed, while LND remains below 85% even at every 10e.The reported Spider operating point corresponds to roughly one on-chain transaction costing under 1e per 10,000e routed.
  • Spider’s Design Choices: Using edge-disjoint widest paths improves Lightning-topology results by 1–10% over other approaches, while increasing Spider from 4 to 8 paths yields less than 5% additional success ratio.Moving from 1 to 2 paths improves success ratio by 30–50%; sparse topologies usually provide only 5–6 edge-disjoint widest paths.
  • Additional Results: Additional experiments report a 2× success-ratio advantage over Celer, more than 95% success with equal channel capacities, fairness for small payments, and high throughput with infrequent rebalancing.These results are reported for supplementary synthetic and real-topology evaluations.

8 Related Work

Prior PCN work addresses routing through max-flow, landmark, embedding, and channel-rebalancing approaches, while Spider combines routing with congestion-control ideas to improve throughput.

  • Routing approaches: Max-flow alternatives are impractical for the Lightning Network because of its scale, while modified max-flow methods account for transaction size.The cited passage identifies over 5,000 nodes and 30,000 channels as the relevant scale constraint.
  • Routing approaches: Landmark routing centralizes routing tables at selected routers, whereas embedding-based routing forwards transactions toward neighbors closest to the destination’s embedding.Flare and SilentWhispers use landmark routing; VOUTE and SpeedyMurmurs use embeddings.
  • Routing approaches: Dynamic computation and updating of node embeddings as topology and link balances change is a primary challenge for embedding-based routing.The cited passage also reports that Spider outperforms landmark and embedding-based approaches in the authors’ experiments and prior work.
  • Rebalancing and congestion control: Channel-rebalancing techniques such as Revive are complementary to Spider, but independently rebalancing funds at routers does not achieve high throughput without balanced routing.The passage connects these approaches to broader congestion-control and network utility maximization ideas.
  • Rebalancing and congestion control: Spider applies congestion-control ideas from data networks to payment channels whose capacities depend on the input rates themselves.This distinguishes the PCN setting from Internet congestion-control work focused on relatively stable link capacities.

9 Conclusion

The paper presents Spider as a balanced, high-throughput PCN routing protocol and reports strong performance on circulation and DAG-containing demands. It also identifies unresolved deadlock-prevention, incentive, and privacy questions.

  • Conclusion: Spider combines packet switching, multi-path congestion control, and in-network scheduling for balanced, high-throughput PCN routing.The conclusion states that Spider achieves nearly 100% throughput on circulation payment demands across synthetic and real topologies.
  • Conclusion: Spider achieves nearly 100% throughput on circulation payment demands across synthetic and real topologies.The result is reported for both synthetic and real network topologies.
  • Conclusion: 4x more transactions can remain on the PCN under DAG-payment scenarios than with the state-of-the-art approach.The conclusion attributes these scenarios to deadlocks that degrade circulation throughput and require on-chain intervention.
  • Limitations: The work does not establish whether deadlocks can be prevented altogether, and it leaves rogue-router incentive compatibility and privacy implications for future work.Spider relies on routers signaling queue buildup correctly, while the paper does not analyze fee-maximizing rogue routers or rigorously treat privacy.

Appendices

The appendices define circulation-based throughput bounds and describe a fluid approximation of Spider’s queues, marking dynamics, and service rates. The model is used for intuition and subsequent optimality analysis under simplifying assumptions.

  • Circulations and throughput bounds: A payment graph assigns each directed demand edge its average requested transfer rate, while a circulation graph preserves bounded demands and equal incoming and outgoing weight at each node.A maximum circulation graph need not be unique for a given payment graph.
  • Circulations and throughput bounds: A balanced routing scheme reaches maximum circulation demand ν(C*) when every payment channel has at least ν(C*) escrowed units, and cannot exceed that throughput.This proposition provides both an achievability condition and an upper bound.
  • Fluid model: The fluid model tracks path flow rates, queue sizes, marked-packet fractions, incoming rates, and service rates as real-valued variables.For path p, x_p(t) is its flow rate; for channel (u,v), q_u,v(t) is queue size, f_u,v(t) the marked fraction, x_u,v(t) incoming flow, and y_u,v(t) service rate.
  • Fluid model: Spider increases a path’s rate after successful acknowledgements and decreases it when packets are marked, with the rate constrained to remain nonnegative.The cited passages describe aggregate marking along a path and the resulting rate adjustment.
  • Fluid model: Queue size grows with incoming rate minus service rate, while packet marking increases when queue size exceeds threshold q_thresh.Equations (13) and (14) model these two dynamics at routers.
  • Fluid model: The model approximates service rates on opposite directions of a channel as equal and makes them depend on arrival rates and current queue occupancies.The approximation is expressed as y_u,v = y_v,u, with the precise service rate determined by both endpoint queues.
  • Fluid model: The fluid model omits delays and uses simplifying approximations, so it is presented as a tool for first-order intuition rather than a complete dynamics model.The following analysis uses it to show optimal rate allocations for a parallel topology.

B.2 Proof of Optimality

The proof analyzes Spider on a parallel bidirectional topology using a converged fluid model. It shows that equilibrium rates satisfy feasibility, balance, complementary slackness, and optimality conditions.

  • Network model: The proof considers k parallel payment channels connecting two sets of end-hosts with cross-set demands and paired paths traversing opposite channel directions.The topology is illustrated as a parallel network with bidirectional flows.
  • Equilibrium analysis: Assuming convergence, steady-state path-flow and queue-growth derivatives are non-positive in the parallel-network fluid model.The converged path rates are denoted by x*_p.
  • Feasibility and balance: At equilibrium, Spider’s rates satisfy channel capacity and balance constraints because queues on used paths remain non-empty and opposite service rates are equal.The argument uses the queue dynamics and the approximation y_u,v(t) = y_v,u(t).
  • Optimality conditions: The equilibrium rates produced by Spider are feasible for the routing optimization problem and induce feasible dual variables through the marking fractions.Nonnegative marking fractions imply nonnegative dual variables associated with channel-capacity constraints.
  • Optimality conditions: Spider’s equilibrium rates satisfy complementary slackness and the primal optimality condition, so the parallel-topology equilibrium is optimal.The proof concludes that the equilibrium rates and mapped dual variables are optimal primal and dual solutions.
  • Conclusion: The proof concludes that Spider finds optimal equilibrium rates for the parallel network topology.This is the stated result of the optimality argument.

C Primal-Dual Algorithm Derivation

The primal-dual algorithm assigns prices to channel capacity and directional imbalance, then iteratively updates path rates and channel prices. Spider estimates demand-capacity gaps from observable arrivals, service rates, and pending funds so routers can update capacity prices without directly estimating transaction delay.

  • Primal-dual updates: The partial Lagrangian decomposes into separate path-rate terms, motivating an iterative primal-dual algorithm for the fluid-model LP.Path prices combine channel prices, and senders update rates on their available paths.
  • Router operation: Spider’s router queueing process schedules transaction units across a channel according to available capacity and transaction priorities.Funds received remain pending until the final receiver supplies the hashlock key.
  • Convergence: Small enough step sizes make the decentralized algorithm converge to the LP’s optimal solution.The positive parameters α, η, and κ determine the convergence rate.
  • Primal-dual updates: Channel prices encode capacity pressure and directional imbalance: λ rises when aggregate load exceeds capacity, while µ tracks directional-rate asymmetry.λ corresponds to capacity constraints, whereas µ(u,v) and µ(v,u) correspond to directional imbalance constraints.
  • Demand-capacity estimation: Routers estimate the demand-capacity gap without first estimating the average delay required for transactions and hashlock keys to traverse a channel.The substitute quantity is a scaled form of the delay-dependent expression but can be estimated directly.
  • Demand-capacity estimation: Pending funds and service rates estimate the additional escrow required to support current arrival rates, while a queue term keeps queue sizes small.The estimate combines both channel directions and subtracts the channel’s escrowed funds; the β min(q_u(t), q_v(t)) term controls queues.
  • Empirical comparison: Spider achieves a 2x success-ratio improvement over Celer even at Celer’s peak performance in the 10-node scale-free experiment.Celer’s success declines after its peak because larger queues at higher capacities eventually cause timeouts.

E Additional Results

Across circulation experiments, Spider outperforms the compared schemes in success ratio, including for large transactions, while maintaining high and more evenly distributed flow throughput.

  • Success ratio: Spider outperforms state-of-the-art schemes in success ratio across all evaluated topologies.The experiments use five circulation traffic matrices on three topologies with equal channel sizes.
  • Success ratio: More than 95% of transactions succeed with less than 25% of the capacity required by LND.This result is reported across the three evaluated topologies.
  • Transaction size: Spider completes nearly 50% more of the largest 12.5% of attempted transactions across all three topologies.The transaction-size breakdown uses intervals corresponding roughly to 12.5% portions of the transaction-size CDF.
  • Fairness: Spider achieves close to 100% throughput across the evaluated scenarios and is fairer to small flows than LND.Its throughput distribution is more vertical, indicating that small flows are not sacrificed to improve aggregate throughput.

E.4 DAG Workload on Synthetic Topologies

Adding a DAG component to demand moves achieved throughput farther from the optimal circulation throughput, whereas proactive rebalancing lets Spider sustain high performance under a 20% DAG workload.

  • DAG workload: No scheme achieves maximum throughput when DAG demand is added, and performance is closer to maximum when the DAG component is smaller.The evaluated DAG components are 5%, 20%, and 40% of demand.
  • Proactive rebalancing: With rebalancing enabled for the 20% DAG workload, Spider exceeds 95% success ratio and 90% normalized throughput when routers rebalance every 10,000 e.LND never sustains more than 75% success ratio even when rebalancing every 10 e routed.
  • Proactive rebalancing: Spider’s performance under the 20% DAG workload indicates that fewer on-chain rebalancing events can sustain high throughput and routing-fee generation.The reported implication concerns both routers locking funds in channels and end users routing through them.
  • DAG workload: As the DAG component increases, normalized throughput moves farther from expected optimal circulation throughput, with a larger gap on the real topology.The figure compares algorithms across topologies while varying the DAG component in the demand matrix.
Loading 1809.05088v5…