How can many signers share one key?

Evidence

Each numbered marker in the text points here, and the ↩ links lead back to every place that cites an entry. Quotes are verbatim from the BIP files at commit 3a10b5b, including their wiki markup; links open the exact lines; the quoted text sits under each entry. Labels say what kind of statement each is: a rule, the author’s rationale, history, a test vector, or our own inference.

1. ↩ History BIP 327 (Jonas Nick, Tim Ruffing, Elliott Jin) was assigned in 2022 and is recorded as Deployed; it is Informational.

   BIP 327 L3–9

   Quoted source text (1)

   Title: MuSig2 for BIP340-compatible Multi-Signatures Authors: Jonas Nick <jonasd.nick@gmail.com> Tim Ruffing <crypto@timruffing.de> Elliott Jin <elliott.jin@gmail.com> Status: Deployed Type: Informational Assigned: 2022-03-22

2. ↩ a b Rule MuSig2 lets several signers create one aggregate public key and cooperatively produce ordinary Schnorr signatures under it; signing needs all of them: it is n-of-n, not a t-of-n threshold scheme.

   BIP 327 L30–32

   Quoted source text (1)

   MuSig2 is a multi-signature scheme that allows multiple signers to create a single aggregate public key and cooperatively create ordinary Schnorr signatures valid under the aggregate public key. Signing requires interaction between ''all'' signers involved in key aggregation. (MuSig2 is a ''n-of-n'' multi-signature scheme and not a ''t-of-n'' threshold-signature scheme.)

3. ↩ a b c Author’s rationale The authors argue a MuSig2 output is essentially one key and one signature, more compact and cheaper to verify than an n-of-n OP_CHECKSIGADD policy, with no consensus limit on n, and indistinguishable on chain from a single-signer Taproot output.

   BIP 327 L38–39 BIP 327 L39 BIP 327 L41

   Quoted source text (3)

   The on-chain footprint of a MuSig2 Taproot output is essentially a single BIP340 public key, and a transaction spending the output only requires a single signature cooperatively produced by all signers. This is '''more compact''' and has '''lower verification cost''' than each signer providing an individual public key and signature

   As a side effect, the number ''n'' of signers is not limited by any consensus rules when using MuSig2.

   MuSig2 Taproot outputs are indistinguishable for a blockchain observer from regular, single-signer Taproot outputs even though they are actually controlled by multiple signers.

4. ↩ Author’s rationale The authors' primary motivation is letting users of different software jointly control Taproot outputs, spent through the key path with a MuSig2 signature.

   BIP 327 L34–36

   Quoted source text (1)

   The primary motivation is to create a standard that allows users of different software projects to jointly control Taproot outputs ([https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki BIP341]). Such an output contains a public key which, in this case, would be the aggregate of all users' individual public keys. It can be spent using MuSig2 to produce a signature for the key-based spending path.

5. ↩ a b c Rule The aggregate key is a BIP 340 x-only key and the final signature passes BIP 340 verification for it; the individual keys fed to aggregation are plain 33-byte compressed keys.

   BIP 327 L52

   Quoted source text (1)

   In this proposal, the aggregate public key is a BIP340 X-only public key, and the signature output at the end of the signing protocol is a BIP340 signature that passes BIP340 verification for the aggregate public key and a message. The individual public keys that are input to the key aggregation algorithm are ''plain'' public keys in compressed format.

6. ↩ Rule BIP 327 standardizes the MuSig2 multi-signature scheme, compatible with BIP 340 public keys and signatures, with tweaking for BIP 32 child keys and BIP 341 Taproot outputs.

   BIP 327 L20–22

   Quoted source text (1)

   This document proposes a standard for the [https://eprint.iacr.org/2020/1261.pdf MuSig2] multi-signature scheme. The standard is compatible with [https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki BIP340] public keys and signatures.

7. ↩ a b c d Rule KeyAgg computes Q = a₁·P₁ + … + aᵤ·Pᵤ, where each coefficient aᵢ is a tagged hash of the hash of the whole key list and the key itself, except that the second distinct key gets coefficient 1 (the MuSig2* optimization, saving a point multiplication).

   BIP 327 L305–306 BIP 327 L334–337 BIP 327 L58

   Quoted source text (3)

   ** Let ''a_i = KeyAggCoeffInternal(pk_1..u, pk_i, pk2)''. * Let ''Q = a₁⋅P₁ + a₂⋅P₂ + ... + a_u⋅P_u''

   * Let ''L = HashKeys(pk_1..u)'' * If ''pk' = pk2'': ** Return 1 * Return ''int(hash_{KeyAgg coefficient}(L || pk')) mod n''

   The optimization consists of assigning the constant key aggregation coefficient ''1'' to the second distinct key in the list of individual public keys to be aggregated (as well as to any key identical to this key).

8. ↩ a b Rule The aggregate key depends on the order of the keys; KeySort can sort them when the application has no canonical order.

   BIP 327 L118–119

   Quoted source text (1)

   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.

9. ↩ a b c Test vector For BIP 327's three-key vector, the aggregate key differs when the same keys are given in reverse order, and neither equals the plain sum of the keys (checked by a test and at build time).

   BIP 327 L118

   Quoted source text (1)

   The aggregate public key produced by ''KeyAgg'' (regardless of the type) depends on the order of the individual public keys.

10. ↩ a b Author’s rationale The authors list its features: non-interactive key aggregation, two communication rounds (fewer than three-round schemes such as MuSig1), a security proof under the AOMDL assumption, and substantially lower complexity than MuSig-DN, at the cost of no deterministic nonces and signing state that must be handled securely.

    BIP 327 L45–46 BIP 327 L47 BIP 327 L48 BIP 327 L48

    Quoted source text (4)

    * '''Simple Key Setup''': Key aggregation is non-interactive and fully compatible with BIP340 public keys. * '''Two Communication Rounds''': MuSig2 is faster in practice than previous three-round multi-signature schemes such as [https://eprint.iacr.org/2018/068.pdf MuSig1]

    MuSig2 has been [https://eprint.iacr.org/2020/1261.pdf proven existentially unforgeable] under the algebraic one-more discrete logarithm (AOMDL) assumption (instead of the discrete logarithm assumption required for single-signer Schnorr signatures).

    However, this comes at the cost of having no ability to generate nonces deterministically and the requirement to securely handle signing state.

    '''Low complexity''': MuSig2 has a substantially lower computational and implementation complexity than alternative schemes like [https://eprint.iacr.org/2020/1057 MuSig-DN].

11. ↩ Rule The same key may appear more than once; the algorithms handle it, and the BIP recommends omitting duplicate checks to simplify error handling, noting it is often impossible then to tell which signer is to blame. Applications may still reject duplicates, for example when one owner runs several signing devices.

    BIP 327 L121–125 BIP 327 L125 BIP 327 L128–131

    Quoted source text (3)

    The same individual public key is allowed to occur more than once in the input of ''KeyAgg'' and ''KeySort''. This is by design: All algorithms in this proposal handle multiple signers who (claim to) have identical individual public keys properly, and applications are not required to check for duplicate individual public keys. In fact, applications are recommended to omit checks for duplicate individual public keys in order to simplify error handling.

    Moreover, it is often impossible to tell at key aggregation which signer is to blame for the duplicate

    While the algorithms in this proposal are able to handle duplicate individual public keys, there are scenarios where applications may choose to abort when encountering duplicates. For example, we can imagine a scenario where a single entity creates a MuSig2 setup with multiple signing devices.

12. ↩ a b Rule Signing takes two broadcast rounds: each signer runs NonceGen and broadcasts a public nonce, which are aggregated with NonceAgg; then each runs Sign and broadcasts a partial signature, and PartialSigAgg combines them into a signature that passes BIP 340 verification if all were honest.

    BIP 327 L83–85 BIP 327 L85 BIP 327 L87–91

    Quoted source text (3)

    '''First broadcast round:''' The signers start the signing session by running ''NonceGen'' to compute ''secnonce'' and ''pubnonce''.

    Then, the signers broadcast their ''pubnonce'' to each other and run ''NonceAgg'' to compute an aggregate nonce.

    '''Second broadcast round:''' At this point, every signer has the required data to sign, which, in the algorithms specified below, is stored in a data structure called [[#session-context|Session Context]]. Every signer computes a partial signature by running ''Sign'' with the secret signing key, the ''secnonce'' and the session context. Then, the signers broadcast their partial signatures to each other and run ''PartialSigAgg'' to obtain the final signature. If all signers behaved honestly, the result passes [https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki BIP340] verification.

13. ↩ Author’s rationale Each signer's nonce is two elliptic curve points; the authors chose the two-point variant, whose proof uses the random oracle plus algebraic group model.

    BIP 327 L59 BIP 327 L757–759

    Quoted source text (2)

    In this proposal, each signer's nonce consists of two elliptic curve points.

    and applies to an optimized scheme variant where the signers' nonces consist of only two points. This proposal uses the latter, optimized scheme variant.

14. ↩ Rule The first round, exchanging nonces, can happen before the message or the exact set of signers is known.

    BIP 327 L54

    Quoted source text (1)

    The first communication round, exchanging the nonces, can happen before the message or the exact set of signers is determined.

15. ↩ a b Rule Session values: the nonce coefficient b is a tagged hash of the aggregate nonce, the aggregate key and the message; the final nonce is R = R₁ + b·R₂; and e is the BIP 340 challenge for R, Q and the message. If R₁ + b·R₂ is the point at infinity, which signals a dishonest aggregator or signer, R is set to G so that signing continues and the culprit is revealed when partial signatures are verified.

    BIP 327 L427–434 BIP 327 L429–431 BIP 327 L434 BIP 327 L738–740

    Quoted source text (4)

    * Let ''b = int(hash_{MuSig/noncecoef}(aggnonce || xbytes(Q) || m)) mod n''

    * Let ''R' = R₁ + b⋅R₂'' * If ''is_infinite(R'): ** Let final nonce ''R = G''

    * Let ''e = int(hash_{BIP0340/challenge}(xbytes(R) || xbytes(Q) || m)) mod n''

    If the nonce aggregator provides ''aggnonce = bytes(33,0) || bytes(33,0)'', either the nonce aggregator is dishonest or there is at least one dishonest signer (except with negligible probability). If signing aborted in this case, it would be impossible to determine who is dishonest. Therefore, signing continues so that the culprit is revealed when collecting and verifying partial signatures.

16. ↩ a b c d Test vector This site's MuSig2 model, a transcription of BIP 327's reference code on audited curve arithmetic, reproduces every case in the BIP's eight JSON vector files, including the error cases with the same blamed signer or message; the four published signature-aggregation sessions aggregate to the published signatures, which noble's BIP 340 verifier accepts.

    BIP 327 L524–526

    Quoted source text (1)

    === Test Vectors and Reference Code ===

17. ↩ a b c d Rule PartialSigVerify checks s·G = Re + e·a·g′·P for one signer, using that signer's own public nonce; its only purpose is identifiable aborts. Partial signatures are not signatures and can be forged, but if all verify, the aggregate is a valid Schnorr signature.

    BIP 327 L504 BIP 327 L182–185 BIP 327 L185

    Quoted source text (3)

    * Fail if ''s⋅G &ne; Re_⁎ + e⋅a⋅g'⋅P''

    The only purpose of the algorithm ''PartialSigVerify'' is to ensure identifiable aborts, and it is not necessary to use it when identifiable aborts are not desired. In particular, partial signatures are ''not'' signatures. An adversary can forge a partial signature, i.e., create a partial signature without knowing the secret key for the claimed individual public key.

    However, if ''PartialSigVerify'' succeeds for all partial signatures then ''PartialSigAgg'' will return a valid Schnorr signature.

18. ↩ a b Rule PartialSigAgg adds the partial signatures and e·g·tacc, the tweak term, and returns xbytes(R) followed by the 32-byte sum: a 64-byte signature.

    BIP 327 L520–521

    Quoted source text (1)

    * Let ''s = s₁ + ... + s_u + e⋅g⋅tacc mod n'' * Return ''sig = ''xbytes(R) || bytes(32, s)''

19. ↩ a b Rule Plain tweaking derives child aggregate keys as in BIP 32; x-only tweaking adds a BIP 341 Taproot commitment, so an output can be spent with a MuSig2 signature or through a script path.

    BIP 327 L201–203

    Quoted source text (1)

    Plain tweaking can be used to derive child public keys from an aggregate public key using [https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki BIP32]. On the other hand, X-only tweaking is required for Taproot tweaking per [https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki BIP341]. A Taproot-tweaked public key commits to a ''script path'', allowing users to create transaction outputs that are spendable either with a MuSig2 multi-signature or by providing inputs that satisfy the script path.

20. ↩ Rule Each partial signature is s = k₁ + b·k₂ + e·a·d mod n, with the secret nonces negated if R has odd y and the key negated as Q and the tweaks require; the BIP recommends that a signer verify its own partial signature before releasing it, a check that can be omitted if too costly.

    BIP 327 L457 BIP 327 L466 BIP 327 L469 BIP 327 L469

    Quoted source text (4)

    * Let ''k₁ = k₁', k₂ = k₂' '' if ''has_even_y(R)'', otherwise let ''k₁ = n - k₁', k₂ = n - k₂' ''

    * Let ''s = (k₁ + b⋅k₂ + e⋅a⋅d) mod n''

    * If ''PartialSigVerifyInternal(psig, pubnonce, pk, session_ctx)'' (see below) returns failure, fail

    It is recommended but can be omitted if the computation cost is prohibitive.

21. ↩ Rule NonceGen must have a high-quality random generator; unlike BIP 340 signing, the nonces must not be derived deterministically from the session parameters, or active adversaries can trick a signer into reusing one.

    BIP 327 L135–136

    Quoted source text (1)

    '''IMPORTANT''': ''NonceGen'' must have access to a high-quality random generator to draw an unbiased, uniformly random value ''rand' ''. In contrast to BIP340 signing, the values ''k₁'' and ''k₂'' '''must not be derived deterministically''' from the session parameters because otherwise active adversaries can [https://medium.com/blockstream/musig-dn-schnorr-multisignatures-with-verifiably-deterministic-nonces-27424b5df9d6#e3b6 trick the victim into reusing a nonce].

22. ↩ a b Rule Sign must not be executed twice with the same secret nonce, since the secret key can then be extracted from the two partial signatures; implementations may erase the secret nonce after use, and an all-zero one is invalid.

    BIP 327 L95–98

    Quoted source text (1)

    '''IMPORTANT''': The ''Sign'' algorithm must '''not''' be executed twice with the same ''secnonce''. Otherwise, it is possible to extract the secret signing key from the two partial signatures output by the two executions of ''Sign''. To avoid accidental reuse of ''secnonce'', an implementation may securely erase the ''secnonce'' argument by overwriting it with 64 zero bytes after it has been read by ''Sign''. A ''secnonce'' consisting of only zero bytes is invalid for ''Sign'' and will cause it to fail.

23. ↩ Rule Passing the secret key, aggregate key and message to NonceGen when known is recommended as defense in depth, but only as a last resort against a bad random value.

    BIP 327 L140 BIP 327 L143

    Quoted source text (2)

    Therefore, it is recommended to provide the optional arguments ''sk'', ''aggpk'', and ''m'' if these session parameters are already determined during nonce generation.

    However, the protection provided by the optional arguments should only be viewed as a last resort.

24. ↩ Rule Signers are normally stateful, keeping the secret nonce between rounds, but one signer can be stateless: it waits for everyone else's nonces and the session parameters, then generates its nonce and signs at once, and may sign deterministically.

    BIP 327 L157–161 BIP 327 L161

    Quoted source text (2)

    In general, MuSig2 signers are stateful in the sense that they first generate ''secnonce'' and then need to store it until they receive the other signers' ''pubnonces'' or the ''aggnonce''. However, it is possible for one of the signers to be stateless.

    Stateless signers may want to consider signing deterministically (see [[#modifications-to-nonce-generation|Modifications to Nonce Generation]]) to remove the reliance on the random number generator in the ''NonceGen'' algorithm.

25. ↩ Rule Aborts are identifiable when contributions are not tampered with, nonce aggregation is honest, and every partial signature is verified; then an honest party's failing algorithm names exactly one malicious signer.

    BIP 327 L168–173 BIP 327 L173

    Quoted source text (2)

    Aborts are identifiable for an honest party if the following conditions hold in a signing session: * The contributions received from all signers have not been tampered with (e.g., because they were sent over authenticated connections). * Nonce aggregation is performed honestly (e.g., because the honest signer performs nonce aggregation on its own or because the aggregator is trusted). * The partial signatures received from all signers are verified using the algorithm ''PartialSigVerify''.

    then the algorithm run by the honest party will output the index of exactly one malicious signer.

26. ↩ Rule An untrusted aggregator can collect and combine nonces and partial signatures; a malicious one can make the session fail but cannot forge a signature, even colluding with all but one signer.

    BIP 327 L93

    Quoted source text (1)

    A malicious aggregator can force the signing session to fail to produce a valid Schnorr signature but cannot negatively affect the unforgeability of the scheme, i.e., even a malicious aggregator colluding with all but one signer cannot forge a signature.

27. ↩ Rule MuSig2 is compatible with BIP 340, not with the ECDSA signatures traditionally used in Bitcoin.

    BIP 327 L774–775

    Quoted source text (1)

    This document proposes a standard for the MuSig2 multi-signature scheme that is compatible with [https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki BIP340]. MuSig2 is ''not'' compatible with ECDSA signatures traditionally used in Bitcoin.