MuSig2 for BIP340-compatible Multi-Signatures

  BIP: 327
  Title: MuSig2 for BIP340-compatible Multi-Signatures
  Authors: Jonas Nick 
           Tim Ruffing 
           Elliott Jin 
  Status: Deployed
  Type: Informational
  Assigned: 2022-03-22
  License: BSD-3-Clause
  Discussion: 2022-04-05: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020198.html [bitcoin-dev] MuSig2 BIP
              2022-10-11: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html [bitcoin-dev] MuSig2 BIP
  Version: 1.0.3

Introduction

Abstract

This document proposes a standard for the MuSig2 multi-signature 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 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). 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). 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, 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 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. 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. X-only tweaking, on the other hand, allows creating a BIP341 tweak to add script paths to a Taproot output. See below 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, 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. 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 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. 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 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.

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 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, 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).

While the algorithms in this proposal are a