Specific fee routing for multi-path payments in Lightning Networks
A heuristic algorithm for payment fee minimization
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.
