RFC: Add exhaustive test for 2-of-2 musig [WIP] #1615

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%)

The code itself looks good and meets the PR goal. But is there any specific reason for this test or is it just to increase test coverage?

Concept ACK, but in 13 one-line mutations I tried, this test caught nothing that tests -t=musig misses.

It could add coverage by looping over all challenges, as the TODO suggests, and over nonces.

Of six musig mutations it caught the four that break signing and missed the two that change key aggregation, since both signers then use the same wrong key and the signature still verifies. Of seven partial_sig_verify mutations it missed only the one that accepts every partial signature; a loop checking that every wrong value is rejected catches it for about 0.03 s at order 13, but tests -t=musig catches it too, as it does all 13. On master e74a018 the branch applies with one conflict in session_impl.h, and the musig part takes 0.2 s at order 13 and 4.7 s at 199.

f1df2b74cfbb4546443bf3051fdccba388eafdcc needs rebase