This article assumes familiarity with Bitcoin, Lightning, the idea of Atomic Multi-Path (AMP) payments and amount-independent routing.

In short, AMP is about splitting up a payment in multiple partial payments that together make up the total amount. The receiver is able to claim the total amount only when all partial payments have been received. This is the atomic aspect of it.

This article describes an algorithm for multi-path routing of payments using a route property that will be introduced as specific fee. It is not about solutions for atomicity.

Objective

Given a Lightning channel graph, a destination node and a payment amount, find a set of paths and partial amounts that together incur the least possible total fee.

In the graph below, there are two channels between Alice and Charlie. Both channels have a capacity of 10 sat in the direction A to C. Fees are not involved, because there are no intermediate hops.

In this graph, sending a payment of 15 sat is only possible using two partial payments that each do not exceed 10 sat and together make 15.

It gets a little more interesting in the following graph:

Here, Alice does not need to compose a multi-path payment. She could send 15 sat through Bob’s expensive 2+50% channel with Charlie in a single payment. Total fees will be 9.5 sat. A single payment through the cheaper channel is not possible because the capacity of that channel is only 10 sat.

However, if she would use both channels and not send more than necessary through the expensive channel, she would end up with: (2+50% of 5) + (3+10% of 10) = 4.5 + 4 = 8.5 sat in total fees.

This also illustrates that any algorithm that only splits payments in multiple paths if a single path payment is not possible, cannot be optimal.

Complexity

Consider the graph below. There are multiple channels from B to C, all with only a base fee and no proportional fee component. To pay 100 sat, there are multiple ways to compose a multi-path payment.

In fact, with a graph like this, the multi-path routing problem starts to resemble the knapsack problem, https://en.wikipedia.org/wiki/Knapsack_problem.

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

Items are channels, weights are capacities and values are fees. It is not exactly the same, because we are looking for items with a total weight (capacity) more than a limit (payment amount) and a total value (fees) as small as possible.

Real channel graphs are more complicated and also each partial payment reduces the remaining capacity in channels that is available to further partial payment. Furthermore, fees need to be added in on the route towards the target node, reducing the maximum payment amount. Intuitively I would think that the multi-path routing problem is at least as as hard to solve as the knapsack problem, but no proof available.

This could also imply that a routing algorithm needs to employ heuristics to reach a solution.

Amount-independent routing

In current Lightning implementations, the process of finding a route is performed for a specific payment amount. It returns the optimal route for that specific amount.

For multi-path routing, such a data point for one specific amount is not very useful. There are many partitionings to be considered and it would be inefficient to sample the full range of payment amounts like that.

What is needed instead is a set of unique routes, each corresponding to one or more payment amount ranges. This set can be acquired through the use of an amount-independent routing algorithm.

Multi-path payments

From amount-independent routing, the step to multi-path routing is relatively straight forward. But let me emphasize that what follows is not guaranteed to result in the optimum multi-path partitioning.

The basic idea is simple: for the first partial payment, select the amount and route that gives the lowest specific fee. Specific fee is defined as fee per amount paid to the target node. For example, if 100 sat can be paid for a 10 sat fee or 150 sat for a 12 sat fee, then make the latter the first partial payment (0.08 sat/sat vs 0.10 sat/sat). This is the central heuristic part of the algorithm.

It is not necessary to consider all payment amounts. For a single route, the compound fee is base fee + fee rate * amount. That means that the lowest fee per satoshi is always reached at the maximum amount that this route can carry. The higher the amount, the lower the relative impact of the base fee.

So for every route, the fee per satoshi is calculated for the top end of its range and the route with the lowest outcome is selected for the first partial payment. This also means that a higher fee route with a higher capacity might be selected before a lower fee, lower capacity route. For example, 10+2% up to 100 (0.12 sat/sat) is used before 10+1% up to 50 (0.21 sat/sat).

After the first partial payment, the available channel capacities are updated by subtracting the amount and fees that these channels carried for the first partial payment.

Then the process proceeds by running the amount-independent routing algorithm again, selecting the second partial payment according to the same specific fee criterium and updating capacities.

This loop is repeated until no route is found anymore or the required payment amount has been paid.

Example output

Below is a screenshot of the output of the described algorithm.

What typically happens with well-connected nodes, is that there is a huge amount of possible routes to the destination and more and more become involved in a multi-path payment as the payment amount rises.

Sub-optimal

There is a situation where this algorithm returns a sub-optimal result. In a Lightning implementation, multi-path routing will be carried out for a specific amount. That means almost always that the last partial payment is not using the full capacity of the route. This is not taken into account for the second last partial. The second last payment may have the lowest fee per sat, but another route might have been able to carry the full remaining amount and avoid a second base fee.

There are probably more situations that result in sub-optimal results. Further investigation needed.

A (brute-forced) multi-path routing test set would be useful as well to benchmark algorithms.

Results

For fee levels for optimal single path payments vs multi-path payments produced by the algorithm described in this article, there are no large volume test results available. But typically the gains are enormous. For an example route from Yalls to Satoshi's Place, see the charts below. As a user you are no longer dependent on scarce, high capacity, high fee channels.

Final words

The idea of Atomic Multi-path Payments is very promising. Open question remains whether there is an algorithm that can provide guaranteed optimum routes within reasonable computation time.

In practice, any reasonable multi-path routing algorithm will already provide a lot of savings. With this post I hope to contribute one of those reasonable algorithms.

Specific fee routing for multi-path payments in Lightning Networks was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.

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.

Amount-independent payment routing in Lightning Networks was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.