Bitcoin Lightning Network path-finding algorithms

What is the Bitcoin Lightning Network

The Lightning Network, a second layer technology, functioning on top of the Bitcoin blockchain network, is a way to instantly send irreversible and confirmed Bitcoins, without waiting for said Bitcoins to be included in blocks found by miners. The technology became known as The Lightning Network, due to its ability to allow for instant Bitcoin transactions between peers, and was first envisioned in 2016 by Joseph Poon and Thaddeus Dryja.

The original paper can be found here, but has since been replaced by a more elaborate specification, called BOLT, the interoperability that makes up the most utilized secondary layer.

Background to The Lightning Network

The idea behind payment channels as payment abstraction layers began at the inception of Bitcoin. Hal Finney wrote that a blockchain would be incapable of handling all the transactions in the world, and still maintain its current architecture as a decentralized ecosystem.

Satoshi seemed to have envisioned something like a payment channel, based on the nSequence operation, which was ultimately disabled, due to that it did not solve the need for a scalable payments layer, as we later had with The Lightning Network. Some alternative nSequence payment channels proposals were discussed, namely duplex micropayment channels, but were later abandoned in favor of The Lightning Network.

Up until The Lightning Network was proposed, and even after The Lightning Network proposal a number of solutions have been debated, and some of them are collected in a big post here. While some variations are interconnected to the current specification of The Lightning Network, the general consensus is to use layers in order to achieve mass transactions, and still maintain a decentralized ecosystem on the base layer.

The Lightning Network topology

For something like The Lightning Network to work at large scale, it must be able to propagate data between the participants in the network. While there is a big difference between path finding and keeping a decentralized structure, the focus has been to ensure that censorship does not happen in the network.

An early map of all the participants in The Lightning Network, shows a distributed, non-centralized map of participants evolving the network itself. Today this stands even more decentralized with a large amount of nodes, and an even larger amount of channels between the different nodes participating in the network.

The behavior of how the network topology is playing out is therefore important for how deploying effective routing algorithms between the participants should be selected. The constrains for deploying different algorithms is however up to the single node participants to decide upon.

Nodes can choose which routing algorithm to deploy since they are not required to be in consensus, but merely be compatible, as specified in the BOLT specification, namely BOLT #4 and BOLT #7.

The Lightning Network implementations

There are currently 3 main implementations, each based on its own language. One is a Scala version called Eclair, one is a Go called LND and one in C called c-lightning. Each of the implementations shares interoperability via the BOLT specifications, yet differ not only in language, but also in their choice of path-finding algorithm which we will explore in more depth.

All routing however deploy the same routing algorithm which is onion routing. The onions contain a path from sender to the receiver, decided by the sender, and are constructed to support as many as 20 nodes in between sender and receiver. The current onion routing algorithm therefore puts a maximum amount of jumps between the head and tail nodes, but as a side-effect limits the complexity the network, which in turn allows for easier path finding between nodes in the network.

Finding the path with algorithms

A number of algorithms existed long before The Lightning Network existed and many path finding algorithms were developed long before the modern consumer internet existed. Path-finding algorithms are not part of the BOLT specification in Lightning, and it is up to each implementation/ node to use what they see fit in order to find the shortest and most optimal path, with the information provided by the gossip protocol.

Path finding algorithms and heuristics are an ever growing challenge in the field of computer science.  As data sets grow, optimizations across the entire field are in increasing demand. The Lightning Network is however nowhere near the limit other networks and scenarios experience. It has on the other hand the potential to explore algorithms in a way no other path finding algorithms has been used before, as the Lightning Network would eventually become sensitive due to that it is handling money, potentially high speed IOT settlements, which would require fast algorithms with custom made heuristics for different scenarios.

Dijkstra algorithm

Dijkstra algorithm is already implemented as one of the path-finding solutions in the some of the Lightning implementations and is a well known algorithm developed back in 1959 by the Dutch scientist Edsger Dijkstra.

Dijkstra’s algorithm finds the shortest path tree from a single source node, by building a set of nodes that have minimum distance from the source. The Lightning Network can be described as an unweighted graph, as the length (fees) between the nodes will in most cases always differ. In the Lightning Networks case, the distance is calculated as the routing fee, and the compounding value of each node hop would be the path with least “length”.

As each node keeps an index of all paths in Lightning, it can compute shortest path, when Dijkstra is in use, by computing the values from between each hop and thus finding the most flexible route. As the network grows, and as more paths become available, computing every single possible path could be too time consuming for a node, and other algorithms should be explored.

A* algorithm

The A* (A star) algorithm is a variation of Dijkstra algorithm in that it uses heuristics to decide upon the next best node, also known as “best first search”. A* would typically give priority to nodes that are supposed to be better than others (all depending on the rules of the heuristics) while Dijkstra’s explores all possible paths, and only looks for shortest path between nodes.

Multiple alternative algorithms

The Lightning Network is strictly speaking nothing special when it comes to path finding, in relation to computer science. A myriad of computer science research and development exists, covering path finding. From D*,  D* Lite to Tree Adaptive A** , and Heuristics path finding research taught in several CS classes, the Lightning network stands to benefit from years of research.

With the added complexity of atomic multi-path payments, where path finding routes can be across multiple nodes, to finally combine all transactions into a finalized payload, search algorithms and decision heuristics are probably set to take up more focus as they become an even more important part of the entire project.

In our next piece about algorithms, we will focus on more novel search heuristics, based on biological systems and how those differ from man made search algorithms such as A*.