--- bip: 327 title: "MuSig2 for BIP340-compatible Multi-Signatures" status: Deployed type: Informational authors: ["Jonas Nick","Tim Ruffing","Elliott Jin"] assigned: 2022-03-22 last_modified: 2026-08-19 topics: ["transactions"] license: "BSD-3-Clause" url: https://bipexplorer.com/bip/327 source: https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki --- # BIP 327: MuSig2 for BIP340-compatible Multi-Signatures > **In plain English:** Standardizes MuSig2, a scheme that lets several people jointly create a single signature that looks like an ordinary one-person Taproot signature. This makes shared-control wallets cheaper and more private, since outsiders cannot tell a multi-party spend from a single-owner one. ## Introduction ### Abstract This document proposes a standard for the [MuSig2](https://eprint.iacr.org/2020/1261.pdf) multi-signature scheme. The standard is compatible with [BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) public keys and signatures. It supports _tweaking_, which allows deriving [BIP32](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki) child keys from aggregate public keys and creating [BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki) Taproot outputs with key and script paths. ### Copyright This document is licensed under the 3-clause BSD license. ### Motivation 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.) The primary motivation is to create a standard that allows users of different software projects to jointly control Taproot outputs ([BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki)). 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. 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 would be required by an _n-of-n_ policy implemented using `OP_CHECKSIGADD` as introduced in ([BIP342](https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki)). As a side effect, the number _n_ of signers is not limited by any consensus rules when using MuSig2. Moreover, MuSig2 offers a **higher level of privacy** than `OP_CHECKSIGADD`: MuSig2 Taproot outputs are indistinguishable for a blockchain observer from regular, single-signer Taproot outputs even though they are actually controlled by multiple signers. By tweaking an aggregate public key, the shared Taproot output can have script spending paths that are hidden unless used. There are multi-signature schemes other than MuSig2 that are fully compatible with Schnorr signatures. The MuSig2 variant proposed below stands out by combining all the following features: - **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 [MuSig1](https://eprint.iacr.org/2018/068.pdf), particularly when signers are connected through high-latency anonymous links. Moreover, the need for fewer communication rounds simplifies the algorithms and reduces the probability that implementations and users make security-relevant mistakes. - **Provable security**: MuSig2 has been [proven existentially unforgeable](https://eprint.iacr.org/2020/1261.pdf) under the algebraic one-more discrete logarithm (AOMDL) assumption (instead of the discrete logarithm assumption required for single-signer Schnorr signatures). AOMDL is a falsifiable and weaker variant of the well-studied OMDL problem. - **Low complexity**: MuSig2 has a substantially lower computational and implementation complexity than alternative schemes like [MuSig-DN](https://eprint.iacr.org/2020/1057). However, this comes at the cost of having no ability to generate nonces deterministically and the requirement to securely handle signing state. ### Design - **Compatibility with BIP340**: 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. - **Tweaking for BIP32 derivations and Taproot**: This proposal supports tweaking aggregate public keys and signing for tweaked aggregate public keys. We distinguish two modes of tweaking: _Plain_ tweaking can be used to derive child aggregate public keys per [BIP32](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki). _X-only_ tweaking, on the other hand, allows creating a [BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki) tweak to add script paths to a Taproot output. See [below](#tweaking-the-aggregate-public-key) for details. - **Non-interactive signing with preprocessing**: The first communication round, exchanging the nonces, can happen before the message or the exact set of signers is determined. Once the parameters of the signing session are finalized, the signers can send partial signatures without additional interaction. - **Key aggregation optionally independent of order**: The output of the key aggregation algorithm depends on the order in which the individual public keys are provided as input. Key aggregation does not sort the individual public keys by default because applications often already have a canonical order of signers. Nonetheless, applications can mandate sorting before aggregation,[1] and this proposal specifies a canonical order to sort the individual public keys before key aggregation. Sorting will ensure the same output, independent of the initial order. - **Third-party nonce and partial signature aggregation**: Instead of every signer sending their nonce and partial signature to every other signer, it is possible to use an untrusted third-party _aggregator_ in order to reduce the communication complexity from quadratic to linear in the number of signers. In each of the two rounds, the aggregator collects all signers' contributions (nonces or partial signatures), aggregates them, and broadcasts the aggregate back to the signers. 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. - **Partial signature verification**: If any signer sends a partial signature contribution that was not created by honestly following the signing protocol, the signing session will fail to produce a valid Schnorr signature. This proposal specifies a partial signature verification algorithm to identify disruptive signers. It is incompatible with third-party nonce aggregation because the individual nonce is required for partial verification. - **MuSig2\* optimization**: This proposal uses an optimized scheme MuSig2\*, which allows saving a point multiplication in key aggregation as compared to MuSig2. MuSig2\* is proven secure in the appendix of the [MuSig2 paper](https://eprint.iacr.org/2020/1261). 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). - **Size of the nonce and security**: In this proposal, each signer's nonce consists of two elliptic curve points. The [MuSig2 paper](https://eprint.iacr.org/2020/1261) gives distinct security proofs depending on the number of points that constitute a nonce. See section [Choosing the Size of the Nonce](#choosing-the-size-of-the-nonce) for a discussion. ## Overview Implementers must make sure to understand this section thoroughly to avoid subtle mistakes that may lead to catastrophic failure. ### Optionality of Features The goal of this proposal is to support a wide range of possible application scenarios. Given a specific application scenario, some features may be unnecessary or not desirable, and implementers can choose not to support them. Such optional features include: - Applying plain tweaks after x-only tweaks. - Applying tweaks at all. - Dealing with messages that are not exactly 32 bytes. - Identifying a disruptive signer after aborting (aborting itself remains mandatory). - Dealing with duplicate individual public keys in key aggregation. If applicable, the corresponding algorithms should simply fail when encountering inputs unsupported by a particular implementation. (For example, the signing algorithm may fail when given a message which is not 32 bytes.) Similarly, the test vectors that exercise the unimplemented features should be re-interpreted to expect an error, or be skipped if appropriate. ### General Signing Flow The signers start by exchanging their individual public keys and computing an aggregate public key using the _KeyAgg_ algorithm. Whenever they want to sign a message, the basic order of operations to create a multi-signature is as follows: **First broadcast round:** The signers start the signing session by running _NonceGen_ to compute _secnonce_ and _pubnonce_.[2] 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 [BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) verification. Both broadcast rounds can be optimized by using an aggregator who collects all signers' nonces or partial signatures, aggregates them using _NonceAgg_ or _PartialSigAgg_, respectively, and broadcasts the aggregate result back to the signers. 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. **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. To simplify the specification of the algorithms, some intermediary values are unnecessarily recomputed from scratch, e.g., when executing _GetSessionValues_ multiple times. Actual implementations can cache these values. As a result, the [Session Context](#session-context) may look very different in implementations or may not exist at all. However, computation of _GetSessionValues_ and storage of the result must be protected against modification from an untrusted third party. This party would have complete control over the aggregate public key and message to be signed. ### Public Key Aggregation We distinguish between two public key types, namely _plain public keys_, the key type traditionally used in Bitcoin, and _X-only public keys_. Plain public keys are byte strings of length 33 (often called _compressed_ format). In contrast, X-only public keys are 32-byte strings defined in [BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki). The individual public keys of signers as input to the key aggregation algorithm _KeyAgg_ (and to _GetSessionValues_ and _PartialSigVerify_) are plain public keys. The output of _KeyAgg_ is a [KeyAgg Context](#keyagg-context) which stores information required for tweaking the aggregate public key (see [below](#tweaking-the-aggregate-public-key)), and it can be used to produce an X-only aggregate public key, or a plain aggregate public key. In order to obtain an X-only public key compatible with BIP340 verification, implementations call the _GetXonlyPubkey_ function with the KeyAgg Context. To get the plain aggregate public key, which is required for some applications of [tweaking](#tweaking-the-aggregate-public-key), implementations call _GetPlainPubkey_ instead. 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. 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, i.e., which signer came up with an individual public key honestly and which disruptive signer copied it. In contrast, MuSig2 is designed to identify disruptive signers at signing time (see [Identifying Disruptive Signers](#identifying-disruptive-signers)). 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. In that case, duplicates may not result from a malicious signing device copying an individual public key of another signing device but from accidental initialization of two devices with the same seed. Since MuSig2 key aggregation would accept the duplicate keys and not error out, which would in turn reduce the security compared to the intended key setup, applications may reject duplicate individual public keys before passing them to MuSig2 key aggregation and ask the user to investigate. ### Nonce Generation **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 _k1_ and _k2_ **must not be derived deterministically** from the session parameters because otherwise active adversaries can [trick the victim into reusing a nonce](https://medium.com/blockstream/musig-dn-schnorr-multisignatures-with-verifiably-deterministic-nonces-27424b5df9d6#e3b6). The optional arguments to _NonceGen_ enable a defense-in-depth mechanism that may prevent secret key exposure if _rand'_ is accidentally not drawn uniformly at random. If the value _rand'_ was identical in two _NonceGen_ invocations, but any other argument was different, the _secnonce_ would still be guaranteed to be different as well (with overwhelming probability), and thus accidentally using the same _secnonce_ for _Sign_ in both sessions would be avoided. Therefore, it is recommended to provide the optional arguments _sk_, _aggpk_, and _m_ if these session parameters are already determined during nonce generation. The auxiliary input _extra\_in_ can contain additional contextual data that has a chance of changing between _NonceGen_ runs, e.g., a supposedly unique session id (taken from the application), a session counter wide enough not to repeat in practice, any nonces by other signers (if already known), or the serialization of a data structure containing multiple of the above. However, the protection provided by the optional arguments should only be viewed as a last resort. In most conceivable scenarios, the assumption that the arguments are different between two executions of _NonceGen_ is relatively strong, particularly when facing an active adversary. In some applications, it is beneficial to generate and send a _pubnonce_ before the other signers, their individual public keys, or the message to sign is known. In this case, only the available arguments are provided to the _NonceGen_ algorithm. After this preprocessing phase, the _Sign_ algorithm can be run immediately when the message and set of signers is determined. This way, the final signature is created quicker and with fewer round trips. However, applications that use this method presumably store the nonces for a longer time and must therefore be even more careful not to reuse them. Moreover, this method is not compatible with the defense-in-depth mechanism described in the previous paragraph. Instead of every signer broadcasting their _pubnonce_ to every other signer, the signers can send their _pubnonce_ to a single aggregator node that runs _NonceAgg_ and sends the _aggnonce_ back to the signers. This technique reduces the overall communication. 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. 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. This signer waits until it receives the _pubnonce_ of all the other signers and until session parameters such as a message to sign, individual public keys, and tweaks are determined. Then, the signer can run _NonceGen_, _NonceAgg_ and _Sign_ in sequence and send out its _pubnonce_ along with its partial signature. 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. ### Identifying Disruptive Signers The signing protocol makes it possible to identify malicious signers who send invalid contributions to a signing session in order to make the signing session abort and prevent the honest signers from obtaining a valid signature. This property is called "identifiable aborts" and ensures that honest parties can assign blame to malicious signers who cause an abort in the signing protocol. 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_. If these conditions hold and an honest party (signer or aggregator) runs an algorithm that fails due to invalid protocol contributions from malicious signers, then the algorithm run by the honest party will output the index of exactly one malicious signer. Additionally, if the honest parties agree on the contributions sent by all signers in the signing session, all the honest parties who run the aborting algorithm will identify the same malicious signer. #### Further Remarks Some of the algorithms specified below may also assign blame to a malicious aggregator. While this is possible for some particular misbehavior of the aggregator, it is not guaranteed that a malicious aggregator can be identified. More specifically, a malicious aggregator (whose existence violates the second condition above) can always make signing abort and wrongly hold honest signers accountable for the abort (e.g., by claiming to have received an invalid contribution from a particular honest signer). 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.[3] However, if _PartialSigVerify_ succeeds for all partial signatures then _PartialSigAgg_ will return a valid Schnorr signature.[4] ### Tweaking the Aggregate Public Key The aggregate public key can be _tweaked_, which modifies the key as defined in the [Tweaking Definition](#tweaking-definition) subsection. In order to apply a tweak, the KeyAgg Context output by _KeyAgg_ is provided to the _ApplyTweak_ algorithm with the _is\_xonly\_t_ argument set to false for plain tweaking and true for X-only tweaking. The resulting KeyAgg Context can be used to apply another tweak with _ApplyTweak_ or obtain the aggregate public key with _GetXonlyPubkey_ or _GetPlainPubkey_. The purpose of supporting tweaking is to ensure compatibility with existing uses of tweaking, i.e., that the result of signing is a valid signature for the tweaked public key. The MuSig2 algorithms take arbitrary tweaks as input but accepting arbitrary tweaks may negatively affect the security of the scheme.[5] Instead, signers should obtain the tweaks according to other specifications. This typically involves deriving the tweaks from a hash of the aggregate public key and some other information. Depending on the specific scheme that is used for tweaking, either the plain or the X-only aggregate public key is required. For example, to do [BIP32](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki) derivation, you call _GetPlainPubkey_ to be able to compute the tweak, whereas [BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki) TapTweaks require X-only public keys that are obtained with _GetXonlyPubkey_. The tweak mode provided to _ApplyTweak_ depends on the application: Plain tweaking can be used to derive child public keys from an aggregate public key using [BIP32](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki). On the other hand, X-only tweaking is required for Taproot tweaking per [BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki). 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. Script path spends require a control block that contains a parity bit for the tweaked X-only public key. The bit can be obtained with _GetPlainPubkey(keyagg\_ctx)\[0\] & 1_. ## Algorithms The following specification of the algorithms has been written with a focus on clarity. As a result, the specified algorithms are not always optimal in terms of computation and space. In particular, some values are recomputed but can be cached in actual implementations (see [General Signing Flow](#general-signing-flow)). ### Notation The following conventions are used, with constants as defined for [secp256k1](https://www.secg.org/sec2-v2.pdf). We note that adapting this proposal to other elliptic curves is not straightforward and can result in an insecure scheme. - Lowercase variables represent integers or byte arrays. - The constant _p_ refers to the field size, _0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F_. - The constant _n_ refers to the curve order, _0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141_. - Uppercase variables refer to points on the curve with equation _y2 = x3 + 7_ over the integers modulo _p_. - _is\_infinite(P)_ returns whether _P_ is the point at infinity. - _x(P)_ and _y(P)_ are integers in the range _0..p-1_ and refer to the X and Y coordinates of a point _P_ (assuming it is not infinity). - The constant _G_ refers to the base point, for which _x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798_ and _y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8_. - Addition of points refers to the usual [elliptic curve group operation](https://en.wikipedia.org/wiki/Elliptic_curve#The_group_law). - [Multiplication (⋅) of an integer and a point](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) refers to the repeated application of the group operation. - Functions and operations: - _||_ refers to byte array concatenation. - The function _x\[i:j\]_, where _x_ is a byte array and _i, j ≥ 0_, returns a _(j - i)_\-byte array with a copy of the _i_\-th byte (inclusive) to the _j_\-th byte (exclusive) of _x_. - The function _bytes(n, x)_, where _x_ is an integer, returns the n-byte encoding of _x_, most significant byte first. - The constant _empty\_bytestring_ refers to the empty byte array. It holds that _len(empty\_bytestring) = 0_. - The function _xbytes(P)_, where _P_ is a point for which _not is\_infinite(P)_, returns _bytes(32, x(P))_. - The function _len(x)_ where _x_ is a byte array returns the length of the array. - The function _has\_even\_y(P)_, where _P_ is a point for which _not is\_infinite(P)_, returns _y(P) mod 2 == 0_. - The function _with\_even\_y(P)_, where _P_ is a point, returns _P_ if _is\_infinite(P)_ or _has\_even\_y(P)_. Otherwise, _with\_even\_y(P)_ returns _\-P_. - The function _cbytes(P)_, where _P_ is a point for which _not is\_infinite(P)_, returns _a || xbytes(P)_ where _a_ is a byte that is _2_ if _has\_even\_y(P)_ and _3_ otherwise. - The function _cbytes\_ext(P)_, where _P_ is a point, returns _bytes(33, 0)_ if _is\_infinite(P)_. Otherwise, it returns _cbytes(P)_. - The function _int(x)_, where _x_ is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is _x_. - The function _lift\_x(x)_, where _x_ is an integer in range _0..2256\-1_, returns the point _P_ for which _x(P) = x_ Given a candidate X coordinate _x_ in the range _0..p-1_, there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then _x_ is not a valid X coordinate either, i.e., no point _P_ exists for which _x(P) = x_. The valid Y coordinates for a given candidate _x_ are the square roots of _c = x3 + 7 mod p_ and they can be computed as _y = ±c(p+1)/4 mod p_ (see [Quadratic residue](https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus)) if they exist, which can be checked by squaring and comparing with _c_. and _has\_even\_y(P)_, or fails if _x_ is greater than _p-1_ or no such point exists. The function _lift\_x(x)_ is equivalent to the following pseudocode: - - - Fail if _x > p-1_. - Let _c = x3 + 7 mod p_. - Let _y' = c(p+1)/4 mod p_. - Fail if _c ≠ y'2 mod p_. - Let _y = y'_ if _y' mod 2 = 0_, otherwise let _y = p - y'_ . - Return the unique point _P_ such that _x(P) = x_ and _y(P) = y_. - The function _cpoint(x)_, where _x_ is a 33-byte array (compressed serialization), sets _P = lift\_x(int(x\[1:33\]))_ and fails if that fails. If _x\[0\] = 2_ it returns _P_ and if _x\[0\] = 3_ it returns _\-P_. Otherwise, it fails. - The function _cpoint\_ext(x)_, where _x_ is a 33-byte array (compressed serialization), returns the point at infinity if _x = bytes(33, 0)_. Otherwise, it returns _cpoint(x)_ and fails if that fails. - The function _hashtag(x)_ where _tag_ is a UTF-8 encoded tag name and _x_ is a byte array returns the 32-byte hash _SHA256(SHA256(tag) || SHA256(tag) || x)_. - Other: - Tuples are written by listing the elements within parentheses and separated by commas. For example, _(2, 3, 1)_ is a tuple. ### Key Generation and Aggregation #### Key Generation of an Individual Signer Algorithm _IndividualPubkey(sk)_:[6] - Inputs: - The secret key _sk_: a 32-byte array, freshly generated uniformly at random - Let _d' = int(sk)_. - Fail if _d' = 0_ or _d' ≥ n_. - Return _cbytes(d'⋅G)_. #### KeyAgg Context The KeyAgg Context is a data structure consisting of the following elements: - The point _Q_ representing the potentially tweaked aggregate public key: an elliptic curve point - The accumulated tweak _tacc_: an integer with _0 ≤ tacc < n_ - The value _gacc_ : 1 or -1 mod n We write "Let _(Q, gacc, tacc) = keyagg\_ctx_" to assign names to the elements of a KeyAgg Context. Algorithm _GetXonlyPubkey(keyagg\_ctx)_: - Let _(Q, \_, \_) = keyagg\_ctx_ - Return _xbytes(Q)_ Algorithm _GetPlainPubkey(keyagg\_ctx)_: - Let _(Q, \_, \_) = keyagg\_ctx_ - Return _cbytes(Q)_ #### Key Sorting Algorithm _KeySort(pk1..u)_: - Inputs: - The number _u_ of individual public keys with _0 < u < 2^32_ - The individual public keys _pk1..u_: _u_ 33-byte arrays - Return _pk1..u_ sorted in lexicographical order. #### Key Aggregation Algorithm _KeyAgg(pk1..u)_: - Inputs: - The number _u_ of individual public keys with _0 < u < 2^32_ - The individual public keys _pk1..u_: _u_ 33-byte arrays - Let _pk2 = GetSecondKey(pk1..u)_ - For _i = 1 .. u_: - Let _Pi = cpoint(pki)_; fail if that fails and blame signer _i_ for invalid individual public key. - Let _ai = KeyAggCoeffInternal(pk1..u, pki, pk2)_. - Let _Q = a1⋅P1 + a2⋅P2 + ... + au⋅Pu_ - Fail if _is\_infinite(Q)_. - Let _gacc = 1_ - Let _tacc = 0_ - Return _keyagg\_ctx = (Q, gacc, tacc)_. Internal Algorithm _HashKeys(pk1..u)_: - Return _hashKeyAgg list(pk1 || pk2 || ... || pku)_ Internal Algorithm _GetSecondKey(pk1..u)_: - For _j = 1 .. u_: - If _pkj ≠ pk1_: - Return _pkj_ - Return _bytes(33, 0)_ Internal Algorithm _KeyAggCoeff(pk1..u, pk')_: - Let _pk2 = GetSecondKey(pk1..u)_: - Return _KeyAggCoeffInternal(pk1..u, pk', pk2)_ Internal Algorithm _KeyAggCoeffInternal(pk1..u, pk', pk2)_: - Let _L = HashKeys(pk1..u)_ - If _pk' = pk2_: - Return 1 - Return _int(hashKeyAgg coefficient(L || pk')) mod n_[7] #### Applying Tweaks Algorithm _ApplyTweak(keyagg\_ctx, tweak, is\_xonly\_t)_: - Inputs: - The _keyagg\_ctx_: a [KeyAgg Context](#keyagg-context) data structure - The _tweak_: a 32-byte array - The tweak mode _is\_xonly\_t_: a boolean - Let _(Q, gacc, tacc) = keyagg\_ctx_ - If _is\_xonly\_t_ and _not has\_even\_y(Q)_: - Let _g = -1 mod n_ - Else: - Let _g = 1_ - Let _t = int(tweak)_; fail if _t ≥ n_ - Let _Q' = g⋅Q + t⋅G_ - Fail if _is\_infinite(Q')_ - Let _gacc' = g⋅gacc mod n_ - Let _tacc' = t + g⋅tacc mod n_ - Return _keyagg\_ctx' = (Q', gacc', tacc')_ ### Nonce Generation Algorithm _NonceGen(sk, pk, aggpk, m, extra\_in)_: - Inputs: - The secret signing key _sk_: a 32-byte array (optional argument) - The individual public key _pk_: a 33-byte array (see [Signing with Tweaked Individual Keys](#signing-with-tweaked-individual-keys) for the reason that this argument is mandatory) - The x-only aggregate public key _aggpk_: a 32-byte array (optional argument) - The message _m_: a byte array (optional argument)[8] - The auxiliary input _extra\_in_: a byte array with _0 ≤ len(extra\_in) ≤ 232\-1_ (optional argument) - Let _rand'_ be a 32-byte array freshly drawn uniformly at random - If the optional argument _sk_ is present: - Let _rand_ be the byte-wise xor of _sk_ and _hashMuSig/aux(rand')_[9] - Else: - Let _rand = rand'_ - If the optional argument _aggpk_ is not present: - Let _aggpk = empty\_bytestring_ - If the optional argument _m_ is not present: - Let _m\_prefixed = bytes(1, 0)_ - Else: - Let _m\_prefixed = bytes(1, 1) || bytes(8, len(m)) || m_ - If the optional argument _extra\_in_ is not present: - Let _extra\_in = empty\_bytestring_ - Let _ki = int(hashMuSig/nonce(rand || bytes(1, len(pk)) || pk || bytes(1, len(aggpk)) || aggpk || m\_prefixed || bytes(4, len(extra\_in)) || extra\_in || bytes(1, i - 1))) mod n_ for _i = 1,2_ - Fail if _k1 = 0_ or _k2 = 0_ - Let _R⁎,1 = k1⋅G, R⁎,2 = k2⋅G_ - Let _pubnonce = cbytes(R⁎,1) || cbytes(R⁎,2)_ - Let _secnonce = bytes(32, k1) || bytes(32, k2) || pk_The algorithms as specified here assume that the _secnonce_ is stored as a 97-byte array using the serialization _secnonce = bytes(32, k1) || bytes(32, k2) || pk_. The same format is used in the reference implementation and in the test vectors. However, since the _secnonce_ is (obviously) not meant to be sent over the wire, compatibility between implementations is not a concern, and this method of storing the _secnonce_ is merely a suggestion. The _secnonce_ is effectively a local data structure of the signer which comprises the value triple _(k1, k2, pk)_, and implementations may choose any suitable method to carry it from _NonceGen_ (first communication round) to _Sign_ (second communication round). In particular, implementations may choose to hide the _secnonce_ in internal state without exposing it in an API explicitly, e.g., in an effort to prevent callers from reusing a _secnonce_ accidentally. - Return _(secnonce, pubnonce)_ ### Nonce Aggregation Algorithm _NonceAgg(pubnonce1..u)_: - Inputs: - The number _u_ of _pubnonces_ with _0 < u < 2^32_ - The public nonces _pubnonce1..u_: _u_ 66-byte arrays - For _j = 1 .. 2_: - For _i = 1 .. u_: - Let _Ri,j = cpoint(pubnoncei\[(j-1)\*33:j\*33\])_; fail if that fails and blame signer _i_ for invalid _pubnonce_. - Let _Rj = R1,j + R2,j + ... + Ru,j_ - Return _aggnonce = cbytes\_ext(R1) || cbytes\_ext(R2)_ ### Session Context The Session Context is a data structure consisting of the following elements: - The aggregate public nonce _aggnonce_: a 66-byte array - The number _u_ of individual public keys with _0 < u < 2^32_ - The individual public keys _pk1..u_: _u_ 33-byte arrays - The number _v_ of tweaks with _0 ≤ v < 2^32_ - The tweaks _tweak1..v_: _v_ 32-byte arrays - The tweak modes _is\_xonly\_t1..v_ : _v_ booleans - The message _m_: a byte array[8] We write "Let _(aggnonce, u, pk1..u, v, tweak1..v, is\_xonly\_t1..v, m) = session\_ctx_" to assign names to the elements of a Session Context. Algorithm _GetSessionValues(session\_ctx)_: - Let _(aggnonce, u, pk1..u, v, tweak1..v, is\_xonly\_t1..v, m) = session\_ctx_ - Let _keyagg\_ctx0 = KeyAgg(pk1..u)_; fail if that fails - For _i = 1 .. v_: - Let _keyagg\_ctxi = ApplyTweak(keyagg\_ctxi-1, tweaki, is\_xonly\_ti)_; fail if that fails - Let _(Q, gacc, tacc) = keyagg\_ctxv_ - Let _b = int(hashMuSig/noncecoef(aggnonce || xbytes(Q) || m)) mod n_ - Let _R1 = cpoint\_ext(aggnonce\[0:33\]), R2 = cpoint\_ext(aggnonce\[33:66\])_; fail if that fails and blame nonce aggregator for invalid _aggnonce_. - Let _R' = R1 + b⋅R2_ - If ''is\_infinite(R'): - Let final nonce _R = G_ (see [Dealing with Infinity in Nonce Aggregation](#dealing-with-infinity-in-nonce-aggregation)) - Else: - Let final nonce _R = R'_ - Let _e = int(hashBIP0340/challenge(xbytes(R) || xbytes(Q) || m)) mod n_ - Return _(Q, gacc, tacc, b, R, e)_ Algorithm _GetSessionKeyAggCoeff(session\_ctx, P)_: - Let _(\_, u, pk1..u, \_, \_, \_, \_) = session\_ctx_ - Let _pk = cbytes(P)_ - Fail if _pk_ not in _pk1..u_ - Return _KeyAggCoeff(pk1..u, pk)_ ### Signing Algorithm _Sign(secnonce, sk, session\_ctx)_: - Inputs: - The secret nonce _secnonce_ that has never been used as input to _Sign_ before: a 97-byte array - The secret key _sk_: a 32-byte array - The _session\_ctx_: a [Session Context](#session-context) data structure - Let _(Q, gacc, \_, b, R, e) = GetSessionValues(session\_ctx)_; fail if that fails - Let _k1' = int(secnonce\[0:32\]), k2' = int(secnonce\[32:64\])_ - Fail if _ki' = 0_ or _ki' ≥ n_ for _i = 1..2_ - Let _k1 = k1', k2 = k2'_ if _has\_even\_y(R)_, otherwise let _k1 = n - k1', k2 = n - k2'_ - Let _d' = int(sk)_ - Fail if _d' = 0_ or _d' ≥ n_ - Let _P = d'⋅G_ - Let _pk = cbytes(P)_ - Fail if _pk ≠ secnonce\[64:97\]_ - Let _a = GetSessionKeyAggCoeff(session\_ctx, P)_; fail if that fails[10] - Let _g = 1_ if _has\_even\_y(Q)_, otherwise let _g = -1 mod n_ - Let _d = g⋅gacc⋅d' mod n_ (See [Negation Of The Secret Key When Signing](#negation-of-the-secret-key-when-signing)) - Let _s = (k1 + b⋅k2 + e⋅a⋅d) mod n_ - Let _psig = bytes(32, s)_ - Let _pubnonce = cbytes(k1'⋅G) || cbytes(k2'⋅G)_ - If _PartialSigVerifyInternal(psig, pubnonce, pk, session\_ctx)_ (see below) returns failure, fail[11] - Return partial signature _psig_ ### Partial Signature Verification Algorithm _PartialSigVerify(psig, pubnonce1..u, pk1..u, tweak1..v, is\_xonly\_t1..v, m, i)_: - Inputs: - The partial signature _psig_: a 32-byte array - The number _u_ of public nonces and individual public keys with _0 < u < 2^32_ - The public nonces _pubnonce1..u_: _u_ 66-byte arrays - The individual public keys _pk1..u_: _u_ 33-byte arrays - The number _v_ of tweaks with _0 ≤ v < 2^32_ - The tweaks _tweak1..v_: _v_ 32-byte arrays - The tweak modes _is\_xonly\_t1..v_ : _v_ booleans - The message _m_: a byte array[8] - The index of the signer _i_ in the public nonces and individual public keys with _0 < i ≤ u_ - Let _aggnonce = NonceAgg(pubnonce1..u)_; fail if that fails - Let _session\_ctx = (aggnonce, u, pk1..u, v, tweak1..v, is\_xonly\_t1..v, m)_ - Run _PartialSigVerifyInternal(psig, pubnoncei, pki, session\_ctx)_ - Return success iff no failure occurred before reaching this point. Internal Algorithm _PartialSigVerifyInternal(psig, pubnonce, pk, session\_ctx)_: - Let _(Q, gacc, \_, b, R, e) = GetSessionValues(session\_ctx)_; fail if that fails - Let _s = int(psig)_; fail if _s ≥ n_ - Let _R⁎,1 = cpoint(pubnonce\[0:33\]), R⁎,2 = cpoint(pubnonce\[33:66\])_ - Let _Re⁎' = R⁎,1 + b⋅R⁎,2_ - Let effective nonce _Re⁎ = Re⁎'_ if _has\_even\_y(R)_, otherwise let _Re⁎ = -Re⁎'_ - Let _P = cpoint(pk)_; fail if that fails - Let _a = GetSessionKeyAggCoeff(session\_ctx, P)_[12] - Let _g = 1_ if _has\_even\_y(Q)_, otherwise let _g = -1 mod n_ - Let _g' = g⋅gacc mod n_ (See [Negation Of The Individual Public Key When Partially Verifying](#negation-of-the-individual-public-key-when-partially-verifying)) - Fail if _s⋅G ≠ Re⁎ + e⋅a⋅g'⋅P_ - Return success iff no failure occurred before reaching this point. ### Partial Signature Aggregation Algorithm _PartialSigAgg(psig1..u, session\_ctx)_: - Inputs: - The number _u_ of signatures with _0 < u < 2^32_ - The partial signatures _psig1..u_: _u_ 32-byte arrays - The _session\_ctx_: a [Session Context](#session-context) data structure - Let _(Q, \_, tacc, \_, R, e) = GetSessionValues(session\_ctx)_; fail if that fails - For _i = 1 .. u_: - Let _si = int(psigi)_; fail if _si ≥ n_ and blame signer _i_ for invalid partial signature. - Let _g = 1_ if _has\_even\_y(Q)_, otherwise let _g = -1 mod n_ - Let _s = s1 + ... + su + e⋅g⋅tacc mod n_ - Return _sig =_ xbytes(R) || bytes(32, s)'' ### Test Vectors and Reference Code We provide a naive, highly inefficient, and non-constant time [pure Python 3 reference implementation of the key aggregation, partial signing, and partial signature verification algorithms](https://github.com/bitcoin/bips/blob/master/bip-0327/reference.py). Standalone JSON test vectors are also available in the [same directory](https://bipexplorer.com/bip/327), to facilitate porting the test vectors into other implementations. The reference implementation is for demonstration purposes only and not to be used in production environments. ## Remarks on Security and Correctness ### Signing with Tweaked Individual Keys The scheme in this proposal has been designed to be secure even if signers tweak their individual secret keys with tweaks known to the adversary (e.g., as in BIP32 unhardened derivation) before providing the corresponding individual public keys as input to key aggregation. In particular, the scheme as specified above requires each signer to provide a final individual public key _pk_ already to _NonceGen_, which writes it into the _secnonce_ array so that it can be checked against _IndividualPubkey(sk)_ in the _Sign_ algorithm. The purpose of this check in _Sign_ is to ensure that _pk_, and thus the secret key _sk_ that will be provided to _Sign_, is determined before the signer sends out the _pubnonce_. If the check in _Sign_ was omitted, and a signer supported signing with at least two different secret keys _sk1_ and _sk2_ which have been obtained via tweaking another secret key with tweaks known to the adversary, then the adversary could, after having seen the _pubnonce_, influence whether _sk1_ or _sk2_ is provided to _Sign_. This degree of freedom may allow the adversary to perform a generalized birthday attack and thereby forge a signature (see [bitcoin-dev mailing list post](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html) and [writeup](https://github.com/jonasnick/musig2-tweaking) for details). Checking _pk_ against _IndividualPubkey(sk)_ is a simple way to ensure that the secret key provided to _Sign_ is fully determined already when _NonceGen_ is invoked. This removes the adversary's ability to influence the secret key after having seen the _pubnonce_ and thus rules out the attack.[13] Note that the scheme as given in the [MuSig2 paper](https://eprint.iacr.org/2020/1261) does not perform the check in _Sign_. However, the security model in the paper does not cover tweaking at all and assumes a single fixed secret key. ### Modifications to Nonce Generation Implementers must avoid modifying the _NonceGen_ algorithm without being fully aware of the implications. We provide two modifications to _NonceGen_ that are secure when applied correctly and may be useful in special circumstances, summarized in the following table. | | needs secure randomness | needs secure counter | needs to keep state securely | needs aggregate nonce of all other signers (only possible for one signer) | | --- | --- | --- | --- | --- | | NonceGen | ✓ |   | ✓ |   | | CounterNonceGen |   | ✓ | ✓ |   | | DeterministicSign |   |   |   | ✓ | First, on systems where obtaining uniformly random values is much harder than maintaining a global atomic counter, it can be beneficial to modify _NonceGen_. The resulting algorithm _CounterNonceGen_ does not draw _rand'_ uniformly at random but instead sets _rand'_ to the value of an atomic counter that is incremented whenever it is read. With this modification, the secret signing key _sk_ of the signer generating the nonce is **not** an optional argument and must be provided to _NonceGen_. The security of the resulting scheme then depends on the requirement that reading the counter must never yield the same counter value in two _NonceGen_ invocations with the same _sk_. Second, if there is a unique signer who is supposed to send the _pubnonce_ last, it is possible to modify nonce generation for this single signer to not require high-quality randomness. Such a nonce generation algorithm _DeterministicSign_ is specified below. Note that the only optional argument is _rand_, which can be omitted if randomness is entirely unavailable. _DeterministicSign_ requires the argument _aggothernonce_ which should be set to the output of _NonceAgg_ run on the _pubnonce_ value of **all** other signers (but can be provided by an untrusted party). Hence, using _DeterministicSign_ is only possible for the last signer to generate a nonce and makes the signer stateless, similar to the stateless signer described in the [Nonce Generation](#nonce-generation) section. #### Deterministic and Stateless Signing for a Single Signer Algorithm _DeterministicSign(sk, aggothernonce, pk1..u, tweak1..v, is\_xonly\_t1..v, m, rand)_: - Inputs: - The secret signing key _sk_: a 32-byte array - The aggregate public nonce _aggothernonce_ (see [above](#modifications-to-nonce-generation)): a 66-byte array - The number _u_ of individual public keys with _0 < u < 2^32_ - The individual public keys _pk1..u_: _u_ 33-byte arrays - The number _v_ of tweaks with _0 ≤ v < 2^32_ - The tweaks _tweak1..v_: _v_ 32-byte arrays - The tweak methods _is\_xonly\_t1..v_: _v_ booleans - The message _m_: a byte array[8] - The auxiliary randomness _rand_: a 32-byte array (optional argument) - If the optional argument _rand_ is present: - Let _sk'_ be the byte-wise xor of _sk_ and _hashMuSig/aux(rand)_ - Else: - Let _sk' = sk_ - Let _keyagg\_ctx0 = KeyAgg(pk1..u)_; fail if that fails - For _i = 1 .. v_: - Let _keyagg\_ctxi = ApplyTweak(keyagg\_ctxi-1, tweaki, is\_xonly\_ti)_; fail if that fails - Let _aggpk = GetXonlyPubkey(keyagg\_ctxv)_ - Let _ki = int(hashMuSig/deterministic/nonce(sk' || aggothernonce || aggpk || bytes(8, len(m)) || m || bytes(1, i - 1))) mod n_ for _i = 1,2_ - Fail if _k1 = 0_ or _k2 = 0_ - Let _R⁎,1 = k1⋅G, R⁎,2 = k2⋅G_ - Let _pubnonce = cbytes(R⁎,1) || cbytes(R⁎,2)_ - Let _d = int(sk)_ - Fail if _d = 0_ or _d ≥ n_ - Let _pk = cbytes(d⋅G)_ - Let _secnonce = bytes(32, k1) || bytes(32, k2) || pk_ - Let _aggnonce = NonceAgg((pubnonce, aggothernonce))_; fail if that fails and blame nonce aggregator for invalid _aggothernonce_. - Let _session\_ctx = (aggnonce, u, pk1..u, v, tweak1..v, is\_xonly\_t1..v, m)_ - Return _(pubnonce, Sign(secnonce, sk, session\_ctx))_ ### Tweaking Definition Two modes of tweaking the aggregate public key are supported. They correspond to the following algorithms: Algorithm _ApplyPlainTweak(P, t)_: - Inputs: - _P_: a point - The tweak _t_: an integer with _0 ≤ t < n_ - Return _P + t⋅G_ Algorithm _ApplyXonlyTweak(P, t)_: - Return _with\_even\_y(P) + t⋅G_ ### Negation Of The Secret Key When Signing In order to produce a partial signature for an X-only aggregate public key that is an aggregate of _u_ individual public keys and tweaked _v_ times (X-only or plain), the _[Sign](#sign-negation)_ algorithm may need to negate the secret key during the signing process. The following elliptic curve points arise as intermediate steps when creating a signature: • _Pi_ as computed in _KeyAgg_ is the point corresponding to the _i_\-th signer's individual public key. Defining _di'_ to be the _i_\-th signer's secret key as an integer, i.e., the _d'_ value as computed in the _Sign_ algorithm of the _i_\-th signer, we have _Pi = di'⋅G_ . • _Q0_ is the aggregate of the individual public keys. It is identical to value _Q_ computed in _KeyAgg_ and therefore defined as _Q0 = a1⋅P1 + a2⋅P2 + ... + au⋅Pu_. • _Qi_ is the tweaked aggregate public key after the _i_\-th execution of _ApplyTweak_ for _1 ≤ i ≤ v_. It holds that _Qi = f(i-1) + ti⋅G_ for _i = 1, ..., v_ where _f(i-1) := with\_even\_y(Qi-1)_ if _is\_xonly\_ti_ and _f(i-1) := Qi-1_ otherwise. • _with\_even\_y(Qv)_ is the final result of the key aggregation and tweaking operations. It corresponds to the output of _GetXonlyPubkey_ applied on the final KeyAgg Context. The signer's goal is to produce a partial signature corresponding to the final result of key aggregation and tweaking, i.e., the X-only public key _with\_even\_y(Qv)_. For _1 ≤ i ≤ v_, we denote the value _g_ computed in the _i_\-th execution of _ApplyTweak_ by _gi-1_. Therefore, _gi-1_ is _\-1 mod n_ if and only if _is\_xonly\_ti_ is true and _Qi-1_ has an odd Y coordinate. In other words, _gi-1_ indicates whether _Qi-1_ needed to be negated to apply an X-only tweak: _f(i-1) = gi-1⋅Qi-1_ for _1 ≤ i ≤ v_. Furthermore, the _Sign_ and _PartialSigVerify_ algorithms set value _g_ depending on whether _Qv_ needed to be negated to produce the (X-only) final output. For consistency, this value _g_ is referred to as _gv_ in this section. _with\_even\_y(Qv) = gv⋅Qv_. So, the (X-only) final public key is _with\_even\_y(Qv) = gv⋅Qv = gv⋅(f(v-1) + tv⋅G) = gv⋅(gv-1⋅(f(v-2) + tv-1⋅G) + tv⋅G) = gv⋅gv-1⋅f(v-2) + gv⋅(tv + gv-1⋅tv-1)⋅G = gv⋅gv-1⋅f(v-2) + (sumi=v-1..v ti⋅prodj=i..v gj)⋅G = gv⋅gv-1⋅...⋅g1⋅f(0) + (sumi=1..v ti⋅prodj=i..v gj)⋅G = gv⋅...⋅g0⋅Q0 + gv⋅taccv⋅G_ where _tacci_ is computed by _KeyAgg_ and _ApplyTweak_ as follows: _tacc0 = 0 tacci = ti + gi-1⋅tacci-1 for i=1..v mod n_ for which it holds that _gv⋅taccv = sumi=1..v ti⋅prodj=i..v gj_. _KeyAgg_ and _ApplyTweak_ compute _gacc0 = 1 gacci = gi-1⋅gacci-1 for i=1..v mod n_ So we can rewrite above equation for the final public key as _with\_even\_y(Qv) = gv⋅gaccv⋅Q0 + gv⋅taccv⋅G_. Then we have _with\_even\_y(Qv) - gv⋅taccv⋅G = gv⋅gaccv⋅Q0 = gv⋅gaccv⋅(a1⋅P1 + ... + au⋅Pu) = gv⋅gaccv⋅(a1⋅d1'⋅G + ... + au⋅du'⋅G) = sumi=1..u(gv⋅gaccv⋅ai⋅di')\*G_. Intuitively, _gacci_ tracks accumulated sign flipping and _tacci_ tracks the accumulated tweak value after applying the first _i_ individual tweaks. Additionally, _gv_ indicates whether _Qv_ needed to be negated to produce the final X-only result. Thus, signer _i_ multiplies its secret key _di'_ with _gv⋅gaccv_ in the _[Sign](#sign-negation)_ algorithm. #### Negation Of The Individual Public Key When Partially Verifying As explained in [Negation Of The Secret Key When Signing](#negation-of-the-secret-key-when-signing) the signer uses a possibly negated secret key _d = gv⋅gaccv⋅d' mod n_ when producing a partial signature to ensure that the aggregate signature will correspond to an aggregate public key with even Y coordinate. The _[PartialSigVerifyInternal](#sigverify-negation)_ algorithm is supposed to check _s⋅G = Re⁎ + e⋅a⋅d⋅G_. The verifier doesn't have access to _d⋅G_ but can construct it using the individual public key _pk_ as follows: _d⋅G = gv⋅gaccv⋅d'⋅G = gv⋅gaccv⋅cpoint(pk)_ Note that the aggregate public key and list of tweaks are inputs to partial signature verification, so the verifier can also construct _gv_ and _gaccv_. ### Dealing with Infinity in Nonce Aggregation 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. However, the final nonce _R_ of a BIP340 Schnorr signature cannot be the point at infinity. If we would nonetheless allow the final nonce to be the point at infinity, then the scheme would lose the following property: if _PartialSigVerify_ succeeds for all partial signatures, then _PartialSigAgg_ will return a valid Schnorr signature. Since this is a valuable feature, we modify MuSig2\* (which is defined in the appendix of the [MuSig2 paper](https://eprint.iacr.org/2020/1261)) to avoid producing an invalid Schnorr signature while still allowing detection of the dishonest signer: In _GetSessionValues_, if the final nonce _R_ would be the point at infinity, set it to the generator instead (an arbitrary choice). This modification to _GetSessionValues_ does not affect the unforgeability of the scheme. Given a successful adversary against the unforgeability game (EUF-CMA) for the modified scheme, a reduction can win the unforgeability game for the original scheme by simulating the modification towards the adversary: When the adversary provides _aggnonce' = bytes(33, 0) || bytes(33, 0)_, the reduction sets _aggnonce = cbytes\_ext(G) || bytes(33, 0)_. For any other _aggnonce'_ , the reduction sets _aggnonce = aggnonce'_ . (The case that the adversary provides an _aggnonce' ≠ bytes(33, 0) || bytes(33, 0)_ but nevertheless _R'_ in _GetSessionValues_ is the point at infinity happens only with negligible probability.) ### Choosing the Size of the Nonce The [MuSig2 paper](https://eprint.iacr.org/2020/1261) contains two security proofs that apply to different variants of the scheme. The first proof relies on the random oracle model (ROM) and applies to a scheme variant where each signer's nonce consists of four elliptic curve points. The second proof requires a stronger model, namely the combination of the ROM and the algebraic group model (AGM), and applies to an optimized scheme variant where the signers' nonces consist of only two points. This proposal uses the latter, optimized scheme variant. Relying on the stronger model is a legitimate choice for the following reasons: First, an approach widely taken is interpreting a Forking Lemma proof in the ROM merely as design justification and ignoring the loss of security due to the Forking Lemma. If one believes in this approach, then the ROM may not be the optimal model in the first place because some parts of the concrete security bound are arbitrarily ignored. One may just as well move to the ROM+AGM model, which produces bounds close to the best-known attacks, e.g., for Schnorr signatures. Second, as of this writing, there is no instance of a serious cryptographic scheme with a security proof in the AGM that is not secure in practice. There are, however, insecure toy schemes with AGM security proofs, but those explicitly violate the requirements of the AGM. [Broken AGM proofs of toy schemes](https://eprint.iacr.org/2022/226.pdf) provide group elements to the adversary without declaring them as group element inputs. In contrast, in MuSig2, all group elements that arise in the scheme are known to the adversary and declared as group element inputs. A scheme very similar to MuSig2 and with two-point nonces was independently proven secure in the ROM and AGM by [Alper and Burdges](https://eprint.iacr.org/2020/1245). ## Backwards Compatibility This document proposes a standard for the MuSig2 multi-signature scheme that is compatible with [BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki). MuSig2 is _not_ compatible with ECDSA signatures traditionally used in Bitcoin. ## Changelog To help implementers understand updates to this document, we attach a version number that resembles _semantic versioning_ (`MAJOR.MINOR.PATCH`). The `MAJOR` version is incremented if changes to the BIP are introduced that are incompatible with prior versions. An exception to this rule is `MAJOR` version zero (0.y.z) which is for development and does not need to be incremented if backwards incompatible changes are introduced. The `MINOR` version is incremented whenever the inputs or the output of an algorithm changes in a backward-compatible way or new backward-compatible functionality is added. The `PATCH` version is incremented for other changes that are noteworthy (bug fixes, test vectors, important clarifications, etc.). - **1.0.4** (2026-08-19): - Fix two minor bugs in the specification of _PartialSigAgg_. - **1.0.3** (2026-01-05): - Fix minor bugs in the specification of _DeterministicSign_. - **1.0.2** (2024-07-22): - Fix minor bug in the specification of _DeterministicSign_ and add small improvement to a _PartialSigAgg_ test vector. - **1.0.1** (2024-05-14): - Fix minor issue in _PartialSigVerify_ vectors. - **1.0.0** (2023-03-26): - Number 327 was assigned to this BIP. - **1.0.0-rc.4** (2023-03-02): - Add expected value of _pubnonce_ to _NonceGen_ test vectors. - **1.0.0-rc.3** (2023-02-28): - Improve _NonceGen_ test vectors by not using an all-zero hex string as _rand\__ values. This change addresses potential issues in some implementations that interpret this as a special value indicating uninitialized memory or a broken random number generator and therefore return an error. - Fix invalid length of a _pubnonce_ in the _PartialSigVerify_ test vectors. - Improve _KeySort_ test vector. - Add explicit _IndividualPubkey_ algorithm. - Rename KeyGen Context to KeyAgg Context. - **1.0.0-rc.2** (2022-10-28): - Fix vulnerability that can occur in certain unusual scenarios (see [bitcoin-dev mailing list](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html): Add mandatory _pk_ argument to _NonceGen_, append _pk_ to _secnonce_ and check in _Sign_ that the _pk_ in _secnonce_ matches. Update test vectors. - Make sure that signer's key is in list of individual public keys by adding failure case to _GetSessionKeyAggCoeff_ and add test vectors. - **1.0.0-rc.1** (2022-10-03): Submit draft BIP to the BIPs repository - **0.8.6** (2022-09-15): Clarify that implementations do not need to support every feature and add a test vector for signing with a tweaked key - **0.8.5** (2022-09-05): Rename some functions to improve clarity. - **0.8.4** (2022-09-02): Make naming of nonce variants _R_ in specifications of the algorithms and reference code easier to read and more consistent. - **0.8.3** (2022-09-01): Overwrite _secnonce_ in _sign_ reference implementation to help prevent accidental reuse and add test vector for invalid _secnonce_. - **0.8.2** (2022-08-30): Fix _KeySort_ input length and add test vectors - **0.8.1** (2022-08-26): Add _DeterministicSign_ algorithm - **0.8.0** (2022-08-26): Switch from X-only to plain public key for individual public keys. This requires updating a large portion of the test vectors. - **0.7.2** (2022-08-17): Add _NonceGen_ and _Sign/PartialSigVerify_ test vectors for messages longer than 32 bytes. - **0.7.1** (2022-08-10): Extract test vectors into separate JSON file. - **0.7.0** (2022-07-31): Change _NonceGen_ such that output when message is not present is different from when message is present but has length 0. - **0.6.0** (2022-07-31): Allow variable length messages, change serialization of the message in the _NonceGen_ hash function, and add test vectors - **0.5.2** (2022-06-26): Fix _aggpk_ in _NonceGen_ test vectors. - **0.5.1** (2022-06-22): Rename "ordinary" tweaking to "plain" tweaking. - **0.5.0** (2022-06-21): Separate ApplyTweak from KeyAgg and introduce KeyGen Context. - **0.4.0** (2022-06-20): Allow the output of NonceAgg to be infinity and add test vectors - **0.3.2** (2022-06-02): Add a lot of test vectors and improve handling of invalid contributions in reference code. - **0.3.1** (2022-05-24): Add _NonceGen_ test vectors - **0.3.0** (2022-05-24): Hash _i - 1_ instead of _i_ in _NonceGen_ - **0.2.0** (2022-05-19): Change order of arguments in _NonceGen_ hash function - **0.1.0** (2022-05-19): Publication of draft BIP on the bitcoin-dev mailing list ## Footnotes 1. Applications that sort individual public keys before aggregation should ensure that the implementation of sorting is reasonably efficient, and in particular does not degenerate to quadratic runtime on pathological inputs. 2. We treat the _secnonce_ and _pubnonce_ as grammatically singular even though they include serializations of two scalars and two elliptic curve points, respectively. This treatment may be confusing for readers familiar with the MuSig2 paper. However, serialization is a technical detail that is irrelevant for users of MuSig2 interfaces. 3. Assume an adversary wants to forge a partial signature for individual public key _P_. It joins the signing session pretending to be two different signers, one with individual public key _P_ and one with another individual public key. The adversary can then set the second signer's nonce such that it will be able to produce a partial signature for _P_ but not for the other claimed signer. An explanation of the individual steps required to create a partial signature forgery can be found in [a write up by Adam Gibson](https://gist.github.com/AdamISZ/ca974ed67889cedc738c4a1f65ff620b). 4. Given a list of individual public keys, it is an open question whether a BIP-340 signature valid under the corresponding aggregate public key is a proof of knowledge of all secret keys of the individual public keys. 5. It is an open question whether allowing arbitrary tweaks from an adversary affects the unforgeability of MuSig2. 6. The _IndividualPubkey_ algorithm matches the key generation procedure traditionally used for ECDSA in Bitcoin 7. The key aggregation coefficient is computed by hashing the individual public key instead of its index, which requires one more invocation of the SHA-256 compression function. However, it results in significantly simpler implementations because signers do not need to translate between public key indices before and after sorting. 8. In theory, the allowed message size is restricted because SHA256 accepts byte strings only up to size of 2^61-1 bytes (and because of the 8-byte length encoding). 9. The random data is hashed (with a unique tag) as a precaution against situations where the randomness may be correlated with the secret signing key itself. It is xored with the secret key (rather than combined with it in a hash) to reduce the number of operations exposed to the actual secret key. 10. Failing _Sign_ when _GetSessionKeyAggCoeff(session\_ctx, P)_ fails is not necessary for unforgeability. It merely indicates to the caller that the scheme is not being used correctly. 11. Verifying the signature before leaving the signer prevents random or adversarially provoked computation errors. This prevents publishing invalid signatures which may leak information about the secret key. It is recommended but can be omitted if the computation cost is prohibitive. 12. _GetSessionKeyAggCoeff(session\_ctx, P)_ cannot fail when called from _PartialSigVerifyInternal_. 13. Ensuring that the secret key provided to _Sign_ is fully determined already when _NonceGen_ is invoked is a simple policy to rule out the attack, but more flexible polices are conceivable. In fact, if the signer uses nothing but the message to be signed and the list of the individual public keys of all signers to decide which secret key to use, then it is not a problem that the adversary can influence this decision after having seen the _pubnonce_. More formally, consider modified algorithms _NonceGen'_ and _Sign'_ , where _NonceGen'_ does not take the individual public key of the signer as input and does not store it in pubnonce, and Sign' does not check read the individual public key from pubnonce and does not check it against the secret key taken as input. Then it suffices that for each invocation of _NonceGen'_ with output _(secnonce, pubnonce)_, a function _fsk_ is determined before sending out _pubnonce_, where _fsk_ maps a pair consisting of a list of individual public keys and a message to a secret key, such that the secret key _sk_ and the session context _session\_ctx = (\_, \_, pk1..u, \_, \_, \_, m)_ provided to the corresponding invocation of _Sign'(secnonce, sk, session\_ctx)_, adhere to the condition _fsk(pk1..u, m) = sk_. However, this requirement is complex and hard to enforce in implementations. The algorithms _NonceGen_ and _Sign_ specified in this BIP are effectively restricted to constant functions _fsk(\_, \_) = sk_. In other words, their usage ensure that the secret key _sk_ of the signers is determined entirely when invoking _NonceGen_, which is enforced easily by letting _NonceGen_ take the corresponding individual public key _pk_ as input and checking _pk_ against _IndividualPubKey(sk)_ in _Sign_. ## Acknowledgements We thank Brandon Black, Riccardo Casatta, Sivaram Dhakshinamoorthy, Lloyd Fournier, Russell O'Connor, and Pieter Wuille for their contributions to this document.