This PR attempts to add an exhaustive test for 2-of-2 signature aggregation via MuSig2. Currently, only the combinations of each participant’s possible signing keys are fully iterated, and other involved cryptographic elements (generated nonces, signing challenge etc.) are either derived from a counter or statically set. Some invalid conditions that are practically unreachable on the full group order for secp256k1 (due to negligible probablity) can obviously hit for the exhaustive group test orders, so some special treatment is needed here to avoid a crash in the test. Those three conditions are:
- aggregated public key results in the point at infinity (in
secp256k1_musig_pubkey_agg): https://github.com/bitcoin-core/secp256k1/blob/a88aa9350633c2d2472bace5c290aa291c7f12c9/src/modules/musig/keyagg_impl.h#L216-L217 → the PR copes with that by letting the function return 0 instead if the condition hits and we compile for exhaustive tests, and skip the current iteration at the call-site in that case - one of the generated nonce scalars is zero (in
secp256k1_musig_nonce_gen{,_counter}): https://github.com/bitcoin-core/secp256k1/blob/a88aa9350633c2d2472bace5c290aa291c7f12c9/src/modules/musig/session_impl.h#L442-L443 → the PR copes with that by letting the function return 0 instead if the condition hits and we compile for exhaustive tests, and try to generate a nonce another time with different input (increased counter), until it succeeds - the generated final nonce is the point at infinity (in
secp256k1_musig_nonce_process): https://github.com/bitcoin-core/secp256k1/blob/a88aa9350633c2d2472bace5c290aa291c7f12c9/src/modules/musig/session_impl.h#L601-L603 This one was a bit tricky. On the full group order, this condition can only be true if both of the aggregated nonce group elements (which are supplied externally) are the point at infinity (encoded as 66 zero-bytes), caused by either a dishonest nonce aggregator or dishonest signer, see https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki#user-content-Dealing_with_Infinity_in_Nonce_Aggregation. On the reduced group orders, this can hit frequently, making the aggregated signature verification fail in the end. → the PR copes with that by checking if the final nonce is G (when possibly a reduction has happened) and skip signing/verification then. that’s a bit hacky and skips also legit cases (i.e. we arrive at G for the final nonce without the reduction being involved), but works for now :-)
I’m asking for general comments at this point what would make the most sense in an exhaustive musig test, or if it is even worth it to have one at all. If yes, is it a good idea to change function behaviour depending on exhaustive tests being compiled? Are there other solutions that I haven’t thought of? It’s also a bit strange that some iterations are skipped, so there should probably an extra check at the end (right now if all iterations are skipped, we wouldn’t even notice it, apart from the WIP-printf output). I guess the basic idea of the PR is still slightly better than having nothing, but still far away from what we would want ideally.
Number of full iterations (i.e. nothing is skipped due to any condition described above) depending on the exhaustive test order:
- EXHAUSTIVE_TEST_ORDER=7 → 18/36 full iterations (50%)
- EXHAUSTIVE_TEST_ORDER=13 → 99/144 full iterations (68.75%)
- EXHAUSTIVE_TEST_ORDER=199 → 38453/39204 full iterations (98.08%)