-
Notifications
You must be signed in to change notification settings - Fork 2.1k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
is the Barabasi Albert Model a reasonable choice for the autopilot? #677
Comments
Great question! I'd say this is the correct venue for such questions, as this feature is currently unique to 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.
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.
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 "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.
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.
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.
Not sure how this is directly related. |
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.
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. |
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
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? |
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. |
Some stuff which caught my eye on alternative network modelling: Things I'd like to see explored include the following: 'Split the bill' 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. 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 Just throwing in 2c :) |
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? |
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 ***@***.***> 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
<#677 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AA87LlkRKCkx9-0o8q_tpENHN9jzFQ3Fks5tPW2XgaJpZM4RvbS2>
.
|
@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.
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. |
@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. |
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 :( |
@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. |
This need not incur a fee. If you are able to reach yourself via a route and receive a |
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/ |
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. |
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. |
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. |
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 :
The problem I see is that initial channel balances need to be known in order to calculate the flow of the network |
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. 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. |
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:
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
The text was updated successfully, but these errors were encountered: