--- Log opened Fri Mar 05 00:00:47 2021
00:42 -!- meshcollider [meshcollid@gateway/shell/ircnow/x-vtakzzjunnrxyedh] has quit [Ping timeout: 264 seconds]
00:46 -!- meshcollider [meshcollid@gateway/shell/ircnow/x-ttsnhkjhgyervsge] has joined ##miniscript
00:55 -!- jonatack_ [~jon@37.167.227.177] has joined ##miniscript
01:25 -!- jonatack_ [~jon@37.167.227.177] has quit [Quit: jonatack_]
01:25 -!- jonatack [~jon@37.167.227.177] has joined ##miniscript
02:49 -!- afilini [~user@gateway/tor-sasl/afilini] has quit [Remote host closed the connection]
03:20 -!- afilini [~user@gateway/tor-sasl/afilini] has joined ##miniscript
03:46 -!- afilini [~user@gateway/tor-sasl/afilini] has quit [Remote host closed the connection]
05:13 -!- jonatack [~jon@37.167.227.177] has quit [Ping timeout: 265 seconds]
06:53 -!- appservicebot5 [~afilini-m@2.233.112.151] has joined ##miniscript
07:21 -!- jonatack [~jon@37.167.227.177] has joined ##miniscript
09:09 -!- appservicebot5 [~afilini-m@2.233.112.151] has quit [Quit: Bridge terminating on SIGTERM]
09:09 -!- appservicebot5 [~afilini-m@2.233.112.151] has joined ##miniscript
09:13 -!- appservicebot5 [~afilini-m@2.233.112.151] has quit [Client Quit]
09:15 -!- appservicebot5 [~afilini-m@2.233.112.151] has joined ##miniscript
09:16 -!- appservicebot52 [~afilini-m@2.233.112.151] has joined ##miniscript
10:41 -!- appservicebot52 [~afilini-m@2.233.112.151] has quit [Quit: Bridge terminating on SIGTERM]
10:41 -!- appservicebot5 [~afilini-m@2.233.112.151] has quit [Remote host closed the connection]
10:43 -!- appservicebot5 [~afilini-m@2.233.112.151] has joined ##miniscript
11:12 < jeremyrubin> I vaugely remember discussing but sanket1729_ coudl you write a bit more about https://github.com/rust-bitcoin/rust-miniscript/pull/168/commits/e75f52e288b0519b80aeca4d1a905d6e8b7e9859
11:14 < andytoshi> if you have repeated keys then none of our satisfiabliity or anti-malleability analysis works
11:15 < jeremyrubin> gotcha... there's no way to make the algorithms work? It's just banned outright?
11:16 < jeremyrubin> (i.e., is this a temp or permanent measure)
11:21 < sipa> if you find a way to perform analysis in the presence of repeated keys, sure :)
11:21 < sipa> but i assume its complexity will be far worse than what we have now
11:32 < jeremyrubin> interestingly, it did catch a bug in my code heh
11:44 < andytoshi> i think "permanent" is probably the best way to think about it
11:45 < andytoshi> as sipa is alluding to, it's more "an open research question" than something that we forbid for any moral reason
11:45 -!- jonatack_ [~jon@37.170.241.200] has joined ##miniscript
11:45 < andytoshi> it is unfortunate because sometimes it's the only way to (efficiently?) express some things in miniscript
11:46 < jeremyrubin> I think it might be worth considering either removing or making it so that abstract keys (e.g., A, B) cannot be surjective?
11:47 < andytoshi> i don't understand
11:47 < jeremyrubin> translate("A") != tranlate("B")
11:48 < sipa> he means adding the assumption that two distinct abstract keys will never be mapped to the same concrete key, i think
11:48 < jeremyrubin> sipa: correct
11:48 < jeremyrubin> or adding the assertion that they are not
11:48 -!- jonatack [~jon@37.167.227.177] has quit [Ping timeout: 260 seconds]
11:48 < jeremyrubin> and erroring
11:48 < andytoshi> like, in the documentation for translate_pk
11:48 < andytoshi> hmmm
11:48 < jeremyrubin> well definitely in docs
11:48 < andytoshi> i agree this is a good idea. i am uncertain how best to implemnet it
11:48 < jeremyrubin> but I'd argue at implementation level
11:49 < andytoshi> yeah, agreed, this is a leak, i didn't realize you could create repeated-key miniscripts this way
11:49 < jeremyrubin> and btw it's definitely one of the *first* "how do I fix it" thoughts I had when I hit the dup error
11:49 < jeremyrubin> so it is a footgun 
11:49 < andytoshi> lol i am not thinking adversarially enough :)
11:49 < jeremyrubin> TBH i find the translate_key trait indecipherable 
11:50 < andytoshi> yeah it's the sorta thing you get when you use rust for something that you should be using haskell for
11:50 < jeremyrubin> maybe a nice time to use names spelled out, Fpkh sounds like an explitive 
11:50 < andytoshi> lol
11:51 < andytoshi> yeah or at least PkHFunc
11:51 < jeremyrubin> ah now I get it
11:52 < jeremyrubin> so it's sort of odd because you don't need to guarantee that Fpkh is non-surjective
11:52 < andytoshi> mm i think you do
11:52 < jeremyrubin> just that for the arguments that it gets called on for a given script it is
11:52 < andytoshi> ah yeah
11:52 < jeremyrubin> So you need to collect all keys into a vec
11:53 < jeremyrubin> and then do a de-dup check
11:53 < andytoshi> a HashSet would have better asymptotics
11:53 < jeremyrubin> nope can have same asymptotes 
11:53 < andytoshi> it _can_, but it won't
11:54 < jeremyrubin> (i'm speaking higher order anyways, more about "you must collect into a O(n) sized data struct)
11:54 < andytoshi> yeah, space wise it'll be the same
11:54 < jeremyrubin> I don't think there's a non-allocating way to confirm
11:54 < jeremyrubin> unless you use a bloom filter or smth?
11:54 < andytoshi> heh, then you'd have random spurious failures
11:55 < jeremyrubin> You can do a non-failing algorithm with a filter 
11:55 < jeremyrubin> if space is really a concern
11:55 < jeremyrubin> but the # of keys is O(script size) anyways
11:55 < andytoshi> yeah i don't think we care about space really
11:56 < sipa> just create a list, and sort it
11:56 < andytoshi> well using a hashmap will have better asymptotic time behavior..
11:56 < andytoshi> and won't require the target key type be sortable
11:56 < andytoshi> though maybe we require all our keys be sortable already
11:57 < jeremyrubin> no I think not since Q is arbitrary right?
11:57 < andytoshi> it has to impl MiniscriptKey which i think has an Ord requirement on it
11:57 < jeremyrubin> maybe Miniscriptkey requires sortablke..
11:57 < jeremyrubin> I agree with sipa btw that sorting is probably faster vs hashing for most use cases, and more cache friendly 
11:58 < sipa> a sparse hash may be faster, i'm not sure
11:58 < sipa> depending on size
11:58 < jeremyrubin> Ah you may be right
11:58 < jeremyrubin> since we can fail on the first error
11:59 < sipa> but if your hash table needs an allocation per element as most general-purpose hash tables do, i'm pretty sure that sorting a vector in place and checking for adjacent identical elements is faster in practice
11:59 < andytoshi> it won't need an allocation per element
11:59 < jeremyrubin> Wait -- question
11:59 < andytoshi> as our key types are all Copy, they'll be inlined
11:59 < jeremyrubin> When is the duplicate check performed?
11:59 < jeremyrubin> Will we check it after translating again anyways?
11:59 < sipa> andytoshi: how does the hash table deal with collisions?
12:00 < jeremyrubin> We might already be covered, so there might not be a backdoor?
12:00 < sipa> most general purpose hash tables use a linked list per bucket, which implies an allocation per element
12:00 < andytoshi> sipa: ohh good question, i think you're right
12:00 < andytoshi> jeremyrubin: no, we don't do any dupe checks after creation
12:00 < sipa> but if you use a sparse hash that places the elements inline in the table, it may be different
12:00 < andytoshi> we'd need to add a check in translate?pk
12:00 < jeremyrubin> sipa: actually IIRC it's not
12:00 < jeremyrubin> c++ has 1 base vec + linked list?
12:01 < sipa> std::unordered_map is an allocation per element
12:01 < jeremyrubin> first one shouldn't require an allocation per bucket
12:01 < jeremyrubin> I thought the first element in a bucket doesn't allocate?
12:01 < sipa> it does
12:01 < sipa> the table just contains pointers
12:01 < sipa> otherwise you can't have stable iterators etc
12:01 < andytoshi> oh in rust that is not a problem
12:02 < andytoshi> i suspect jeremyrubin is right for rust's HashMap
12:02 < andytoshi> but honestly i don't care enough about this to benchmark it :) so i probably will go with HashSet because it's an easier API to use for dupe-checking
12:02 < andytoshi> if you want to translate miniscripts super fast then you probably want to re-implement it with a better representation than the current recursive data structure
12:03 < andytoshi> (which i have tried a couple times and it's a huge PITA)
12:04 < andytoshi> tbh i don't know how to efficiently create a flat tree where nodes have variable numbers of children
12:04 < andytoshi> maybe if i'd done a CS degree :)
12:04 < jeremyrubin> andytoshi: you don't need to
12:04 < jeremyrubin> you can fail on the first duplicate
12:04 < jeremyrubin> you just need a HashSet
12:04 < andytoshi> yeah, i am going to do that
12:05 < andytoshi> but translating pks will still be stupidly slow and cache-inefficient because it involves reconstructing the whole miniscript structure
12:05 < jeremyrubin> a suggestion might be to get rid of Fpkh
12:05 < jeremyrubin> and just make it a hashmap
12:06 < andytoshi> oh interesting
12:06 < andytoshi> if we need a hashmap anyway..
12:06 < jeremyrubin> and you can turn it into a trait which is FpkhAble
12:06 < jeremyrubin> that both Fpkh and HashMap implement --> non breaking change
12:07 < andytoshi> heh nah let's just do the breaking change where we take a hashmap in place of Fpkh
12:07 < andytoshi> i'd rather have a breaking change and less trait nonsense
12:07 < andytoshi> than more trait nonsense
12:07 < jeremyrubin> I guess the one weird thing is if it is key -> abstract or abstract -> key?
12:07 < jeremyrubin> you need a bijective map datastructure
12:08 < andytoshi> i don't understand, translate_pk does not have anotion of one key being more abstract than another
12:09 < andytoshi> nor does it ever reverse the map. it can't, given that it currently takes a function :)
12:09 < jeremyrubin> Yes
12:09 < jeremyrubin> I'm just saying you need a bijective map
12:09 < andytoshi> why?
12:09 < jeremyrubin> How would a non-bijective map passed in solve the problem?
12:10 < andytoshi> you replace the closure it currently takes with a hashmap
12:10 < andytoshi> and then you replace ( and ) with [ and ]
12:10 < jeremyrubin> Ok, so then let's say the hashmap is "A" -> 1, "B" -> 1
12:10 < jeremyrubin> how did that help?
12:10 < andytoshi> oh derp i see what you're saying
12:10 < andytoshi> yeah ok you still need to create the HashSet
12:11 < andytoshi> so there's no point in taking a HashMap to begin with
12:11 < jeremyrubin> unless there's something clever that you can eek a bimap out of std
12:11 < jeremyrubin> ahhh!
12:11 < andytoshi> can you do a bimap more efficiently than two hashmaps?
12:11 < jeremyrubin> Yes there is kind of?
12:11 < andytoshi> or a hashmap+hashset which is all we need here
12:12 < jeremyrubin> We actually don't care that the source is valid, just the dest?
12:12 < andytoshi> correct
12:18 < jeremyrubin> I think the best bet might be to pass a Vec<(KeyT, KeyS)>
12:19 < jeremyrubin> then what you do is first sort by KeyT, translate using binary search, then sort by KeyS, then dedup check
12:20 < jeremyrubin> it means that you can do it all with a single vec allocation and 2 sorts 
12:22 < jeremyrubin> you can improve this a little with a smart constructor for the type TranslationVec that has a smart constructor so you can't pass in an invalid vec
12:23 < jeremyrubin> other than that I don't have more ideas, just problems ;)
12:28 < jeremyrubin> i opened https://github.com/rust-bitcoin/rust-miniscript/issues/238 for it just so it doesn't get forgotten -- let me know if you want to tackle it otherwise I can prepare a patch
12:28 < jeremyrubin> it is super bikesheddable and I don't care what color gets picked too much
12:46 < andytoshi> thanks! i'll just do the simple/obvious HashSet thing
12:46 < andytoshi> no need to add multiple sort passes and a binary search to every single key lookup
12:47 -!- jonatack_ [~jon@37.170.241.200] has quit [Quit: jonatack_]
12:47 -!- jonatack [~jon@37.170.241.200] has joined ##miniscript
13:42 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has quit [Ping timeout: 245 seconds]
13:42 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has joined ##miniscript
14:46 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has quit [Ping timeout: 256 seconds]
15:23 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has joined ##miniscript
15:41 -!- jonatack [~jon@37.170.241.200] has quit [Read error: Connection reset by peer]
17:15 -!- shesek [~shesek@unaffiliated/shesek] has quit [Remote host closed the connection]
18:28 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has quit [Ping timeout: 265 seconds]
19:37 < sanket1729_> andytoshi: Since the policy and Miniscript are public enums, it is directly possible to create Miniscripts/Policies without the FromStr/Compile/ParseScript route. Users can directly create using enums Terminal::AndV(Terminal::Key(A),Terminal::Key(B))`
19:45 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has joined ##miniscript
21:49 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has quit [Ping timeout: 276 seconds]
--- Log closed Sat Mar 06 00:00:48 2021