Part 1: Analyze the LN network in under 100 lines of python
Part 2: Build a first LN channel advisor in Python
Part 3: Find LN peers that reduce the number of hops
In the previous episode, we tried to look if there were 'islands' of nodes in the network, in order to be the bridge between them to be the one to route all the payment between the members of those islands.
We found out that
- There actually aren't much nodes that are not already connected to the main part of the network graph
- The few groups that are not connected to the the rest of the graph are like this for for a reason, so they woudln't suddenly route to other nodes just because you created a channel
So if we want to create channels that are 'shortcuts', we must create channels that creater shorter routes than the existing ones. In Part 1, we already generated lists of peers that are X hops away from us. We will try to use this to find peers that would greatly reduce the number of hops in the network, so we can become the shortcut nodes go through to route payments.
Note: From now on, I will not provide complete working code, but only python/algorithmic fragments where they are needed to illustrate the subject.
Why hops count matters
Let's first discuss what are some advantages of reducing the number of hops for a route (all other things being equal):
- A payment has less intermediaries, so has less reasons to fail
- A routing fee is spread between less nodes, so cheaper routes for the users, and/or more profitable routes for the node operators
- If creating the channels between nodes that were 'far', it creates new shortcuts and reduces centralisation of the traffic.
Which hops count to target?
The next question that comes to mind is the following:
From which 'hop level' group should you select a new peer?
We saw earlier that there are reachable peers up to about 8 hops from you. Let's call hop level N the list of peers where the shortest path to reach them (in terms of number of hops) is N hops
Some hops levels must be more adapted to find peers, right?
- The nodes reached at the first hop would be the nodes directly connected to you. So you obviously won't gain anything (in terms of reducing hop count at least) to open new channels to them.
- The second hop level is the nodes your peers are connected to. No need to connect to them either (in terme os reduction of number of hops)
- And so on for each new hop level
As soon as you are connected to a few peers that have a few channels, hops 1-3 will contain most of the big nodes of the network.
As your node gets more channels, they will concentrate on hop levels 1-2.
The further hops are for the nodes that are further from the main nodes.
Now, how do we chose a hop level to connect to?
First, let's remind that we previously found out we needed 8 hops until we cannot reach anymore node.
In theory, we should assume from this that there is up to 8x2=16 hops between some peers of the network, as you cannot assume (from the simple metric of Part1) that peers have common 'ancestors' in the graph befor ereaching you.
In reality, it's pretty rare that a new node will connect to a (poorly connected) node at the edge of the public network graph.
So we can really assume that there are at most 8 hops worth considering.
One channel to the furthest creates the biggest shortcut!
One obvious choice of hop level, for someone who would want to to reduce the number of hops in the network, is the edge of the network.
If you just keep connecting to nodes from the outside of the graph, you shoudl bring them closer to the center, bringing the bigger number of hops reduction par new channel created?
Let's show this more visually. Each number will represent the nodes that are reachable for a certain hop count.
If you connect to one of the nodes with the biggest number of hops to reach (8), the network that was
0(you)-1-2-3-4-5-6-7-8
becomes
0-1-2-3-4 | | 8--7--6-5
So now, any of those nodes is only at most 4 hops from you. You could say the network is now like this:
0-1-2-3-4
Great!
We saw in the first article that there were only 2 nodes 8 hops from us. So we just need to open two channels to those, and now suddenly everyone will be at most only 4 hops away from each other, right?
Obviously this is not the case.
The first argument that comes to mind is that it it were that easy, there would already be only up to 4 hops between anyone.
The second real reason is something less obvious at first:
The Lightning Network has no center (and it would be yet less likely it would be you).
Look again at the example above.
- the circle formed between 0 and 8 is actually only formed on the suite of nodes that create the path to the node at hop 8 you chose.
- nodes 7 hops from you were not all connected to the node at hop 8 you chose. So most of them are still 7 hops from you (and they could still in theory be 14 hops from each other)
Let's take an example to illustrate it another way. Let's consider all the nodes 8 hops from you.
Now let's imagine a new node, that has no channel yet, connects to all those channels.
It did NOT become the center of the network because it 'pulled' the edges of the network to the center!
In reality, from the point of view of your node, it is now a node at a 9th hop!
And a last way of seeing it:
If you would represent the lightning network graph on a sphere, where the 'outer' nodes are on the edges (example).
- The nodes furthest from you are not necessarily on the edge of the circle
- Even if they were, if you had to draw geometrically on that sphere, the position of a node connected to them, you could say that the point at the same distance of all 'far' nodes is the most adequate? So that node would then be at the center of the sphere? In reality, that node would be drawn on the outer of the graph too. Or at another totally different place depending on the other channels it is connected to. And actually, also depending of the weight of all other channels between all other nodes of the network, and the parameters of the algorithm drawing it, and the random values it might use.
Nodes are at the 8th hop for a reason
There is a last reason why choosing the furthest nodes is a wrong idea to reduce the number of hops. Those nodes are really far from most nodes. They probably do not yet have a lot of channels. And they probably are not trying to be a routing node, more probably thet are nodes of consumrers of a service that just connected to what they need, and keep their channel balance in a balance that suits their needs.
Even if you actually shorten some routes by connecting to them, you will route almost nothing from them. Trust me, i tried it..
Also, you would add YOUR satoshis in this channel to them. So you could even say they are not the ones who deserve it the most
There is another way to go from 8 to 4 hops
Yes, you might already thought about it, there is actually another better way to go from 8 hops to 4 hops from a route. Instead of connecting to the 8th hop level.. you can also connect to the 4th hop level!
Using the same drawing scheme as above:
0(you)-1-2-3-4-5-6-7-8
becomes
0-1-2-3-4 | 5--6--7-8
And now you are also connecting to a node that is already better connected!
- It is not no near, so connecting to it will still create somewhat big shortcutsto nodes in the middle of the network
- but also not so far in the network, so it can still bring some of the furthest nodes nearer
- And it probably already have a good number of good sized channels, so there should not be too many 'channel balance issues' that make routes fail
From this, we can conclude that we should choose peers that are at most 4 hops away from us.
We will probably also not gain much from peers 2 hops from us (the peers our our peers), since it owuld only shorten path of 1 hop, for a small quantity of paths.
Meaning, that most good candidates for hops reduction are at the 3rd ahd 4th hop level.
Selecting from the candidates
We now have a list of candidates to pick from. But there are still a few thousand nodes that are 3 and 4 hops from us. We have to find other criteria to choose the next peer to connect to from all of those.
It should be some kind of metric of 'how much one node brings nearer from us'. I'll talk about what i chose at that time; there is porably a more 'mathematical' way to find a good answer.
First idea:
For each candidate: - Take the hops metric from the first article. - Add a fake channel to that peer and run again the hops enumeration - Then compare the values for each hop, to obtain a metric of **how much nodes are now nearer from you** Then order them by that metric, and take the best
You could have a variant where you instead calculate How many channels it brings nerarer to account for the multiple channels that might bring to a node. It won't technically mean more sats would flow (it's the nodes who initiate the routes, not the channels). But it might help having alternate paths so the payments would have more chances to succeed on one of the routes going through you.
Now, all channels are not equal.
- Smaller channels will likely bring less sats moved.
- Channels bigger than the one you want to open will not bring a lot more traffic than channels equal to the capacity you chose (it might actually be the opposite, but that's what i intuitively thought at the time)
So now, we can update our selection algorithm:
Run the hop metric. But for each level, accumulate the capacity of the channels of that hop level (capping the channel sizes to the value of the channel you want to open) For all the candidates: - Run it again, simulating a channel to that peer - Compare it to the reference result. You now have a metric of **How many satoshis are now nearer from you** Order them by that metric, and take the best
Add a pinch of subjectivity
Finally, we have an algorithm that can give as one candidate after some 'not so absurd' logic. But it is also a naîve and simplist logic, i'm sure you will agree.
Add your final touch by taking the few best suggestions for hop level 3 and 4, and do some manual research on the nodes to choose for yourselves the one you tink fits best!
The results
The end result is somewhat what the very alpha version of my lightning node advisor at lnshortcut.ovh looked like a bit more than a year ago.
I can say it brought more routes through my node than my previous (yet more naîve) manually selected channels. But not really much.
The two main issues i identified with the channels that had been selected were the following:
- Balance issues: it still selected channels that would eventually be stuck with liquidity in one side
- It still did not really brought much traffic, because it still did not really evaluate properly what each candidater brings. For example, you could create a route that has 4 less hops, but if there is another longer route that has a lower total fee, it will be tried first!
The next step
In the next part, i guess i'll write about what was done in the next rewrite of my channel advisor, to account for fees and channel balances