Amount-independent payment routing in Lightning Networks
Efficient path finding for the full range of payment amounts
This article assumes familiarity with Bitcoin and Lightning Networks.
In current Lightning implementations, the process of finding a route is always performed for a specific payment amount. For example: find the lowest cost route for Alice to pay 1000 satoshis to Charlie.
To make a regular payment, this is just what is needed.
For other purposes, it may be more useful to derive a set of optimum routes without assuming any specific payment amount. For example:
- Assessment of the value of the current set of open channels of a node.
- Decision making support in opening new channels.
- Re-balancing decisions.
- Routing for multi-path payments (AMP).
This article describes an algorithm for amount-independent payment routing.
In the current Lightning network, accurate capacities for channels other than your own channels are unknown. In the remainder of this article, capacities are assumed to be accurate.
Before going into the details of the algorithm, we will first explain the notions of compound fee and compound capacity.
Compound fees
A compound fee is defined as the total fee that is paid to all intermediate hops of a route. It could be looked at as a “virtual” fee that needs to be paid to the target node if all intermediate hops were to be removed. In the way fees are currently structured in Lightning, it is possible to express the compound fee as a base fee and a fee rate, identical to the fees that individual nodes charge.
Suppose Charlie in the end gets paid a satoshis. The compound fee for this route from Alice to Charlie is the sum of:
- Dave’s fee for forwarding amount a to Charlie = 5 + 10% * a.
- Bob’s fee for forwarding amount (a + Dave’s fee) to Dave = 3 + 20% * (a + 5 + 10% * a) = 4 + 22% * a.
This makes the compound fee 9 + 32% of the amount that Charlie gets paid.
Compound capacity
Similar to the compound fee, a compound capacity can be calculated for a route. This is defined as the maximum amount the can be received at the final node, taking into account the channel capacities along the way and the additional capacity that is needed to carry the fees.
For the example above:
- Alice can get a maximum of 200 satoshis to Bob.
- If Bob forwards on to Dave, he will charge 3+20% of the forwarded amount. The maximum that his channel to Dave can carry is 40 sat. The fee for that is 11 sat. Bob expects a total of 51 sat from Alice. The Alice-Bob channel can carry that. Alice can get a maximum of 40 sat to Dave.
- Dave charges 5+10% for forwarding to Charlie. If he receives the maximum that can reach him, 40 sat, he will first subtract his forwarding fee. The maximum that this budget allows him to forward is (40–5)/(1+10%) = 31.8 sat. This amount can be carried by his channel to Charlie. Alice can get a maximum of 31.8 sat to Charlie.
This makes the compound capacity of this route 31.8 sat.
Path finding
An common element of path finding algorithms is edge relaxation. This entails updating the least cost path to a node. It is part of Dijkstra’s algorithm (used in lnd) and the Bellman-Ford algorithm (used in c-lightning). Cost in the context of Lightning is typically the total fee accumulated so far plus a penalty for time locks. This cost value is a single number and only relates to one specific payment amount.
The notion of edge relaxation can be extended to payment amount ranges.
The basic idea is that for each node, a table is kept that contains payment ranges, compound fees, compound capacities and paths back to the source node (in case of forward routing).
Relaxation is then defined as adding the new range/fees/capacity entry to the table and pruning all entries that have become useless after this last addition. It could be that the newly added entry is pruned immediately. But it could also be that one or more of the existing entries are pruned or that nothing is pruned at all.
For example, an entry that describes a path that provides 10+10% fee up to 1000 sat will be dropped from the table when a new path is added that provides 5+8% fee up to 2000 sat. However, if the new path would have been 12+15% fee up to 3000 sat, both would stay in the table. Either of them could be optimal depending on the amount.
This process can also lead to splitting up existing entries if for a specific amount but narrow range the new entry carries a lower compound fee.
For the actual driving loop to perform the iterative relaxation, Dijkstra seems not very suitable. It needs a definition of the node that can be reached with the lowest cost for its priority queue. Having a table of paths per node, lowest cost is not naturally defined. It may work by using the lowest cost for any amount in the ranges, but this was not investigated.
Instead, Bellman-Ford is used. With its |nodes| * |edges| complexity it is significantly slower than Dijkstra, but in practice running time can be controlled by limiting the number of iterations based on the maximum number of hops in Lightning. This is currently twenty hops. Running through and relaxing all edges twenty times will result in the shortest paths for routes up to twenty hops.
An additional advantage of Bellman-Ford is that is can handle negative edge weights. At the moment, negative weights are probably not present in Lightning, but they may be in the future. It can be useful to promote specific routes that re-balance the network.
In regular payment routing, the search is (or should be) performed backwards. The process starts with the amount to be received by the target and working towards the source, costs are accumulated and channel capacities checked.
The amount-independent algorithm described here can be implemented either as a backward or a forward search, because there is not a specific amount that we are after.
Deciding the search direction depends on the purpose. If an analysis is required from source to all targets, forward searching gets all results in a single run. If an analysis from all sources to a specific target is required, the backwards variation is needed.
When the algorithm has finished, the table of paths at the target node contains the lowest fee routes to that node for all payment amounts.
Minimum amount and time lock delta
Channel policy parameters that are missing are the minimum payment amount (min htlc) and time lock delta. Both are relevant, but are left out for now. The algorithm can be extended to take these parameters into account without major changes.
Example
The screenshot of the algorithm output below shows that for any payment amount from 382002 up to 399998 sat, the least cost route as a single payment is through the btc.lnetwork.tokyo and Kangaxx nodes.
The graph shows the nodes and channels involved in any of the routes. This is all that is needed for payments of any amount to the chosen destination.
Note that this does not take into account that channel capacities may be inaccurate, nodes may be down, fees not updated, etc. In reality the routing process will likely need to be repeated multiple times as some routes will fail and this may result in use of nodes and channels that are not in this graph.
Multi-path routing
One of the uses of amount-independent routing is in the calculation of multi-path payments. Continue reading on specific fee multi-path routing.
