TL;DR
This paper tackles the financial challenge of participating in payment channel networks (PCNs) like Bitcoin’s Lightning Network. The authors formalize the problem of maximizing a node's routing fee revenue and prove it is NP-hard, then introduce a greedy algorithm that strategically selects channel partners and optimizes fees, outperforming default settings by a factor of four.
What Problem Does This Paper Address?
Payment channel networks are a "Layer 2" solution designed to scale blockchains by allowing users to conduct many transactions off-chain, only settling the final balance on the main blockchain. However, for this to work, participants must "lock up" their coins as collateral in these channels. This creates an opportunity cost: those coins could be used elsewhere.
To compensate for this, nodes charge small fees for routing payments for others. Currently, most users simply stick to "default" fee settings. The authors argue that if we want these networks to be robust and liquid, we need to provide clear financial incentives. They address the question: If I am a node operator with a limited budget, which channels should I open and what fees should I charge to maximize my profit?
Methods
The authors model the PCN as a weighted directed graph where edge weights represent transaction fees. They assume nodes always route payments through the cheapest path.
- Complexity Analysis: They prove that finding the optimal set of channels and fees is NP-hard by reducing it to the "Maximum Betweenness Improvement" (MBI) problem.
- Channel Selection Function (CSF): Since the optimal solution is computationally infeasible, they propose a greedy algorithm. It iteratively adds the channel that provides the highest marginal increase in total expected reward.
- Channel Fee Function (CFF): Choosing the right fee is a balancing act: high fees increase profit per transaction but decrease the likelihood of being chosen for a route. The authors developed a recursive search algorithm that exploits the fact that "edge betweenness centrality" (the fraction of shortest paths passing through an edge) is a monotone decreasing function of the fee. This allows them to prune the search space and find the best fee 10 to 100 times faster than an exhaustive search.
Datasets
The study uses a real-world snapshot of the Bitcoin Lightning Network data obtained from 1ml.com on July 10, 2019.
- Initial Graph: 4,618 nodes and 68,729 edges.
- Filtered Graphs: They created "medium" and "macro" payment graphs (68,697 and 32,193 edges respectively) by removing channels with insufficient capacity for specific transaction sizes.
Key Insights and Ideas
- The Betweenness Connection: Profit is directly tied to "betweenness centrality"—essentially, how often you sit on the "cheapest" path between any two random nodes in the network.
- Strategic vs. Centrality-based Selection: Simply connecting to the most popular nodes (high degree or high Pagerank) isn't the best way to make money. Instead, a node should look for "gaps" where it can provide a new, cheaper shortcut for many pairs of users.
- Fee Monotonicity: The authors observed that as you increase your fee, your "importance" in the network (betweenness) only goes down. This mathematical property is what makes their efficient recursive fee-search algorithm possible.
- Default Fees are Suboptimal: The study confirms that the current "status quo" of using default fees is highly inefficient for individual profit.
Key Results
- Profit Boost: The proposed greedy strategy increased profit by 4x compared to using default fee values.
- Superiority over Heuristics: The strategy performed at least 2x better than other common network strategies, such as connecting to nodes with the highest number of connections (Degree) or the highest Pagerank.
- Efficiency: The recursive CFF algorithm significantly reduces the computational overhead of finding the "sweet spot" for fees, making it practical for real-world node operators.
Limitations and Future Work
- Capacity Ignored: The model assumes that if a channel exists, it has enough liquidity to route the payment. In reality, channels can become "unbalanced" (all funds on one side), causing routing failures.
- Static Environment: The evaluation assumes other nodes don't change their fees in response to your strategy. A more realistic model would involve a game-theoretical framework where multiple rational nodes compete for routing traffic.
- Transaction Distribution: The authors assumed all pairs of nodes are equally likely to trade. Future work could use more sophisticated models of how money actually flows through the network.
Summary updated