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-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:
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-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 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
If I want to pay less fees, I would open a channel directly with the destination node where I do several payments and I can even use keysend.
But if I want more privacy in a payments I would choose a path with at least 4-6 hops.
simple, direct and clear...
You would be interested in the k-center algorithm from this paper.
Dang these are great posts thanks!
Thank you for documenting your process
Is open source?
I did not put the git repo on a public server no. I would have to cleanup the code a little, but i have nothing against it.
Do you mean, so that i can prove that it is not biased to making people opening channels that are in my interest? Maybe it's a good reason. I have to admit i have trouble personally with running things such as rebalance-lnd, lndg, autopilot, because i want to be sure i understand what they actually do and that it conforms to what i would want to do with the sats i have in my channels
Verifying for bias is important. Also, anyone who uses it now has to trust you aren't keeping logs that correlate their IP address to the search queries. If open source, we can self host.
For advanced users, skimming a git repo is sometimes preferred to reading a blog post.
It makes it easy to fork so people can add their own "pinch of subjectivity".
Who knows, maybe you'll even get the occasional PR with suggested improvements!