--- Log opened Sat Mar 26 00:00:39 2022
02:56 < sanket1729> jeremyrubin: explore everything left than right
02:56 < sanket1729> I always assumed that to be the canonical ordering
02:57 < sanket1729> Good point tough, even BIP371(taproot Psbt BIP) is not explicit about it
03:05 < sanket1729> shesek_: I don't remember why it was private. I don't think it being private is necessary. I agree that it is more intuitive, will make a PR before release to make it pub
03:24 < sanket1729> I do think, using builder API is simpler, but the choice can be given to users to implement what they feel is simplest
03:24 < sanket1729> This is how I was imagining the API would be used: https://gist.github.com/sanket1729/9d92d1ad962769c7832f3df835dc7d5a
05:57 < shesek_> sanket1729, incredible, thank you :-)
05:57 < shesek_> would it help if I sent the PR?
06:23 -!- Guest23 [~Guest23@cpc97890-walt21-2-0-cust505.13-2.cable.virginm.net] has joined ##miniscript
06:42 -!- Guest23 [~Guest23@cpc97890-walt21-2-0-cust505.13-2.cable.virginm.net] has quit [Quit: Client closed]
07:49 -!- shesek_ is now known as shesek
09:58 < jeremyrubin> sanket1729: more probelmatically, your represenations may not even have a left or right if you use an unordered set ;) (but good thing we talked about using BTrees for rust wherever we can ;) )
10:00 < jeremyrubin> E.g., enum Tree<T> { Node(HashSet<Box<Tree<T>>>, Leaf(T))
10:00 < jeremyrubin> it's sometimes a weird choice of repr, but these come up sometimes in various algos like e.g. tries 
10:05 < jeremyrubin> in taproot it's also funny because the nodes get switched up into lexicographic order for hashing
10:05 < jeremyrubin> so it's not even clear to me there is ONE canonical ordering
10:05 < jeremyrubin> since you could permute neighboring things in theory and get the same answer?
10:07 < jeremyrubin> this also has some funny implications, now that i think of it, for descriptors
10:08 < jeremyrubin> (i dont really know the notation that well so bear with)
10:08 < jeremyrubin> Q: give a descriptor with N paths having different xpubs, will derivations give the same script fragments the same lookup path in the taproot tree?
10:08 < jeremyrubin> A: No, because the lexicographic ordering ends up permuting the tree
10:09 <@sipa> if by "path" you mean left/right, of course... there is no left/right in taproot trees
10:09 < jeremyrubin> yep!
10:10 <@sipa> if by path you mean the merkle path values... yes, but that'd even be the case if we didn't have the lexicographic sorting
10:10 <@sipa> (because the hashes depend on the keys in the leaves)
10:10 < jeremyrubin> yep
10:10 < jeremyrubin> im just pointing out theres not really a good canonical DFS
10:11 <@sipa> for a specific script tree, there is... just sort the leaves lexicographically at every level
10:12 <@sipa> if you're talking about a descriptor which has key expressions that depend on the index; indeed... but descriptors always have many different ways of encoding the same thing
10:12 <@sipa> well, not always, but it's far from the only ambiguity
10:16 < jeremyrubin> sipa: the issue is you can't really do the lexicographic sorting for the example sanket gave https://gist.github.com/sanket1729/9d92d1ad962769c7832f3df835dc7d5a
10:16 < jeremyrubin> in this example, the nodes are sorted, so it doesn't matter
10:17 < jeremyrubin> err not sorted, fixed in order
10:17 <@sipa> i guess i'm missing context then
10:17 < jeremyrubin> but the lexicographic ordering isn't info you'd have when you visit each node
10:17 <@sipa> why do you need a canonical ordering in the first place?
10:18 < jeremyrubin> a user specifies a tree and they want to use it to create a taproot address
10:19 <@sipa> yes, ok
10:19 < jeremyrubin> in this case, the user then makes a taproot builder
10:19 < jeremyrubin> and then the builder creates a taproot spend info
10:19 < jeremyrubin> they have to save the taproot spend info
10:19 < jeremyrubin> not the tree spec 
10:20 <@sipa> why?
10:20 < jeremyrubin> because otherwise the tree spec is not canonically traversible &they can't recover the merkle proofs
10:20 <@sipa> in a descriptor, they effective have the tree
10:20 <@sipa> why does it need to be canonically traversable
10:21 <@sipa> every tree gives rise to some address; most reorderings of that tree will give a different address, some will give the same address
10:21 <@sipa> without the lexicographic sorting, all reorderings would give a different address
10:21 < jeremyrubin> yes
10:21 <@sipa> just keep the tree in the order you want it
10:21 < jeremyrubin> 🤦
10:21 < jeremyrubin> yes, you need a canonical order to search the tree
10:22 < jeremyrubin> this is part of the issue that shesek is having
10:22 <@sipa> sorry, i don't understand what you're trying to achieve
10:22 <@sipa> or why just keeping the tree is a problem
10:22 < jeremyrubin> well it's not *just* keeping the tree
10:22 < jeremyrubin> it's keeping the tree and a canonical DFS
10:22 < jeremyrubin> which is what "keep the tree in the order you want it" means
10:23 < jeremyrubin> shesek is manually creating a tree out of minsc
10:23 <@sipa> forget the lexicographical ordering that taproot trees have
10:23 < jeremyrubin> and then wanting to generate a Taproot builder from that
10:23 <@sipa> and think of them as trees where the order of children always matters
10:23 < jeremyrubin> and sanket1729 said 'visit them in DFS order'
10:24 < jeremyrubin> and i responded that if you do that, you should have a canonical DFS ordering for the tree representation being used
10:24 < jeremyrubin> otherwise you aren't reproducible from your tree spec to a descriptor 
10:25 <@sipa> a DFS traversal of a tree (i.e., list of (leaf, depth) pairs in traversal order) can be converted to the tree and the other way around
10:26 <@sipa> i think we're talking past each other... answer this to me: do you believe that the problem you're trying to solve is in any way made more complicated by the fact that taproot merkle trees do this lexicographic ordering thing?
10:27 <@sipa> because you say "canonical ordering", and I'm not sure if you're referring to the mapping between (normal) trees and their DFS traversal order, or to the fact that some reorderings of taproot script trees do not change the hash
10:28 <@sipa> (or about something specific to the rust API, in which case I'm ignorant)
10:30 < jeremyrubin> > 10:05 <jeremyrubin> so it's not even clear to me there is ONE canonical ordering
10:30 <@sipa> of what?
10:30 < jeremyrubin> the order that you have to feed nodes into a taproot builder to get the same address out
10:30 < jeremyrubin> that's all i'm pointing out
10:31 <@sipa> just the DFS traversal order
10:31 < jeremyrubin> which DFS traversal order 
10:31 <@sipa> you have a tree
10:31 <@sipa> ignore the fact that taproot trees do this funky thing where they lexicographically sort child hashes to compute the parent
10:32 < jeremyrubin> i am 
10:32 <@sipa> traverse the tree in DFS order
10:32 < jeremyrubin> ok
10:33 <@sipa> (list of (leaf,depth) pairs) is just another way of describing a tree
10:33 <@sipa> which avoids recursive/tree algorithms
10:33 < jeremyrubin> ok
10:33 < jeremyrubin> imagine i fill the tree left-right vs right-left
10:34 < jeremyrubin> i will get a different result, yes?
10:34 < jeremyrubin> so you also need to define what the DFS order is
10:34 <@sipa> DFS is DFS
10:35 <@sipa> like draw the tree on a piece of paper, root at the top, leaves at the bottom... read the leaves from first to last
10:36 < jeremyrubin> i think that's the point
10:37 < jeremyrubin> imagine i, instead, scan the list
10:37 < jeremyrubin> and i make a list (depth, set (leaf, occurences))
10:38 < jeremyrubin> and then i draw up a random tree satisfying that constraint
10:38 <@sipa> what are occurrences?
10:38 < jeremyrubin> if you disallow repeating the same leaf >1 times for simplicity, it would always be 1
10:38 <@sipa> oh, just a count, i see
10:39 <@sipa> so a list of pairs (depth, multiset of leaves)
10:39 < jeremyrubin> the point is that you'd be able to make > 1 binary trees that have the same DFS ranking, but not a 'canonical' thing
10:39 <@sipa> that's not a faithful representation of the tree
10:39 < jeremyrubin> cool, we agree
10:39 <@sipa> you lose information about the structure
10:40 <@sipa> so don't do that
10:40 < jeremyrubin> ok we agree
10:40 <@sipa> ok
10:40 < jeremyrubin> that's the point
10:40 < jeremyrubin> if shesek is going to make some custom tree outside of Miniscript
10:40 <@sipa> in that case i agree with a point, but don't see why it matters :)
10:41 <@sipa> if you want to represent trees, you need faithful encodings of them
10:41 < jeremyrubin> the advice to traverse in DFS orders means he should be careful to ensure his representations have a canonical DFS order
10:41 < jeremyrubin> sipa:
10:41 < jeremyrubin> oops
10:41 < jeremyrubin> so consider the tree as follows, which is faithful, but does not permit a simple DFS
10:42 < jeremyrubin> data Tree a = Node (Set(Tree a) | Leaf a
10:43 <@sipa> parenthesis is unbalanced
10:43 < jeremyrubin> data Tree a = Node (Set(Tree a)) | Leaf a
10:43 < jeremyrubin> lol
10:43 <@sipa> the set can only have exactly two elements, or also more?
10:44 < jeremyrubin> let's assume it can support >2, but that your input data is always a binary tree
10:45 <@sipa> so... if you're talking about general trees (ignoring the lexicographic sorting aspect), that's not actually a faithful representation
10:45 <@sipa> but it happens to be sufficient for our taproot trees
10:45 < jeremyrubin> what is a faithful representation?
10:45 <@sipa> one that lets you recover the tree
10:45 < jeremyrubin> maybe my advice boils down to be careful to have a faithful representation?
10:45 <@sipa> without loss of information
10:46 < jeremyrubin> gotcha, so actually this is a faithful tree
10:46 < jeremyrubin> i can give you a canonical DFS for it
10:46 <@sipa> in any case, for the use case of taproot trees, you can define a canonical ordering of the leaves here: just pick the first element of the set first
10:46 <@sipa> s/pick/traverse/
10:46 < jeremyrubin> sipa: nit: not the first element of the set, you have to Ord the elements and pick the first
10:47 < jeremyrubin> the whole point is the Set's notion of first might be randomized
10:47 < jeremyrubin> e.g. hash set
10:47 < jeremyrubin> but it's still faithful!
10:47 <@sipa> only if you're talking about taproot script trees
10:48 <@sipa> for generic trees, this is not a faithful representation, as the order of the children may matter
10:48 <@sipa> so this loses some information... but what is lost is exactly the part that doesn't matter for taproot trees
10:49 < jeremyrubin> ah -- well i think the point is that it works for not just taproot trees, but for any tree where i don't care *which* order, but i do care that there is *an* order
10:49 < jeremyrubin> as long as `a` is Ord a, then you can define a canonical DFS for whatever algorithm
10:49 <@sipa> right, agree
10:49 < jeremyrubin> and if you want to preserve order for some other reason, just do a = (int, b)
10:50 < jeremyrubin> altho maybe that makes set querying bad
10:50 <@sipa> my advice would be to not use such a representation (sets tend to be more complex than just lists, even though they're information theoretically "simpler")
10:50 < jeremyrubin> so maybe a = (b, int) and when you extract from the hash set sort by b
10:50 < jeremyrubin> *int
10:50 < jeremyrubin> i think we share the same advice
10:50 < jeremyrubin> which is more or less what i was saying
10:51 <@sipa> and represent your trees as Tree a = Node (Tree a, Tree a) | Leaf a
10:51 <@sipa> or as lists [(a, depth)]
10:51 < jeremyrubin> so there are real reasons not to do this in rust
10:51 < jeremyrubin> and C++
10:51 < jeremyrubin> which is that you need to do: Tree a = Node (Box<Tree a>, Box<Tree a>)  | Leaf a
10:51 <@sipa> or as anything equivalent to it... as long as it maintains the order of children
10:52 < jeremyrubin> so you end up with a lot of Boxes and stuff
10:52 <@sipa> ah, this is rust syntax?
10:52 < jeremyrubin> ugh
10:52 <@sipa> i thought it was haskell
10:52 < jeremyrubin> hybrid 
10:52 < jeremyrubin> let me fix
10:52 <@sipa> it doesn't matter
10:52 <@sipa> i think i got your point
10:55 < jeremyrubin> it's just a fun source of bugs because it's something where you'd like see your code work fine end to end, then try to repeat it and get different results, but if you were testing it e.g. inside WASM you'd see it work again (no entropy!), so it's kind of a confusing one. 
10:56 < jeremyrubin> conseqeuntly, i've been trying to make sure that we always prefer BTree based sets/maps so that things are always ordered in the rust code 
10:57 < jeremyrubin> since using the hashmap things not only adds DoS concerns when using from WASM, but also leads to some undesirable behaviors around repeatability 
10:57 < jeremyrubin> but AFAIU we don't use them inside any data structures presently 
10:58 < jeremyrubin> but anyways, interesting chatting :)
16:21 -!- shesek [~shesek@user/shesek] has quit [Remote host closed the connection]
16:21 -!- shesek [~shesek@user/shesek] has joined ##miniscript
17:38 -!- shesek_ [~shesek@user/shesek] has joined ##miniscript
17:38 -!- shesek [~shesek@user/shesek] has quit [Remote host closed the connection]
17:51 -!- shesek__ [~shesek@user/shesek] has joined ##miniscript
17:53 -!- shesek_ [~shesek@user/shesek] has quit [Remote host closed the connection]
19:49 -!- shesek__ [~shesek@user/shesek] has quit [Remote host closed the connection]
22:50 < sanket1729> shesek: https://github.com/rust-bitcoin/rust-bitcoin/pull/910, but I  can't promise it will make the release. It is already super-delayed. Don't want to add more PRs to it now
--- Log closed Sun Mar 27 00:00:37 2022