is the Barabasi Albert Model a reasonable choice for the autopilot?

[renepickhardt]

I am not sure if that is directly a bug but I thought the bugtracker is still a better place than the mailinglist.

As far as I understand your documentation of the autopilot it opens channels with nodes that already have most channels open following the barabasi albert model of preferential attachment.

While a scale-free network topology seems reasonable to me I doubt that it makes sense to use that graph model and design decisions for the following reasons:

• It creates power nodes with a large indegree. As long as those nodes don't have enough funding the payment channels will be pretty unbalanced. also it creates a risk that the connectivity breaks when a powernode breaks. Especially a chain reaction of this could happen.
• the power nodes will have to do quite a lot of routing. Also maybe just because they habe been there first. Maybe they don't have the computing power to be connected to millions of payment channels. (nor the funding as mentioned above)
• While social network graphs also follow these kind of distributions I think there are more metrics to consider. For example the number of triangles created (which should be an important property for the lighting network because triangles mean that there are always more that 2 routs in case a channel breaks) This point is similar to the fact that in physical networking we also have routing protocols that use other routing metrics than hops (for example latency, bandwith, some measure of reliability,...). I guess the same will hold true for the lightning network.
• Also in web applications nodes with high indegree usually create quite some chalange for the programmers since they produce so much traffic which needs to be handled.

I am pretty confident we need another network topology that is more stable for the autopilot. In fact I am rather positive that the current form of the autopilot will yield quite some problems in the future.

In case you people agree I'd be very willing to learn go and work on some different strategy to automatically build the lightning network.

@Roasbeef @michielbdejong @jimpo

[Roasbeef]

Great question! I'd say this is the correct venue for such questions, as this feature is currently unique to lnd.

Before I comment on your points, I want to point out that this the current model is only a momentary default. Autopilot itself is not in anyway strongly coupled to this set of heuristics. Instead, there's an interface which allows alternative strategies to be easily coded up. The BA model is the current default as no one else has bothered to start experimenting with alternative models. We have a list of other models we'd like to start to experiment with, however there are higher priorities items which have been consuming most of our development time.

It creates power nodes with a large indegree.

These nodes with larger in-degree are distributed across the network, so not as if there'd only be a handful of them. It's easy to confirm this by looking at the current testnet which is largely driven by this model.

. As long as those nodes don't have enough funding the payment channels will be pretty unbalanced.

With the current network, they don't need to commit any funds for incoming channels. As long as nodes themselves also establish outbound channels, funds will be able to flow.

The power nodes will have to do quite a lot of routing. Also maybe just because they habe been there first. Maybe they don't have the computing power to be connected to millions of payment channels.

The "computing" power require for routing is pretty minimal. It's possible to route 1-2k payment/sec on a laptop for example. As for the "millions" of channels, once we reach that point, I'd say the project is a resounding success! However, it's a mistake to assume that this will be the only dominant optimistic channel establishment strategy at that point.

While social network graphs also follow these kind of distributions I think there are more metrics to consider. For example the number of triangles created (which should be an important property for the lighting network because triangles mean that there are always more that 2 routs in case a channel breaks)

Indeed. A high-degree of path diversity will be an important characteristic of the network, as higher path diversity means that the network is more diffuse and a few nodes going down won't cripple the existing payment routing functionality.

This point is similar to the fact that in physical networking we also have routing protocols that use other routing metrics than hops (for example latency, bandwith, some measure of reliability,...). I guess the same will hold true for the lightning network.

The constraints of physical networks aren't directly applicable to LN, per-say. I can quickly establish a new link at cost only to myself. Also, hops aren't the only metric that we consider during path finding.

Also in web applications nodes with high indegree usually create quite some chalange for the programmers since they produce so much traffic which needs to be handled.

Not sure how this is directly related.

[renepickhardt]

The BA model is the current default as no one else has bothered to start experimenting with alternative models. We have a list of other models we'd like to start to experiment with, however there are higher priorities items which have been consuming most of our development time.

So where can I find that list? I am currently helping someone setting up a webshop which is supposed to accept lightning payments but after this (starting next weekend) I'd be happy to learn go (doesn't lookt that complex) and start contributing by extending the interface and providing more strategies for the autopilot.

The "computing" power require for routing is pretty minimal. It's possible to route 1-2k payment/sec on a laptop for example. As for the "millions" of channels, once we reach that point, I'd say the project is a resounding success!

Very true but since lighting is supposed to fix the scaling issues of Bitcoin I'd expect more than 10k payments per second for regular consumers. As soon as stock exchanges start switching to bitcoin and lightning we might even add another order of magnitude. Sure not every payment goes through the power nodes. But still I think the mentioned path diversity should still be a topic of interest.

[Roasbeef]

So where can I find that list?

The list isn't yet public, but with a bit of research one should be able to compile a similar list. Aside from that, you could start to experiment with some of the suggestions that you laid out above. We'll likely have a blog post out soonish that highlights the concept of autopilot and touches on some alternative heuristics.

Very true but since lighting is supposed to fix the scaling issues of Bitcoin I'd expect more than 10k payments per second for regular consumers.

That's over a single channel. The throughput should scale linearly with the number of channels. Also note that we've done virtually zero optimization on that point, as it isn't currently a high priority. Are there existing cryptocurrency accepting web stores that do more than 10k payments/second?

[renepickhardt]

cool I will probably start next weekend with my own list and ideas of making the autopilot a little bit more useful.

As for the 10k: Completely agree with you. However I think the goal of lightning is to be able to make bitcoin the defacto standard for payments over the internet. Always having visa with 4k/s in Mind.

[bretton]

Some stuff which caught my eye on alternative network modelling: https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model https://en.wikipedia.org/wiki/Triadic_closure

Things I'd like to see explored include the following:

'Split the bill' Cost fairness spread between parties opening channels, for example a channel ring of A->B->C->A all pay the same fee, and have payments going around in both directions, or to other channels.

If a 4th party comes along, they only need to open one channel to someone in the ring, along with someone else in the ring opening a channel back to them. Repeat for for parties 5 & 6 and other combinations so the triangle/circle and the cost fairness is preserved, with many possible routes for payments.

And so on. Every new node become part of a triangle where someone is contributing as much as they are to open a channel.

Weighted distribution Develop some sort of weighted distribution in node choices, such as one geographically close node, 2 nodes in a densely connected area, and 2 nodes many hops away to "bring in the edge"

Just throwing in 2c :)

[renepickhardt]

just saw this really interesting graph on reddit touching this topic and suggesting to add 1 random channel (I guess assuming an uniform distribution) for each node which sounds to me like a very reasonable idea.

@Roasbeef I set up go, glide, ide (can u recomand golang?) and lnd. As soon as I finnish the webshop for this instagram artist I am helping to test lightning on main net I will start working on this issue. So you can assign me in the issue tracker if you wish. Is here the place to announce my plan or should I register to some of the other communication tools you are using?

@bretton like your thinking but wouldn't those rings again impose the risk of breaking routes?

[Roasbeef]

That graph isn't really that accurate. Most people on mainnet made a single channel to buy a sticker or w/e to the blockstream store. Hence the unbalanced nature of that publicly advertised sub-graph.

Most channels in the future won't even be publicly advertised, so metrics like this are simply a lower bound.

I would advise not getting caught up in the "centralization vs decentralized" strawman cycle. The actual realities are much more nuanced. One needs begin analysis based on a number of desirable qualitative/quantitative metrics, what the cost of entry is, etc.

On Sun, Jan 28, 2018, 11:04 PM renepickhardt notifications@github.com wrote:

just saw this really interesting graph https://www.reddit.com/r/Bitcoin/comments/7tobq9/lightning_massive_decentralization_improvement_if/ on reddit touching this topic and suggesting to add 1 random channel (I guess assuming an uniform distribution) for each node which sounds to me like a very reasonable idea.

@Roasbeef https://github.com/roasbeef I set up go, glide, ide (can u recomand golang?) and lnd. As soon as I finnish the webshop for this instagram artist I am helping to test lightning on main net https://www.reddit.com/r/Bitcoin/comments/7tmjn8/instagram_artist_journalspiration_131k_follower/ I will start working on this issue. So you can assign me in the issue tracker if you wish. Is here the place to announce my plan https://github.com/lightningnetwork/lnd/blob/master/docs/code_contribution_guidelines.md#ShareEarly or should I register to some of the other communication tools you are using?

@bretton https://github.com/bretton like your thinking but wouldn't those rings again impose the risk of breaking routes?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/lightningnetwork/lnd/issues/677#issuecomment-361156879, or mute the thread https://github.com/notifications/unsubscribe-auth/AA87LlkRKCkx9-0o8q_tpENHN9jzFQ3Fks5tPW2XgaJpZM4RvbS2 .

[jimpo]

@renepickhardt I'm really glad you are looking into this because it certainly needs attention.

Selecting peers based on network topology is interesting and certainly useful (because you would like to be able to route payments in as few hops as possible), but there are other factors to consider that, even if they are more difficult to determine upfront.

• Fees: I'd like to be connected to peers that offer lower fees. You can monitor channel announcements from a node, but take into account that they might advertise low fees to try to to bait you to open a channel then either raise them or refuse to route payments as a DoS.
• Reliability: I'd like my peers to be able to route payments with minimal latency. You can try pinging to at least get a measure of network latency.

Most of these signals can only be determined by actually trying to route payments through a node (even if they are not a direct peer). One idea might be to create circuits sending payments to yourself (you'd incur a fee) to see how reliable other nodes on the route are, then opening channels to them. The autopilot mode could also proactively close channels to nodes with poor connectivity or high fees and allocate the funds to a new channel.

[bretton]

@renepickhardt human-driven networks with a high level of reciprocity tend to persist longer, with a greater sense of social responsibility to the whole?

in the same sense an autopilot model could open channel loops based on broadcasted fee level & reciprocal partners willing to close a triangle/loop.

loss of individual nodes/channels in a growing series of loops doesn't matter, there's always an additional redundant path available.

[renepickhardt]

I started an outline for a short white paper in my git repo before I implement other interfaces for the autopilot. You can find the compiled pdf of the draft as a release in that repo. The pdf is currently just 2 pages with bullet points. So it really is a quick read.

Following your contribution guide I would obviously love to have input like the one from @bretton (even though I was already familiar with Watts Strogatz and triadic closure the hint was still very useful seeing that other people think in the same direction) The input is in particularly welcome for chapter 2 (related work) and 3 (metrics and desired properties of the lightning network) which I am suggesting at the moment.

My goal ist to actually do some simulation and benchmarking before deciding which heuristic to implement. Hope my inactive git account over the last 2-3 years is not an issue for you people. I was pretty busy with other stuff :(

[nalinbhardwaj]

@renepickhardt : I see your white-paper touches on metrics to moderate via autopilot, here's my suggestion on that:

A very good metric to quantify connectivity and the amount we can transact between nodes is max flow in the graph. So, the graph edges are given capacities as their channel sizes, and average flow from a source node(taking each other node as sink) is computed and attempted to maximise.

To incorporate fees/latency etc. into this very metric, maybe we could come up with some variant of Min Cost Max Flow problem, which are also solvable in quadratic time.

[bretton]

Relevant: https://zmnscpxj.github.io/offchain/cyclicsuperhubs.html

[ZmnSCPxj]

One idea might be to create circuits sending payments to yourself (you'd incur a fee) to see how reliable other nodes on the route are, then opening channels to them

This need not incur a fee. If you are able to reach yourself via a route and receive a update_offer_htlc of the cyclic self-payment, then you already know the information you need -- you know they will reliably forward payments -- and can reply with an update_fail_htlc, reversing the payment and not incurring a fee. It will require that you have some money in channels and you risk getting it locked up if a node shuts down after it forwards your payment, but you need not actually incur a fee.

[renepickhardt]

This issue was being discussed on the 2nd lightninghackday in Berlin last weekend. A summary of the discussion can be found at: https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin/

[bretton]

Great to see some progress here. I'm horribly under-qualified and out of my depth for anything except "ra ra go team go" support on this :)

I've had some successful uptakes with my manual model of reciprocal channels, where A opens to B, B opens to C, and C opens to A.

However it's not autopilot, and requires a negotiation layer with all parties on the same page, and commitment to keep channels open.

All 3 participants share an equal cost in initiating channels, which is fair, and provided the same setup can be repeated with other trios, could create an interesting topology.

[renepickhardt]

I've had some successful uptakes with my manual model of reciprocal channels, where A opens to B, B opens to C, and C opens to A.

so what you basically propose is that wedges in the graph should be closed as triangles or in general an heuristic for triangle closing since this is the shortest meaningful circle in the graph. I guess having many triangles is a decent heuristic and probably already more useful than the Barabasi Albert model. I like the idea that an autopilot runs not only in the beginning but keeps running and tries to close triangles.

[bretton]

I like the idea that an autopilot runs not only in the beginning but keeps running and tries to close triangles.

cool, if something like that is possible, then maybe it will be useful. Requires incoming channels, but maybe that's the difference between a new node trying to establish a broad connection to the network, and a mature node trying to establish better redundancy(?)

Happy to test once we have more to work with.

[renepickhardt]

taking into consideration the paper cited in this Blogpost: https://medium.com/@dimapiatkivskyi/why-would-you-re-balance-a-payment-network-796756ad4f31 maybe the even the best strategy for the autopilot would be to create channels which increase :

1. ones own outgoing flow
2. help others to improve their ingoing flow

The problem I see is that initial channel balances need to be known in order to calculate the flow of the network

[dmytropiatkivskyi]

Hi!

I recently started thinking on the autopilot issue myself, mostly in the long-term perspective. Here are some of my thoughts.

Except for the already mentioned groups of characteristics like strengthening the topology (in term of graph properties, e.g increasing the maximum flow and shortening the path lengths) and nodes’ ratings (uptime), I think the short-term effect on the network should also be taken into account. Let me explain it. In my vision, the efficient network topology will have to mimic the traffic created in the network. The traffic is highly dynamic however, yet the topology is static. Autopilot could bring the two closer. For example, if there is a massive flow from one part of the network to another part of the network, the channel balances get depleted in one direction. It would make sense to create new channels in the direction of depletion, so additional liquidity is provided. Even though it’s suboptimal in long term. Moreover, long term optimality is always a guess, while short term is suggested by the network state.

I suggest monitoring fees in the network as an indication of the network flows. If the network gets skewed fees are growing in that direction. That is of course assuming that nodes will be changing their fees according to the distribution of channel capacities.