Implementation error for malleability type inference for `or_d`

[benma]

The e type property for or_d is computed as e=e_x*e_y

https://github.com/sipa/miniscript/blob/484386a50dbda962669cc163f239fe16e101b6f0/bitcoin/script/miniscript.cpp#L175

The website's type table however states that e=e_z (which in the code would be e=e_y):

https://github.com/sipa/miniscript/blob/484386a50dbda962669cc163f239fe16e101b6f0/index.html#L624

The rust-miniscript library also implements it as e=e_y:

https://github.com/rust-bitcoin/rust-miniscript/blob/a0648b3a4d63abbe53f621308614f97f04a04096/src/miniscript/types/malleability.rs#L241

[darosior]

I don't think it's an error in the C++ implementation. In a Script of the form:

[X] IFDUP NOTIF [Z] ENDIF

If it has more than one dissatisfactions that don't involve a signature (take sha256() for instance), so does the script. Therefore the e property for or_d requires that both x and y be e. (EDIT: after https://github.com/sipa/miniscript/issues/128#issuecomment-1375729585)

It looks like it's rather the spec table and the Rust implementation that are wrong here. Good catch.

[benma]

@darosior thanks for checking. Can you open an issue at Rust miniscript, or should I?

[darosior]

Yeah i think i'll just open a PR there. ------- Original Message ------- Le lundi 9 janvier 2023 à 3:38 PM, benma @.***> a écrit :

@.***(https://github.com/darosior) thanks for checking. Can you open an issue at Rust miniscript?

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: @.***>

[darosior]

Also unrelated to this issue but if you are reading the implementation, note it's slightly out of date in this repo. The latest version is in the Bitcoin Core repo at https://github.com/bitcoin/bitcoin/tree/master/src/script.

[sipa]

In or_d, the first (X) argument is required to be "d", so "d_x" and "d_x d_z" are equivalent.

[sipa]

Sorry, my previous comment was besides the point; this is about "e", not "d".

Still, the same reasoning applies.

For an or_d to be non-malleable, the left argument must be "e"; if it's not, the script is already malleable, and the entirety of e/f/s properties don't matter anymore (because their only purpose is assessing malleability).

Therefore, for the cases where the "e" property on or_d matters, "e_y" and "e_x & e_y" are equivalent expressions. In de website the simpler one ("e_y") is listed, but in the C++ code, it was easier to implement "e_x & e_y". That does mean that strictly speaking these two versions won't always end up with the same types, but for non-malleable miniscripts, they will.

[benma]

@sipa thanks, good to know.

It would be nice to have test vectors shared by implementations. The ones in rust-miniscript at ms-tests.rs could be a great start, but they check against expected type properties. It would be helpful to have the same implementation for this type property everywhere so these test vectors can be used, or to change the test vectors to disregard e/s/f and only focus on m. I guess the latter would be better :thinking: cc @darosior

[darosior]

I agree shared test vectors would be helpful. I've had to adapt some myself for https://github.com/darosior/python-bip380. I think it's doable (just long) to make rust-miniscript not assign malleability analysis properties if the Miniscript is malleable and then fix the test vectors from there.

I think a better approach than the dozens of thousands (!!!) of rust-miniscript's vectors pseudo-randomly generated using Aloy would be to compile a list of a few dozens vectors exercising the various properties, share it between implementations and eventually add it to a potential Miniscript-descriptors BIP.

An alternative to test the correctness of a new implementation is to fuzz it against existing ones. I know in the past the Rust and C++ implementations have been fuzzed one against the other (it was prior to my involvement with the project so i don't know whether there is any code nor if it was very effective). We also spent quite a lot of time trying to create effective fuzz targets prior to integrating the C++ implem in Bitcoin Core: https://github.com/bitcoin/bitcoin/blob/master/src/test/fuzz/miniscript.cpp, https://github.com/darosior/bitcoin/blob/miniscript_wallet_signing/src/test/fuzz/miniscript.cpp. These can probably be ran against the seeds at https://github.com/bitcoin-core/qa-assets to gather the specific miniscripts that exercised various code paths and test them against another implementation.

[benma]

Closing as there is not actually a bug as @sipa explained above.