Re: [Lightning-dev] Measuring centrality of nodes in LN graph
rib/lib-autopilot.py#L205 > [2] https://twitter.com/renepickhardt/status/1034066602273193985 > [3] https://github.com/lightningnetwork/lnd/issues/677 > [4] > https://github.com/renepickhardt/Automatically-Generating-a-Robust-Topology-for-the-Lightning-Network-on-top-of-Bitcoin > [5] > https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin/ > > best regards Rene > > > On Mon, Aug 27, 2018 at 11:59 PM Kulpreet Singh wrote: >> >> Hi all, >> >> I have been thinking about how we could measure the centrality of >> various nodes in the LN graph and the dependence on some nodes to >> route payments and to prevent network partitions. I think measuring >> and tracking the changes in key metrics could help the community >> decide on which nodes to open new channels with. >> >> I measured the centrality of nodes and the central point dominance as >> defined in the seminal paper by Lindon C. Freeman, "A Set of Measures >> of Centrality Based on Betweenness", Sociometry 40, pp. 35-41, 1977. >> >> I also measured the number of articulation points in the network as >> per Robert E. Tarjan, "Depth first search and linear graph algorithms" >> SIAM Journal on Computing, 1(2):146-160, 1972. >> >> I want to add, that this is just a start, I understand that we should >> probably look at treating LN as a directed graph and that we should do >> some work in trying to do some analysis based on treating LN as a flow >> network. >> >> However, I am eager to share my early results and would welcome any >> feedback or suggestions on the way forward. >> >> I wrote a medium post describing the approach and show my results >> there. I also elaborate on the choice of the two metrics and what they >> mean for LN. The post is available here: >> https://medium.com/@jungly/measuring-node-centrality-in-lightning-network-8102a5f0 >> >> Looking forward to your suggestions and feedback. >> >> Thanks >> Kulpreet >> ___ >> Lightning-dev mailing list >> Lightning-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > > > > -- > https://www.rene-pickhardt.de > > Skype: rene.pickhardt > > mobile: +49 (0)176 5762 3618 ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
[Lightning-dev] Measuring centrality of nodes in LN graph
Hi all, I have been thinking about how we could measure the centrality of various nodes in the LN graph and the dependence on some nodes to route payments and to prevent network partitions. I think measuring and tracking the changes in key metrics could help the community decide on which nodes to open new channels with. I measured the centrality of nodes and the central point dominance as defined in the seminal paper by Lindon C. Freeman, "A Set of Measures of Centrality Based on Betweenness", Sociometry 40, pp. 35-41, 1977. I also measured the number of articulation points in the network as per Robert E. Tarjan, "Depth first search and linear graph algorithms" SIAM Journal on Computing, 1(2):146-160, 1972. I want to add, that this is just a start, I understand that we should probably look at treating LN as a directed graph and that we should do some work in trying to do some analysis based on treating LN as a flow network. However, I am eager to share my early results and would welcome any feedback or suggestions on the way forward. I wrote a medium post describing the approach and show my results there. I also elaborate on the choice of the two metrics and what they mean for LN. The post is available here: https://medium.com/@jungly/measuring-node-centrality-in-lightning-network-8102a5f0 Looking forward to your suggestions and feedback. Thanks Kulpreet ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Measuring centrality of nodes in LN graph
Hi Elias, Thanks for the pointer to your excellent paper. I really enjoyed reading the idea of using locked flows to allow for a distributed execution for finding valid flows, which will enable discovering routes for payments. Pretty neat idea indeed. I just have few questions. My understanding might be incorrect and therefore I ask. 1. The distributed execution as proposed in the Goldberg paper requires a number of nodes to communicate with each other, essentially nodes are talking to their neighbours, but I imagine this results in a waterfall eventually as nodes talk their neighbours and so on. How do you see this working practically? Do you envision periodic route calculation phases, where all routing nodes collaborate even x seconds to help find routes for all the payments in that phase? This might result in the "instant payment" property of LN suffering a bit. I hope I understood the Goldberg approach and my question isn't completely off the hook. 2. If we leave the distributed execution aside for a moment and try the "feasible flow" approach from your paper and compare that to the current implementation in LN for route calculation, it might make for an interesting result. So the question is, do you have an implementation of the push-relable algorithm in Go that could be tried out in LN? Or have you see one as part of another lib? About my work to observe LN metrics, I was hoping to see if there were any metrics from the network flow literature that might be relevant to LN. Do you think any specific one might be interesting to track? Thanks again for sharing your paper Kulpreet On Wed, 29 Aug 2018 at 11:45, Elias Rohrer wrote: > > Hello Kulpreet, > > thank you a lot for your work, your post highlights some really interesting > results. > > I'm looking forward to your future work measuring the network's structure and > decentralization. Moreover, I find thinking about the LN as a flow network to > be a real interesting perspective. In fact, as an initial entry towards this > direction, we did some work on a multi-path routing algorithm based on the > push-relabel algorithm (cf. 1). However, I think there is much room for > improvement and other flow algorithms could turn out to be promising > candidates for routing in the LN. > > As far as I understood, you would be using flow algorithms for a more > in-depth analysis of the networks graph structure? > > Kind Regards, > > Elias > > On 29 Aug 2018, at 8:40, Kulpreet Singh wrote: > > Hi René, > > Thanks for sharing the links to the issues and the excellent work you are > doing. > > I see that you are quite interested in helping autopilot create a > graph such that is provides certain characteristics. It is quite a > challenging task, and I admire your courage to take it on. I saw your > lib-autopilot too, though I didn't take a closer look at the code yet. > > I am focussing on a much simpler task of figuring out which metrics > the community will find useful and then trying to determine which > algorithms we could quickly run to get some initial results while we > try to develop more pertinent analysis algorithms. > > I focussed on betweeness centrality and articulation points as > personally I was most curious about those. Next I want to try and > figure out which max-flow algorithm might suit LN the best. Have you > looked at this? I might have missed something you might have already > pointed to. > > I noticed your concern about tracking articulation points. I agree, > that once central point dominance goes down the dependence on some > important articulation points will go down too. But as I noticed in my > results, some nodes are high in the list of articulation points sorted > by the number of atleast 5 node biconnected components they connect > to. But their centrality is not that high. For example, > mainnet.lightningconductor.net is in the list of top articulation > points but does not make it to the list of top 20 nodes by centrality. > > I am still curious about articulation points and want to keep tracking > it, who knows we might learn something interesting by tracking the > information. > > I am curious how are you running your graph evaluations. Are you using > python binding to BGL or python networkx? > > I imagine we got slightly different results also because we used data > from different times. I intend to publish the json output I got from > LND when I get around to plotting my results on a chart so we can > verify I am not making an error somewhere. > > Thanks and regards > Kulpreet > > > On Tue, 28 Aug 2018 at 00:31, René Pickhardt > wrote: > > Hey Kulpreet, > > thanks for this nice overview article! I have just today implemented a first > draft for the c-lightn
Re: [Lightning-dev] Removing channel reserve for mobile wallet users
From my nascent understanding this will require differentiating between types of participants. Will the above then add complications of participant type into the protocol at the time of creating commitments, forwarding HTLCs and also finding routes? -kp --- Original Message --- On Wednesday, October 18th, 2023 at 3:51 PM, Bastien TEINTURIER wrote: > Good morning list, > > I'd like to discuss the channel reserve requirement, and argue that it > should be fine to get rid of it for channels between mobile wallet users > and their service provider. I know, I know, your first reaction will be > "but this is a security parameter, I don't want to hear about it", but > please bear with me (and I'll be happy to hear thoughts on why we should > *not* get rid of this requirement if you still feel strongly about that > after reading this post). > > Let's start by explaining why we generally want a channel reserve. It > ensures that both peers always have an output in the commit tx, which > has two important consequences: > > - if a malicious node publishes a revoked commitment, they will always > have some funds in it that the honest node can claim, so they risk > losing money > - nodes are disincentivized from force-closing channels, because they > will need to pay on-chain fees to get their funds back (through a > 2nd-stage transaction) > > I believe those are important properties for channels between normal > routing nodes that don't provide paid services to each other. If we > remove the channel reserve, and at one point in time, one of the nodes > has nothing at stake in the channel, they will be incentivized to > broadcast a revoked commit tx: if they get away with it, they win some > money, and otherwise, they don't lose any (because they have nothing at > stake in the latest channel state). This is particularly true for the > non-initiator, who doesn't pay the on-chain fees for the commit tx, > otherwise a malicious initiator would still lose on-chain fees. > > Now what are the drawbacks of having a channel reserve? The first one is > capital efficiency, because this channel reserve is unused liquidity. If > you are a routing node this is fine, because you actively manage your > channels to only keep those that earn you enough routing fees. But if > you are a wallet provider, this is a very different story: you need to > keep at least one channel open with each of your users. For each of > these channels, you must maintain a reserve of 1% of the channel > capacity, even if all the funds are on their side. You thus have unused > liquidity proportional to the number of users and the total amount of > sats your users own. This doesn't scale very well. > > The second drawback is UX: users look at their channel state to figure > out how much they can receive off-chain. It's really hard to explain > why there is a large gap between what they think they should be able > to receive and what they can actually receive. > > Now, why is it ok in this setting to remove the reserve on both sides? > First of all, the service provider is the one paying the on-chain fees > for the commit tx (at least that's what we do for Phoenix). That means > that when publishing a revoked commit tx, even if the service provider > doesn't have an output in the transaction, they still pay on-chain fees, > so they lose *something*. For the wallet user, this is ok: they still > get their funds back using penalty transactions, which doesn't cost > them more than normal 2nd-stage transactions. The service provider > cannot steal funds, it only lets them grief their users (at the cost > of paying on-chain fees and missing out on future routing fees). Also, > the wallet user can publicly show that the service provider published > a revoked commitment, which is bad for their reputation. > > Removing the reserve on the wallet user's side is a risk that the wallet > provider takes in order to guarantee a good UX. The user can grief the > service provider, but the griefing amount is limited. Also, the user has > paid fees to the wallet provider before that, because they must have > used the wallet to get into that state. This makes it an acceptable > trade-off for service providers. > > Lastly, we can also argue that LN-penalty without channel reserves is > similar to LN-symmetry (Eltoo). In Eltoo, a cheating node can always > publish a previous commitment: the honest node will simply be able to > replay the latest state on top of that commitment, and the cheating > node's only penalty is the on-chain fees they paid for that commit tx. > Here this is the same when the service provider is trying to cheat, > because they pay the on-chain fees for the commit tx. If this is ok > for Eltoo, why wouldn't it be ok now? > > Cheers, > Bastien___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
