Add module "musig" that implements MuSig2 multi-signatures (BIP 327) #1479

Remind me what the difference was to the function secp256k1_ec_pubkey_cmp. Is there no difference and we simply overlooked this? I suspect what happened is this:

• When we had x-only keys as input to key agg, we had to add a comparison function for x-only keys (to extrakeys module)
• Then we switched to compressed keys as input, and we changed the comparison function to also take compressed keys, not noticing that there's one already in secp256k1.h

There is no difference. I removed the commit.

I think we should simply get rid of this branch entirely, see #1352. I can work on a PR next week.

See #1480

Yes thanks! I considered doing this but didn't want to make this PR dependent on a separate issue.

Got rid of this by rebasing.

I think this function should be in the main module because it works on secp256k1_pubkey objects, and the comparison function is also there. (Extrakeys would make sense for x-only, I guess.) I don't think code size is an issue, the heap sort implementation should be tiny.

That's reasonable. Done.

I think these should be in group.h, even though they'll be used only by the musig module. Infinity can be helpful in other contexts, and conceptually it's a group function.

Anyway, the comment needs to be updated ge_save and ge_load have been renamed.

Agree, done.

Do we recommend that users sort their pubkeys before aggregating them? The musig_pubkey_agg API documentation simply says the user "can" do it.

If we recommend the sorting step, including it in the example file would be helpful.

I think there's no catch-all recommendation. BIP327 says "The aggregate public key produced by KeyAgg (regardless of the type) depends on the order of the individual public keys. If the application does not have a canonical order of the signers, the individual public keys can be sorted with the KeySort algorithm to ensure that the aggregate public key is independent of the order of signers."

In other words: If in your application, the collection of pubkeys (or signers represented by them) is conceptually an (ordered) list, then don't bother with sorting. If in your application, the collection of pubkeys is conceptually an (unordered) set, i.e., the application doesn't want to care about the order of pubkeys, then sort to make sure the set has a canonical serialization.

Perhaps we can explain this somewhere in more detail, either in the API docs or in the example.

nit: I think it would be nice to including sorting in the example for the following reasons:

• It provides a practical example on how to use the sorting API
• It's a good hook for adding a comment explaining what @real-or-random just explained above. Feels a bit nicer to have that comment in the example, vs the API docs

Added sorting and a comment.

Is there any specific reason for avoiding sha256 mid-state optimization in the musig_compute_noncehash and nonce_function_musig functions?

Because apparently I had been to lazy so far :D. I added this optimization.

We should probably rename this. Despite this big fat warning, session_id itself sounds like a public value.

Brain dump:

• session_nonce: too easy to confuse with the sec nonce
• session_rand: but what if it's counter
• session_seed: okayish

But now that I think about this again, I believe that the confusion stems from the fact that we have these two modes: It's either random and secret, or a counter, but that's only okay if you provide a seckey. A single name that fits both scenarios is necessarily imprecise.

I think a better approach is to provide two different functions, e.g., secp256k1_musig_nonce_gen and secp256k1_musig_nonce_gen_with_counter (like in the BIP where we have CounterNonceGen as a separate algorithm). Then we can have clear argument names, even very verbose ones like session_secret_rand and nonrepeating_counter. Moreover, we can enforce the presence of the seckey in the counter function.

Agreed. I split the two nonce_gen functions.

We should then drop the condition "If you do not provide a seckey,"

We could also add a reference to the new function, maybe below the numbered list.

something like "If you don't have access to good randomness, but you have access to a non-repeating counter, then see ..."

Added both suggestions.

seckey is mandatory for this function anyway.

I think usually I would suggest moving this big explainer at the top of the module, so that it covers both functions and does not need to be repeated. But in this case of a big fat warning, it's probably better to keep it in the docstring, where it's harder to miss...

dropped mention of seckey

We could expand a bit to mention that this includes cases where the same seckey is used on multiple devices. (Any other precautions to mention?)

done

in https://github.com/bitcoin-core/secp256k1/pull/1479/commits/26dde295d0ad12a011fc4062ad642852f7ff68fa ("extrakeys: add secp256k1_pubkey_sort"):

Does it make sense to move this block into the secp256k1_sort function? I ended up copying these lines while writing a secp256k1_silentpayments_recipient_sort function, which made me realize anyone else would also need to copy these lines when writing a sort function for heapsort.

You mean into secp256k1_hsort? I'd guess the wrong warning is emitted when secp256k1_hsort is called and therefore it would be to late when the warning was disabled in secp256k1_hsort.

c936266: why does second_pk_x need to be normalized?

it doesn't anymore, fixed

c936266: micro nit: s/x/pk_x

This was a bogus comment anyway. Fixed.

c936266: slightly confused here and in L277. is a VERIFY_CHECK instead of return 0 sufficient for these failures?

I believe so. These conditions are effectively unreachable. If they do become reachable, then we have a serious bug that the tests hopefully notice. Moreover, we cannot exercise the VERIFY_CHECKed conditions with a test, so if we would add a branch we couldn't cover it.

c936266: nit: remove double (()).

done

This line can be removed, as the function was already added in the last release 0.5.0

fixed

This code block already exists about 30 lines above (was it intended to be moved from top to bottom?).

I think the duplication was just introduced as a mistake when rebasing after #1482

Yes, fixed

Verified that the example also succeeds with larger values of N_SIGNERS, like e.g. 15000. At some point if the limit is increased further (e.g. 20000), segmentation faults occur on my machine, I guess this happens due to some stack limits being exceeded.

I replaced the stack allocations with heap allocations here: https://github.com/josibake/secp256k1/commit/35ac3b194aefc064e8cee94e93498be224cc0d69

and ran the example with 100,000 signers. Everything up until signing was very fast, whereas signing took 45 mins (ran on a relatively powerful machine). Worth mentioning the time is a somewhat useless number here and the goal was more to stress test. The sign function in the example does both rounds of communication in the same function and the partial signing is done sequentially, whereas in reality the partial signing would be done in parallel

I was a quite confused at first that signing took 45 minutes on your machine, until I realized that all signers in the example effectively do the coordinator's job of aggregating nonces. I changed that to only aggregate nonces once. Entire example with 100,000 signers takes 12 seconds on my laptop now.

Ah, nice!

            return 0;

oops, fixed

nit:

    /* Note that we did not provide an output_pk argument, because the

done

nit: if an operation takes longer, it would be nice to see this message already before the function call following returns

    printf("Signing message........."); fflush(stdout);

(noticed this for larger values of N_SIGNERS, for the value of 3 chosen here it shouldn't matter though even on slow hardware)

Makes sense. Added fflush after every printf without a newline.

c936266: don't we need to do the e⋅g⋅tacc part of this equation s = s1 + ... + su + e⋅g⋅tacc mod n?

We've already done the g*tacc computation in tweak_add and e*g*tacc in nonce_process.

 *  include/secp256k1_musig.h and doc/musig.md.

done

Shouldn't this function call _musig_partial_sig_load, in order to check the 4 bytes magic and verify that the scalar doesn't overflow? (similar to the _musig_{pub,agg}nonce_serialize functions which also call _musig_{pub,agg}nonce_load first)

Added a memcmp. I don't think parsing the scalar is necessary because if properly initialized (which we ensure by checking the magic), the scalar cannot overflow. _musig_{pub,agg}nonce_serialize call load because they are required to do more work.

nit: IIUC, agg_pk can be directly retrieved in the _musig_pubkey_agg call:

 *  secp256k1_musig_pubkey_agg(..., agg_pk, keyagg_cache, pubkeys, ...)

(that's how it's also done in the API description for the x-only tweaking function below)

Yep, fixed

nit: not sure how strict we want to be here to match the exact API, but with all parameters considered, it would look like e.g.

 *  secp256k1_ec_pubkey_serialize(..., buf2, &outlen, agg_pk, ...)

fixed

 *  secp256k1_musig_pubkey_xonly_tweak_add(..., output_pk, keyagg_cache, tweak32)

fixed

c936266: what is the difference between doing ARG_CHECKs like this here vs SECP256K1_ARG_NONNULL(4) checks in the function declaration for the same function parameter.

The SECP256K1_ARG_NONNULL attribute relies on a GNU extension that can give a warning at compile time. A failing ARG_CHECK will call the illegal_callback at runtime. They complement each other.

c936266: isn't this a repetition of L230?

Yes, removed

c936266: s/session_secrand/nonrepeating_cnt

fixed

c936266: SECP256K1_ARG_NONNULL(4) too?

nonrepeating_cnt isn't a pointer, so it cannot be NULL.

nit, could also check the lower bound of prefix_size:

    VERIFY_CHECK(prefix_size >= 1 && prefix_size <= 8);

Done

could use the _write_be64 helper here:

    secp256k1_write_be64(buf, nonrepeating_cnt);

nice, done

Is this comment a leftover? I couldn't figure out to what sizeof it refers to and where a subtraction happens.

Yes, removed the comment

I've noticed that the aggregated nonce points are converted from affine to jacobi coordinates here, and then again from jacobi to affine inside secp256k1_musig_nonce_process_internal. Could pass as affine coordinates to the internal function instead in order to do only one conversion there. With the following patch, the tests still pass:

<details> <summary>Patch</summary>

diff --git a/src/modules/musig/session_impl.h b/src/modules/musig/session_impl.h
index b0ea45d..b073ec0 100644
--- a/src/modules/musig/session_impl.h
+++ b/src/modules/musig/session_impl.h
@@ -557,14 +557,14 @@ static int secp256k1_musig_compute_noncehash(unsigned char *noncehash, secp256k1
     return 1;
 }
 
-static int secp256k1_musig_nonce_process_internal(int *fin_nonce_parity, unsigned char *fin_nonce, secp256k1_scalar *b, secp256k1_gej *aggnoncej, const unsigned char *agg_pk32, const unsigned char *msg) {
+static int secp256k1_musig_nonce_process_internal(int *fin_nonce_parity, unsigned char *fin_nonce, secp256k1_scalar *b, secp256k1_ge *aggnonce, const unsigned char *agg_pk32, const unsigned char *msg) {
     unsigned char noncehash[32];
     secp256k1_ge fin_nonce_pt;
     secp256k1_gej fin_nonce_ptj;
-    secp256k1_ge aggnonce[2];
+    secp256k1_gej aggnoncej[2];
 
-    secp256k1_ge_set_gej(&aggnonce[0], &aggnoncej[0]);
-    secp256k1_ge_set_gej(&aggnonce[1], &aggnoncej[1]);
+    secp256k1_gej_set_ge(&aggnoncej[0], &aggnonce[0]);
+    secp256k1_gej_set_ge(&aggnoncej[1], &aggnonce[1]);
     if (!secp256k1_musig_compute_noncehash(noncehash, aggnonce, agg_pk32, msg)) {
         return 0;
     }
@@ -588,7 +588,6 @@ static int secp256k1_musig_nonce_process_internal(int *fin_nonce_parity, unsigne
 int secp256k1_musig_nonce_process(const secp256k1_context* ctx, secp256k1_musig_session *session, const secp256k1_musig_aggnonce  *aggnonce, const unsigned char *msg32, const secp256k1_musig_keyagg_cache *keyagg_cache) {
     secp256k1_keyagg_cache_internal cache_i;
     secp256k1_ge aggnonce_pt[2];
-    secp256k1_gej aggnonce_ptj[2];
     unsigned char fin_nonce[32];
     secp256k1_musig_session_internal session_i;
     unsigned char agg_pk32[32];
@@ -607,10 +606,8 @@ int secp256k1_musig_nonce_process(const secp256k1_context* ctx, secp256k1_musig_
     if (!secp256k1_musig_aggnonce_load(ctx, aggnonce_pt, aggnonce)) {
         return 0;
     }
-    secp256k1_gej_set_ge(&aggnonce_ptj[0], &aggnonce_pt[0]);
-    secp256k1_gej_set_ge(&aggnonce_ptj[1], &aggnonce_pt[1]);
 
-    if (!secp256k1_musig_nonce_process_internal(&session_i.fin_nonce_parity, fin_nonce, &session_i.noncecoef, aggnonce_ptj, agg_pk32, msg32)) {
+    if (!secp256k1_musig_nonce_process_internal(&session_i.fin_nonce_parity, fin_nonce, &session_i.noncecoef, aggnonce_pt, agg_pk32, msg32)) {
         return 0;
     }

</details>

Cool, implemented your suggestion.

nit: could assign the result directly rather than adding (session_i.s_part is zero at this point):

        session_i.s_part = e_tmp;

yes, done

nit: though it doesn't hurt, normalizing doesn't seem to be necessary, considering that pk is created via deserialization (_musig_secnonce_load -> _ge_from_bytes -> _ge_from_storage -> _fe_from_storage), where the group element's coordinates x and y are always normalized initially. Same for pk.x below.

Removed both calls to fe_normalize

Considering that rand contains secret data, should it be cleared at the end of the function? (same for buf and sha_tmp in the loop below I guess)

Done

c9362664e: micro grammar nit: s/is normalizes/normalizes

c9362664e: micro nit: we could remove the last 33 bytes and make it expected_secnonce[64].

Hm the test vector is 97 bytes though. I changed the test to check that last 33 bytes of expected_secnonce as well, to make sure it's really the public key as expected.

I think this was lost in some rebase.

 * Automatically generated by tools/test_vectors_musig2_generate_.py.

And just remove contrib/musig2-vectors.py, the PR currently adds the (identical) script to both paths.

Not a rebase issue, just confusion: I had thought that I had forgotten to add the python script because it's called differently in -zkp.

fixed

nit:

## API misuse

(also for all other headings below)

# is the same level as the heading for the entire document, see the rendered file.

fixed

(Okay, I'm all in favor of not doing updating years and stuff, but this is just too wrong. :D)

 * Written by Jonas Nick                                                 *

Removed name and year from all headers

nit

    /* Note that we did not provide an output_pk argument, because the
     * resulting pk is also saved in the cache and so if one is just interested
     * in signing, the output_pk argument is unnecessary. On the other hand, if

(for avoiding this to be read as "signing the output_pk argument")

Fixed.

The aggregated agg_pk resulting from the _musig_pubkey_agg is an x-only public key, so it can't be used for the _ec_pubkey_... functions below. Seems like the earlier version, getting agg_pk from the keyagg_cache via _musig_pubkey_get(...), was correct (sorry, it was me who proposed this "simplification" in #1479 (review) 🤦‍♂️ ).

 *  secp256k1_musig_pubkey_agg(..., keyagg_cache, pubkeys, ...)
 *  secp256k1_musig_pubkey_get(..., agg_pk, keyagg_cache)
 *  secp256k1_musig_pubkey_ec_tweak_add(..., output_pk, tweak32, keyagg_cache)
 *  secp256k1_ec_pubkey_serialize(..., buf, ..., output_pk, ...)
 *  secp256k1_ec_pubkey_tweak_add(..., agg_pk, tweak32)
 *  secp256k1_ec_pubkey_serialize(..., buf2, ..., agg_pk, ...)

Oops I missed that too, fixed.

nit: the resulting agg_pk is not used here, as it's overwritten in the tweak call below (maybe it's also fine to keep passing it for demonstration purposes, I just thought it could cause confusion, in the sense that readers think this result is needed for the tweaking below, in addition to the cache)

Set agg_pk argument to NULL and improved comment.

Should the secrets be cleared out (here and in sign), like also done in other examples?

Thanks, secrets should be cleared everywhere now.

nit, feel free to ignore:

    unsigned char pks_hash[32];

maybe, to express that this is the hash of multiple pubkeys, not a single one?

done

 * otherwise tagged_hash(pk_hash, pk) where pk_hash is the hash of public keys.

fixed

nit

    if (agg_pk != NULL) {
        secp256k1_extrakeys_ge_even_y(&pkp);
        secp256k1_xonly_pubkey_save(agg_pk, &pkp);
    }

done

in https://github.com/bitcoin-core/secp256k1/pull/1479/commits/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

nit: spacing

/** This module implements BIP 327 "MuSig2 for BIP340-compatible
  * Multi-Signatures"
  * (https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki)
  * v1.0.0. You can find an example demonstrating the musig module in
  * examples/musig.c.
  *
  * The module also supports BIP-341 ("Taproot") public key tweaking.
  *
  * It is recommended to read the documentation in this include file carefully.
  * Further notes on API usage can be found in doc/musig.md
  *
  * Since the first version of MuSig is essentially replaced by MuSig2, we use
  * MuSig, musig and MuSig2 synonymously unless noted otherwise.

I improved this doc comment in a way that's consistent with the existing doc.

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Seems brittle to point to a blog for an important warning about the risks of using a struct in this library. What about copying the relevant parts from the blog into doc/musig.md and updating this link to point to the docs?

Yeah, I re-read the post and I'm not sure what exactly we wanted to convey here. The link predates the BIP. I think just saying that copying the nonce can leak the secret key is clear enough. I removed the link.

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

micro-nit: for all of the other function pairs, the order in the header is parse, serialize. This one switches the order, which is a bit ocd' triggering :sweat_smile:

Let's minimize the triggers where reasonable ;P Changed.

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

nit: this reads a bit like a suggestions, perhaps:

 *  This function is required if you want to _sign_ for a tweaked aggregate key.
 *  If you are only computing a public key but not intending to create a signature 
 *  for it, use `secp256k1_ec_pubkey_tweak_add` instead.

done

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

nit: same as above:

 *  This function is required if you want to _sign_ for a tweaked aggregate key.
 *  If you are only computing a public key but not intending to create a signature 
 *  for it, use `secp256k1_xonly_pubkey_tweak_add` instead.

done

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Any reason *cache_i isn't const? You'd need to also make the in params for both _ge_to_bytes and _ge_to_bytes_ext to be const, but seems like they should be unless I'm missing something.

FWIW, I changed these functions to const and was able to compile and run the tests.

Thanks, fixed.

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Note to self/other reviewers: this initially tripped me up a bit as I expected something like memcpy(ptr, &cache_i->parity_acc, 1); but after some googling, apparently this is the more idiomatic/performant way of doing this!

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

nit: slightly more readable if pk is plural:

static int secp256k1_musig_compute_pk_hash(const secp256k1_context *ctx, unsigned char *pk_hash, const secp256k1_pubkey * const* pks, size_t n_pks) {

done

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Could move this outside the loop to make this slightly more performant and, imo, more readable. Not sure the performance matters but could make a difference if computing pk_hash for a large number of keys?

I think that would be less readable than declaring the variables only in the block where they are needed. The compiler will almost certainly optimize the current version to not cause any overhead.

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Not sure how important this check is , but I noticed this branch is not covered while checking gcov results. IIUC, the test case to add would be for pk and second_pk to have the same x value but even and odd y values.

Good catch! We want everything covered by gcov. I replaced this with ge_equals_ge_var which was added after I wrote this code.

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Note to self/reviewers: wasn't obvious to me how ctx was being used at first but it's being used in the ARG_CHECK macro.

On second thought, seems a bit strange to be using ARG_CHECK inside an internal function (i.e., not exposed in the musig module API). Why not do an assert or a return here, which would let you simplify the function by removing ctx from the function signature?

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Feels like I'm missing some context here. Generally, I'd expect setting the group element to the point at infinity to be a failure (i.e., expect the function to return 0;). But here it seems to be perfectly acceptable? My guess is that this failure mode is handled later on in a different function? It might be worth add some context in the comment for why this function is returning true, despite returning the point at infinity in the output param

The point of the serialize_ext and parse_ext functions is to be able to serialize and parse the point at infinity. So this is not a failure case. This is noted in the doc of the function:

/* Outputs the point at infinity if the given byte array is all zero, otherwise
 * attempts to parse compressed point serialization. */

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

static void secp256k1_musig_secnonce_save(secp256k1_musig_secnonce *secnonce, const secp256k1_scalar *k, const secp256k1_ge *pk) {

fixed (also in a few other places in session_impl.h)

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

static int secp256k1_musig_secnonce_load(const secp256k1_context* ctx, secp256k1_scalar *k, secp256k1_ge *pk, const secp256k1_musig_secnonce *secnonce) {

fixed

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

Generally speaking, seems like the ARG_CHECKS should be happening in the public facing functions, not internal functions? i.e., doing a runtime check inside a function an external caller doesn't have access to seems a bit strange to me.

At the cost of code duplication?

In this case, I think it helps with the clarity to have the arg checking happen in the public function before calling the internal function (even at the cost of code duplication).

That being said, this is really just a style nit so feel free to resolve this discussion if you prefer the (current) more concise version.

I tried this suggestion and I prefer the more concise version.

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

per my comment above, this is where I'd expect the ARG_CHECKS to happen, vs inside the internal function

in https://github.com/bitcoin-core/secp256k1/commit/f8f4f3c7a10345295ed72cdae0faecff37a919e5:

This function could be simplified to return void if the ARG_CHECK were moved outside the function (seems like we could safely check these conditions before calling _load?)

The while is unnecessary here (see #1570)

Let's keep it consistent for now with the other examples.

It might be worth including a warning in the example (or even the API docs) that the tweak functions take generic tweaks and it is the caller's responsibility to make sure these tweaks are safely and correctly computed, e.g., according to the BIP341 spec in the case of a taproot commitment.

When reviewing the musig_pubkey_tweak_add_internal function, I was a bit surprised when I didn't see taptweak logic in the function because I had seen "taproot commitment", "tap tweak" mentioned a few times in the API docs/examples. Obviously, it makes sense that this would be a generic tweak32 and we wouldn't want the musig2 module to be implementing logic from other protocols, but I could also see a naive caller passing h to _xonly_tweak_add, assuming it will be computing H_TapTweak(P || h)under the hood.

Good point. I updated the include file, example & musig.md to clarify that tweak32 is supposed to be a hash. Also added two sentences to the include file that say that the user is responsible for providing a tweak32 that is compatible with MuSig2 (although it is not known whether a fully attacker-controlled tweak32 breaks unforgeability).

nit: perhaps worth having an assert that secnonce is 0 to drive the point home?

Hm, then people will copy the assert into their code...

nit: spacing

int main(void) {

nit: ordering, add secp256k1_extrakeys.hsince keypair is used

#include <secp256k1.h>
#include <secp256k1_extrakeys.h
#include <secp256k1_musig.h>
#include <secp256k1_schnorrsig.h>

In the API description for _musig_partial_sig_parse: the statement "sig will always be initialized" is currently not true, as the function returns if the scalar encoded in in32 overflows, without setting sig: https://github.com/jonasnick/secp256k1/blob/cf20ad88cd15bd21fcae9e3e7080d310434a21ce/src/modules/musig/session_impl.h#L281-L294

I removed that paragraph.

What we can provide to the user is the guarantee that even if the return value of partial_sig_parse isn't checked, then partial_sig_verify will for sure fail. Even though that was already the case due to the magic, I added an extra memset to make this extra clear. I don't see a reason to mention this to the user (they should just check return values...).

whitespace nit

    if (!secp256k1_keyagg_cache_load(ctx, &cache_i, keyagg_cache)) {

in _musig_nonce_gen_internal: for the internal pubkey serialization function _eckey_pubkey_serialize, the last parameter is a bool, rather than a collection of flags:

    pk_serialize_success = secp256k1_eckey_pubkey_serialize(&pk, pk_ser, &pk_ser_len, 1);

(out of scope for this PR, but maybe we should assert compressed == 0 || compressed == 1 in this function, to avoid issues like this that can happen very easily?)

in _musig_nonce_gen_internal: nit, could limit the scope of cache_i to where it's needed, i.e inside the if (keyagg_cache != NULL) body

fixed

in API description for _musig_nonce_process: should the "Takes the public nonces of" part be replaced by something like "Takes the public aggregated nonce of..."?

Wow this sentence was older than nonce aggregation. Fixed.

whitespace nit

    const secp256k1_musig_aggnonce *aggnonce,

pedantic mini-nit: the public _parse/_serialize functions appear in a different order in the API description than in the implementation file here (parse, serialize vs serialize, parse)

fixed

nit, since this is just a single byte:

    acc = 0;

(or is this then more likely to be optimized out by the compiler?)

I guess dead store elimination happens at a later compilation stage that does not care whether the store came from an assignment or a memset, so they're equally likely to be optimized out by the compiler.

So unfortunately both variants are without effect. The advantage of an explicit memset is that it stands out / is grepable, if something wants to pick up #636. (Feel free to give it a shot :P)

this function always succeeds, so it could be declared void instead, and the return value check in _musig_nonce_process_internal below can then be removed as well.

fixed

nit: duplicate call

fixed

any reason why storing the result into ret and calling the _CHECKMEM_DEFINE macro isn't needed/done here?

The return value doesn't depend on secret data.

nit: one initialized too much i guess

/* Checks that the initialized tagged hashes have the expected

fixed

nit: not sure if it's worth to change it, but could either use strlen or sizeof(tag)-1 to avoid specifying the exact size for the array

        char tag[] = "KeyAgg list";
        secp256k1_musig_keyagglist_sha256(&sha);
        sha256_tag_test_internal(&sha, (unsigned char*)tag, sizeof(tag)-1);

done

in https://github.com/bitcoin-core/secp256k1/pull/1479/commits/2288e8808883556dc27cea6a61f409c08f70b30d:

nit: took me a second to mentally parse this function since the variable name is singular (ge), but it really is two group elements. Not a big deal since this is an internal function, but I think it would be more clear if the variable name were something like ges or two_ges. There are several other places where an array of secp256k1_ge objects is referred to as just ge, would be nice to make them all plural if you end up taking this suggestion.

Ok, I should have replaced all the singulars with plurals.

in https://github.com/bitcoin-core/secp256k1/pull/1479/commits/2288e8808883556dc27cea6a61f409c08f70b30d:

nit: same feedback regarding singular vs plural:

static void secp256k1_musig_compute_noncehash(unsigned char *noncehash, secp256k1_ge *aggnonces, const unsigned char *agg_pk32, const unsigned char *msg) {

this should be moved up to the "Unreleased" section now

Oh, done!

nit: no field element type is used in this header, so could remove this include

done

comment nit in function secp256k1_musig_partial_sig_verify: IIUC, the effective nonce here is computed from the individual signer's public nonce points, not the aggregated ones (the latter we could just fetch from the session instance), according to https://github.com/bitcoin/bips/blob/97012a82064c7247df502a170c03b053825cdd15/bip-0327.mediawiki?plain=1#L497-L499

    /* Compute "effective" nonce rj = pubnonce[0] + b*pubnonce[1] */
    /* TODO: use multiexp to compute -s*G + e*mu*pubkey + pubnonce[0] + b*pubnonce[1] */
    if (!secp256k1_musig_pubnonce_load(ctx, nonce_pt, pubnonce)) {
        return 0;
    }

Yes, done.

in the secp256k1_musig_nonce_process API description: should the "some signer..." part be removed, as suggested in secp256k1-zkp (https://github.com/BlockstreamResearch/secp256k1-zkp/pull/189)? seems like the "sent invalid pubnonce" case would have already been caught previously by the nonce aggregation function

 *  Returns: 0 if the arguments are invalid, 1 otherwise

Right, forgot about that. We can even make the type of nonce_process_internal void.

nit: this line shouldn't be needed, as fin_nonce_ptj is overwritten in the next line anyways

fwiw, out of curiosity I tried deduplicating the calculation of $R = R1 + b*R2$ (needed both for calculating the final nonce in _musig_nonce_process and for the "effective" nonce in the partial sig verification _musig_partial_sig_verify) on the following branch: https://github.com/theStack/secp256k1/commit/419c05cce03b2b719fcdc86f734f86a87953bdf1 Not sure if its worth it to pick this up, but if yes, it probably needs a better name for the helper function 😅

Yes, done. Also added your helper function.

It's unclear to me if these structs have any alignment needs. On the surface it looks like they don't but that might make the performance worse on some architectures? If it's not the case then it could be still nice to explicitly say they are unaligned in the doc. If it's the case maybe instead align them and say it in the doc?

Hm, I don't see how anyone could get the idea that any type in a public header would have stricter alignment than what C anyway requires (unless otherwise specified in the header, of course). And The implied alignment is 1 in this case.

As far as I remember, we "read" from these char arrays into our internal data structures (the performance penalty is probably negligible), and so alignment shouldn't matter for performance either.

Someone coming from Rust and being paranoid about everything. :D Thanks for clarifying, though I think a documentation comment would still be nice.

Wouldn't it be better to declare this as const unsigned char (*in66)[66]? Aside from clarity it could help static analysis tools or perhaps bindings generators to generate correct bindings.

That's an interesting point. Right now, we consistently use declarations of the form const unsigned char *in66 consistently in the library. I prefer to have a standard across the whole API and would avoid just changing this in the musig module.

That makes sense. Might be nice to change all of them at some point unless there's a problem I'm missing.

You cannot pass arrays as arguments in C; they collapse into pointers. The syntax

int some_func(char c[32]) {
    ...
}

is for all intents and purposes equivalent to int some_func(char *c) { ...}, including the fact that sizeof(c) will be 4 or 8 bytes (same as sizeof(char*)). Because it is so confusing, it's generally considered misleading to use arrays as arguments in C code.

EDIT: Oh, you're not suggesting this, but int some_func(char (*c)[32]) instead. That does work, and equivalent after compilation, but it does mean an additional & at the caller, and an additional * inside the callee. Can you elaborate on the (potential) advantages for static analysis or binding generators?

For instance in Rust we have bindgen, a tool that generates bindings automatically. I've tried to pass it this header file:

void foo(const unsigned char *arg);
void bar(const unsigned char arg[32]);
void baz(const unsigned char (*arg)[32]);

And it generated this code:

extern "C" {
    pub fn foo(arg: *const ::std::os::raw::c_uchar);
}
extern "C" {
    pub fn bar(arg: *const ::std::os::raw::c_uchar);
}
extern "C" {
    pub fn baz(arg: *const [::std::os::raw::c_uchar; 32usize]);
}

As you can see, the last one has a different type. And while it's the same from ABI perspective, there's a real difference between them in Rust since you can directly pass in &array without any casts because the types match making the code more obviously correct.

Currently, we aren't using bidgen in rust-secp256k1 but we might in the future and I'd be surprised if similar tools don't exist in other languages.

Also I'm not familiar with the current state of static analysis in C but I think a reasonable static analyzer should be able to see that statements like out[33] = 42 or baz(&twentyone_item_array) are obviously wrong. gcc already complains about the these when compiling with -O2 -W -Wall -Warray-bounds.

Interesting!

It's unfortunate that it's an API break to introduce this (but indeed not an ABI break, I think).

Oh, I found that bindgen has an option to generate *const [c_uchar; 32] instead of *const c_uchar for arguments defined as const unsigned char arg[32], so maybe even that is already valuable? (IIUC not API-breaking) I think it has documentation value too.

It looks like cppcheck is also able to detect mistakes when you use these (I haven't tested but I found a PR that supposedly does it.)

@Kixunil We discussed this in our IRC meeting today. Can you try if bindgen understands arg[static 32]? This is a special syntax in C99, see https://hamberg.no/erlend/posts/2013-02-18-static-array-indices.html

Nit: the public nonces.

fixed

I think it makes sense to stress that the normal (safer) mode is to construct the nonces after the message is known, rather than only pointing out the alternative here.

Suggested language:

Steps 1 through 5 above can happen before or after the message to be signed is known to the signers. Wherever possible, it is recommended to only generate the nonces after the message is known, as it has more defense-in-depth measures, but requires two communication rounds at signing time. The alternative, generating the nonces in a pre-processing step before the message is known, removes those measures, but means signing can happen non-interatively.

Agree, improved the wording.

In case someone has no way around storing session data on disk somewhere, would the recommendation be:

• To store/load the secnonce to/from disk (violating rule 3 here, plus risking platform dependence).
• To store/load the session_secrand32 to/from disk and re-run secp256k1_musig_nonce_gen to obtain the same secnonce (violating rule 1 here, and duplicating computation).

I suspect some users will have not have the ability to leave the secnonce in volatile memory, so it may be useful to give advice on how to do that (plus reiterate the dangers of not wiping the stored data after signing).

We don't provide the ability to serialize the secnonce right now, which prevents users from storing/loading from disk. Maybe worth a separate PR?

Well they can just store the raw bytes on disk, which works, but risks platform-dependency issues.

If we provide the on store/load the secnonce from disk, we should also provide de/serialization functions because our API docs instruct users to not read the raw bytes. I had considered this out of scope for this initial PR because it seems dangerous. Especially since so far no one requested this feature, just "don't store to disk" seems to be a sensible answer.

Actually one developer asked me about the missing de/serialization functions for the secnonce but further discussion on their motivation for requesting this revealed that they planned to build a very insecure protocol because they had entirely misunderstood what nonce reuse actually is. In the end they agreed that they should not store the secnonce to disk and changed their implementation accordingly.

Also I had hoped that someone would eventually come up with a more clever API that can protect from misuse better than simple de/serialization functions (at least in some cases). But maybe that just doesn't exist.

That's totally reasonable, but I don't think you have answered my question. If someone is somehow not able to keep everything in volatile memory, they have two (bad) options (store secnonce, or store session_secrand32), and both options violate a rule. Which of the two would you, as API and protocol designer, recommend people take?

If someone really needs to do this right now, then I would probably recommend option 2. In contrast to option 1, if you reuse session_secrand but you're signing for a different message or aggregate public key, you're protected.

One downside of that method is that session_secrand has no "in-memory protection", in the sense that the session_secrand buffer is not cleared after nonce_generation. We do wipe the secnonce after signing. Maybe we should change nonce generation to overwrite the session_secrand buffer?

I agree that option 2 is better for the reasons mentioned.

We do wipe the secnonce after signing. Maybe we should change nonce generation to overwrite the session_secrand buffer?

That sounds reasonable to me.

Seems like a good idea, yes.