📅 Original date posted:2022-03-14
📝 Original message:
Hi Rene,
On Mon, Mar 14, 2022 at 12:56:24PM +0100, René Pickhardt via Lightning-dev wrote:
> > 1) What's the reasoning behind combining parallel channels?
> I think that should work and especially when including fees to the
> cost function and considering how nodes handle routing requests on
> parallel channels we might have to do so anyway.
I think lnd accepts the minimum fee of all parallel channels, even if
a higher fee rate is configured for the channel that is actually used.
I'm not too sure about this, though. Having parallel channels with
different fee settings seems weird to me, anyway.
> 1.1) A payment of size 2 needs to be split into 1+1 to fit through
> However I believe in practice one cannot just send a 2 satoshi onion and
> expect the routing node to split the amount correctly / accordingly
> between the two parallel channels. (I might be wrong here).
Exactly. This kind of split could be possible in theory, but at least
lnd doesn't do it. I guess there are lots of interesting questions to
answer before this becomes reality (channel jamming?).
> So in that case
> modelling and computing probabilities for parallel channels might be
> necessary anyway though the math indicates that splitting liquidity in
> parallel channels will get you selected less frequently for routing.
Which is OK, as in reality it IS less likely to succeed.
> 1.2) The Mission Control information provided by lnd [...]
> I think you talk a about a maximum available balance of a channel (and not
> min available balance)?
Yes, although MC also has information about "known" amounts (due to
failures that only happened further down the road).
> In the case of parallel channels I am not even sure if such information is
> accurate as it is my understanding that the routing node may decide to use
> the parallel channel to forward the amount even though the other channel
> was specified in the onion.
The routing node is free to pick any of the parallel channels, yes. The
MC data only reasons about pairs of nodes, though, not individual
channels.
> Assuming that routing nodes indeed do so we would have learnt that neither
> channel has an effective capacity of N. So the combined virtual channel
> could be seen as 2N-1.
You mean 2(N-1) = 2N-2?
> However if routing nodes don't locally split a
> forwarding request across both channels we would know that calaculating
> with 2N-1 is bad as a request of N could not be fulfilled.
Exactly, also for 2N-2. Only N-1 would be a reasonable assumption.
Based on your responses I'll treat parallel channels individually, and
see how it works out.
> > 3) Size of Piecewise Linearization
> The main difference here is that a channel of 1 BTC is highly preferable
> from a probabilistic payment delivery perspective over a channel of 0.01
> BTC. Even approximating the 1 BTC channel with 1000 intervalls of 0.001 BTC
> should still have a lower unit cost in all pieces of the first 0.01 BTC of
> the liquidity than the first piece of the 0.01 BTC channel. So I think
> splitting all channels in the equal number of pieces is pretty well
> motivated but let me elaborate on this:
OK great, got it.
> > 4) Leftovers after Piecewise Linearization
> I am not sure if I understand your question / issue here. The splitting
> works by selecting N points on the domain of the function and splitting the
> domain into segments at those points. This should never leave sats over.
With quantization of 10,000 a channel of size 123,456 ends up as an arc
with a capacity of 12 units. Cutting this into 5 pieces gives us
5*2 with 2 units not ending up in any of those pieces. Or am I missing
something here, and we should split into 5 pieces of size 2.4 = 12/5?
> If the quantization however makes a channel so small that we cannot
> even create 5 (or N) disjoint segments then I guess the likelihood for
> being included into the final result is too small anyway.
It may not be very likely, but flat-out ignoring 20k sat (in my
contrived example above) or up to 4*quantization sats (which is the case
you described) doesn't feel right.
> Again this yield interesting pruning opportunities to reduce the seize of
> the network before doing the expensive min cost flow computation. For
> example I could prune channels with high unit costs on the first segment.
> Especially if they are further away from the source and destination node.
> This would overall reduce the size of the graph and improve runtime.
Let's talk about optimizations later :)
> 5) Fees (and other properties?)
> arcs.append((src,dest,int(cap/(N*QUANTIZATION)),(i+1)*unit_cost +
> mu*fee_rate_ppm))
Great, that helps! Thanks alot!
> Note two things:
> 1. the only requirement for the solver to work is that \mu*fee_rate_ppm
> needs to be an integer. So in case \mu was smaller than 1 we could also
> scale the term from the linearized log probabilities by putting a larger mu
> to the feature arising from the cost of the uncertainty.
Good to know!
Bye,
Carsten
--
Dr. Carsten Otto
carsten at c-otto.de
https://c-otto.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220314/2418fb43/attachment.sig>;
Carsten Otto [ARCHIVE] /
npub13f…tgaqs
2023-06-09 13:05:31
in reply to nevent1q…nfcc
Author Public Key
npub13fccestrh5xf26m53n73xn5yly9z040a4n9vq30mernkj0cqszuq9tgaqsPublished at
2023-06-09 13:05:31Event JSON
{
"id": "b9f5e18ccc68fd6af93a42ea864ef3377eed8f1343f50b894795a1329244ab0e",
"pubkey": "8a718cc163bd0c956b748cfd134e84f90a27d5fdaccac045fbc8e7693f0080b8",
"created_at": 1686315931,
"kind": 1,
"tags": [
[
"e",
"23813e61141e9c848ba0b144e5a9930e93968efb778b53acea9487b101f83f67",
"",
"root"
],
[
"e",
"01ccc008c7d4cb1ad5c828d5bc7f00188640fe4d4cb994d881c255629c892212",
"",
"reply"
],
[
"p",
"17ccd89be295c0ae65f1cd3740a9dad84ec8b6d7050712a7f04ae5284b2fab99"
]
],
"content": "📅 Original date posted:2022-03-14\n📝 Original message:\nHi Rene,\n\nOn Mon, Mar 14, 2022 at 12:56:24PM +0100, René Pickhardt via Lightning-dev wrote:\n\u003e \u003e 1) What's the reasoning behind combining parallel channels?\n\u003e I think that should work and especially when including fees to the\n\u003e cost function and considering how nodes handle routing requests on\n\u003e parallel channels we might have to do so anyway.\n\nI think lnd accepts the minimum fee of all parallel channels, even if\na higher fee rate is configured for the channel that is actually used.\nI'm not too sure about this, though. Having parallel channels with\ndifferent fee settings seems weird to me, anyway.\n\n\u003e 1.1) A payment of size 2 needs to be split into 1+1 to fit through\n\u003e However I believe in practice one cannot just send a 2 satoshi onion and\n\u003e expect the routing node to split the amount correctly / accordingly\n\u003e between the two parallel channels. (I might be wrong here).\n\nExactly. This kind of split could be possible in theory, but at least\nlnd doesn't do it. I guess there are lots of interesting questions to\nanswer before this becomes reality (channel jamming?).\n\n\u003e So in that case\n\u003e modelling and computing probabilities for parallel channels might be\n\u003e necessary anyway though the math indicates that splitting liquidity in\n\u003e parallel channels will get you selected less frequently for routing.\n\nWhich is OK, as in reality it IS less likely to succeed.\n\n\u003e 1.2) The Mission Control information provided by lnd [...]\n\u003e I think you talk a about a maximum available balance of a channel (and not\n\u003e min available balance)?\n\nYes, although MC also has information about \"known\" amounts (due to\nfailures that only happened further down the road).\n\n\u003e In the case of parallel channels I am not even sure if such information is\n\u003e accurate as it is my understanding that the routing node may decide to use\n\u003e the parallel channel to forward the amount even though the other channel\n\u003e was specified in the onion.\n\nThe routing node is free to pick any of the parallel channels, yes. The\nMC data only reasons about pairs of nodes, though, not individual\nchannels.\n\n\u003e Assuming that routing nodes indeed do so we would have learnt that neither\n\u003e channel has an effective capacity of N. So the combined virtual channel\n\u003e could be seen as 2N-1.\n\nYou mean 2(N-1) = 2N-2?\n\n\u003e However if routing nodes don't locally split a\n\u003e forwarding request across both channels we would know that calaculating\n\u003e with 2N-1 is bad as a request of N could not be fulfilled.\n\nExactly, also for 2N-2. Only N-1 would be a reasonable assumption.\n\nBased on your responses I'll treat parallel channels individually, and\nsee how it works out.\n\n\u003e \u003e 3) Size of Piecewise Linearization\n\u003e The main difference here is that a channel of 1 BTC is highly preferable\n\u003e from a probabilistic payment delivery perspective over a channel of 0.01\n\u003e BTC. Even approximating the 1 BTC channel with 1000 intervalls of 0.001 BTC\n\u003e should still have a lower unit cost in all pieces of the first 0.01 BTC of\n\u003e the liquidity than the first piece of the 0.01 BTC channel. So I think\n\u003e splitting all channels in the equal number of pieces is pretty well\n\u003e motivated but let me elaborate on this:\n\nOK great, got it.\n\n\u003e \u003e 4) Leftovers after Piecewise Linearization\n\u003e I am not sure if I understand your question / issue here. The splitting\n\u003e works by selecting N points on the domain of the function and splitting the\n\u003e domain into segments at those points. This should never leave sats over.\n\nWith quantization of 10,000 a channel of size 123,456 ends up as an arc\nwith a capacity of 12 units. Cutting this into 5 pieces gives us\n5*2 with 2 units not ending up in any of those pieces. Or am I missing\nsomething here, and we should split into 5 pieces of size 2.4 = 12/5?\n\n\u003e If the quantization however makes a channel so small that we cannot\n\u003e even create 5 (or N) disjoint segments then I guess the likelihood for\n\u003e being included into the final result is too small anyway.\n\nIt may not be very likely, but flat-out ignoring 20k sat (in my\ncontrived example above) or up to 4*quantization sats (which is the case\nyou described) doesn't feel right.\n\n\u003e Again this yield interesting pruning opportunities to reduce the seize of\n\u003e the network before doing the expensive min cost flow computation. For\n\u003e example I could prune channels with high unit costs on the first segment.\n\u003e Especially if they are further away from the source and destination node.\n\u003e This would overall reduce the size of the graph and improve runtime.\n\nLet's talk about optimizations later :)\n\n\u003e 5) Fees (and other properties?)\n\u003e arcs.append((src,dest,int(cap/(N*QUANTIZATION)),(i+1)*unit_cost +\n\u003e mu*fee_rate_ppm))\n\nGreat, that helps! Thanks alot!\n\n\u003e Note two things:\n\u003e 1. the only requirement for the solver to work is that \\mu*fee_rate_ppm\n\u003e needs to be an integer. So in case \\mu was smaller than 1 we could also\n\u003e scale the term from the linearized log probabilities by putting a larger mu\n\u003e to the feature arising from the cost of the uncertainty.\n\nGood to know!\n\nBye,\nCarsten\n-- \nDr. Carsten Otto\ncarsten at c-otto.de\nhttps://c-otto.de\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: signature.asc\nType: application/pgp-signature\nSize: 195 bytes\nDesc: not available\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220314/2418fb43/attachment.sig\u003e",
"sig": "52281d13f2a586d548743394bd95edf21cf047e70d90eacde76dee817bde895030fcb0cf0e533ca6d3c1a661d782b36edeb3674993a814638378811de0c9ea24"
}