--- Log opened Wed May 26 00:00:06 2021
04:33 < adiabat_> huh, well guess everyone has to move servers!
04:33 < adiabat_> guess this channel didn't get banned, but maybe it will now: irc.libera.chat:6697
04:35 < adiabat_> (also freenode was a cooler name than Libera Chat but oh well)
04:35 -!- adiabat_ [~adiabat@63.209.32.102] has quit [Quit: WeeChat 1.9.1]
07:06 -!- mdrollette [~mdrollett@cpe-70-123-125-237.tx.res.rr.com] has joined #utreexo
--- Log closed Wed May 26 07:12:32 2021
--- Log opened Wed May 26 07:18:20 2021
--- Log closed Wed May 26 07:20:51 2021
--- Log opened Wed May 26 07:21:27 2021
--- Log closed Wed May 26 07:46:25 2021
--- Log opened Wed May 26 07:48:04 2021
--- Log closed Wed May 26 07:48:17 2021
--- Log opened Wed May 26 07:48:32 2021
07:48 -!- gnusha [~gnusha@user/gnusha] has joined #utreexo
07:48 [Users #utreexo]
07:48 [ achow101] [ dergoegge] [ gnusha   ] [ kcalvinalvin] [ pigeons] 
07:48 [ adiabat ] [ FelixWeis] [ kallewoof] [ khs9ne      ] 
07:48 -!- Irssi: #utreexo: Total of 9 nicks [0 ops, 0 halfops, 0 voices, 9 normal]
--- Log closed Wed May 26 07:49:01 2021
--- Log opened Wed May 26 07:49:19 2021
07:49 -!- gnusha [~gnusha@user/gnusha] has joined #utreexo
07:49 [Users #utreexo]
07:49 [ achow101] [ dergoegge] [ gnusha   ] [ kcalvinalvin] [ pigeons] 
07:49 [ adiabat ] [ FelixWeis] [ kallewoof] [ khs9ne      ] 
07:49 -!- Irssi: #utreexo: Total of 9 nicks [0 ops, 0 halfops, 0 voices, 9 normal]
07:50 -!- Channel #utreexo created Wed May 19 11:14:50 2021
07:51 -!- Irssi: Join to #utreexo was synced in 156 secs
08:45 -!- achow101 [~achow101@2001:19f0:5:4654:125c:f81c:3778:c4ac] has quit [Quit: Bye]
08:45 -!- achow101 [~achow101@2001:19f0:5:4654:125c:f81c:3778:c4ac] has joined #utreexo
08:52 -!- achow101 [~achow101@2001:19f0:5:4654:125c:f81c:3778:c4ac] has quit [Changing host]
08:52 -!- achow101 [~achow101@user/achow101] has joined #utreexo
11:00 < dergoegge> i have a question for the swapless design. consider the 8 leaf tree here https://github.com/mit-dci/utreexo/blob/master/accumulator/printout.txt
11:00 < dergoegge> if we delete 02 and 03 then the entire sub tree below 08 has to move up, right?
11:01 < dergoegge> i am just wondering how bad that would be if larger subtree have to move up
11:01 < dergoegge> i guess not worse than swapping ranges like we are currently doing
11:02 < dergoegge> i mean the pollard has no problem with this but the disk forest might struggle a bit
11:09 < adiabat> dergoegge: so there's 2 ways to look at this
11:09 < adiabat> in the 8-tree case of delete(02, 03)
11:10 < adiabat> first apply the raiseTwins() function and get delete(09)
11:11 < adiabat> delete 09 means that *logically* 08 replaces 12
11:11 < adiabat> in that 14 = hash(08, 13) afterwards
11:12 < adiabat> one way to do it would be to have the on-disk positions directly reflect the logical / hash based tree, so:
11:12 < adiabat> 08 -> 12, 00 -> 08, 01 -> 09
11:14 < adiabat> another way which is "lazy" in that there's less up-front disk i/o is to just delete 12 and 09
11:14 < adiabat> so nothing moves, 12 is just replaced with 0 bytes or ffff or something, and same with 09
11:14 < adiabat> 02 and 03 don't even need to be deleted from disk
11:15 < adiabat> then when you're creating a proof for 01, you get 01, then up to 09 but that's empty so skip, then 13
11:17 < adiabat> it doesn't quite work for proofs on the other side though, like proving 04 is: 05, 11, 12 (empty)
11:18 < adiabat> so maybe need different "empty" hashes; one meaning empty and there's nothing below, and one "empty" but there are valid leaves below
11:19 < adiabat> or, probably simpler is to copy 08 to 12
11:19 < adiabat> from the verifier side, there should be no difference since they don't store the tree on disk and only care about what the hashes are
11:20 < adiabat> but on the bridge node side, you can have all sorts of ways to represent the tree on disk. 
11:21 < adiabat> it seems like it would be a tradeoff of up-front disk i/o vs later on disk i/o.  Also leaving things in place is more read-heavy, and moving subtrees is more write-heavy
11:22 < dergoegge> with the first approach we could potentially prune dead parts of the forest if we split it into multiple files.
11:23 < dergoegge> it also feels a bit more straight forward to implement 
11:24 < dergoegge> was there ever a forest version that used leveldb?
11:26 < dergoegge> that would probably be slow but we could have a "pointer" based on disk forest
11:27 < dergoegge> it might be harder to deal with the position map with the second approach. 
11:43 < dergoegge> another example in the 16 leaf forest:
11:43 < dergoegge> if we remove 02, 03 and 25 then we would first move subtree(8) to 24
11:44 < dergoegge> and then move the same tree up again when deleting 25
11:44 < dergoegge> maybe we can get rid of multiple moves like that
13:05 < adiabat> it feels like it would be simpler to keep the logical and "physical" trees the same
13:06 < adiabat> but in either way recovering empty space is a bit tricky
13:07 < adiabat> we have tried "full pollard" which works but was a bit slower.  though with swapless it may be useful again
13:08 < adiabat> full pollard was just using the pollard struct and node storage, but keeping every leaf
13:09 < adiabat> For the 16-leaf tree, deleting 02, 03, 25
13:09 < adiabat> would through raiseTwins() become delete 17, 25
13:09 < adiabat> which means 16 moves to 28
13:10 < adiabat> not sure what you mean by subtree(8)
13:11 < adiabat> from a CSN point of view, only one hash needs to be computed to delete 17, 25
13:11 < adiabat> (which is really deleting 02, 03, 04, 05, 06, 07)
13:14 < adiabat> in the verify process the CSN has seen 16 as part of the proof for 02 and 03
13:15 < adiabat> for the delete step, all the CSN needs to do is hash 16 and 29 and save that as the root
13:15 < adiabat> (they can also keep 16 as the left child of the root if they want)
13:25 < adiabat> Though I suppose for the curreny algo, no hashing at all is required for either the CSN or the bridge, as 29 becomes a root at 28, and 16 becomes a root at 20
13:25 < adiabat> *current
13:26 < adiabat> but keeping everything in order seems worth that one extra hash operation
--- Log closed Wed May 26 14:27:15 2021
--- Log opened Wed May 26 14:27:15 2021
21:44 -!- achow101 [~achow101@user/achow101] has quit [Read error: Connection reset by peer]
21:45 -!- achow101 [~achow101@user/achow101] has joined #utreexo
--- Log closed Thu May 27 00:00:20 2021