An Exposition of Pathfinding Strategies Within Lightning Network Clients

Each LN client, including Lightning Network Daemon (LND), Core Lightning (CLN), Lightning Development Kit (LDK), and Eclair, employs its unique pathfinding strategy, primarily based on variants of the shortest-path algorithm. These strategies are distinguished by their specific weight functions that define the cost of paths, affecting performance outcomes such as fees, path length, routing delays, and reliability of payment delivery. Despite the critical role of these algorithms, there's a notable lack of research aimed at identifying the most optimal client or pathfinding strategy tailored to user-specific preferences, indicating a significant gap in the existing literature.

Pathfinding within the LN involves navigating the network graph using algorithms like Dijkstra’s or modified versions thereof to find a viable path from the sender to the receiver. The complexity of this task is compounded by various constraints imposed to ensure desirable properties of the payment path, such as limiting total fees or achieving a minimum success probability for the transaction. These constraints transform the problem into a constrained shortest-path issue, which is inherently NP-complete, making the search for an optimal solution challenging. The strategies adopted by different LN clients vary, particularly in terms of how they incorporate success probabilities into the total path cost, with some opting for an inverse probability penalization while others use a negative logarithm of the success probability.

The study delves into the empirical performance of different LN client implementations under varying conditions. It introduces a new weight function assumption, termed LND-un, which uses a uniform liquidity distribution for calculating channel-wise success probabilities. This approach, along with others, was tested using a dataset reflecting the LN's structure but without real balance data, relying instead on simulated channel balances chosen according to uniform or bimodal distributions. The findings reveal that LND-un achieves notably high success rates in routing payments, especially for smaller amounts. In contrast, under a bimodal balance distribution, fine-tuning the liquidity broadening scale significantly enhances the success rates of LND-bm, illustrating the potential for optimizing pathfinding performance through adjustments in the estimation of channel liquidity.

The analysis underscores the importance of developing more sophisticated algorithms than the current adaptations of Dijkstra’s algorithm to improve pathfinding efficiency and reliability. It highlights the need for better-designed weight functions that can offer improved trade-offs among key metrics such as payment reliability, routing fees, and other desired properties. Furthermore, the insights from this study suggest avenues for future enhancements not only in single-path pathfinding algorithms but also in multi-part payment pathfinding strategies, which rely on solving minimum cost flow problems—a generalization of shortest path problems. The overall conclusion points towards substantial opportunities for advancements in LN pathfinding strategies, advocating for a more nuanced approach that could significantly benefit both LN developers and users. For further details on this comprehensive analysis, readers are directed to the full study available at https://arxiv.org/pdf/2410.13784.