--- Log opened Sun Aug 23 00:00:57 2020
00:40 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 240 seconds]
00:47 -!- mdunnio [~mdunnio@208.59.170.5] has joined #c-lightning
00:52 -!- mdunnio [~mdunnio@208.59.170.5] has quit [Ping timeout: 265 seconds]
01:03 -!- blockstream_bot [blockstrea@gateway/shell/sameroom/x-dgxzrzsddndesmel] has left #c-lightning []
01:03 -!- blockstream_bot [blockstrea@gateway/shell/sameroom/x-dgxzrzsddndesmel] has joined #c-lightning
01:17 -!- fjahr [sid374480@gateway/web/irccloud.com/x-fkccgjyyhbxwqmut] has quit [Ping timeout: 260 seconds]
01:18 -!- fjahr [sid374480@gateway/web/irccloud.com/x-ljdthgnwgzteqqfh] has joined #c-lightning
01:20 -!- liberliver [~Thunderbi@x4db72988.dyn.telefonica.de] has joined #c-lightning
01:23 -!- liberliver1 [~Thunderbi@144.49.211.130.bc.googleusercontent.com] has joined #c-lightning
01:24 -!- liberliver [~Thunderbi@x4db72988.dyn.telefonica.de] has quit [Ping timeout: 246 seconds]
01:24 -!- liberliver1 is now known as liberliver
01:26 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #c-lightning
01:56 -!- mdunnio [~mdunnio@208.59.170.5] has joined #c-lightning
02:21 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #c-lightning
02:47 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Quit: jonatack]
02:52 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #c-lightning
02:56 -!- mdunnio [~mdunnio@208.59.170.5] has quit [Remote host closed the connection]
03:26 <@cdecker> zmnscpxj__: can't find it anymore, but I'm sure I mentioned this somewhere. How about we snap the presplit to the closest multiple of 10000 * 16^n, where n is the smallest n such that the result is larger or equal to the amount being sent?
03:27 < zmnscpxj__> https://github.com/ElementsProject/lightning/pull/3942#issuecomment-674510063
03:27 < zmnscpxj__> I think fibonacci split is better, so I implemented that in #3951
03:27 <@cdecker> That'd limit the number of initial splits to 1 - 16 parts, while still bucketizing the part amounts into global buckets (i.e., not directly dependendent on the initial amount, only on the order of magnitude)
03:28 <@cdecker> I'm unclear as to what Fibonacci brings to the table, other than being yet another series that we can align to
03:28 < zmnscpxj__> https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-August/002778.html
03:29 <@cdecker> IMHO if we split into a fibonacci sequence it still is way easier to reconstruct the original amount rather than having global buckets
03:30 <@cdecker> No, strike that, it works as you describe, but the choice of fibonacci "because it grows quicker than simple power of two" seems obscure to me
03:30 < zmnscpxj__> I conjecture that fibonacci lets us utilize the same capacity on channels with fewer splits, than if we were always dividing by 2
03:30 <@cdecker> That divisor is hell to work with on a binary system, when we could just use other powers of two
03:31 < zmnscpxj__> i.e. given a random channel capacity, it is more likely that a fibonacci schedule will require fewer splits to utilize the same % of that capacity
03:31 <@cdecker> Any literature that could be used to prove that conjecture?
03:31 < zmnscpxj__> just that post
03:31 < zmnscpxj__> as well as the use of generalized fibonacci sequences in memory allocation
03:32 <@cdecker> Ok, I'll have to read up on that then
03:33 < zmnscpxj__> I can implement the 16^n thing as well if you wish, but tomorrow.  For now I am packing on PSBT-based PRs, since you are supposedly on vacation
03:33 <@cdecker> Just want to make sure I understand the advantage of using a fibonacci sequence before locking that choice in (since that'll pretty much be the buckets we'll align on globally for the foreseeable future to improve privacy)
03:34 <@cdecker> No hurry, I think you're onto something with fibonacci, but want to make sure it's the right choice first :-)
03:35 -!- mdunnio [~mdunnio@208.59.170.5] has joined #c-lightning
03:36 < zmnscpxj__> more intuitively: if a channel is failing to forward because of channel capacity, then if we split by fibonacci and try the larger split first, if the first fails to fit, we can retry with the second, smaller split
03:37 < zmnscpxj__> whereas if we split the payment in half, if the first split fails to fit, the second (which is approximately equal to that) is also very likely not going to fit
03:38 < zmnscpxj__> so it seems to me that splitting in half is actually the worst possible thing to try
03:39 < zmnscpxj__> so the splitting point has to be something a little *off* half, but not so large that you would be wasting all your time trying slightly-smaller splits
03:39 <@cdecker> That expects sequential attempts though, doesn't it?
03:39 -!- mdunnio [~mdunnio@208.59.170.5] has quit [Ping timeout: 240 seconds]
03:40 < zmnscpxj__> yes, but our `getroute` impl is sequential anyway :P
03:40 < zmnscpxj__> might be useful to add some kind of sequentialization where we try to getroute one split first and then  the other split
03:42 < zmnscpxj__> On the other hand, even if the smaller split enters the channel first, the larger split can also split into the same value, plus another even smaller split that, when added to the existing smaller split, equals the original larger split
03:42 <@cdecker> But it can still come back to bite us: assume a payment split according to fibonacci into A (large) and B (small). The initial attempt tries B on a channel that'd fit `A + eps` while A is attempted on a payment that'd fit `B+eps`. So B succeeds, and A fails. But the `A+eps` now doesn't fit A anymore since B already used up some capacity
03:42 < zmnscpxj__> i.e. if you split N to a + b[0], a splits to b[1] + c, and if a would have fit, then b[0] + c would sum up to a
03:43 < zmnscpxj__> Yes, but A splits into B + C, and we can try to the C now
03:43 < zmnscpxj__> which is the nice thing about fibonacci
03:43 <@cdecker> We can repeat that game however often we want, and we can still end up splitting more than necessary
03:43 < zmnscpxj__> yes
03:44 < zmnscpxj__> so it would be nice if we can assure that larger splits get tried first
03:44 <@cdecker> Since you present a memory allocation comparison, I think that might presume knowledge of the buckets at our disposal, which we don't have in our case
03:44 < zmnscpxj__> was thinking of adding a delay, but first we need to convince ourselves that fibonacci is the way to go
03:44 <@cdecker> Damn, why did I give up on the routing simulation framework
03:45 < zmnscpxj__> Note that a memory allocator implementation does not know how much memory the program will use, or the system it is running on to have
03:45 < zmnscpxj__> it has to somehow adapt to all conditions in runtime
03:45 < zmnscpxj__> just as we have to adapt to all conditions in pay-time
03:45  * cdecker jots down the notes for a student thesis that'd consider optimal routing in our scenario
03:46 < zmnscpxj__> memory the program will use ~= invoice amount we want to pay for
03:47 < zmnscpxj__> memory the system has ~= channel capacities we have to push payments through
03:47 < zmnscpxj__> and memory allocators handling memory blocks know that each split of the memory they are allocating has to take up memory in metadata managing that memory
03:47 < zmnscpxj__> which also approximates our HTLC cost overheads/limits
03:48 <@cdecker> Yes, but in a memory allocator we know the exact patches of memory that we can use, whereas in LN routing we have upper bounds that may be several orders of magnitude off
03:48 < zmnscpxj__> which is why I trawled memory allocator algos
03:48 < zmnscpxj__> and if the OS says "not enough memory" what can your mem allocator do? Try to fob less memory off the OS
03:48 < zmnscpxj__> same thing as when a hop node says "not enough sats"
03:50 < zmnscpxj__> sure, it is not an exact fit
03:50 < zmnscpxj__> but we have to start *somewhere* lol
03:51 <@cdecker> True, and the similarities are quite nice :+1: But somehow I always end up in the devils advocate role :-)
03:51 < zmnscpxj__> well, memory allocation was the nearest existing algo I could find
03:52 < zmnscpxj__> dunno if there are other algos nearer to our case of figuring out how to allocate how much sats to which channels
03:55 -!- vasild_ [~vd@gateway/tor-sasl/vasild] has joined #c-lightning
03:58 -!- vasild [~vd@gateway/tor-sasl/vasild] has quit [Ping timeout: 240 seconds]
03:58 -!- vasild_ is now known as vasild
05:05 -!- mdunnio [~mdunnio@208.59.170.5] has joined #c-lightning
05:09 -!- mdunnio [~mdunnio@208.59.170.5] has quit [Ping timeout: 240 seconds]
05:16 -!- mdunnio [~mdunnio@208.59.170.5] has joined #c-lightning
05:20 -!- mdunnio [~mdunnio@208.59.170.5] has quit [Ping timeout: 240 seconds]
07:06 -!- zmnscpxj__ [~zmnscpxj@gateway/tor-sasl/zmnscpxj] has quit [Ping timeout: 240 seconds]
08:51 -!- justanotheruser [~justanoth@unaffiliated/justanotheruser] has quit [Ping timeout: 240 seconds]
09:09 -!- blockstream_bot [blockstrea@gateway/shell/sameroom/x-dgxzrzsddndesmel] has left #c-lightning []
09:09 -!- blockstream_bot [blockstrea@gateway/shell/sameroom/x-dgxzrzsddndesmel] has joined #c-lightning
09:16 -!- justanotheruser [~justanoth@unaffiliated/justanotheruser] has joined #c-lightning
09:57 -!- justanotheruser [~justanoth@unaffiliated/justanotheruser] has quit [Quit: WeeChat 2.7.1]
10:00 -!- justanotheruser [~justanoth@unaffiliated/justanotheruser] has joined #c-lightning
12:37 -!- liberliver [~Thunderbi@144.49.211.130.bc.googleusercontent.com] has quit [Quit: liberliver]
15:36 -!- DeanWeen [~dean@gateway/tor-sasl/deanguss] has joined #c-lightning
15:36 -!- Dean_Guss [~dean@gateway/tor-sasl/deanguss] has quit [Remote host closed the connection]
15:55 -!- vasild_ [~vd@gateway/tor-sasl/vasild] has joined #c-lightning
15:58 -!- vasild [~vd@gateway/tor-sasl/vasild] has quit [Ping timeout: 240 seconds]
15:58 -!- vasild_ is now known as vasild
16:02 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has quit [Ping timeout: 240 seconds]
16:59 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #c-lightning
17:04 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has left #c-lightning []
17:37 -!- blockstream_bot [blockstrea@gateway/shell/sameroom/x-dgxzrzsddndesmel] has left #c-lightning []
17:37 -!- blockstream_bot [blockstrea@gateway/shell/sameroom/x-dgxzrzsddndesmel] has joined #c-lightning
18:11 -!- sr_gi [~sr_gi@static-144-88-225-77.ipcom.comunitel.net] has quit [Read error: Connection reset by peer]
18:11 -!- sr_gi [~sr_gi@static-144-88-225-77.ipcom.comunitel.net] has joined #c-lightning
20:56 -!- queip [~queip@unaffiliated/rezurus] has quit [Ping timeout: 240 seconds]
21:00 -!- queip [~queip@unaffiliated/rezurus] has joined #c-lightning
21:05 -!- queip [~queip@unaffiliated/rezurus] has quit [Ping timeout: 258 seconds]
21:25 -!- queip [~queip@unaffiliated/rezurus] has joined #c-lightning
22:31 -!- justanotheruser [~justanoth@unaffiliated/justanotheruser] has quit [Ping timeout: 272 seconds]
23:05 -!- shesek [~shesek@unaffiliated/shesek] has quit [Remote host closed the connection]
23:26 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 240 seconds]
23:42 -!- k3tan [~pi@gateway/tor-sasl/k3tan] has quit [Ping timeout: 240 seconds]
23:47 -!- k3tan [~pi@gateway/tor-sasl/k3tan] has joined #c-lightning
--- Log closed Mon Aug 24 00:00:58 2020