Improving Lightning Network Pathfinding Latency by Path Splicing and Other Real-Time Strategy Game Techniques

Summary:

The Lightning Network faces the challenge of pathfinding, which involves finding the most efficient route for a payment to travel through the network. One issue is the significant amount of time taken for mainnet Lightning nodes to find a route between themselves and an arbitrary payee node due to the pathfinding algorithm. To solve this problem, the `permuteroute` algorithm was introduced, limiting its search space to within 3 hops, equivalent to searching the friend-of-friend network, to quickly get a route or a failure indication. Pathfinding on Lightning requires a "good enough" path, not necessarily the most optimal path, and needs to look for paths in a large map in a very short time. To improve latency, the article suggests using techniques used in real-time strategy games, such as A* algorithm, double-buffering, and flocking system. However, using A* is not possible under Lightning unless we have pre-computed and cached data, and the cached data may become stale if the channel topology changes. Another approach is using high-level "rough" maps to find trampoline routes, where a payment hops between nodes on the rough map to reach its destination. Tr\*sted servers can provide rough maps for nodes with limited storage capacity, or self-serving nodes can generate their own rough maps by running both a limited-smooth-map node and a server. Myopic trampoline nodes that do not have complete smooth-level routemaps can allow for a wider distribution of trampoline nodes. Finally, the article introduces the concept of flocking, which involves grouping payments together to reduce the number of pathfinding requests made by individual payments.Lightning Network does not need to pioneer any new research into pathfinding. Shortcuts, techniques, and optimizations used in real-time strategy games deserve closer examination as potential points of inspiration for similar techniques for Lightning. There are potentially many more techniques whose ideas might be possible to adapt in finding Lightning Network routes in large public networks in short amounts of time with acceptable fees and locktimes.

Updated on: 2023-06-02T19:41:36.179295+00:00