--- Log opened Mon Oct 16 00:00:57 2023
03:30 < darosior> But the availability of A doesn't matter, if it has a sig and B doesn't it would never be picked anyhow.
04:08 -!- salvatoshi [~salvatosh@103.151.37.100] has quit [Ping timeout: 246 seconds]
04:14 < darosior> At signing time, the satisfaction algorithm would always pick B. At "maybe time", it would just do the same. So the properties are the same for maybiness?
04:55 <@sipa> darosior: my example is bad, i think
04:57 <@sipa> i have a fuzzer that runs the satisfier with all keys/hashes as "maybe", and tests that its nonmalleable satisfaction size is not less than actually constructed non-malleable satisfactions
04:58 < darosior> Ah
04:58 < darosior> And it failed?
04:58 <@sipa> and when it failed, i tried playing around with it, until coming to the conclusion that its approach is just fundamenally too simple to be correct
04:58 <@sipa> but i should construct a minimal informative example to demonstrate the problem
04:58 < darosior> hmm ok
05:03 < darosior> The only case in which we may pick a different satisfaction, due to different sizes, at maybe-time and signing-time is if (both A and B have sigs and are non-malleable) or (both A and B don't have sigs [and are therefore both marked as malleable]). So it seems we'd always have the same properties between maybe-time and signing-time? 
05:04 <@sipa> well ending up with different properties at sign and maybe time is easy, but i have a hard time finding an example where that actually matters for the overall satisfaction cost
05:05 <@sipa> if you have a branch between a with-sig and a without-sig, if both are available, you pick the without-sig (which has no sig); if only the with-sig is available you pick the with-sig
05:05 <@sipa> so the result of that disjunction at maybe time should really be something that either isn't available, is available with-sig, or is available without-sig
05:06 < darosior> I'm only talking about properties that matter for the satisfaction algorithm (has sig, malleable, available).
05:06 <@sipa> yes
05:06 <@sipa> those are the only ones that matter
05:07 <@sipa> ok, it's easy to see why this is wrong in the current code; but perhaps there is a much simpler fix than what i suggest yesterday
05:07 <@sipa> say you have a branch between a small without-sig satisfaction, and a large with-sig satisfaction
05:08 <@sipa> the current code will prefer the small without-sig one
05:08 <@sipa> if both are MAYBE
05:08 <@sipa> but it's possible at signing time that only the large with-sig satisfaction is available, so the preference for without-sig between two MAYBEs results in an underestimate
05:14 -!- mode/##miniscript [+o darosior] by sipa
05:14 <@sipa> darosior: makes sense?
05:15 <@darosior> Yes
05:17 <@sipa> so a simple solution may be to just say the logic is reversed: generally no-sig is better tham with-sig, non-malleable is better than malleable, smaller is better than larger; we could say between YESses, pick the better one - between MAYBE pick the worst one, because we may have to
05:17 <@sipa> but that doesn't work either
05:18 <@sipa> say or_i(or_b(pk(A),hash(B)),pk(C))
05:18 <@sipa> eh
05:18 <@sipa> say or_i(or_b(pk(A),hash(B)),hash(C))
05:18 <@sipa> say all 3 leaves are MAYBE
05:19 <@sipa> the inner or_b would prefer the "worse" pk(A), as it has a sig
05:19 <@sipa> and the outer or_i would see a branch with a sig, and a branch without (the hash(C))
05:20 <@sipa> so it would pick the hash(C), thinking it's nonmalleable
05:20 <@sipa> but at signing time the pk(A) may be unavailable, so the result would be malleable
05:25 <@darosior> Or we could make maybeness only compatible with *both* malleable and non-malleable solutions? I'm not sure how much of an overestimate it would be
05:26 <@darosior> Between two MAYBEs just always pick the largest dissatisfaction, disregarding has_sig and malleable
05:27 <@sipa> that would work, but i think it may be a big overestimate
05:29 <@sipa> darosior: to be clear, this is not urgent and not something we need to have figured out before 26
05:29 <@darosior> Yeah
05:31 <@sipa> but i'm working writing a fuzz test that for sufficiently small miniscripts tries all combinations of availability, so it can verify that all the upper bounds (witness size, ops, max exec stack size) are actually reachable
05:31 <@darosior> Nice
05:32 <@sipa> but that obviously only works if they're actually tight upper bounds
05:33 <@darosior> So, lazy solution for the size estimation with MAYBEs. Just always pick the largest between two MAYBEs and in a method `GetMaxContextualWitnessSize` to which we pass contextual information about what challenges are available or not, run the satisfaction algorithm and upper-bound it by the existing `GetMaxWitnessSize` (which is for non-malleable
05:33 <@darosior> sats).
05:35 <@sipa> that works, but means tests for GetWitnessSize become very weak (i was hoping for a GetWitnessSize() >= maybe-satisfaction-size)
05:36 <@sipa> we have a good way to test that GetWitnessSize is not too small (finding a larger satisfaction would disprove it)
05:36 <@sipa> but we don't have a way to find out if it's too high
05:37 <@darosior> Yeah the lazy solution isn't adapted for testing
05:37 <@sipa> actually, i'm wrong - maybe satisfaction doesn't actually help with detecting too large GetWitnessSize
05:37 <@sipa> only exhaustive testing can do that
05:38 <@sipa> darosior: do you think my approach with tracking 5 per-type satisfactions is too complex?
05:40 <@darosior> To be honest i haven't read it entirely yet
05:40 <@darosior> Doing it now
05:48 <@darosior> Wouldn't that dramatically increase the computation for a thresh?
05:50 <@darosior> I'm sorry i really can't focus on this right now, will get back ASAP
06:03 <@sipa> darosior: only a constant factor slower, i believe
06:08 -!- salvatoshi [~salvatosh@103.100.173.166] has joined ##miniscript
08:39 -!- ghost43_ [~ghost43@gateway/tor-sasl/ghost43] has quit [Remote host closed the connection]
08:39 -!- ghost43 [~ghost43@gateway/tor-sasl/ghost43] has joined ##miniscript
08:46 -!- salvatoshi [~salvatosh@103.100.173.166] has quit [Ping timeout: 240 seconds]
15:31 -!- jonatack [~jonatack@user/jonatack] has quit [Read error: Connection reset by peer]
15:32 -!- jonatack [~jonatack@user/jonatack] has joined ##miniscript
17:01 -!- salvatoshi [~salvatosh@103.100.173.166] has joined ##miniscript
19:17 -!- salvatoshi [~salvatosh@103.100.173.166] has quit [Ping timeout: 258 seconds]
19:18 -!- salvatoshi [~salvatosh@103.100.173.166] has joined ##miniscript
19:24 -!- salvatoshi [~salvatosh@103.100.173.166] has quit [Ping timeout: 255 seconds]
22:03 -!- salvatoshi [~salvatosh@103.151.37.100] has joined ##miniscript
23:54 -!- Earnestly [~earnest@user/earnestly] has quit [Ping timeout: 252 seconds]
--- Log closed Tue Oct 17 00:01:00 2023