Elias Rohrer [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2018-08-29 to 2022-06-10
💬 Posted a total of 5 messages
📚 Participated in the following categories: Lightning-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-08-03 17:33:21

- reply

📅 Original date posted:2023-08-03
🗒️ Summary of this message: Long-term collection of proposed data could potentially re-identify anonymized channel counterparties, raising concerns about privacy and data storage.
📝 Original message:
Hi Carla + Clara,
I want to prefix this by saying that I'm very familiar with how limiting
the lack of available real-world datasets can be for conducting
significant simulations and empirical experiments on Lightning.
However, it may be noteworthy that long-term collection of the proposed
fields could potentially allow to re-identify the anonymized channel
counterparties based off some heuristics correlating with the public
graph data, especially when datasets from multiple (possibly
neighbouring) collection points will end up being combined.
Subsequently, this might allow to draw further conclusions on
transferred amounts, channel liquidities at particular times, and, as
HTLC settlement/failure timestamps are recorded in nanosecond
resolution, potentially even the payment destination's identity (cf.
[1]).
As surrendering this kind of data therefore requires a good level of
trust in the researchers, it might be helpful (and best practise) if you
could clarify upfront whether you intend to time-box the collection
period, where the data would be stored, and who would have access to it.
From my point of view clearly defining the collection period would also
be mandatory as we don't want to incentivise node operators to collect
and store HTLC data longer-term, especially if it's to this degree of
detail.
Best,
Elias
[1]: https://arxiv.org/pdf/2006.12143.pdf
> ### 1. Collect Anonymized Data
> We're aware that we are dealing with sensitive and private
> information.
> For this reason, we propose defining a common data format so that
> analysis tooling can be built around, so that node operators can run
> the analysis locally if desired. Fields marked with [P] *MUST* be
> randomized if exported to researching teams.
>
> The proposed format is a CSV file with the following fields:
> * version (uint8): set to 1, included to future-proof ourselves
> against the need to change this format.
> * channel_in (uint64)[P]: the short channel ID of the incoming channel
> that forwarded the HLTC.
> * channel_out (uint64)[P]: the short channel ID of the outgoing
> channel that forwarded the HTLC.
> * peer_in (hex string)[P]: the hex encoded pubkey of the remote peer
> for the channel_in.
> * peer_out (hex_string)[P]: the hex encoded pubkey of the remote peer
> for the channel_out.
> * fee_msat(uint64): the fee offered by the HTLC, expressed in msat.
> * outgoing_liquidity (float64): the portion of
> `max_htlc_value_in_flight` that is occupied on channel_out after the
> HTLC has been forwarded.
> * outgoing_slots (float64): the portion of `max_accepted_htlcs` that
> is occupied on channel_out after the HTLC has been forwarded.
> * ts_added_ns (uint64): the unix timestamp that the HTLC was added,
> expressed in nanoseconds.
> * ts_removed_ns (uint64): the unix timestamp that the HLTC was
> removed, expressed in nanoseconds.
> * htlc_settled (bool): set to 0 if the HTLC failed, and 1 if it was
> settled.
> * incoming_endorsed (int16): an integer indicating the endorsement
> status of the incoming HTLC (-1 if not present, otherwise set to the
> value in the incoming endorsement TLV).
> * outgoing_endorsed (int16): an integer indicating the endorsement
> status of the outgoing HTLC (-1 if not set, otherwise set to the
> value set in the outgoing endorsement TLV).
>
> Before we add endorsement signaling and setting via an experimental
> TLV, the last two values here will always be -1. The data is still
> incredibly useful in the meantime, and allows for easy update once the
> TLV is propagated through the network.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20230803/17adad5b/attachment.html>

2023-06-09 13:02:11

- reply

📅 Original date posted:2021-03-18
📝 Original message:
Dear René,
ah, it seems I overlooked that sentence. Thanks for clearing this up. I
agree, filtering based on probability and then weighing based on cost is
probably very similar to doing it vice versa.
Kind Regards,
Elias
On 18 Mar 2021, at 10:12, René Pickhardt wrote:
> Dear Elias,
>
> Thanks for your kind words!
>
> In the paper we suggest clients sort paths by probability but skip the
> ones
> that charge fees that are too high for a user, which could be defined
> in a
> user setting. I should have repeated that when I expressed that
> implicitly
> with this sentence in my mail:
>
> "This means that nodes which provide a lot of liquidity and thus
> utility
> might be able to charge higher fees (as long as they are small enough
> so
> that users are willing to pay them)"
>
> I think that is very similar to your suggestion and of course one
> could
> include not only fees but other criteria while filtering.
>
> In general I think it is reasonable to be aware of the most likely
> path as
> the inverse probability is the number of expected attempts. This if
> due to
> failures and updating the knowledge and channel probabilities the
> remaining
> path probabilities drop below a certain (configurable) value one might
> want
> to stop trying or consider a more expensive path.
>
> So if for example a user was to say I am willing to pay up to 0.5% of
> the
> amount in routing fees but after a few attempts the likeliest path has
> only
> a 0.01% chance a client could say something like: "it is very unlikely
> to
> deliver the payment but if you pay 0.7% fees there is a chance (want
> to
> try?)" Of course at some point onchain / opening a new channel might
> be
> cheaper which would contribute to the potential emerging fee market.
>
> Instead of filtering paths by fees one could also weight the
> probabilities
> with the fees. An easy (but maybe not optimal) approach for that would
> be
> to multiply the log probabilities (which have to be low for high
> success)
> with the fees. That being said I think the main important result is
> that we
> should always be aware of (multi)path probabilities during the trial
> and
> error phase especially in order to make splitting decisions and to
> determine when to stop trying
>
> Best Rene
>
> Elias Rohrer <lnml at tnull.de> schrieb am Do., 18. März 2021, 09:34:
>
>> Dear René,
>>
>> thank you for the great work!
>>
>> One quick question regarding the consequence you mentioned: it seems
>> plausible that manipulating the path choices would become harder, if
>> the
>> ability of doing so was correlated with the capacity locked in the
>> network.
>> However, if paths were only chosen regarding the probability of
>> payment
>> success (and neglecting accruing fees), couldn't high-capacity nodes
>> in
>> absence of competition simply raise their fee levels indefinitely,
>> since
>> they would be chosen regardless? Do you have any ideas how to protect
>> against this?
>>
>> I imagine that some kind of 'mixed' strategy could be reasonable, in
>> which
>> certain paths are pre-filtered based on the probability of payment
>> success,
>> and then the final path is selected along the lines of the currently
>> deployed fee rate/CLTV risk assessment?
>>
>> Kind Regards,
>>
>> Elias
>>
>> On 17 Mar 2021, at 13:50, René Pickhardt via Lightning-dev wrote:
>>
>> Dear fellow Lightning Network developers,
>>
>> I am very pleased to share with you some research progress [0] with
>> respect to achieving better payment path finding and a better
>> reliability
>> of the payment process.
>>
>> TL;DR summary: In payment (multi)path finding use the (multi)paths
>> with
>> the highest success probability instead of the shortest or cheapest
>> ones.
>> (multi)path success probability is the product of channel success
>> probabilities. Given current data crawled on the Network the channel
>> success probability grows with the capacity of the channel and with
>> smaller
>> amounts that are to be sent (which is both intuitively obvious).
>> (Multi)path success probability thus declines exponentially the more
>> uncertain channels are included.
>>
>> I understand that the actual payment path finding is not part of the
>> spec
>> but I think my results should be relevant to the list since:
>>
>> a) The payment pathfinding is currently based on trial and error
>> approach
>> which has consequences that have not been studied well in the context
>> of
>> the Lightning Network
>> b) All implementations will use some heuristics in order to achieve
>> pathfinding.
>> c) Quick path finding is a crucial for a good user experience.
>> d) The uncertainty of payment paths is frequently quoted as a major
>> criticism of the Lightning Network (c.f. [1]) and I believe the
>> methodology
>> of this paper can be used to address this.
>>
>> The main breakthrough is that a very simple model that puts the
>> uncertainty of channel balances at its heart. We belief the
>> uncertainty of
>> channel balance values is the main reason why some payments take
>> several
>> attempts and thus take more time. With the help of probability
>> theory we
>> are able to define the channel success and failure probabilities and
>> similarly (multi)path success and failure probabilities. Other
>> Failure
>> reasons could also be included to the probability distributions.
>>
>> With the help of crawling small samples of the network we observe
>> that the
>> probability distributions of the channel balances can be estimated
>> well
>> with a uniform distribution (which was a little bit surprising) but
>> leads
>> to surprisingly easy formulas. We are able to quantify the
>> uncertainty in
>> the channels and use negative Bernoulli trials to compute the
>> expected
>> number of attempts that are necessary to deliver a payment of a
>> particular
>> amount from one node to another participant of the network. This can
>> be
>> used to abort the trial and error path finding if the probability
>> becomes
>> to low (expected number of attempts too high)
>>
>> We can mathematically show what people already knew (and draw
>> conclusions
>> like the mentioned ones from it):
>>
>> a) smaller amounts have higher success probabilities
>> b) the success probability declines exponentially with the number of
>> uncertain channels in a (multi)path.
>> c) depending on the payment pair, amount and splitting strategy it
>> can be
>> decided into how many parts a payment should be split to achieve the
>> highest success probability.
>> d) In particular for small amounts splitting almost never makes
>> sense.
>>
>> We demonstrate that sorting paths by their descending success
>> probability
>> during the trial and error payment process (instead of currently used
>> heuristics like fees or route length) and updating the probabilities
>> from
>> current failures decreases the number of average attempts and
>> produces a
>> much faster delivery of payments.
>>
>> Additionally we looked what happened if BOLT14 [2] was implemented or
>> nodes otherwise would pro-actively rebalance their channels according
>> to
>> previous research [3] and realized that the observed prior
>> distribution
>> changes from uniform to normal. This is great as small payments
>> become even
>> more likely (as one would intuitively assume and as previously
>> showed) Our
>> results show that probabilisitic path finding on a rebalanced network
>> works
>> even better (as in fewer failed attempts) which is yet another hint
>> why
>> BOLT14 might be a good idea. However as mentioned the results can be
>> implemented even without BOLT14 or without other protocol changes by
>> any
>> implementation.
>>
>> One consequence from the paper that is not discussed heavily within
>> the
>> paper that I find pretty interesting is that if implementations
>> follow the
>> recommendation to use a probabilistic approach they will tend to
>> route
>> payments along high capacity channels. While the fee based routing
>> can
>> easily be gamed by dumping fees it is much harder to provide more
>> liquidity. And if done this would actually provide a service to the
>> network. This means that nodes which provide a lot of liquidity and
>> thus
>> utility might be able to charge higher fees (as long as they are
>> small
>> enough so that users are willing to pay them) which would probably
>> allow
>> the emergence of a real routing fee market.
>>
>> One note on the question of MPP: In the last couple weeks I have been
>> collaborating with Christian Decker. I belief (by using the
>> methodology
>> from this paper) to also have a definite solution to the question of:
>>
>> How to split a payment into k parts and how many funds to allocate to
>> each
>> path to increase the (multi)path success probability.
>>
>> While this is is not addressed in the attached paper as we still need
>> to
>> run evaluations I can already share that an equal sized split as used
>> in
>> the paper (and by some implementations) is not preferable as one can
>> easily
>> see from this example:
>> Imagine one is to deliver 100 satoshi and has to paths with 1
>> uncertain
>> channel on each path. The first of capacity 101 and the second of
>> 51.
>> Obviously trying to send 100 satoshi along the 101 capacity channel
>> is bad.
>> Similarly splitting 50/50 and sending 50 Satoshi along the 51 satoshi
>> capacity channel is also bad. Thus a split that allocates for example
>> 67
>> Satoshi to the 101 capacity and 33 to the 51 satoshi channel seems
>> way more
>> reasonable. Actually 75/25 would probably be the best solution for
>> such a
>> setting. And no it is only random coincident that a binary splitter
>> would
>> have arrived at that split eventually (after potential miss trials)
>> There is way more math theory of how to actually solve the
>> optimization
>> problem in the general case and how to find a split and paths that
>> maximizes the probability of the attempts. I cannot share these
>> results yet
>> but I am pretty confident that there will be updates on that end very
>> soon.
>>
>> with kind regards Rene
>>
>> [0]: https://arxiv.org/abs/2103.08576 Security and Privacy of
>> Lightning
>> Network Payments with Uncertain Channel Balances
>> [1]:
>> https://www.whatbitcoindid.com/podcast/peter-rizuns-lightning-critique-fud-or-fair
>> [2]: https://github.com/lightningnetwork/lightning-rfc/pull/780
>> [3]:
>> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002406.html
>>
>> --
>> https://www.rene-pickhardt.de
>>
>> Skype: rene.pickhardt
>>
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210318/c071a113/attachment-0001.html>

2023-06-09 13:02:10

- reply

📅 Original date posted:2021-03-18
📝 Original message:
Dear René,
thank you for the great work!
One quick question regarding the consequence you mentioned: it seems
plausible that manipulating the path choices would become harder, if the
ability of doing so was correlated with the capacity locked in the
network. However, if paths were only chosen regarding the probability of
payment success (and neglecting accruing fees), couldn't high-capacity
nodes in absence of competition simply raise their fee levels
indefinitely, since they would be chosen regardless? Do you have any
ideas how to protect against this?
I imagine that some kind of 'mixed' strategy could be reasonable, in
which certain paths are pre-filtered based on the probability of payment
success, and then the final path is selected along the lines of the
currently deployed fee rate/CLTV risk assessment?
Kind Regards,
Elias
On 17 Mar 2021, at 13:50, René Pickhardt via Lightning-dev wrote:
> Dear fellow Lightning Network developers,
>
> I am very pleased to share with you some research progress [0] with
> respect
> to achieving better payment path finding and a better reliability of
> the
> payment process.
>
> TL;DR summary: In payment (multi)path finding use the (multi)paths
> with the
> highest success probability instead of the shortest or cheapest ones.
> (multi)path success probability is the product of channel success
> probabilities. Given current data crawled on the Network the channel
> success probability grows with the capacity of the channel and with
> smaller
> amounts that are to be sent (which is both intuitively obvious).
> (Multi)path success probability thus declines exponentially the more
> uncertain channels are included.
>
> I understand that the actual payment path finding is not part of the
> spec
> but I think my results should be relevant to the list since:
>
> a) The payment pathfinding is currently based on trial and error
> approach
> which has consequences that have not been studied well in the context
> of
> the Lightning Network
> b) All implementations will use some heuristics in order to achieve
> pathfinding.
> c) Quick path finding is a crucial for a good user experience.
> d) The uncertainty of payment paths is frequently quoted as a major
> criticism of the Lightning Network (c.f. [1]) and I believe the
> methodology
> of this paper can be used to address this.
>
> The main breakthrough is that a very simple model that puts the
> uncertainty of channel balances at its heart. We belief the
> uncertainty of
> channel balance values is the main reason why some payments take
> several
> attempts and thus take more time. With the help of probability theory
> we
> are able to define the channel success and failure probabilities and
> similarly (multi)path success and failure probabilities. Other Failure
> reasons could also be included to the probability distributions.
>
> With the help of crawling small samples of the network we observe that
> the
> probability distributions of the channel balances can be estimated
> well
> with a uniform distribution (which was a little bit surprising) but
> leads
> to surprisingly easy formulas. We are able to quantify the
> uncertainty in
> the channels and use negative Bernoulli trials to compute the expected
> number of attempts that are necessary to deliver a payment of a
> particular
> amount from one node to another participant of the network. This can
> be
> used to abort the trial and error path finding if the probability
> becomes
> to low (expected number of attempts too high)
>
> We can mathematically show what people already knew (and draw
> conclusions
> like the mentioned ones from it):
>
> a) smaller amounts have higher success probabilities
> b) the success probability declines exponentially with the number of
> uncertain channels in a (multi)path.
> c) depending on the payment pair, amount and splitting strategy it can
> be
> decided into how many parts a payment should be split to achieve the
> highest success probability.
> d) In particular for small amounts splitting almost never makes sense.
>
> We demonstrate that sorting paths by their descending success
> probability
> during the trial and error payment process (instead of currently used
> heuristics like fees or route length) and updating the probabilities
> from
> current failures decreases the number of average attempts and produces
> a
> much faster delivery of payments.
>
> Additionally we looked what happened if BOLT14 [2] was implemented or
> nodes
> otherwise would pro-actively rebalance their channels according to
> previous
> research [3] and realized that the observed prior distribution changes
> from
> uniform to normal. This is great as small payments become even more
> likely
> (as one would intuitively assume and as previously showed) Our results
> show
> that probabilisitic path finding on a rebalanced network works even
> better
> (as in fewer failed attempts) which is yet another hint why BOLT14
> might be
> a good idea. However as mentioned the results can be implemented even
> without BOLT14 or without other protocol changes by any
> implementation.
>
> One consequence from the paper that is not discussed heavily within
> the
> paper that I find pretty interesting is that if implementations follow
> the
> recommendation to use a probabilistic approach they will tend to route
> payments along high capacity channels. While the fee based routing can
> easily be gamed by dumping fees it is much harder to provide more
> liquidity. And if done this would actually provide a service to the
> network. This means that nodes which provide a lot of liquidity and
> thus
> utility might be able to charge higher fees (as long as they are small
> enough so that users are willing to pay them) which would probably
> allow
> the emergence of a real routing fee market.
>
> One note on the question of MPP: In the last couple weeks I have been
> collaborating with Christian Decker. I belief (by using the
> methodology
> from this paper) to also have a definite solution to the question of:
>
> How to split a payment into k parts and how many funds to allocate to
> each
> path to increase the (multi)path success probability.
>
> While this is is not addressed in the attached paper as we still need
> to
> run evaluations I can already share that an equal sized split as used
> in
> the paper (and by some implementations) is not preferable as one can
> easily
> see from this example:
> Imagine one is to deliver 100 satoshi and has to paths with 1
> uncertain
> channel on each path. The first of capacity 101 and the second of 51.
> Obviously trying to send 100 satoshi along the 101 capacity channel is
> bad.
> Similarly splitting 50/50 and sending 50 Satoshi along the 51 satoshi
> capacity channel is also bad. Thus a split that allocates for example
> 67
> Satoshi to the 101 capacity and 33 to the 51 satoshi channel seems way
> more
> reasonable. Actually 75/25 would probably be the best solution for
> such a
> setting. And no it is only random coincident that a binary splitter
> would
> have arrived at that split eventually (after potential miss trials)
> There is way more math theory of how to actually solve the
> optimization
> problem in the general case and how to find a split and paths that
> maximizes the probability of the attempts. I cannot share these
> results yet
> but I am pretty confident that there will be updates on that end very
> soon.
>
> with kind regards Rene
>
> [0]: https://arxiv.org/abs/2103.08576 Security and Privacy of
> Lightning
> Network Payments with Uncertain Channel Balances
> [1]:
> https://www.whatbitcoindid.com/podcast/peter-rizuns-lightning-critique-fud-or-fair
> [2]: https://github.com/lightningnetwork/lightning-rfc/pull/780
> [3]:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002406.html
>
> --
> https://www.rene-pickhardt.de
>
> Skype: rene.pickhardt
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210318/e55f0d5d/attachment-0001.html>

2023-06-09 12:51:29

- reply

📅 Original date posted:2018-09-14
📝 Original message:
Hello Kulpreet,
Thank you for the interest in our work!
wrt. 1.: You are correct, message complexity could be one of the main challenges in the distributed case (~ O(n^3) in the asynchronous model, according to Goldberg et al.). While this is clearly unfeasible to run for every single payment, ideas like introducing rounds or batching payments could help with that. However, you are absolutely right that a lot more work would be needed to find an optimized distributed solution with feasible overhead.
wrt. 2.: Yes, replacing the route selection algorithm of the current source routing scheme with a flow-based approach should be possible and would be interesting to see. In particular, I would find it especially promising to combine such a flow-based approach with the atomic multi-path payment (AMP) scheme that was proposed in the beginning of this year.
So far, I have not looked into possible library candidates for a prototype implementation in the Go client. But maybe I should, as it seems exiting (now that I'm thinking about it ;)).
Ah, nice! I think, as a first idea, it could be enlightening (no pun intended) to even have a look at (average) maximum flows between all or random nodes. This could help to understand how much payment capacity can be unlocked by implementing a multi-path approach, such as AMP.
Thanks & Best Regards,
Elias
On 13 Sep 2018, at 14:55, Kulpreet Singh wrote:
> 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 <elias.rohrer at tu-berlin.de> 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 <r.pickhardt at googlemail.com> wrote:
>>
>> Hey Kulpreet,
>>
>> thanks for this nice overview article! I have just today implemented a first draft for the c-lightning autopilot [0]. I have implemented 4 heuristics to select nodes to which one could connect. On of those [1] samples from the nodes that contribute to the high diameter. This heuristic was included not to increase the utility of the node that is running the autopilot but to improve the network properties. I believe that this heuristic should also reduce the articulation points and biconnected components that you mention in your article. As endpoints of longest shortest paths will most likely be in two different biconnectivity components (at least if those exist and have a certain size).
>>
>> Regarding the centrality. I also calculated the betweeness centrality and have similar results [2] to yours. I guess the difference will be due to the fact that we don't work on the exact same snapshot. My autopilot implementation also connects to a few rather central nodes. I doubt this is useful for the network but I guess it is good for the node running the autopilot since it gains access to many nodes. ( Actually I think - but don't know - that in combination with [1] it even helps the network).
>>
>> Regarding your 200 Articulation points I would guess that many of those are just nodes that only have one channel with the node that acts as an articulation point. I guess this is not something that we would need to take care of so much since it is also in the responsibility of those nodes to have more than one channel. for larger biconnectivity components the problem would probably be resolved with the above mentioned heuristic. Therefor I believe looking at the articulation points should not be our main focus.
>>
>> Something that (regarding the autopilot) I am currently missing in your article is how much funds should be allocated for the suggested channels. I am currently experimenting with a probability density function that is proportional to the average capacity of each node in the candidate set. I smooth this with a uniform distribution. However simulations at this point are quite expensive (if done primitively since the centralities have to be recomputed) I guess this would be a nice future work. I will probably tomorrow publish the rest of the code for the lib-autopilot that uses this heuristic for channel balances since I am currently still working on it.
>>
>> If you consider working more on the autopilot but also on research related to this I would also suggest the following resources [3],[4] and [5]
>>
>> [0] https://github.com/ElementsProject/lightning/pull/1888
>> [1] https://github.com/renepickhardt/lightning/blob/8c91f57490b51f772513a274d679d3ab62e7201a/contrib/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 <zapfmann at gmail.com> 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-8102a59999f0
>>
>> Looking forward to your suggestions and feedback.
>>
>> Thanks
>> Kulpreet
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at 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 at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4970 bytes
Desc: S/MIME digital signature
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180914/cabf7fde/attachment.p7s>

2023-06-09 12:51:25

- reply

📅 Original date posted:2018-08-29
📝 Original message:
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
[1]: https://arxiv.org/abs/1708.02419
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 <r.pickhardt at googlemail.com> wrote:
>>
>> Hey Kulpreet,
>>
>> thanks for this nice overview article! I have just today implemented a first draft for the c-lightning autopilot [0]. I have implemented 4 heuristics to select nodes to which one could connect. On of those [1] samples from the nodes that contribute to the high diameter. This heuristic was included not to increase the utility of the node that is running the autopilot but to improve the network properties. I believe that this heuristic should also reduce the articulation points and biconnected components that you mention in your article. As endpoints of longest shortest paths will most likely be in two different biconnectivity components (at least if those exist and have a certain size).
>>
>> Regarding the centrality. I also calculated the betweeness centrality and have similar results [2] to yours. I guess the difference will be due to the fact that we don't work on the exact same snapshot. My autopilot implementation also connects to a few rather central nodes. I doubt this is useful for the network but I guess it is good for the node running the autopilot since it gains access to many nodes. ( Actually I think - but don't know - that in combination with [1] it even helps the network).
>>
>> Regarding your 200 Articulation points I would guess that many of those are just nodes that only have one channel with the node that acts as an articulation point. I guess this is not something that we would need to take care of so much since it is also in the responsibility of those nodes to have more than one channel. for larger biconnectivity components the problem would probably be resolved with the above mentioned heuristic. Therefor I believe looking at the articulation points should not be our main focus.
>>
>> Something that (regarding the autopilot) I am currently missing in your article is how much funds should be allocated for the suggested channels. I am currently experimenting with a probability density function that is proportional to the average capacity of each node in the candidate set. I smooth this with a uniform distribution. However simulations at this point are quite expensive (if done primitively since the centralities have to be recomputed) I guess this would be a nice future work. I will probably tomorrow publish the rest of the code for the lib-autopilot that uses this heuristic for channel balances since I am currently still working on it.
>>
>> If you consider working more on the autopilot but also on research related to this I would also suggest the following resources [3],[4] and [5]
>>
>> [0] https://github.com/ElementsProject/lightning/pull/1888
>> [1] https://github.com/renepickhardt/lightning/blob/8c91f57490b51f772513a274d679d3ab62e7201a/contrib/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 <zapfmann at gmail.com> 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-8102a59999f0
>>>
>>> Looking forward to your suggestions and feedback.
>>>
>>> Thanks
>>> Kulpreet
>>> _______________________________________________
>>> Lightning-dev mailing list
>>> Lightning-dev at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180829/3c71f054/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4970 bytes
Desc: S/MIME digital signature
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180829/3c71f054/attachment-0001.p7s>

2023-06-07 23:10:24

- reply

📅 Original date posted:2022-06-10
📝 Original message:Hi alicexbt,
Routing attacks have actually been studied quite a bit in literature.
You may be interested in the research articles of Maria Apostolaki et al.[1,2], Muoi Tran et al.[3], and related works.
Best,
Elias
[1]: https://arxiv.org/pdf/1605.07524.pdf
[2]: https://arxiv.org/pdf/1808.06254.pdf
[3]: https://allquantor.at/blockchainbib/pdf/tran2020stealthier.pdf
On 9 Jun 2022, at 20:24, alicexbt via bitcoin-dev wrote:
> Hi Bitcoin Developers,
>
> Based on this [answer][1] from 2014, bitcoin nodes are vulnerable to BGP hijacking. There was an incident in March 2022, twitter prefix was hijacked and details are shared in 2 blog posts:
>
> https://isc.sans.edu/diary/rss/28488
>
> https://www.manrs.org/2022/03/lesson-learned-twitter-shored-up-its-routing-security/
>
> 'nusenu' had written an article about Tor network being vulnerable to BGP hijacking attacks: https://nusenu.medium.com/how-vulnerable-is-the-tor-network-to-bgp-hijacking-attacks-56d3b2ebfd92
>
> After doing some research I found that RPKI ROA and BGP prefix length can help against BGP hijacking attacks. I checked BGP prefix length and RPKI ROA for first 10 IP addresses returned in `getnodeaddresses` in bitcoin core and it had vulnerable results.
>
> https://i.stack.imgur.com/KD7jH.png
>
> Has anyone written a detailed blog post or research article like nusenu? If not I would be interested to write one in next couple of weeks?
> Looking for some "technical" feedback, links if this was already discussed in past with some solutions.
>
> [1]: https://bitcoin.stackexchange.com/a/30305/133407
>
>
> /dev/fd0
>
> Sent with Proton Mail secure email.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev