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

jonasnick · 2024-01-06T20:40:28Z

EDIT: based on #1518. Closes #1452. Most of the code is a copy from libsecp256k1-zkp. The API added in this PR is identical with the exception of two modifications:

I removed the unused scratch_space argument from secp256k1_musig_pubkey_agg. This argument was intended to allow using ecmult_multi algorithms for key aggregation in the future. But at this point it's unclear whether the scratch_space object will remain in its current form (see Rework or get rid of scratch space #1302).
Support for adaptor signatures was removed and therefore the adaptor argument of musig_nonce_process was also removed.

In contrast to the module in libsecp256k1-zkp, the module is non-experimental. I slightly cleaned up parts of the module, adjusted the code to the new definition of the VERIFY_CHECK macro and applied some simplifications that were possible because the module is now in the upstream repo (ge_from_bytes, ge_to_bytes). You can follow the changes I made to the libsecp256k1-zkp module at https://github.com/jonasnick/secp256k1-zkp/commits/musig2-upstream/.

include/secp256k1_extrakeys.h

src/secp256k1.c

jonasnick · 2024-01-11T14:01:04Z

Rebased on top of master to get #1480 which allowed dropping a commit. Old state is preserved at https://github.com/jonasnick/secp256k1/tree/musig2-module-backup.

real-or-random

needs rebase :)

real-or-random · 2024-01-18T16:50:28Z

include/secp256k1_extrakeys.h

+/** Sort public keys using lexicographic order of their compressed
+ *  serialization.
+ *
+ *  Returns: 0 if the arguments are invalid. 1 otherwise.
+ *
+ *  Args:     ctx: pointer to a context object
+ *  In:   pubkeys: array of pointers to pubkeys to sort
+ *      n_pubkeys: number of elements in the pubkeys array
+ */
+SECP256K1_API int secp256k1_pubkey_sort(
+    const secp256k1_context *ctx,
+    const secp256k1_pubkey **pubkeys,
+    size_t n_pubkeys
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2);
+


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.

real-or-random · 2024-01-18T16:55:17Z

src/modules/musig/keyagg.h

+/* musig_ge_to_bytes_ext and musig_ge_from_bytes_ext are identical to ge_save and ge_load
+ * except that they allow saving and loading the point at infinity */
+static void secp256k1_musig_ge_to_bytes_ext(unsigned char *data, secp256k1_ge *ge);
+
+static void secp256k1_musig_ge_from_bytes_ext(secp256k1_ge *ge, const unsigned char *data);


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.

t-bast · 2024-01-23T14:19:46Z

FWIW, we have JVM bindings on top of this branch in ACINQ/secp256k1-kmp#93 and an implementation of swap-in-potentiam (musig2 key-path with alternative delayed script path) in ACINQ/bitcoin-kmp#107 and everything is working fine, and the API is easy enough to use!

jonasnick · 2024-01-23T19:23:30Z

Rebased.

Thanks @t-bast, that's good to hear.

siv2r · 2024-02-01T05:21:26Z

Attaching a visualization for the API flow.

Edit: The above visualization is incorrect. I will update it with the correct one soon.

siv2r · 2024-02-05T10:23:29Z

examples/musig.c

+        pubkeys_ptr[i] = &signers[i].pubkey;
+    }
+    printf("ok\n");
+    printf("Combining public keys...");


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.

siv2r · 2024-02-06T09:13:54Z

src/modules/musig/session_impl.h

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.

include/secp256k1_musig.h

real-or-random · 2024-03-14T08:13:43Z

include/secp256k1_musig.h

+ *     If you do not provide a seckey, session_secrand32 _must_ be UNIFORMLY RANDOM
+ *     AND KEPT SECRET (even from other signers).


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.

real-or-random · 2024-03-14T08:18:14Z

include/secp256k1_musig.h

+ *  2. If you already know the seckey, message or aggregate public key
+ *     cache, they can be optionally provided to derive the nonce and increase
+ *     misuse-resistance. The extra_input32 argument can be used to provide


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

real-or-random · 2024-03-14T08:25:27Z

include/secp256k1_musig.h

+ *  1. The nonrepeating_cnt argument must be a counter value that never
+ *     repeats, i.e., you must never call `secp256k1_musig_nonce_gen_counter`
+ *     twice with the same seckey and nonrepeating_cnt value.


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

josibake

I'm also using the heapsort commits in #1471. What do you think about splitting out the sort commits into their own PR? Also fine with cherry-picking for now, but figured I'd mention it since it might simplify both of our PRs.

josibake · 2024-04-08T14:41:15Z

src/modules/extrakeys/main_impl.h

+    /* Suppress wrong warning (fixed in MSVC 19.33) */
+    #if defined(_MSC_VER) && (_MSC_VER < 1933)
+    #pragma warning(push)
+    #pragma warning(disable: 4090)
+    #endif


in 26dde29 ("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.

jonasnick · 2024-04-16T19:32:39Z

@josibake

What do you think about splitting out the sort commits into their own PR?

That's a good idea. In particular, if more fixups are needed for the sort commits. See #1518.

7d2591c Add secp256k1_pubkey_sort (Jonas Nick) Pull request description: This PR adds a `secp256k1_pubkey_sort` function the the public API which was originally part of the musig PR (#1479). However, I opened a separate PR because it adds internal functions that are also used by the WIP silent payments module. ACKs for top commit: sipa: ACK 7d2591c josibake: ACK 7d2591c real-or-random: ACK 7d2591c Tree-SHA512: d0e4464dc9cd4bdb35cc5d9bb4c37a7b71233328319165d49bc940d8d3394a2d74a43d2f73ee7bfe8f3f90a466ee8afcdca75cfbbf3969e218d76b89f4af55fb

jonasnick force-pushed the musig2-module branch from f5a74fd to fb60ae9 Compare January 6, 2024 21:56

real-or-random reviewed Jan 7, 2024

View reviewed changes

include/secp256k1_extrakeys.h Outdated Show resolved Hide resolved

real-or-random reviewed Jan 7, 2024

View reviewed changes

src/secp256k1.c Outdated Show resolved Hide resolved

jonasnick force-pushed the musig2-module branch 5 times, most recently from ab7fc1e to eaf1e78 Compare January 8, 2024 08:06

Davidson-Souza mentioned this pull request Jan 8, 2024

Topicos Janeiro saopaulobitdevs/saopaulobitdevs.org#17

Closed

jonasnick force-pushed the musig2-module branch from eaf1e78 to 70bb685 Compare January 11, 2024 13:58

real-or-random added the feature label Jan 11, 2024

real-or-random mentioned this pull request Jan 18, 2024

Upstream PRs 1426, 1430, 1184, 1437, 1442, 1441, 1445, 1438, 1393, 1446, 1450, 1451, 1431, 990, 1455, 1380, 1465, 1466, 1473, 1474, 1476, 1480, 1468, 1482, 1249 BlockstreamResearch/secp256k1-zkp#285

Merged

sstone mentioned this pull request Jan 18, 2024

Add support for musig2 ACINQ/secp256k1-kmp#93

Merged

real-or-random reviewed Jan 18, 2024

View reviewed changes

narcelio mentioned this pull request Jan 23, 2024

Topicos Janeiro plebemineira/bhbitdevs.org#1

Open

jonasnick force-pushed the musig2-module branch from 70bb685 to dd4932b Compare January 23, 2024 19:21

theStack mentioned this pull request Jan 30, 2024

Add silentpayments (BIP352) module #1471

Closed

siv2r reviewed Feb 5, 2024

View reviewed changes

siv2r reviewed Feb 6, 2024

View reviewed changes

Roasbeef mentioned this pull request Feb 12, 2024

Lightning Specification Meeting 2024/02/12 lightning/bolts#1134

Closed

22 tasks

real-or-random reviewed Mar 7, 2024

View reviewed changes

include/secp256k1_musig.h Outdated Show resolved Hide resolved

jonasnick force-pushed the musig2-module branch from 2017bbe to 4619706 Compare March 10, 2024 14:57

real-or-random reviewed Mar 14, 2024

View reviewed changes

achow101 mentioned this pull request Mar 18, 2024

wallet: Be able to receive and spend inputs involving MuSig2 aggregate keys bitcoin/bitcoin#29675

Draft

josibake reviewed Apr 8, 2024

View reviewed changes

extrakeys: add secp256k1_pubkey_sort

cc7d18a

jonasnick added 9 commits April 16, 2024 19:18

group: add ge_to_bytes and ge_from_bytes

e60c7bf

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

a8b9761

build: allow enabling the musig module in cmake

503fe7e

fixup! use optimized tagged hashes

bfc0d33

fixup! move musig_ge_{to,from} to group.h

426aa2f

fixup! split counter mode from musig_nonce_gen

590cb5e

fixup! Add pubkey_sort to changelog

458e039

fixup! add musig module to change log

8b0309b

fixup! improve nonce_gen doc

ae7ca3d

jonasnick mentioned this pull request Apr 16, 2024

Add secp256k1_pubkey_sort #1518

Merged

jonasnick force-pushed the musig2-module branch from 3b6c90a to ae7ca3d Compare April 16, 2024 19:29

real-or-random mentioned this pull request Apr 18, 2024

FROST Trusted Dealer BlockstreamResearch/secp256k1-zkp#278

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

jonasnick commented Jan 6, 2024 •

edited

jonasnick commented Jan 11, 2024

real-or-random left a comment

real-or-random Jan 18, 2024

jonasnick Mar 8, 2024

real-or-random Jan 18, 2024

jonasnick Mar 8, 2024

t-bast commented Jan 23, 2024

jonasnick commented Jan 23, 2024

siv2r commented Feb 1, 2024 •

edited

siv2r Feb 5, 2024 •

edited

real-or-random Feb 5, 2024

siv2r Feb 6, 2024

jonasnick Mar 8, 2024

real-or-random Mar 14, 2024

real-or-random Mar 14, 2024

jonasnick Apr 16, 2024

real-or-random Mar 14, 2024

jonasnick Apr 16, 2024

real-or-random Mar 14, 2024

jonasnick Apr 16, 2024

josibake left a comment

josibake Apr 8, 2024

jonasnick Apr 16, 2024

jonasnick commented Apr 16, 2024

		* If you do not provide a seckey, session_secrand32 _must_ be UNIFORMLY RANDOM
		* AND KEPT SECRET (even from other signers).

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

Are you sure you want to change the base?

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

Conversation

jonasnick commented Jan 6, 2024 • edited

jonasnick commented Jan 11, 2024

real-or-random left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

t-bast commented Jan 23, 2024

jonasnick commented Jan 23, 2024

siv2r commented Feb 1, 2024 • edited

siv2r Feb 5, 2024 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

josibake left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jonasnick commented Apr 16, 2024

jonasnick commented Jan 6, 2024 •

edited

siv2r commented Feb 1, 2024 •

edited

siv2r Feb 5, 2024 •

edited