Specific fee routing for multi-path payments in Lightning Networks

A heuristic algorithm for payment fee minimization

Joost Jager
Jul 2, 2018 · 6 min read
Image for post
Image for post
Photo by Nick Fewings on Unsplash

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

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.

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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

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

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

Image for post
Image for post

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 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

Image for post
Image for post
Single-path fees
Image for post
Image for post
Multi-path fees

Final words

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.

Coinmonks

Coinmonks is a non-profit Crypto educational publication.

Sign up for Cryptoanarchy

By Coinmonks

A newsletter that brings you week's best crypto and blockchain stories and trending news directly in your inbox, by CoinCodeCap.com Learn more

Create a free Medium account to get Cryptoanarchy in your inbox.

Joost Jager

Written by

Software Developer | Algorithms

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Joost Jager

Written by

Software Developer | Algorithms

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store