--- Log opened Wed May 25 00:00:33 2022 01:11 -!- theStack [~theStack@95.179.145.232] has joined ##miniscript 10:17 -!- darosior [~darosior@194.36.189.246] has quit [Read error: Connection reset by peer] 10:18 -!- darosior [~darosior@194.36.189.246] has joined ##miniscript 11:16 <@sipa> darosior sanket1729 (re discussion in the review club today): The requirement for no duplicate keys really only matters to the extent it prevents converting one HASSIG branch into another HASSIG branch in the non-malleable signing algorithm. "no duplicate keys" is actually too strong a condition for that. If we're going to implement it programmatically anyway, maybe we can be more exact? 11:16 <@sipa> The most obvious example would be that a duplicate key across an and is not a problem. 11:18 <@sipa> A simple improvement would be to stop the duplicate key checking in and_b, and_v (and just union the key sets there instead). 11:18 <@sipa> Now I wonder: what about thresh? Is there an efficient algorithm there too? 11:18 <@sipa> (we can skip n-of-n threshes, and treat them like ands) 11:19 <@sipa> But for k-of-n with k Agreed, we can do something better. 11:20 < sanket1729> But in practice something else is off if a satisfaction requires two same signatures in an `and` 11:21 <@sipa> This is still an approximation, because the exact problem would be reasoning about all sets of valid signers, and making sure there is never a branch where that set is a strict subset on one side vs the other. 11:22 <@sipa> sanket1729: that's a good point - it's only inaccurate in a dimension that's uninteresting anyway. 11:24 <@sipa> So as an example: or(and(a,b),and(b,c)) ought to be fine... but on the other hand it can be more efficiently rewritten as and(a,or(b,c)). 11:24 <@sipa> And dealing with this case isn't simple either. 11:47 < sanket1729> Here is another (bad)suggestion. We allow repeated keys, but when when reasoning about fees/witness cost, we consider the effect of third party malleability. 11:48 <@sipa> Hmm. 11:48 <@sipa> So inside the signing algorithm, you mean? 11:48 < sanket1729> The signing would stay the same 11:48 <@sipa> That's probably not hard. 11:49 <@sipa> Oh, then I don't know what you mean. 11:49 < sanket1729> When reasoning about witness size, we should assume that third party can go from one HASSIG to another HASSIG with the same sigs 11:50 <@sipa> Well we already take the maximum size of all satisfaction paths, I think? 11:50 <@sipa> in case of maybes 11:52 < sanket1729> Relooking the signing code again. 11:53 <@sipa> But at signing time, I think we can actually keep track of the set of keys-signed-with, and use those to guide choices. 11:54 <@sipa> Maybe all of this is moot though - if you're working with reasonable scripts, there just won't be duplicates across choices (because actual malleability) or across conjunctions (because dumb). 11:58 < sanket1729> If we keep track of keys signed with. When choosing between two YESes, we should take the maximum if it is possible to malleate from one stack to another. 11:59 < sanket1729> Sorry about it earlier, the signing algorithm does change 11:59 < sanket1729> I think this is the superset thing that you were referring to earlier 12:01 < sanket1729> I tend to think that it's not worth the effort because of the above reason you stated 12:02 <@sipa> yeah 12:04 <@sipa> I think it may also run into issues with ops/stacksize, because now the signing algorithm may choose branches which have lower witness size, but higher ops/stacksize than the static analysis assumed. 12:04 <@sipa> So this would require making those static analyses take potentially-malleable combinations into account, as they may at signing time be discovered to be non-malleable still. --- Log closed Thu May 26 00:00:35 2022