Skip to content
This repository has been archived by the owner on Jun 6, 2024. It is now read-only.

musig: tracking issue #92

Open
7 of 15 tasks
oleganza opened this issue Feb 15, 2019 · 1 comment
Open
7 of 15 tasks

musig: tracking issue #92

oleganza opened this issue Feb 15, 2019 · 1 comment

Comments

@oleganza
Copy link
Contributor

oleganza commented Feb 15, 2019

About MuSig

For multi-signature accounts and multi-party contracts we need to implement a n-of-n MuSig protocol (overview, paper).

The verification construction is very similar to the aggregated transaction signature except the key aggregation happens offline — the verifier is exposed only to the single pubkey.

The proving construction is a 3-round MuSig procedure (see the MuSig paper).

We'll also need to extend the ZkVM witness types and Prover API to handle the multi-party signing: we'd need to produce verifiable "signing instructions" that every co-signer can check before computing their part of the signature. It's not clear yet how that should be structured - this remains to be designed.

Checklist

FAQ

What's the role of Merlin transcripts?

MuSig can be specified more cleanly with transcripts rather than with nested hash constructions: e.g. instead of making a delinearization factor as H(my key, H(all keys)) you'd just commit all pubkeys into a transcript, then squeeze all factors one by one from it. Also, no need to specify message hashing and padding - just have the user prepare the signature transcript however they please and then do the schnorr proof with it w/o worrying about the message.

How do we do 2-of-3 and other thresholds?

Via predicate tree: happy path would be the most-expected 2-of-2 (Alice+Bob), while other combinations (Alice+Carol, Bob+Carol) tucked into deeper branches. This does not scale well to large number of participants, but works fine for typically small sizes.

Why not a threshold scheme?

Threshold signatures (m-of-n, m ≤ n) use a very similar cryptographic construction outlined in MuSig paper, yet have two important practical differences:

  1. The secret keys have to be interactively created. N-of-N aggregation allows every party to generate or even reuse their existing keys (e.g. derived from a Keytree keytree: new package for key derivation scheme with Ristretto and Merlin #87) w/o having to make a multi-round protocol to compute some synthetic keys and have them stored.
  2. Threshold signatures are more compact than a merkle tree of combinations, but not accountable: you can never learn who were exact parties that signed off the particular message. For some protocols it's important to know whether "cold storage key" or "escrow agent" was involved or not. Combining n-of-n keys with the predicate tree allows seeing who actually signed, while threshold signatures erase this information. Note: accountability is available only to the parties in-the-know, for the rest of the network all the keys look random.

We'd eventually need threshold scheme too, especially for large thresholds or for cases where accountability is not necessary and we only need redundancy.

References

@oleganza
Copy link
Contributor Author

Seems like for "51%" threshold with a predicate tree and k-of-k keys, the merkle proof grows linearly with the number of parties:

https://www.wolframalpha.com/input/?i=plot+log_2%5BBinomial%5B2k,k%2B1%5D%5D+for+k+from+1+to+10

image

@oleganza oleganza changed the title musig: implementation of aggregated N-of-N signatures with Ristretto and Merlin musig: tracking issue Mar 21, 2019
oleganza pushed a commit that referenced this issue Mar 27, 2019
As described here: #92

  Make own MuSigError
  Make own TranscriptProtocol
  Make own PointOp (instead of direct verification), for compatibility with ZkVM
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant