--- Log opened Tue Jan 24 00:00:23 2023
00:04 -!- salvatoshi [~salvatosh@genymobile-2-6-86.fib.nerim.net] has joined ##miniscript
00:15 -!- benma [~benma@2a02:168:5366:0:f7c2:b229:3cc7:8874] has joined ##miniscript
01:27 < benma> hi. i am looking at the non-canonical dissatisfactions of and_b with regards to malleability. the implementation at https://github.com/sipa/miniscript/blob/be0655fe76a7842eafbca8cfbbde2210126eb413/bitcoin/script/miniscript.h#L943 includes these marked as NonCanon, but does not mark them as Malleable, even though the witness would be malleable if these ended up in the witness. what am i missing?
01:28 < benma> sipa ^
03:22 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 256 seconds]
03:44 < darosior> benma: yeah it's missing 2 `SetMalleable()`. Note the latest version of the Miniscript codebase is at https://github.com/bitcoin/bitcoin/pull/24149. The miniscript repo wasn't updated in a long time and we'll do it once #24149 is merged.
04:04 -!- jonatack [~jonatack@user/jonatack] has joined ##miniscript
04:09 < benma> darosior: great
04:11 < benma> darosior: another small question: can the (non-canonical) dissat for and_v ever actually end up in a witness? 
04:12 < darosior> benma: and_v is non-dissatisfiable
04:12 < darosior> From the website: The fact that non-"d" expressions cannot be dissatisfied in valid witnesses rules out the usage of the non-canonical and_v dissatisfaction.
04:31 < benma> darosior: that is what i thought, but then why does the implementation add it then? https://github.com/bitcoin/bitcoin/pull/24149/files#diff-a55760aaec4bce216663f5ebf65823516347356a8320d30459427149f7bbc2c5R922 - seems like it should just use INVALID there?
05:15 -!- sanket1729_ [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has joined ##miniscript
05:20 -!- Netsplit *.net <-> *.split quits: sanket1729
06:13 <@sipa> @benma Hmm, the fact that they're marked as non-canonical means the logic is already asserting that these solutions are never used, even without the malleable flag.
06:15 <@sipa> Ah, it's on the website:
06:15 <@sipa> > If and_b(X,Y) is "d", a non-HASSIG dissatisfaction "dsat(Y) dsat(X)" must exist, and thus rules out any usage of "dsat(Y) sat(X)" and "sat(Y) dsat(X)". Those are also overcomplete. 
07:45 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
07:45 < benma> sipa: for and_v it is clear why it is never used. for and_b, they could be used (if malleable solutions are allowed), right? 
07:46 <@sipa> Sure, but all of this is about the non-malleable signing algorithm.
07:46 <@sipa> If you accept malleable solutions, things being marked as malleable doesn't matter.
07:47 <@sipa> So I think what happened here is that for and_b, there are (a) reasons why the sat/dsat mixed dissatisfactions are never used and (b) reasons why, if they were used, they would be malleable. And the code only implements (a).
07:48 <@sipa> (never used by the non-malleable signing algorithm, to be clear)
07:50 < benma> i am still confused - if it's only about non-malleable solutions, why are the `.Malleable()` satisfactions included at all in the code?
07:51 <@sipa> The non-malleable signing algorithm needs to know which solutions are malleable so it can avoid them?
07:52 <@sipa> Ah, I see what you mean now. We can't just leave them out, because they may be available to attackers, so their presence in some cases influences the reasoning.
07:53 <@sipa> There are lots of conditions for non-malleability; not including malleable sats/dsats is only one of them.
07:54 <@sipa> E.g. an or_b between two subexpressions that have both satisfactions without signatures in them has a malleable satisfaction, even when both the subexpressions' satisfactions are non-malleable.
07:58 < benma> maybe i need to understand this: if a candidate satisfaction is marked as .Malleable(), can it ever end up in the final (non-malleable) witness? 
07:58 <@sipa> No.
07:59 <@sipa> But it may cause another not-otherwise-malleable satisfaction to become malleable.
07:59 <@sipa> So just not having it could sometimes lead to incorrectly concluding that a non-malleable satisfaction exists, while in fact none so satisfaction exists.
08:04 <@sipa> You see what I'm saying?
08:05 <@sipa> Say you have or_b(X, Y). X has a nice non-malleable satisfaction that needs no signature. Y has a malleable satisfaction that needs no signature.
08:05 <@sipa> Any satisfaction for or_b(X,Y) is going to be malleable, because it's a branch between two no-signature choices, so whatever side you pick in the signing algorithm, a malleator (is that a word?) can turn it into the other one.
08:06 <@sipa> However, if we'd just remove the malleable Y satisfaction from the codebase, the algorithm would treat Y as having no satisfactions at all, which would make the or_b(X,Y) non-malleably satisfiable.
08:08 <@sipa> Because it wouldn't be able to observe the fact that a third party malleator has an additional option.
08:10 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 252 seconds]
08:12 -!- jonatack [~jonatack@user/jonatack] has joined ##miniscript
08:15 < benma> thanks - this is a clear explanation and resolves my misunderstanding! i will have to come up with more examples where this applies to get a better feel for it, e.g. some involving the non-canonical dissats of and_b
08:16 <@sipa> Also "NonCanon()" in the codebase has no effect apart from driving assertions. It's just there because reasoning exists of the form "we know this solution should never end up in the final solution", which can be asserted, but it otherwise has no impact on the choices made by the signing algorithm (otherwise it wouldn't be as useful as an assertion).
08:18 -!- jonatack [~jonatack@user/jonatack] has quit [Quit: WeeChat 3.8]
08:19 < benma> this assertion also holds for "Malleable()" though, so why the distinction?
08:19 < benma> also, should every NonCanon() satisfacation also be marked Malleable()?
08:20 -!- jonatack [~jonatack@user/jonatack] has joined ##miniscript
08:21 <@sipa> That's not true: https://github.com/sipa/miniscript/blob/master/bitcoin/script/miniscript.cpp#L338L339
08:21 <@sipa> Solutions being malleable definitely influences the choices made by the signing logic.
08:23 <@sipa> Also under "Non-malleable signing algorithm" on https://bitcoin.sipa.be/miniscript/, the "DONTUSE" flag there is what's called Malleable in the source code.
08:23 < benma> yes. the section basically says that every non-canonical satisfaction is DONTUSE, or not?
08:25 <@sipa> I think there are non-canonical things possible that are not malleable.
08:25 <@sipa> Because the non-malleable signing algorithm will never choose some things that are nonetheless non-malleable.
08:27 < benma> as an example, "The non-canonical options for and_b, or_b, and thresh are always overcomplete (reason 3), so instead use DONTUSE", but the code doesn't mark it as DONTUSE (SetMalleable), but just as NonCanon: https://github.com/bitcoin/bitcoin/pull/24149/files#diff-a55760aaec4bce216663f5ebf65823516347356a8320d30459427149f7bbc2c5R888
08:27 < benma> for thresh
08:29 <@sipa> Yeah, for the same reason as and_b not needing the SetMalleable.
08:29 <@sipa> > thresh(k,...) is always "d", a non-HASSIG dissatisfaction with just dissatisfactions must exist due to typing rules, and thus rules out usage of the other dissatisfactions. They are also overcomplete.
08:30 <@sipa> Basically not having the Malleable marker there makes the assertion's detection power stronger, because we know that even without informing the algorithm that the solution would be malleable, we can reason that it should never be used.
08:31 <@sipa> It wouldn't hurt to add Malleable() for those, but it would just mean an additional reason for the signing algorithm to avoid it.
08:32 <@sipa> Because if something is Malleable it definitely won't appear in the final solution, explicitly.
08:32 <@sipa> NonCanon() means "you should be able to figure out on your own that this should never be used".
08:32 < benma> so the SetMalleable() in the and_b case could also be removed here? https://github.com/bitcoin/bitcoin/pull/24149/files#diff-a55760aaec4bce216663f5ebf65823516347356a8320d30459427149f7bbc2c5R926
08:33 <@sipa> For that one there is no reasoning of the form "another non-sig solution always exists, so this one should never be used".
08:34 <@sipa> So no, the SetMalleable() is necessary there, because the only reason not to use that solution is that it's overcomplete, which is not something the signing algorithm knows on its own.
08:34 <@sipa> I guess we should add comments explaining all these things...
08:35 < benma> would be great, and also update https://bitcoin.sipa.be/miniscript/, as there it sounds like non-canon is the same as DONTUSE (which in the code is "Malleable()")
08:38 < benma> thanks for your time - it was more complicated than i expected at first glance :) takeaway: some dissats cannot be used due to the "d" type, so they don't need to be marked as Malleable explicitly. i understood this for and_v right away but not for thresh. the second confusion was that these sats/dsats still need to be included in the code as an attacker could use them to make a otherwise non-malleable solution mall
08:38 < benma> eable.
08:47 < benma> in rust-miniscript, it seems the non-canonical/malleable dissats are not considered for and_b? https://github.com/rust-bitcoin/rust-miniscript/blob/64e45459c4defaaef13994fa48d0dc68d5c0557a/src/miniscript/satisfy.rs#L1385 - could that lead to malleable solutions? cc sanket1729_ darosior
08:50 < benma> sipa: sry one more sanity check: could this and_v non-canon dissat be replaced by INVALID, i.e. is it only there so you can do sanity-checks on the non_canon property and nothing else?
08:50 < benma> https://github.com/bitcoin/bitcoin/pull/24149/files#diff-a55760aaec4bce216663f5ebf65823516347356a8320d30459427149f7bbc2c5R922
08:58 <@sipa> AFK now, will check in an hour or two.
09:06 -!- jonatack [~jonatack@user/jonatack] has quit [Quit: WeeChat 3.8]
09:14 -!- jonatack [~jonatack@user/jonatack] has joined ##miniscript
10:47 <@sipa> benma: I think that may be correct, at least for non-malleable signing. Though I could imagine a case where you accept a malleable signature and using this right-hand-dsat dissatisfaction of and_v is cheaper.
11:11 -!- roze_paul [~quassel@132.216.191.43] has quit [Remote host closed the connection]
11:56 < benma> thanks!
12:57 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 252 seconds]
13:04 -!- jonatack [~jonatack@user/jonatack] has joined ##miniscript
13:50 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
14:25 -!- benma [~benma@2a02:168:5366:0:f7c2:b229:3cc7:8874] has quit [Remote host closed the connection]
15:13 -!- roze_paul [~quassel@132.216.191.43] has quit [Quit: https://quassel-irc.org - Chat comfortably. Anywhere.]
15:13 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
15:15 -!- roze_paul [~quassel@132.216.191.43] has quit [Client Quit]
15:15 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
15:19 -!- roze_paul [~quassel@132.216.191.43] has quit [Client Quit]
15:19 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
15:24 -!- roze_paul [~quassel@132.216.191.43] has quit [Client Quit]
15:25 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
15:25 -!- roze_paul [~quassel@132.216.191.43] has quit [Client Quit]
15:25 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
15:27 -!- roze_paul_ [~quassel@132.216.191.43] has joined ##miniscript
15:28 -!- roze_paul [~quassel@132.216.191.43] has quit [Client Quit]
15:28 -!- roze_paul_ [~quassel@132.216.191.43] has quit [Client Quit]
15:34 -!- roze_paul [~quassel@132.216.191.43] has joined ##miniscript
15:35 -!- roze_paul [~quassel@132.216.191.43] has quit [Client Quit]
20:37 -!- troglodito [~cave@2a00:d880:3:1::85b7:69dc] has quit [Ping timeout: 252 seconds]
20:40 -!- troglodito [~cave@2a00:d880:3:1::85b7:69dc] has joined ##miniscript
22:31 -!- w0xlt [sid555702@id-555702.ilkley.irccloud.com] has quit []
22:31 -!- w0xlt [sid555702@id-555702.ilkley.irccloud.com] has joined ##miniscript
--- Log closed Wed Jan 25 00:00:25 2023