Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add MuSig2 adaptor signatures #24

Open
wants to merge 1 commit into
base: master
Choose a base branch
from

Conversation

jonasnick
Copy link
Collaborator

Fixes #23.

Turns out it's not that easy to specify adaptor signatures for multisignatures while keeping a healthy balance between clarity and complexity. Perhaps that's why I haven't found an existing and complete one. So let me know if anyone has ideas for how to make the adaptor signature algorithms as specified here more understandable.

Since #23 mentions two different approaches for how to do MuSig2 adaptor signatures, I looked into the security definitions of Generalized Bitcoin-Compatible Channels and sketched out proofs for them. That was useful to iron out the adaptor signature spec itself, but I'm not sure if the sketches provide any value to the reader because it may well be that what I've written there is incomprehensible without being very familiar with both the Generalized Bitcoin-Compatible Channels and MuSig2 paper. And without having received feedback so far, I'm presuming they have significant holes.

md/musig2-adaptorsig.md Outdated Show resolved Hide resolved
They are not too different to the proof for Schnorr adaptor signatures in that publication, but does not require strong unforgeability of the underlying signature scheme
The sketches are intended to test above definition of the scheme, give some intuition about what adaptor signatures tries to achieve and should give a bit more confidence as long as there exists no complete proof.

### aExistential Unforgeability under Chosen Message Attack
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

extra a here

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That's actually the name according to the paper. Perhaps a stands for adaptor? Should probably add [sic].

Thus, the game starts by running the forger with the public key and generated public nonces until it provides a public key, nonces and message
The game responds with a pre-signature on the message with a fresh adaptor and the forger wins if it produces a signature for a message that hasn't appeared in a (pre-)signature query.

We will now describe an algorithm that transforms a winner of the aEUF-CMA into a winner against a EUF-CMA for multisignatures (as defined in the MuSig2 paper) which is simplified for brevity
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

aEUF

Copy link

@ejhanrienaOut ejhanrienaOut left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@

@jonasnick
Copy link
Collaborator Author

Note to self: See https://eprint.iacr.org/2021/150.pdf section 5 which contains definitions for two party adaptor sigs and a generic transformation from a one-party adaptor sig scheme to a two-party adaptor sig scheme.

Copy link
Contributor

@t-bast t-bast left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't have the skills to review the Security section, but the rest looks good to me.

Before reviewing this PR, I tried to independently figure out how to combine adaptor sigs and musig2, and ended up with the same result (apart from notation and some shortcuts). See t-bast/lightning-docs#15

Comment on lines +72 to +73
But this has the downside of revealing to every participant in the multisig that an adaptor signature protocol is being executed
For example, if there is a MuSig setup with three signers and only two of them are making use of adaptor signatures, then this option would require the third signer to know about the adaptor to compute `b`.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Interesting point to note, I hadn't thought about that.
I generally found it better to add T to R1 just because it stayed closer to the vanilla Musig2 construction, but that's an additional argument for it.

t'*G = T
```

## Security
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

very nit: since github markdown doesn't preserve the line returns, it looks a bit weird that the . are missing at the end of sentences in all of this section.

real-or-random added a commit to BlockstreamResearch/secp256k1-zkp that referenced this pull request Dec 20, 2021
ac1e367 musig: turn off multiexponentiation for now (Jonas Nick)
3c79d97 ci: increase timeout for macOS tasks (Jonas Nick)
22c8881 musig: replace MuSig(1) with MuSig2 (Jonas Nick)

Pull request description:

  The main commit comprises `905 insertions(+), 1253 deletions(-)`. The diff isn't as small as I had hoped, but that's mostly because it was possible to simplify the API quite substantially which required rewriting large parts. Sorry, almost all of the changes are in one big commit which makes the diff very hard to read. Perhaps best to re-review most parts from scratch.

  A few key changes:

  - Obviously no commitment round. No big session struct and no `verifier` sessions. No `signer` struct.
  - There's a new `secnonce` struct that is the output of musig_nonce_gen and derived from a uniformly random session_id32. The derivation can be strengthened by adding whatever session parameters (combined_pk, msg) are available. The nonce function is my ad-hoc construction that allows for these optional inputs. Please have a look at that.
  - The secnonce is made invalid after being used in partial_sign.
  - Adaptor signatures basically work as before, according to BlockstreamResearch/scriptless-scripts#24 (with the exception that they operate on aggregate instead of partial sigs)
  - To avoid making this PR overly complex I did not consider how this implementation interacts with nested-MuSig, sign-to-contract, and antiklepto.
  - Testing should be close to complete. There's no reachable line or branch that isn't exercised by the tests.
  - [x] ~In the current implementation when a signer sends an invalid nonce (i.e. some garbage that can't be mapped to a group element), it is ignored when combining nonces. Only after receiving the signers partial signature and running `partial_sig_verify` will we notice that the signer misbehaved. The reason for this is that 1) this makes the API simpler and 2) malicious peers don't gain any additional powers because they can always interrupt the protocol by refusing to sign. However, this is up for discussion.~ EDIT: this is not the case anymore since invalid nonces are rejected when they're parsed.
  - [x] ~For every partial signature we verify we have to parse the pubnonce (two compressed points), despite having parsed it in `process_nonces` already. This is not great. `process_nonces` could optionally output the array of parsed pubnonces.~ EDIT: fixed by having a dedicated type for nonces.
  - [x] ~I left `src/modules/musig/musig.md` unchanged for now. Perhaps we should merge it with the `musig-spec`~ EDIT: musig.md is updated
  - [x] partial verification should use multiexp to compute `R1 + b*R2 + c*P`, but this can be done in a separate PR
  - [x] renaming wishlist
      - pre_session -> keyagg_cache (because there is no session anymore)
      - pubkey_combine, nonce_combine, partial_sig_combine -> pubkey_agg, nonce_agg, partial_sig_agg (shorter, matches terminology in musig2)
      - musig_session_init -> musig_start (shorter, simpler) or [musig_generate_nonce](#131 (comment)) or musig_prepare
      - musig_partial_signature to musig_partial_sig (shorter)
  - [x] perhaps remove pubnonces and n_pubnonces argument from process_nonces (and then also add a opaque type for the combined nonce?)
  - [x] write the `combined_pubkey` into the `pre_session` struct (as suggested [below](#131 (comment)): then 1) session_init and process_nonces don't need a combined_pk argument (and there can't be mix up between tweaked and untweaked keys) and 2) pubkey_tweak doesn't need an input_pubkey and the output_pubkey can be written directly into the pre_session (reducing frustration such as Replace MuSig(1) module with MuSig2 #131 (comment))
  - [x] perhaps allow adapting both partial sigs (`partial_sig` struct) and aggregate partial sigs (64 raw bytes) as suggested [below](#131 (comment)).

  Based on #120.

ACKs for top commit:
  robot-dreams:
    ACK ac1e367
  real-or-random:
    ACK ac1e367

Tree-SHA512: 916b42811aa5c00649cfb923d2002422c338106a6936a01253ba693015a242f21f7f7b4cce60d5ab5764a129926c6fd6676977c69c9e6e0aedc51b308ac6578d
@jonasnick
Copy link
Collaborator Author

Note to self: See https://eprint.iacr.org/2021/150.pdf section 5 which contains definitions for two party adaptor sigs and a generic transformation from a one-party adaptor sig scheme to a two-party adaptor sig scheme.

The paper "Foundations of Adaptor Signatures" (https://link.springer.com/content/pdf/10.1007/978-3-031-58723-8.pdf) shows that there are gaps in previous formalizations. It would be better to argue for the security of MuSig2 adaptor signatures using their new definitions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

MuSig2 Adaptor Signatures
4 participants