<div dir="ltr">Matt wrote:<br>> I'm frankly still very confused why we're having these conversations now<br><br>1000% this!!<br><br>This entire conversation strikes me as extremely premature and backwards<br>tbh.  Someone experimenting with a new approach shouldn't prompt us to<br>immediately modify the protocol to better "fit" the approach, particularly<br>before any sort of comparative analysis has even been published. At this<br>point, to my knowledge we don't even have an independent implementation of<br>the algorithm that has been tightly integrated into an existing LN<br>implementation. We don't know in which conditions the algorithm excels, and<br>in which conditions this improvement is maybe negligible (likely when payAmt<br><< chanCapacity). <br><br>I think part of the difficulty here lies in the current lack of a robust<br>framework to use in comparing the efficacy of different approaches. Even in<br>this domain, there're a number of end traits to optimize for including: path<br>finding length, total CLTV delay across all shards, the amount of resulting<br>splits (goal should be consume less commitment space), attempt iteration<br>latency, amount/path randomization, path finding memory, etc, etc.<br><br>This also isn't the first time someone has attempted to adapt typical<br>flow-based algorithms to path finding in the LN setting. T-bast from ACINQ<br>initially attempted to adapt a greedy flow-based algorithm [1], but found<br>that a number of implementation related edge cases (he cites that the<br>min+max constraints in addition to the normal fee limit most implementations<br>as barriers to adapting the algorithm) led him to go with a simpler approach<br>to then iterate off of. I'd be curious to hear from T-bast w.r.t how this<br>new approach differs from his initial approach, and if he spots any<br>yet-to-be-recognized implementation level complexities to properly<br>integrating flow based algorithms into path finding.<br><br>> a) to my knowledge, no one has (yet) done any follow-on work to<br>> investigate pulling many of the same heuristics Rene et al use in a<br>> Dijkstras/A* algorithm with multiple passes or generating multiple routes<br>> in the same pass to see whether you can emulate the results in a faster<br>> algorithm without the drawbacks here,<br><br>lnd's current approach (very far from perfect, derived via satisficement)<br>has some similarities to the flow-based approach in its use of probabilities<br>to attempt to quantify the level of uncertainty of internal network channel<br>balances. <br><br>We start by assuming a config level a priori probability of any given route<br>working, we then take that, and the fee to route across a given link and<br>convert the two values into a scalar "distance/weight" (mapping to an<br>expected cost) we can plug into vanilla Dijkstras [2]. A fresh node uses<br>this value to compare routes instead of the typical hop count distance<br>metric. With a cold cache this doesn't really do much, but then we'll update<br>all the a priori probabilities with observations we gain in the wild. <br><br>If a node is able to forward an HTLC to the next hop, we boost their<br>probability (conditional on the amount forward/failed, so there's a bayesian<br>aspect). Each failure results in the probabilities of nodes being affected<br>differently (temp chan failure vs no next node, etc). For example, if we're<br>able to route through the first 3 hops of the route, but the final hop fails<br>with a temp chan failure. We'll rewards all the nodes with a success<br>probability amount (default rn is 95%) that applies when the amount being<br>carried is < that prior attempt. <br><br>As we assume balances are always changing, we then apply a half life decay<br>that slows increases a penalized probability back to the baseline. The<br>resulting algorithm starts with no information/memory, but then gains<br>information with each attempt (increasing and decreasing probabilities as a<br>function of the amount attempted and time that has passed since the last<br>attempt). The APIs also let you mark certain nodes as having a higher<br>apriori probability which can reduce the amount of bogus path exploration.<br>This API can be used "at scale" to create a sort of active learning system<br>that learns from the attempts of a fleet of nodes, wallets, trampoline<br>nodes, wallets, etc (some privacy caveats apply, though there're ways to<br>fuzz things a bit differential style).<br><br>Other knobs exist such as the min probability setting, which controls how<br>high a success probability a candidate edge needs to have before it is<br>explored. If the algo is exploring too many lackluster paths (and there're a<br>lot of these on mainnet due to normal balance imbalance), this value can be<br>increased which will let it shed a large number of edges to be explored.<br>When comparing this to the discussed approach that doesn't use any prior<br>memory, there may be certain cases that allows this algorithm to "jump" to<br>the correct approach and skip all the pre-processing and optimization that<br>may result in the same route, just with added latency before the initial<br>attempt. I'm skipping some other details like how we handle repeated<br>failures of a node's channels (there's a mechanism that penalizes them more<br>heavily, as the algo assumes most of the node's channels aren't well<br>maintained/balanced, so why waste time trying the other 900 channels).<br><br>Our approach differs more dramatically from this new approach further when<br>it comes to the question of how to split a payment either due to a failure,<br>or when it's necessary (amt > max(chanCapacities...)). lnd takes a very<br>a simple approach of just divides the problem in half (divide and conquer, so<br>fork into two instances of amt/2) and try again. The divide and conquer<br>approach typically means you'll end up with a minimal-ish amount of fees.<br>There's also a knob that lets you control the largest split size, which can<br>force the algo to split sooner, as otherwise it only splits when no route<br>exists (either we explored a ton and they all failed, or the payment amt is<br>larger than chan capacity).<br><br>The algo works pretty well when the probabilities combined with well tuning<br>of the parameters help the algorithm naturally ignore lower probability<br>routes during the edge relaxation step of Dijkstras. However if a client has<br>no prior observations (and didn't get any from say it's wallet provider or<br>w/e), then it can end up exploring poor routes for a while and eventually<br>hit the default timeout (particularly with a slow disk, but that'll be <div>optimized away in lnd 0.14).<br><br>One interesting area of research would be to investigate if a small amount<br>of flow pre-planning can help the algorithm effectively re-summarize its<br>current working memory to ignore more paths we know likely won't work. </div><div><br></div><div>In the end, there's still so much of the design space that needs exploring,<br>so settling on something (and advertising that everything is solved by<br>magically setting a particular value to zero) that appears (so far we're<br>going mainly off of experimental anecdotes w/ unclear methods) to improve on<br>things in certain scenarios, and morphing the protocol around it is a<br>premature declaration of "Mission Accomplished!".</div><div><br></div><div>In any case, major kudos to Rene and Stefan for examining the problem in a new<br>light, and re-invigorating research of related areas!<br><br>-- Laolu<br><br><br>[1]: <a href="https://github.com/ACINQ/eclair/pull/1427">https://github.com/ACINQ/eclair/pull/1427</a><br>[2]: <a href="https://github.com/lightningnetwork/lnd/blob/958119a12ab60d24c75c7681f344ceb5a450c4ad/routing/pathfind.go#L930">https://github.com/lightningnetwork/lnd/blob/958119a12ab60d24c75c7681f344ceb5a450c4ad/routing/pathfind.go#L930</a><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Aug 15, 2021 at 5:07 PM Matt Corallo <<a href="mailto:lf-lists@mattcorallo.com">lf-lists@mattcorallo.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Thanks, AJ, for kicking off the thread.<br>
<br>
I'm frankly still very confused why we're having these conversations now. In one particular class of applicable routing <br>
algorithms you could use for lightning routing having a base fee makes the algorithm intractably slow, but:<br>
<br>
a) to my knowledge, no one has (yet) done any follow-on work to investigate pulling many of the same heuristics Rene et <br>
al use in a Dijkstras/A* algorithm with multiple passes or generating multiple routes in the same pass to see whether <br>
you can emulate the results in a faster algorithm without the drawbacks here,<br>
<br>
b) to my knowledge, no one has (yet) done any follow-on work to investigate mapping the base fee to other, more <br>
flow-based-routing-compatible numbers, eg you could convert the base fee to a minimum fee by increasing the "effective" <br>
proportional fees. From what others have commented, this may largely "solve" the issue.<br>
<br>
c) to my knowledge, no one has (yet) done any follow-on work to analyze where the proposed algorithm may be most optimal <br>
in the HTLC-value<->channel liquidity ratio ranges. We may find that the proposed algorithm only provides materially <br>
better routing when the HTLC value approaches X% of common network channel liquidity, allowing us to only use it for <br>
large-value payments where we can almost ignore the base fees entirely.<br>
<br>
There's real cost to distorting the fee structures on the network away from the costs of node operators, especially as <br>
we move towards requiring and using Real (tm) amounts of capital on routing nodes. If we're relying purely on hobbyists <br>
forever who are operating out of goodwill, we should just remove all fees. If we think Lightning is going to involve <br>
capital with real opportunity cost, matching fees to the costs is important, or at least important enough that we <br>
shouldn't throw it away after one (pretty great) paper and limited further analysis.<br>
<br>
Imagine we find some great way to address HTLC slot flooding/DoS attacks (or just chose to do it in a not-great way) by <br>
charging for HTLC slot usage, now we can't fix a critical DoS issue because the routing algorithms we deployed can't <br>
handle the new costing. Instead, we should investigate how we can apply the ideas here with the more complicated fee <br>
structures we have.<br>
<br>
Color me an optimist, but I'm quite confident with sufficient elbow grease and heuristics we can get 95% of the way <br>
there. We can and should revisit these conversations if such exploration is done and we find that its not possible, but <br>
until then this all feels incredibly premature.<br>
<br>
Matt<br>
<br>
On 8/14/21 21:00, Anthony Towns wrote:<br>
> Hey *,<br>
> <br>
> There's been discussions on twitter and elsewhere advocating for<br>
> setting the BOLT#7 fee_base_msat value [0] to zero. I'm just writing<br>
> this to summarise my understanding in a place that's able to easily be<br>
> referenced later.<br>
> <br>
> Setting the base fee to zero has a couple of benefits:<br>
> <br>
>   - it means you only have one value to optimise when trying to collect<br>
>     the most fees, and one-dimensional optimisation problems are<br>
>     obviously easier to write code for than two-dimensional optimisation<br>
>     problems<br>
> <br>
>   - when finding a route, if all the fees on all the channels are<br>
>     proportional only, you'll never have to worry about paying more fees<br>
>     just as a result of splitting a payment; that makes routing easier<br>
>     (see [1])<br>
> <br>
> So what's the cost? The cost is that there's no longer a fixed minimum<br>
> fee -- so if you try sending a 1sat payment you'll pay 0.1% of the fee<br>
> to send a 1000sat payment, and there may be fixed costs that you have<br>
> in routing payments that you'd like to be compensated for (eg, the<br>
> computational work to update channel state, the bandwith to forward the<br>
> tx, or the opportunity cost for not being able to accept another htlc if<br>
> you've hit your max htlcs per channel limit).<br>
> <br>
> But there's no need to explicitly separate those costs the way we do<br>
> now; instead of charging 1sat base fee and 0.02% proportional fee,<br>
> you can instead just set the 0.02% proportional fee and have a minimum<br>
> payment size of 5000 sats (htlc_minimum_msat=5e6, ~$2), since 0.02%<br>
> of that is 1sat. Nobody will be asking you to route without offering a<br>
> fee of at least 1sat, but all the optimisation steps are easier.<br>
> <br>
> You could go a step further, and have the node side accept smaller<br>
> payments despite the htlc minimum setting: eg, accept a 3000 sat payment<br>
> provided it pays the same fee that a 5000 sat payment would have. That is,<br>
> treat the setting as minimum_fee=1sat, rather than minimum_amount=5000sat;<br>
> so the advertised value is just calculated from the real settings,<br>
> and that nodes that want to send very small values despite having to<br>
> pay high rates can just invert the calculation.<br>
> <br>
> I think something like this approach also makes sense when your channel<br>
> becomes overloaded; eg if you have x HTLC slots available, and y channel<br>
> capacity available, setting a minimum payment size of something like<br>
> y/2/x**2 allows you to accept small payments (good for the network)<br>
> when you're channel is not busy, but reserves the last slots for larger<br>
> payments so that you don't end up missing out on profits because you<br>
> ran out of capacity due to low value spam.<br>
> <br>
> Two other aspects related to this:<br>
> <br>
> At present, I think all the fixed costs are also incurred even when<br>
> a htlc fails, so until we have some way of charging failing txs for<br>
> incurring those costs, it seems a bit backwards to penalise successful<br>
> txs who at least pay a proportional fee for the same thing. Until we've<br>
> got a way of handling that, having zero base fee seems at least fair.<br>
> <br>
> Lower value HTLCs don't need to be included in the commitment transaction<br>
> (if they're below the dust level, they definitely shouldn't be included,<br>
> and if they're less than 1sat they can't be included), and as such don't<br>
> incur all the same fixed costs that HTLCs that are committed too do.<br>
> Having different base fees for microtransactions that incur fewer costs<br>
> would be annoying; so having that be "amortised" into the proportional<br>
> fee might help there too.<br>
> <br>
> I think eltoo can help in two ways by reducing the fixed costs: you no<br>
> longer need to keep HTLC information around permanently, and if you do<br>
> a multilevel channel factory setup, you can probably remove the ~400<br>
> HTLCs per channel at any one time limit. But there's still other fixed<br>
> costs, so I think that would just lower the fixed costs, not remove them<br>
> altogether and isn't a fundamental change.<br>
> <br>
> I think the fixed costs for forwarding a HTLC are very small; something<br>
> like:<br>
> <br>
>     0.02sats -- cost of permanently storing the HTLC info<br>
>                 (100 bytes, $500/TB/year, 1% discount rate)<br>
>     0.04sats -- compute and bandwidth cost for updating an HTLC ($40/month<br>
>                 at linode, 1 second of compute)<br>
> <br>
> The opportunity cost of having HTLC slots or Bitcoin locked up until<br>
> the HTLC succeeds/fails could be much more significant, though.<br>
> <br>
> Cheers,<br>
> aj<br>
> <br>
> [0] <a href="https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md#the-channel_update-message" rel="noreferrer" target="_blank">https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md#the-channel_update-message</a><br>
> [1] <a href="https://basefee.ln.rene-pickhardt.de/" rel="noreferrer" target="_blank">https://basefee.ln.rene-pickhardt.de/</a><br>
> <br>
> _______________________________________________<br>
> Lightning-dev mailing list<br>
> <a href="mailto:Lightning-dev@lists.linuxfoundation.org" target="_blank">Lightning-dev@lists.linuxfoundation.org</a><br>
> <a href="https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev</a><br>
> <br>
_______________________________________________<br>
Lightning-dev mailing list<br>
<a href="mailto:Lightning-dev@lists.linuxfoundation.org" target="_blank">Lightning-dev@lists.linuxfoundation.org</a><br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev</a><br>
</blockquote></div>