Path finding on the Lightning Network

how path-finding and routing works to deliver value on the Lightning Network

On the Lightning Network we cannot just interconnect nodes with channels, we must find a way to route transactions across the existing channels. Infact our node cannot connect each existing node which it wants to send funds to; this would not escalate. This is why pathfinding and routing is basics on the Lightning Network theory.

Path-finding vs routing

Pathfinding is the process of finding and choosing a contiguous path made of payment channels that connects a sender (origin node) to a recipient (final node). It is important to distinguish pathfinding from routing, which refers to the series of interactions across the network that attempt to forward a payment along the previously selected path.

In the Lightning Network, pathfinding is source-based, meaning that the sender of the payment is responsible for finding the path through the network to the intended destination. This differs from typical internet routing where intermediary nodes decide how to forward packets.

To find a path, the sending node needs information about the network's structure or topology. This information is gathered by nodes building an internal map of the Lightning Network, known as a channel graph.

Channel Graph Construction

• The channel graph is the interconnected set of publicly advertised channels and the nodes that these channels interlink.

• Nodes build and maintain their perspective of this graph by listening to gossip protocol messages from their peers.

• Key gossip messages include:

  • node_announcement: Provides information needed to create the nodes (vertices) of the graph.

  • channel_announcement: Allows nodes to create the edges of the graph representing payment channels. Since channel balance splits mean liquidity differs in each direction, the graph is directed. A channel_announcement also includes proof that a channel exists between two nodes. Channels are referenced using a short channel ID (scid), which encodes their location in the Bitcoin blockchain.

  • channel_update: Contains metadata for a channel, such as routing fees and timelock duration. This allows incorporating fees and timelocks to set the cost or weight of the graph edges.

• Nodes continuously build and update their channel graph from the moment they start and connect to peers. More gossip information improves a node's "map" and pathfinding effectiveness.

• It is crucial to understand that there is no single, canonical "the" channel graph; each node constructs its own channel graph based on the information it has received, which is necessarily incomplete, incorrect, and out-of-date to some extent.

The Pathfinding Problem

• Pathfinding in the Lightning Network falls under graph theory and graph traversal. It's a problem of finding a path through a directed graph with numerical capacity constraints on its edges, similar to a flow network.

• If exact channel balances were known, standard pathfinding algorithms could easily compute paths, optimizing for factors like fees.

• However, channel balances (liquidity) are not known to the sender for privacy and scalability reasons. Nodes only know the aggregate channel capacity. For a payment to succeed, there must be adequate balance on the sending side of each channel in the path in the correct direction.

• This lack of knowledge about liquidity makes pathfinding significantly more complex than in theoretical computer science problems. The information is also highly dynamic.

Finding Candidate Paths

• With only partial information about channel liquidity, innovative pathfinding strategies are needed.

• Nodes can use the channel graph information (nodes, channels, topology, announced capacities, fee policies) to find paths.

• Since fees are accumulated from the recipient backward to the sender, pathfinding algorithms like Dijkstra's or A* are often applied backward from the recipient to the sender. The cost function for edges might include fees, estimated liquidity, timelock delta, or a combination.

• Paths must have sufficient liquidity not only for the payment amount but also for the cumulative fees of all subsequent hops.

Payment Delivery (Trial-and-Error Loop)

• The pathfinding mechanism currently implemented in Lightning nodes often involves creating a list of candidate paths, filtering and sorting them by some function (e.g., cost, capacity combination).

• The node or wallet then probes paths by attempting to deliver the payment in a trial-and-error loop until a path is found that successfully delivers the payment. This probing is not directly seen by the user but may cause delays.

• During the trial-and-error process, nodes can learn from failures and successes. For example, receiving an "insufficient balance" error from a node for a specific channel narrows the estimated range of liquidity for that channel. A successful payment indicates that all channels on that path had sufficient liquidity for the amount plus fees, allowing the node to update its liquidity estimates. This reduces the uncertainty of balances.

Multipart Payments (MPP)

• Multipart payments (MPP) are an advanced pathfinding strategy where a large payment is split into multiple smaller parts and sent over different paths simultaneously.

• This strategy helps overcome the challenge of uncertain liquidity, as smaller payments have a higher chance of succeeding on individual channels.

• MPP algorithms aim to find the optimal number of splits and amounts for each split, potentially utilizing paths that might not have sufficient liquidity for the full amount but can handle a smaller part.

• The process can involve multiple rounds of pathfinding, updating the channel graph after each round based on payment successes and failures to optimize subsequent attempts for any remaining amount.

While the process of finding the "best" path is complex and still an area of active research, the combination of building a channel graph from gossip, utilising pathfinding algorithms adapted for uncertain liquidity, and the trial-and-error probing process with learning from failures/successes enables payment delivery on the network. Pathfinding is not specified in a BOLT standard, allowing different implementations to use varying strategies.