--- Log opened Sun Nov 24 00:01:01 2024
08:55 -!- b42 [~mmilata@2a03:3b40:fe:1e5::1] has joined #bitcoin-rust
09:13 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 252 seconds]
09:21 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-rust
09:25 < andytoshi> Ademan: heh, funny you should ask that
09:26 < andytoshi> Ademan: i have a PR (not opne yet but probably in the next week) that will break this :( i eliminated a ton of recursion and inefficiencies
09:26 < andytoshi> and i've struggled for a bit to try to recreate the ordering that thte current TaprootBuilder::with_huffman_tree produces ... but i haven't managed it
09:27 < andytoshi> and like, we've said elsewhere that "the compiler output is not stable and has no stability guarantees even with same version on same system" (though ofc we've put some effort into making it deterministic)
09:27 < andytoshi> ...but. how important is this to you?
09:54 -!- pablomartin [~pablomart@188.241.144.34] has joined #bitcoin-rust
10:38 -!- pablomartin [~pablomart@188.241.144.34] has quit [Quit: Leaving]
11:15 < Ademan> andytoshi: pretty critically important, but I can always either pin the version, or implement my own algorithm that I know will remain stable
11:16 < Ademan> But anyone who constructs a taproot output using with_huffman_tree in an older version is going to have trouble spending it in a newer version, won't they?
11:17 < Ademan> (I'm much more likely to implement my own version, since I'd rather stay up to date with rust-bitcoin)
11:18 < Ademan> unless they save off the tree somewhere, of course, but even in that case you'd want to be able to regenerate it in a recovery situation
11:19 -!- pablomartin [~pablomart@192.145.39.150] has joined #bitcoin-rust
11:20 < Ademan> it sounds well worth the breaking change in this case, but I know I'd appreciate being able to rely on certain behavior (even if it's a separate, ugly, versioned API or something)
11:21 < Ademan> or maybe I yank what's currently there into a new crate...
11:38 < Ademan> and to be clear I don't depend on the current behavior *yet* what I'm working on is a PoC anyway so breaking it is of minimal consequence, but I'll need *a* stable tap tree construction algorithm sometime between now and if/when I ever release this
12:22 -!- jungly [~jungly@user/jungly] has joined #bitcoin-rust
12:55 < andytoshi> Ademan: ok, good to know re "pretty critically important". it is true that this will change the position of tapleaves in ways that will likely result in different addresses (not guaranteed -- e.g. you can swap two sibling leaves and because the taptree hash is unordered it'll be harmless)
12:55 < andytoshi> but OTOH, it's really really not a reasonable promise for us to make that the optimizing compiler will have deterministic output. it'd really tie our hands in general to promise that
12:56 < andytoshi> Ademan: also, point taken that you aren't doing it *yet* ... part of why i am not too worried about this break is that i know that almost nobody is using taproot
12:56 < andytoshi> dariorsor's code at liana is using it, but it's full of hacks and stuff so that's fine
12:57 < andytoshi> darosior i mean*
12:57 < andytoshi> also
12:57 < andytoshi> Ademan: if you want a specific ordering out of the huffman tree, you can always assign unique weights to every leaf in your policy
12:57 < andytoshi> and then the huffman tree will be unique
12:57 < andytoshi> hmm.. actually i may be wrong about that
14:06 < Ademan> hrm yeah even if the leaves are uniquely weighted you could end up with nodes that have the same weight
14:07 < Ademan> I have to admit the deficiency with the current algo in master escapes me, I'm happy to just keep my own copy of it assuming that's allowed in CC0 (I think it is?)
14:41 -!- pablomartin [~pablomart@192.145.39.150] has quit [Ping timeout: 260 seconds]
18:21 -!- pablomartin [~pablomart@192.145.39.147] has joined #bitcoin-rust
18:21 -!- pablomartin [~pablomart@192.145.39.147] has quit [Remote host closed the connection]
18:34 < andytoshi> Ademan: yeah, definitely allowed
18:34 < andytoshi> the issue with the current algo in master is that it's recursive, and is tied to the recursive TapTree type, which is unable to keep track of control blocks
18:35 < andytoshi> so instead we punt the control-block stuff (and some other stuff) to rust-bitcoin, which is (a) really inefficient since rust-bitcoin has this weird-leaf-to-contro-block map we don't need, and (b) makes for an incomprehensible API
18:37 < andytoshi> Ademan: basically, i went to start working on making a nice iterator API where you can iterate over each leaf and get its control block, script, miniscript, etc. but then to do this I realized i needed to tie the hash of each node to the node itself. and because of stupid rust API limitations (the TapTree type itself does not reqeuire Pk: ToMiniscriptKey but computing control blocks or scripts 
18:37 < andytoshi> does require this), i found that this would involve putting an Arc<Mutex<Hash>> onto every node
18:38 < andytoshi> and also I needed parent links for each node in the tree. but then i needed weak arc pointers. and to traverse i needed to constantly be upgrading the arcs
18:38 < andytoshi> and i can't project through mutexes or upgraded arcs (i.e. i can't return references to them)
18:39 < andytoshi> so, i realized this all would be solved if i threw away the recursive TapTree type and replaced it with a flat type that internally held each node in a vector. this would also be faster to construct, derived trait impls (esp Drop) would not be recursive so i didn't need to worry about stack blowouts, the depth of the tree would be easy to check at construction time
18:39 < andytoshi> and importantly, i needed only one Arc<Mutex> to hold the whole tree
18:39 < andytoshi> but
18:39 < andytoshi> replacing the whole data structure required that i replace all the constructors
18:39 < andytoshi> including the huffman one
18:40 < andytoshi> having said all this, it's not hard for me to reorder the tree after construction. the hard part is figuring out how the original ordering was actually defined
18:40 < andytoshi> i'll put some more work into this, and see if i can't avoid the breakage
--- Log closed Mon Nov 25 00:00:01 2024