BIP: 327 source
Title: MuSig2 for BIP340compatible MultiSignatures
Author: Jonas Nick <jonasd.nick@gmail.com>
Tim Ruffing <crypto@timruffing.de>
Elliott Jin <elliott.jin@gmail.com>
Status: Draft
License: BSD3Clause
Type: Informational
Created: 20220322
PostHistory: 20220405: https://lists.linuxfoundation.org/pipermail/bitcoindev/2022April/020198.html [bitcoindev] MuSig2 BIP
20221011: https://lists.linuxfoundation.org/pipermail/bitcoindev/2022October/021000.html [bitcoindev] MuSig2 BIP
CommentsURI: https://github.com/bitcoin/bips/wiki/Comments:BIP0327
Table of Contents

Introduction
Abstract
This document proposes a standard for the MuSig2 multisignature scheme. The standard is compatible with BIP340 public keys and signatures. It supports tweaking, which allows deriving BIP32 child keys from aggregate public keys and creating BIP341 Taproot outputs with key and script paths.
Copyright
This document is licensed under the 3clause BSD license.
Motivation
MuSig2 is a multisignature 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 nofn multisignature scheme and not a tofn thresholdsignature scheme.)
The primary motivation is to create a standard that allows users of different software projects to jointly control Taproot outputs (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 keybased spending path.
The onchain 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 nofn policy implemented using OP_CHECKSIGADD
as introduced in (BIP342).
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, singlesigner 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 multisignature 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 noninteractive and fully compatible with BIP340 public keys.
 Two Communication Rounds: MuSig2 is faster in practice than previous threeround multisignature schemes such as MuSig1, particularly when signers are connected through highlatency anonymous links. Moreover, the need for fewer communication rounds simplifies the algorithms and reduces the probability that implementations and users make securityrelevant mistakes.
 Provable security: MuSig2 has been proven existentially unforgeable under the algebraic onemore discrete logarithm (AOMDL) assumption (instead of the discrete logarithm assumption required for singlesigner Schnorr signatures). AOMDL is a falsifiable and weaker variant of the wellstudied OMDL problem.
 Low complexity: MuSig2 has a substantially lower computational and implementation complexity than alternative schemes like MuSigDN. 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 Xonly 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. Xonly tweaking, on the other hand, allows creating a BIP341 tweak to add script paths to a Taproot output. See below for details.
 Noninteractive 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.
 Thirdparty 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 thirdparty 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 thirdparty 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. 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 gives distinct security proofs depending on the number of points that constitute a nonce. See section 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 xonly 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.
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 multisignature 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. 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 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 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 Xonly public keys. Plain public keys are byte strings of length 33 (often called compressed format). In contrast, Xonly public keys are 32byte strings defined in BIP340.
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 which stores information required for tweaking the aggregate public key (see below), and it can be used to produce an Xonly aggregate public key, or a plain aggregate public key. In order to obtain an Xonly 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, 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 Identifiying 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 highquality random generator to draw an unbiased, uniformly random value rand' . In contrast to BIP340 signing, the values k_{1} and k_{2} must not be derived deterministically from the session parameters because otherwise active adversaries can trick the victim into reusing a nonce.
The optional arguments to NonceGen enable a defenseindepth 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 defenseindepth 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) 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.
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 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 Xonly tweaking. The resulting KeyAgg Context can be used to apply another tweak with ApplyTweak or obtain the aggregate public key with GetXonlyPubkey or GetPlainPubkey.
In addition to individual public keys, the KeyAgg algorithm accepts tweaks, which modify the aggregate public key as defined in the Tweaking Definition subsection. For example, if KeyAgg is run with v = 2, is_xonly_t_{1} = false, is_xonly_t_{2} = true, then the aggregate key is first plain tweaked with tweak_{1} and then Xonly tweaked with tweak_{2}.
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 Xonly aggregate public key is required. For example, to do BIP32 derivation, you call GetPlainPubkey to be able to compute the tweak, whereas BIP341 TapTweaks require Xonly 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. On the other hand, Xonly tweaking is required for Taproot tweaking per BIP341. A Taproottweaked public key commits to a script path, allowing users to create transaction outputs that are spendable either with a MuSig2 multisignature or by providing inputs that satisfy the script path. Script path spends require a control block that contains a parity bit for the tweaked Xonly 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 Signing Flow).
Notation
The following conventions are used, with constants as defined for secp256k1. 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 y^{2} = x^{3} + 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..p1 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.
 Multiplication (⋅) of an integer and a point 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 ith byte (inclusive) to the jth byte (exclusive) of x.
 The function bytes(n, x), where x is an integer, returns the nbyte 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 32byte array, returns the 256bit unsigned integer whose most significant byte first encoding is x.
 The function lift_x(x), where x is an integer in range 0..2^{256}1, returns the point P for which x(P) = x^{[6]} and has_even_y(P), or fails if x is greater than p1 or no such point exists. The function lift_x(x) is equivalent to the following pseudocode:
 Fail if x > p1.
 Let c = x^{3} + 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 33byte 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 33byte 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 hash_{tag}(x) where tag is a UTF8 encoded tag name and x is a byte array returns the 32byte 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
 Inputs:
 The secret key sk: a 32byte 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
 Let (Q, _, _) = keyagg_ctx
 Return xbytes(Q)
 Let (Q, _, _) = keyagg_ctx
 Return cbytes(Q)
Key Sorting
 Inputs:
 The number u of individual public keys with 0 < u < 2^32
 The individual public keys pk_{1..u}: u 33byte arrays
 Return pk_{1..u} sorted in lexicographical order.
Key Aggregation
 Inputs:
 The number u of individual public keys with 0 < u < 2^32
 The individual public keys pk_{1..u}: u 33byte arrays
 Let pk2 = GetSecondKey(pk_{1..u})
 For i = 1 .. u:
 Let P_{i} = cpoint(pk_{i}); fail if that fails and blame signer i for invalid individual public key.
 Let a_{i} = KeyAggCoeffInternal(pk_{1..u}, pk_{i}, pk2).
 Let Q = a_{1}⋅P_{1} + a_{2}⋅P_{2} + ... + a_{u}⋅P_{u}
 Fail if is_infinite(Q).
 Let gacc = 1
 Let tacc = 0
 Return keyagg_ctx = (Q, gacc, tacc).
 Return hash_{KeyAgg list}(pk_{1}  pk_{2}  ...  pk_{u})
 For j = 1 .. u:
 If pk_{j} ≠ pk_{1}:
 Return pk_{j}
 If pk_{j} ≠ pk_{1}:
 Return bytes(33, 0)
 Let pk2 = GetSecondKey(pk_{1..u}):
 Return KeyAggCoeffInternal(pk_{1..u}, pk', pk2)
 Let L = HashKeys(pk_{1..u})
 If pk' = pk2:
 Return 1
 Return int(hash_{KeyAgg coefficient}(L  pk')) mod n^{[8]}
Applying Tweaks
 Inputs:
 The keyagg_ctx: a KeyAgg Context data structure
 The tweak: a 32byte 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
 Inputs:
 The secret signing key sk: a 32byte array (optional argument)
 The individual public key pk: a 33byte array (see Modifications to Nonce Generation for the reason that this argument is mandatory)
 The xonly aggregate public key aggpk: a 32byte array (optional argument)
 The message m: a byte array (optional argument)^{[9]}
 The auxiliary input extra_in: a byte array with 0 ≤ len(extra_in) ≤ 2^{32}1 (optional argument)
 Let rand' be a 32byte array freshly drawn uniformly at random
 If the optional argument sk is present:
 Let rand be the bytewise xor of sk and hash_{MuSig/aux}(rand')^{[10]}
 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 k_{i} = int(hash_{MuSig/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 k_{1} = 0 or k_{2} = 0
 Let R_{⁎,1} = k_{1}⋅G, R_{⁎,2} = k_{2}⋅G
 Let pubnonce = cbytes(R_{⁎,1})  cbytes(R_{⁎,2})
 Let secnonce = bytes(32, k_{1})  bytes(32, k_{2})  pk^{[11]}
 Return (secnonce, pubnonce)
Nonce Aggregation
 Inputs:
 The number u of pubnonces with 0 < u < 2^32
 The public nonces pubnonce_{1..u}: u 66byte arrays
 For j = 1 .. 2:
 For i = 1 .. u:
 Let R_{i,j} = cpoint(pubnonce_{i}[(j1)*33:j*33]); fail if that fails and blame signer i for invalid pubnonce.
 Let R_{j} = R_{1,j} + R_{2,j} + ... + R_{u,j}
 For i = 1 .. u:
 Return aggnonce = cbytes_ext(R_{1})  cbytes_ext(R_{2})
Session Context
The Session Context is a data structure consisting of the following elements:
 The aggregate public nonce aggnonce: a 66byte array
 The number u of individual public keys with 0 < u < 2^32
 The individual public keys pk_{1..u}: u 33byte arrays
 The number v of tweaks with 0 ≤ v < 2^32
 The tweaks tweak_{1..v}: v 32byte arrays
 The tweak modes is_xonly_t_{1..v} : v booleans
 The message m: a byte array^{[9]}
 Let (aggnonce, u, pk_{1..u}, v, tweak_{1..v}, is_xonly_t_{1..v}, m) = session_ctx
 Let keyagg_ctx_{0} = KeyAgg(pk_{1..u}); fail if that fails
 For i = 1 .. v:
 Let keyagg_ctx_{i} = ApplyTweak(keyagg_ctx_{i1}, tweak_{i}, is_xonly_t_{i}); fail if that fails
 Let (Q, gacc, tacc) = keyagg_ctx_{v}
 Let b = int(hash_{MuSig/noncecoef}(aggnonce  xbytes(Q)  m)) mod n
 Let R_{1} = cpoint_ext(aggnonce[0:33]), R_{2} = cpoint_ext(aggnonce[33:66]); fail if that fails and blame nonce aggregator for invalid aggnonce.
 Let R' = R_{1} + b⋅R_{2}
 If is_infinite(R'):
 Let final nonce R = G (see Dealing with Infinity in Nonce Aggregation)
 Else:
 Let final nonce R = R'
 Let e = int(hash_{BIP0340/challenge}(xbytes(R)  xbytes(Q)  m)) mod n
 Return (Q, gacc, tacc, b, R, e)
 Let (_, u, pk_{1..u}, _, _, _, _) = session_ctx
 Let pk = cbytes(P)
 Fail if pk not in pk_{1..u}
 Return KeyAggCoeff(pk_{1..u}, pk)
Signing
 Inputs:
 The secret nonce secnonce that has never been used as input to Sign before: a 97byte array^{[11]}
 The secret key sk: a 32byte array
 The session_ctx: a Session Context data structure
 Let (Q, gacc, _, b, R, e) = GetSessionValues(session_ctx); fail if that fails
 Let k_{1}' = int(secnonce[0:32]), k_{2}' = int(secnonce[32:64])
 Fail if k_{i}' = 0 or k_{i}' ≥ n for i = 1..2
 Let k_{1} = k_{1}', k_{2} = k_{2}' if has_even_y(R), otherwise let k_{1} = n  k_{1}', k_{2} = n  k_{2}'
 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^{[12]}
 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)
 Let s = (k_{1} + b⋅k_{2} + e⋅a⋅d) mod n
 Let psig = bytes(32, s)
 Let pubnonce = cbytes(k_{1}'⋅G)  cbytes(k_{2}'⋅G)
 If PartialSigVerifyInternal(psig, pubnonce, pk, session_ctx) (see below) returns failure, fail^{[13]}
 Return partial signature psig
Partial Signature Verification
 Inputs:
 The partial signature psig: a 32byte array
 The number u of public nonces and individual public keys with 0 < u < 2^32
 The public nonces pubnonce_{1..u}: u 66byte arrays
 The individual public keys pk_{1..u}: u 33byte arrays
 The number v of tweaks with 0 ≤ v < 2^32
 The tweaks tweak_{1..v}: v 32byte arrays
 The tweak modes is_xonly_t_{1..v} : v booleans
 The message m: a byte array^{[9]}
 The index of the signer i in the of public nonces and individual public keys with 0 < i ≤ u
 Let aggnonce = NonceAgg(pubnonce_{1..u}); fail if that fails
 Let session_ctx = (aggnonce, u, pk_{1..u}, v, tweak_{1..v}, is_xonly_t_{1..v}, m)
 Run PartialSigVerifyInternal(psig, pubnonce_{i}, pk_{i}, session_ctx)
 Return success iff no failure occurred before reaching this point.
 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)^{[14]}
 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)
 Fail if s⋅G ≠ Re_{⁎} + e⋅a⋅g'⋅P
 Return success iff no failure occurred before reaching this point.
Partial Signature Aggregation
 Inputs:
 The number u of signatures with 0 < u < 2^32
 The partial signatures psig_{1..u}: u 32byte arrays
 The session_ctx: a Session Context data structure
 Let (Q, _, tacc, _, _, R, e) = GetSessionValues(session_ctx); fail if that fails
 For i = 1 .. u:
 Let s_{i} = int(psig_{i}); fail if s_{i} ≥ 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 = s_{1} + ... + s_{u} + e⋅g⋅tacc mod n
 Return sig = xbytes(R)  bytes(32, s)
Test Vectors and Reference Code
We provide a naive, highly inefficient, and nonconstant time pure Python 3 reference implementation of the key aggregation, partial signing, and partial signature verification algorithms.
Standalone JSON test vectors are also available in the same directory, 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 sk_{1} and sk_{2} 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 sk_{1} or sk_{2} is provided to Sign. This degree of freedom may allow the adversary to perform a generalized birthday attack and thereby forge a signature (see bitcoindev mailing list post and writeup for details).
Checking pk against InvidualPubkey(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.^{[15]} Note that the scheme as given in the MuSig2 paper 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 highquality 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 section.
Deterministic and Stateless Signing for a Single Signer
 Inputs:
 The secret signing key sk: a 32byte array
 The aggregate public nonce aggothernonce (see above): a 66byte array
 The number u of individual public keys with 0 < u < 2^32
 The individual public keys pk_{1..u}: u 32byte arrays
 The number v of tweaks with 0 ≤ v < 2^32
 The tweaks tweak_{1..v}: v 32byte arrays
 The tweak methods is_xonly_t_{1..v}: v booleans
 The message m: a byte array^{[9]}
 The auxiliary randomness rand: a 32byte array (optional argument)
 If the optional argument rand is present:
 Let sk' be the bytewise xor of sk and hash_{MuSig/aux}(rand)
 Else:
 Let sk' = sk
 Let keyagg_ctx_{0} = KeyAgg(pk_{1..u}); fail if that fails
 For i = 1 .. v:
 Let keyagg_ctx_{i} = ApplyTweak(keyagg_ctx_{i1}, tweak_{i}, is_xonly_t_{i}); fail if that fails
 Let aggpk = GetPubkey(keyagg_ctx_{v})
 Let k_{i} = int(hash_{MuSig/deterministic/nonce}(sk'  aggothernonce  aggpk  bytes(8, len(m))  m  bytes(1, i  1))) mod n for i = 1,2
 Fail if k_{1} = 0 or k_{2} = 0
 Let R_{⁎,1} = k_{1}⋅G, R_{⁎,2} = k_{2}⋅G
 Let pubnonce = cbytes(R_{⁎,2})  cbytes(R_{⁎,2})
 Let d = int(sk)
 Fail if d = 0 or d ≥ n
 Let pk = cbytes(d⋅G)
 Let secnonce = bytes(32, k_{1})  bytes(32, k_{2})  pk
 Let aggnonce = NonceAgg((pubnonce, aggothernonce)); fail if that fails and blame nonce aggregator for invalid aggothernonce.
 Let session_ctx = (aggnonce, u, pk_{1..u}, v, tweak_{1..v}, is_xonly_t_{1..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:
 Inputs:
 P: a point
 The tweak t: an integer with 0 ≤ t < n
 Return P + t⋅G
 Return with_even_y(P) + t⋅G
Negation Of The Secret Key When Signing
In order to produce a partial signature for an Xonly aggregate public key that is an aggregate of u individual public keys and tweaked v times (Xonly or plain), the Sign algorithm may need to negate the secret key during the signing process.
• P_{i} as computed in KeyAgg is the point corresponding to the ith signer's individual public key. Defining d_{i}' to be the ith signer's secret key as an integer, i.e., the d' value as computed in the Sign algorithm of the ith signer, we have
P_{i} = d_{i}'⋅G .
• Q_{0} is the aggregate of the individual public keys. It is identical to value Q computed in KeyAgg and therefore defined as
Q_{0} = a_{1}⋅P_{1} + a_{2}⋅P_{2} + ... + a_{u}⋅P_{u}.
• Q_{i} is the tweaked aggregate public key after the ith execution of ApplyTweak for 1 ≤ i ≤ v. It holds that
Q_{i} = f(i1) + t_{i}⋅G for i = 1, ..., v where
f(i1) := with_even_y(Q_{i1}) if is_xonly_t_{i} and
f(i1) := Q_{i1} otherwise.
• with_even_y(Q_{v}) 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 Xonly public key with_even_y(Q_{v}).
f(i1) = g_{i1}⋅Q_{i1} for 1 ≤ i ≤ v.
Furthermore, the Sign and PartialSigVerify algorithms set value g depending on whether Q_{v} needed to be negated to produce the (Xonly) final output. For consistency, this value g is referred to as g_{v} in this section.
with_even_y(Q_{v}) = g_{v}⋅Q_{v}.
with_even_y(Q_{v})
= g_{v}⋅Q_{v}
= g_{v}⋅(f(v1) + t_{v}⋅G)
= g_{v}⋅(g_{v1}⋅(f(v2) + t_{v1}⋅G) + t_{v}⋅G)
= g_{v}⋅g_{v1}⋅f(v2) + g_{v}⋅(t_{v} + g_{v1}⋅t_{v1})⋅G
= g_{v}⋅g_{v1}⋅f(v2) + (sum_{i=v1..v} t_{i}⋅prod_{j=i..v} g_{j})⋅G
= g_{v}⋅g_{v1}⋅...⋅g_{1}⋅f(0) + (sum_{i=1..v} t_{i}⋅prod_{j=i..v} g_{j})⋅G
= g_{v}⋅...⋅g_{0}⋅Q_{0} + g_{v}⋅tacc_{v}⋅G
where tacc_{i} is computed by KeyAgg and ApplyTweak as follows:
tacc_{0} = 0
tacc_{i} = t_{i} + g_{i1}⋅tacc_{i1} for i=1..v mod n
for which it holds that g_{v}⋅tacc_{v} = sum_{i=1..v} t_{i}⋅prod_{j=i..v} g_{j}.
gacc_{0} = 1
gacc_{i} = g_{i1}⋅gacc_{i1} for i=1..v mod n
So we can rewrite above equation for the final public key as
with_even_y(Q_{v}) = g_{v}⋅gacc_{v}⋅Q_{0} + g_{v}⋅tacc_{v}⋅G.
with_even_y(Q_{v})  g_{v}⋅tacc_{v}⋅G
= g_{v}⋅gacc_{v}⋅Q_{0}
= g_{v}⋅gacc_{v}⋅(a_{1}⋅P_{1} + ... + a_{u}⋅P_{u})
= g_{v}⋅gacc_{v}⋅(a_{1}⋅d_{1}'⋅G + ... + a_{u}⋅d_{u}'⋅G)
= sum_{i=1..u}(g_{v}⋅gacc_{v}⋅a_{i}⋅d_{i}')*G.
Intuitively, gacc_{i} tracks accumulated sign flipping and tacc_{i} tracks the accumulated tweak value after applying the first i individual tweaks. Additionally, g_{v} indicates whether Q_{v} needed to be negated to produce the final Xonly result. Thus, signer i multiplies its secret key d_{i}' with g_{v}⋅gacc_{v} in the Sign algorithm.
Negation Of The Individual Public Key When Partially Verifying
d = g_{v}⋅gacc_{v}⋅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.
s⋅G = Re_{⁎} + e⋅a⋅d⋅G.
d⋅G
= g_{v}⋅gacc_{v}⋅d'⋅G
= g_{v}⋅gacc_{v}⋅cpoint(pk)
Note that the aggregate public key and list of tweaks are inputs to partial signature verification, so the verifier can also construct g_{v} and gacc_{v}.
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) 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 (EUFCMA) 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 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 bestknown 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 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 twopoint nonces was independently proven secure in the ROM and AGM by Alper and Burdges.
Backwards Compatibility
This document proposes a standard for the MuSig2 multisignature scheme that is compatible with BIP340. MuSig2 is not compatible with ECDSA signatures traditionally used in Bitcoin.
Change Log
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 backwardcompatible way or new backwardcompatible functionality is added.
The PATCH
version is incremented for other changes that are noteworthy (bug fixes, test vectors, important clarifications, etc.).
 1.0.0 (20230326):
 Number 327 was assigned to this BIP.
 1.0.0rc.4 (20230302):
 Add expected value of pubnonce to NonceGen test vectors.
 1.0.0rc.3 (20230228):
 Improve NonceGen test vectors by not using an allzero 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.0rc.2 (20221028):
 Fix vulnerability that can occur in certain unusual scenarios (see bitcoindev mailing list: 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.0rc.1 (20221003): Submit draft BIP to the BIPs repository
 0.8.6 (20220915): Clarify that implementations do not need to support every feature and add a test vector for signing with a tweaked key
 0.8.5 (20220905): Rename some functions to improve clarity.
 0.8.4 (20220902): Make naming of nonce variants R in specifications of the algorithms and reference code easier to read and more consistent.
 0.8.3 (20220901): Overwrite secnonce in sign reference implementation to help prevent accidental reuse and add test vector for invalid secnonce.
 0.8.2 (20220830): Fix KeySort input length and add test vectors
 0.8.1 (20220826): Add DeterministicSign algorithm
 0.8.0 (20220826): Switch from Xonly to plain public key for individual public keys. This requires updating a large portion of the test vectors.
 0.7.2 (20220817): Add NonceGen and Sign/PartialSigVerify test vectors for messages longer than 32 bytes.
 0.7.1 (20220810): Extract test vectors into separate JSON file.
 0.7.0 (20220731): Change NonceGen such that output when message is not present is different from when message is present but has length 0.
 0.6.0 (20220731): Allow variable length messages, change serialization of the message in the NonceGen hash function, and add test vectors
 0.5.2 (20220626): Fix aggpk in NonceGen test vectors.
 0.5.1 (20220622): Rename "ordinary" tweaking to "plain" tweaking.
 0.5.0 (20220621): Separate ApplyTweak from KeyAgg and introduce KeyGen Context.
 0.4.0 (20220620): Allow the output of NonceAgg to be infinity and add test vectors
 0.3.2 (20220602): Add a lot of test vectors and improve handling of invalid contributions in reference code.
 0.3.1 (20220524): Add NonceGen test vectors
 0.3.0 (20220524): Hash i  1 instead of i in NonceGen
 0.2.0 (20220519): Change order of arguments in NonceGen hash function
 0.1.0 (20220519): Publication of draft BIP on the bitcoindev mailing list
Footnotes
 ^ 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.
 ^ 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.
 ^ 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.
 ^ Given a list of individual public keys, it is an open question whether a BIP340 signature valid under the corresponding aggregate public key is a proof of knowledge of all secret keys of the individual public keys.
 ^ It is an open question whether allowing arbitrary tweaks from an adversary affects the unforgeability of MuSig2.
 ^ Given a candidate X coordinate x in the range 0..p1, 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 = x^{3} + 7 mod p and they can be computed as y = ±c^{(p+1)/4} mod p (see Quadratic residue) if they exist, which can be checked by squaring and comparing with c.
 ^ The IndividualPubkey algorithm matches the key generation procedure traditionally used for ECDSA in Bitcoin
 ^ The key aggregation coefficient is computed by hashing the individual public key instead of its index, which requires one more invocation of the SHA256 compression function. However, it results in significantly simpler implementations because signers do not need to translate between public key indices before and after sorting.
 a b c d In theory, the allowed message size is restricted because SHA256 accepts byte strings only up to size of 2^611 bytes (and because of the 8byte length encoding).
 ^ 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.
 a b The algorithms as specified here assume that the secnonce is stored as a 97byte array using the serialization secnonce = bytes(32, k_{1})  bytes(32, k_{2})  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 (k_{1}, k_{2}, 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.  ^ 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.
 ^ 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.
 ^ GetSessionKeyAggCoeff(session_ctx, P) cannot fail when called from PartialSigVerifyInternal.
 ^ 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 = (_, _, pk_{1..u}, _, _, _, m) provided to the corresponding invocation of Sign'(secnonce, sk, session_ctx), adhere to the condition fsk(pk_{1..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, Lloyd Fournier, Russell O'Connor, and Pieter Wuille for their contributions to this document.