BIP: ?
  Title: MuSig2
  Author:
  Status: Draft
  License: BSD-3-Clause
  Type: Informational
  Created: 2022-03-22

Table of Contents Introduction Abstract Copyright Motivation Design Description Notation Specification Key Sorting Key Aggregation Nonce Generation Nonce Aggregation Session Context Signing Partial Signature Verification Partial Signature Aggregation Signing Flow Test Vectors and Reference Code Remarks on Security and Correctness Tweaking Negation Of The Secret Key When Signing Negation Of The Public Key When Partially Verifying Dealing with Infinity in Nonce Aggregation Choosing the Size of the Nonce Footnotes Acknowledgements

Introduction

Abstract

This document proposes a standard for the MuSig2 protocol. The standard is compatible with BIP340 public keys and signatures. It also supports tweaking, which allows creating BIP341 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 a single Schnorr signature for the aggregate key and a message. This is more space-efficient and has lower verification costs than each signer providing an individual public key and signature. Since MuSig2 is not a threshold-signature scheme, the cooperation of all signers involved in key aggregation is required to produce a signature.

One of the primary motivations for MuSig2 is the activation of Taproot (BIP341) on the Bitcoin network, which introduced the ability to authorize transactions with Schnorr signatures. This standard allows the creation of aggregate public keys that can be used in Taproot outputs. Such outputs are indistinguishable for a blockchain observer from regular, single-signer outputs but are actually controlled by multiple signers. Moreover, by tweaking an aggregate 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. MuSig2 stands out by combining 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 three-round multi-signature protocols, particularly when signers are connected through high-latency anonymizing links. Moreover, less communication rounds simplifies the specification and reduces the probability that users make security-relevant mistakes. To prove the security of using only two communication rounds, MuSig2 relies on the algebraic one-more discrete logarithm (AOMDL) assumption instead of the discrete logarithm assumption. 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. 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: The aggregate public key created as part of this MuSig2 specification is a BIP340 X-only public key, and the signature output at the end of the protocol is a BIP340 signature that passes BIP340 verification for the aggregate key and a message. The public keys that are input to the key aggregation algorithm are also X-only public keys. Compared to compressed serialization, this adds complexity to the specification, but as X-only keys are becoming more common, the full key may not be available.
• Tweaking for BIP32 derivations and Taproot: The specification supports tweaking aggregate public keys and signing for tweaked aggregate public keys. We distinguish two modes of tweaking: Ordinary tweaking can be used to derive child aggregate public keys per BIP32. X-only tweaking, on the other hand, allows creating a BIP341 tweak to add script paths to a Taproot output. See section Tweaking below for details.
• Non-interactive signing with preprocessing: The first communication round, exchanging the nonces, can happen before the message or even the exact set of signers is determined. Therefore, the signers can view it as a preprocessing step. Later, when the parameters of the signing session are chosen, they can send partial signatures without additional interaction.
• Key aggregation optionally independent of order: The output of the key aggregation algorithm depends on the order of the input public keys. The specification defines an algorithm to sort the public keys before key aggregation. This will ensure the same output, independent of the initial order. Key aggregation does not sort the public keys by default because applications often already have a common order of signers. Then, sorting is unnecessary and very slow for a large set of signers compared to the rest of the MuSig2 protocol. In the worst case, sorting algorithms in standard libraries can have quadratic run time, which is undesirable in adversarial settings. Nonetheless, standards using this specification can mandate sorting before aggregation. Note that the key aggregation coefficient is computed by hashing the 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.
• Third party nonce aggregation: Instead of every signer sending their nonce to every other signer, it is possible to use an untrusted third party that collects all signers' nonces, computes an aggregate nonce, and broadcasts it to the signers. This reduces the communication complexity from quadratic to linear in the number of signers. If the aggregator sends an incorrect aggregate nonce, the signing session will fail to produce a valid Schnorr signature. However, the aggregator cannot negatively affect the security of the scheme.
• Partial signature verification: If any signer sends a partial signature contribution that was not created by honestly following the protocol, the signing session will fail to produce a valid Schnorr signature. This standard specifies a partial signature verification algorithm to identify disruptive signers. It is incompatible with third-party nonce aggregation because it would be impossible to tell if a signer or the aggregator is to blame.
• MuSig2* optimization: The specification uses an optimization that allows saving a point multiplication in key aggregation. The MuSig2 scheme with this optimization is called MuSig2* and proven secure in the appendix of the MuSig2 paper. The optimization is that the second key in the list of public keys given to the key aggregation algorithm (as well as any keys identical to this key) gets the constant key aggregation coefficient 1.
• Parameterization of MuSig2 and security: In this specification, 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.

The specification itself is designed such that efficiency and clarity are balanced. The algorithms, as specified, are not optimal in terms of computation and space. In particular, some values are recomputed but can be cached in actual implementations (see Signing Flow). Also, the signers' public nonces are serialized in compressed format (33 bytes) instead of the smaller (32 bytes) but more complicated X-only serialization.

Description

When implementing the specification, make sure to understand this section thoroughly, particularly the Signing Flow, to avoid subtle mistakes that lead to catastrophic failure.

Notation

The following conventions are used, with constants as defined for secp256k1. We note that adapting this specification 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² = x³ + 7 over the integers modulo p.
  • is_infinite(P) returns whether or not 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.
  • 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 i-th byte (inclusive) to the j-th byte (exclusive) of x.
  • The function bytes(x), where x is an integer, returns the 32-byte encoding of x, most significant byte first.
  • The function bytes(P), where P is a point, returns bytes(x(P)).
  • 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, returns a || bytes(P) where a is a byte that is 2 if has_even_y(P) and 3 otherwise.
  • 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..2²⁵⁶-1, returns the point P for which x(P) = x^[1] 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 = x³ + 7 mod p.
    • Let y' = c^(p+1)/4 mod p.
    • Fail if c ≠ y'² 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 point(x), where x is a 32-byte array ("X-only" serialization), returns lift_x(int(x)). Fail if lift_x fails.
  • The function pointc(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 hash_tag(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.

Specification

Key Sorting

Input:

• The number u of public keys with 0 < u < 2^32
• The public keys pk_1..u: u 32-byte arrays

KeySort(pk_1..u):

• Return pk_1..u sorted in lexicographical order.

Key Aggregation

Input:

• The number u of public keys with 0 < u < 2^32
• The public keys pk_1..u: u 32-byte arrays
• The number v of tweaks with 0 ≤ v < 2^32
• The tweaks tweak_1..v: v 32-byte arrays
• The tweak methods is_xonly_t_1..v : v booleans

KeyAgg(pk_1..u, tweak_1..v, is_xonly_t_1..v):

• Let (Q,_,_) = KeyAggInternal(pk_1..u, tweak_1..v, is_xonly_t_1..v); fail if that fails.
• Return bytes(Q).

KeyAggInternal(pk_1..u, tweak_1..v, is_xonly_t_1..v):

• Let pk2 = GetSecondKey(pk_1..u)
• For i = 1 .. u:
  • Let P_i = point(pk_i); fail if that fails.
  • Let a_i = KeyAggCoeff'(pk_1..u, pk_i, pk2).
• Let Q₀ = a₁⋅P₁ + a₂⋅P₁ + ... + a_u⋅P_u
• Fail if is_infinite(Q₀).
• Let tacc₀ = 0
• Let gacc₀ = 1
• For i = 1 .. v:
  • Let (Q_i, gacc_i, tacc_i) = Tweak(Q_i-1, gacc_i-1, tweak_i, tacc_i-1, is_xonly_t_i); fail if that fails
• Return (Q_v, gacc_v, tacc_v).

HashKeys(pk_1..u):

• Return hash_{KeyAgg list}(pk₁ || pk₂ || ... || pk_u)

GetSecondKey(pk_1..u):

• For j = 1 .. u:
  • If pk_j ≠ pk₁:
    • Return pk_j
• Return bytes(0)

KeyAggCoeff(pk_1..u, pk'):

• Let pk2 = GetSecondKey(pk_1..u):
• Return KeyAggCoeff'(pk_1..u, pk', pk2)

KeyAggCoeff'(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

Tweak(Q_i-1, gacc_i-1, tweak_i, tacc_i-1, is_xonly_t_i):

• If is_xonly_t_i and not has_even_y(Q_i-1):
  • Let g_i-1 = -1 mod n
• Else: let g_i-1 = 1
• Let t_i = int(tweak_i); fail if t ≥ n
• Let Q_i = g_i-1⋅Q_i-1 + t_i⋅G
  • Fail if is_infinite(Q_i)
• Let gacc_i = g_i-1⋅gacc_i-1 mod n
• Let tacc_i = t_i + g_i-1⋅tacc_i-1 mod n
• Return (Q_i, gacc_i, tacc_i)

Nonce Generation

NonceGen():

• Generate two random integers k₁, k₂ in the range 1...n-1
• Let R^*₁ = k₁⋅G, R^*₂ = k₂⋅G
• Let pubnonce = cbytes(R^*₁) || cbytes(R^*₂)
• Let secnonce = bytes(k₁) || bytes(k₂)
• Return secnonce and pubnonce

Nonce Aggregation

Input:

• The number u of pubnonces with 0 < u < 2^32
• The public nonces pubnonce_1..u: u 66-byte arrays

NonceAgg(pubnonce_1..u):

• For i = 1 .. 2:
  • For j = 1 .. u:
    • Let R_i,j = pointc(pubnonce_j[(i-1)*33:i*33]); fail if that fails
  • Let R'_i = R_i,1 + R_i,2 + ... + R_i,u
  • Let R_i = R'_i if not is_infinite(R'_i), otherwise let R_i = G (see Dealing with Infinity in Nonce Aggregation)
• Return aggnonce = cbytes(R₁) || cbytes(R₂)

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 public keys with 0 < u < 2^32
• The public keys pk_1..u: u 32-byte arrays
• The number v of tweaks with 0 ≤ v < 2^32
• The tweaks tweak_1..v: v 32-byte arrays
• The tweak methods is_xonly_t_1..v : v booleans
• The message m: a 32-byte array

We write "Let (aggnonce, u, pk_1..u, v, tweak_1..v, is_xonly_t_1..v, m) = session_ctx" to assign names to the elements of a Session Context.

GetSessionValues(session_ctx):

• Let (aggnonce, u, pk_1..u, v, tweak_1..v, is_xonly_t_1..v, m) = session_ctx
• Let (Q, gacc_v, tacc_v) = KeyAggInternal(pk_1..u, tweak_1..v, is_xonly_t_1..v); fail if that fails
• Let b = int(hash_{MuSig/noncecoef}(aggnonce || bytes(Q) || m)) mod n
• Let R₁ = pointc(aggnonce[0:33]), R₂ = pointc(aggnonce[33:66]); fail if that fails
• Let R = R₁ + b⋅R₂
• Fail if is_infinite(R)
• Let e = int(hash_{BIP0340/challenge}(bytes(R) || bytes(Q) || m)) mod n
• Return (Q, gacc_v, tacc_v, b, R, e)

GetSessionKeyAggCoeff(session_ctx, P):

• Let (_, u, pk_1..u, _, _, _, _) = session_ctx
• Return KeyAggCoeff(pk_1..u, bytes(P))

Signing

Input:

• The secret nonce secnonce that has never been used as input to Sign before: a 64-byte array
• The secret key sk: a 32-byte array
• The session_ctx: a Session Context data structure

Sign(secnonce, sk, session_ctx):

• Let (Q, gacc_v, _, b, R, e) = GetSessionValues(session_ctx); fail if that fails
• Let k'₁ = int(secnonce[0:32]), k'₂ = int(secnonce[32:64])
• Fail if k'_i = 0 or k'_i ≥ n for i = 1..2
• Let k₁ = k'₁, k₂ = k'₂ if has_even_y(R), otherwise let k₁ = n - k'₁, k₂ = n - k₂
• Let d' = int(sk)
• Fail if d' = 0 or d' ≥ n
• Let P = d'⋅G
• Let a = GetSessionKeyAggCoeff(session_ctx, P); fail if that fails
• Let gp = 1 if has_even_y(P), otherwise let gp = -1 mod n
• Let g_v = 1 if has_even_y(Q), otherwise let g_v = -1 mod n
• Let d = g_v⋅gacc_v⋅gp⋅d' (See Negation Of The Secret Key When Signing)
• Let s = (k₁ + b⋅k₂ + e⋅a⋅d) mod n
• Let psig = bytes(s)
• Let pubnonce = cbytes(k'₁⋅G) || cbytes(k'₂⋅G)
• If PartialSigVerifyInternal(psig, pubnonce, bytes(P), session_ctx) (see below) returns failure, abort^[2].
• Return partial signature psig

Partial Signature Verification

Input:

• The partial signature psig: a 32-byte array
• The number u of public nonces and public keys with 0 < u < 2^32
• The public nonces pubnonce_1..u: u 66-byte arrays
• The public keys pk_1..u: u 32-byte arrays
• The number v of tweaks with 0 ≤ v < 2^32
• The tweaks tweak_1..v: v 32-byte arrays
• The tweak methods is_xonly_t_1..v : v booleans
• The message m: a 32-byte array
• The index of the signer i in the public nonces and public keys with 0 < i ≤ u

PartialSigVerify(psig, pubnonce_1..u, pk_1..u, tweak_1..v, is_xonly_t_1..v, m, i):

• 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.

Input:

• The partial signature psig: a 32-byte array
• The public nonce of the signer pubnonce: a 66-byte array
• The public key of the signer pk^* (in pk_1..u of the session_ctx): a 32-byte array
• The session_ctx: a Session Context data structure

PartialSigVerifyInternal(psig, pubnonce, pk^*, session_ctx):

• Let (Q, gacc_v, _, b, R, e) = GetSessionValues(session_ctx); fail if that fails
• Let s = int(psig); fail if s ≥ n
• Let R^*₁ = pointc(pubnonce[0:33]), R^*₂ = pointc(pubnonce[33:66])
• Let R^*' = R^*₁ + b⋅R^*₂
• Let R^* = R^*' if has_even_y(R), otherwise let R^* = -R^*'
• Let g_v = 1 if has_even_y(Q), otherwise let g_v = -1 mod n
• Let g' = g_v⋅gacc_v mod n
• Let P = g'⋅point(pk^*); fail if that fails (See Negation Of The Public Key When Partially Verifying)
• Let a = GetSessionKeyAggCoeff(session_ctx, P); fail if that fails
• Fail if s⋅G ≠ R^* + e⋅a⋅P
• Return success iff no failure occurred before reaching this point.

Partial Signature Aggregation

Input:

• The number u of signatures with 0 < u < 2^32
• The partial signatures psig_1..u: u 32-byte arrays
• The session_ctx: a Session Context data structure

PartialSigAgg(psig_1..u, session_ctx):

• Let (Q, _, tacc_v, _, _, R, e) = GetSessionValues(session_ctx); fail if that fails
• For i = 1 .. u:
  • Let s_i = int(psig_i); fail if s_i ≥ n.
• Let g_v = 1 if has_even_y(Q), otherwise let g_v = -1 mod n
• Let s = s₁ + ... + s_u + e⋅g_v⋅tacc_v mod n
• Return sig = bytes(R) || bytes(s)

Signing Flow

Note that this specification unnecessarily recomputes intermediary values (such as the aggregate and tweaked public key) that can be cached in real implementations.

There are multiple ways to use above algorithms and arrive at a final Schnorr signature. One of them can be described as follows: The signers 1 to n each run NonceGen to compute secnonce and pubnonce. Every signer sends its public key and pubnonce to every other signer and all signers agree on a single message to sign. Then, the signers run NonceAgg and Sign with their secret signing key and secnonce. They send the resulting partial signature to every other signer and combine them with the PartialSigAgg algorithm.

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 partial signatures. An implementation may invalidate the secnonce argument after Sign to avoid any reuse. Avoiding reuse also implies that the NonceGen algorithm must compute unbiased, uniformly random values k₁ and k₂.

Test Vectors and Reference Code

There are some vectors in libsecp256k1's MuSig test file. Search for the musig_test_vectors_keyagg and musig_test_vectors_sign functions.

Remarks on Security and Correctness

Tweaking

This MuSig2 specification supports two modes of tweaking that correspond to the following algorithms:

Input:

• P: a point
• The tweak t: an integer with 0 ≤ t < n

OrdinaryTweak(P, t):

• Return P + t⋅G

XonlyTweak(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 public key that is an aggregate of u X-only keys and tweaked v times (X-only or ordinarily), the Sign algorithm may need to negate the secret key during the signing process.

The following public keys arise as intermediate steps in the MuSig2 protocol:
• P_i as computed in KeyAggInternal is the point corresponding to the i-th signer's X-only public key. Defining d'_i to be the d' value as computed in the Sign algorithm of the i-th signer, we have
    P_i = with_even_y(d'_i⋅G) .
• Q₀ is an aggregate of the signer's public keys and defined in KeyAggInternal as
    Q₀ = a₁⋅P₁ + a₂⋅P₁ + ... + a_u⋅P_u.
• Q_i as computed in Tweak for 1 ≤ i ≤ v is the tweaked public key after the i-th tweaking operation. It holds that
    Q_i = f(i-1) + t_i⋅G for i = 1, ..., v where
        f(i) := with_even_y(Q_i) if is_xonly_t_i+1 and
        f(i) := Q_i otherwise.

The goal is to produce a partial signature corresponding to the output of KeyAgg, i.e., the final (X-only) public key point after v tweaking operations with_even_y(Q_v).

We define gp_i for 1 ≤ i ≤ u to be gp as computed in the Sign algorithm of the i-th signer. It holds that
    P_i = gp_i⋅d'_i⋅G.
 For 0 ≤ i ≤ v-1, the Tweak algorithm called from KeyAggInternal sets g_i to -1 mod n if and only if is_xonly_t_i+1 is true and Q_i has an odd Y coordinate. Therefore, we have
    f(i) = g_i⋅Q_i for 0 ≤ i ≤ v - 1.
 Furthermore, the Sign and PartialSigVerify algorithms set g_v such that
    with_even_y(Q_v) = g_v⋅Q_v.

So, the (X-only) final public key is
    with_even_y(Q_v)
        = g_v⋅Q_v
        = g_v⋅(f(v-1) + t_v⋅G)
        = g_v⋅(g_v-1⋅(f(v-2) + t_v-1⋅G) + t_v⋅G)
        = g_v⋅g_v-1⋅f(v-2) + g_v⋅(t_v + g_v-1⋅t_v-1)⋅G
        = g_v⋅g_v-1⋅f(v-2) + (sum_i=v-1..v t_i⋅prod_j=i..v g_j)⋅G
        = g_v⋅g_v-1⋅...⋅g₁⋅f(0) + (sum_i=1..v t_i⋅prod_j=i..v g_j)⋅G
        = g_v⋅...⋅g₀⋅Q₀ + g_v⋅tacc_v⋅G
    where tacc_i is computed by KeyAggInternal and Tweak as follows:
      tacc₀ = 0
      tacc_i = t_i + g_i-1⋅tacc_i-1 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.

KeyAggInternal and Tweak compute
    gacc₀ = 1
    gacc_i = g_i-1⋅gacc_i-1 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₀ + g_v⋅tacc_v⋅G.

Then we have
    with_even_y(Q_v) - g_v⋅tacc_v⋅G
        = g_v⋅gacc_v⋅Q₀
        = g_v⋅gacc_v⋅(a₁⋅P₁ + ... + a_u⋅P_u)
        = g_v⋅gacc_v⋅(a₁⋅gp₁⋅d'₁⋅G + ... + a_u⋅gp_u⋅d'_u⋅G)
        = sum_i=1..u(g_v⋅gacc_v⋅gp_i⋅a_i⋅d'_i)*G.

Thus, signer i multiplies its secret key d'_i with g_v⋅gacc_v⋅gp_i in the Sign algorithm.

Negation Of The Public Key When Partially Verifying

As explained in Negation Of The Secret Key When Signing the signer uses a possibly negated secret key
    d = g_v⋅gacc_v⋅gp⋅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 algorithm is supposed to check
  s⋅G = R^* + e⋅a⋅d⋅G.

The verifier doesn't have access to d⋅G, but can construct it using the xonly public key pk^* as follows:
d⋅G
    = g_v⋅gacc_v⋅gp⋅d'⋅G
    = g_v⋅gacc_v⋅point(pk^*)

Dealing with Infinity in Nonce Aggregation

If it happens that is_infinite(R'_i) inside NonceAgg there is at least one dishonest signer (except with negligible probability). If we fail here, we will never be able to determine who it is. Therefore, we continue so that the culprit is revealed when collecting and verifying partial signatures.

However, dealing with the point at infinity requires defining a serialization and may require extra code complexity in implementations. Instead of incurring this complexity, we make two modifications (compared to the MuSig2* appendix in the MuSig2 paper) to avoid infinity while still allowing us to detect the dishonest signer:

• In NonceAgg, if an output R'_i would be infinity, instead output the generator (an arbitrary choice).
• In Sign, implicitly disallow the input aggnonce to contain infinity (since the serialization format doesn't support it).

The entire NonceAgg function (both the original and modified version) only depends on publicly available data (the set of public pre-nonces from every signer). In the unforgeability proof, NonceAgg is considered to be performed by an untrusted party; thus modifications to NonceAgg do not affect the unforgeability of the scheme.

The (implicit) modification to Sign is equivalent to adding a clause, "abort if the input aggnonce contained infinity". This modification only depends on the publicly available aggnonce. Given a successful adversary against the security game (EUF-CMA) for the modified scheme, a reduction can win the security game for the original scheme by simulating the modification (i.e. checking whether to abort) towards the adversary.

We conclude that these two modifications preserve the security of the MuSig2* scheme.

Choosing the Size of the Nonce

The MuSig2 paper contains two security proofs that apply to different protocol variants. The first is for a variant where each signer's nonce consists of four elliptic curve points and uses the random oracle model (ROM). In the second variant, the signers' nonces consist of only two points. Its proof requires a stronger model, namely the combination of the ROM and the algebraic group model (AGM). 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 protocol 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 protocol 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.

Footnotes

1. ^ 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 = x³ + 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.
2. ^ Verifying the signature before leaving the signer prevents random or attacker 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.

Acknowledgements