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

Summary:

A recent discovery has shown that the current Lightning Network pathfinding search algorithms are not sufficient for the size of the network, as Lightning nodes take too much time to find a route between themselves and an arbitrary payee node. To address this issue, an alternative algorithm called `permuteroute` is proposed, which is faster due to not having to scan a large number of channels. This algorithm would be helpful in supporting JIT-Routing nodes while there are still few JIT-Routing nodes.However, most of the public channels in the network today are underutilized, with capital largely being over-allocated. Based on active network analysis, only a few hundred nodes are actively managing their channels effectively, allowing them to be effective routing nodes. Engineers should focus on low hanging engineering fruits and incremental algorithmic updates rather than getting distracted by distant ideas.The latest version of the software has moved beyond rudimentary time-based edge/node pruning in response to failures. It factors in past pathfinding attempts into its central "mission control," allowing it to learn from each attempt and even import existing state into its pathfinding memory. JIT-Routing is still strictly superior to permuteroute, as the node reporting the failure has more information about local conditions. However, permuteroute gets immediate benefits to the node that upgrades to utilize it.To speed up payment routing to arbitrary nodes, a new `getroutequick` command can be implemented that uses the cached Dijkstra data for finding acceptable routes from the destination node to the source node. A* algorithm can also be used on Lightning if we have precomputed and cached the costs from a node to all other nodes. If the channel topology remains unchanged, A* can run very quickly. However, if the topology changes, the cached data may become stale and require recalculation.In Lightning Network, when a hop fails and the node with that channel does not itself do JIT-Routing, permuteroute can prevent it from being in the known-successful prefix. Pathfinding on Lightning has requirements such as looking for a "good enough" path instead of the most optimal path, dynamically changing maps, and large pathfinding in a short time. The C-Lightning pay command is parametrized with two tweakable arguments: maxfeepercent and maxdelay. Costs in Lightning involve the fee charged by the node and the number of blocks in the difference of the incoming versus outgoing HTLCs.In conclusion, the Lightning Network team has proposed several improvements to the pathfinding algorithm of their payment system. These improvements include permuteroute, which is faster and helpful in supporting JIT-Routing nodes. The latest version of the software factors in past pathfinding attempts into its central "mission control," allowing it to learn from each attempt. Additionally, a new `getroutequick` command can be implemented to speed up payment routing to arbitrary nodes. Finally, A* algorithm can also be used on Lightning if we have precomputed and cached the costs from a node to all other nodes.The Lightning Network is proposing a new routing algorithm called Trampoline Routing that aims to reduce the amount of computation needed for pathfinding. The team proposes dividing the network into two separate maps: a "smooth" map and a "rough" map. The rough map provides a normal route to a high-level node, followed by a short trampoline route from that node to the destination. Trusted Rough Maps are also proposed, which involve centralized trusted servers providing rough maps to nodes with extremely limited space. Self-Serving servers can also provide rough maps using free and open source software. Myopic Trampoline Nodes are also proposed, which involve nodes keeping only a small portion of the global routemap in memory.The author argues that trampoline nodes should be allowed to advertise themselves even if they don't have a complete smooth-level routemap. The author then discusses flocking, which is a technique used in real-time strategy games where a player needs to immediately send a large group of units to a location. The solution is to select one unit as the leader and have only the leader request a path, while the other units "flock" around that leader. The author applies this concept to Lightning Network payments, specifically split payments using AMP/Multi-part/Bass Amplifier.Overall, the Lightning Network does not need to pioneer new research into pathfinding. Instead, real-time strategy game programming techniques deserve closer examination as potential points of inspiration for similar techniques for Lightning.

Updated on: 2023-05-23T02:12:53.855521+00:00