Paper 2018/068

Simple Schnorr Multi-Signatures with Applications to Bitcoin

Gregory Maxwell and Andrew Poelstra and Yannick Seurin and Pieter Wuille

Abstract

We describe a new Schnorr-based multi-signature scheme (i.e., a protocol which allows a group of signers to produce a short, joint signature on a common message) called MuSig, provably secure in the plain public-key model (meaning that signers are only required to have a public key, but do not have to prove knowledge of the private key corresponding to their public key to some certification authority or to other signers before engaging the protocol), which improves over the state-of-art scheme of Bellare and Neven (ACM-CCS 2006) and its variants by Bagherzandi et al. (ACM-CCS 2008) and Ma et al. (Des. Codes Cryptogr., 2010) in two respects: (i) it is simple and efficient, having the same key and signature size as standard Schnorr signatures; (ii) it allows key aggregation, which informally means that the joint signature can be verified exactly as a standard Schnorr signature with respect to a single ``aggregated'' public key which can be computed from the individual public keys of the signers. To the best of our knowledge, this is the first multi-signature scheme provably secure in the plain public-key model which allows key aggregation. As an application, we explain how our new multi-signature scheme could improve both performance and user privacy in Bitcoin.

Note: A flaw in the security proof of the 2-round version of MuSig that we initially proposed was recently discovered and described in ePrint report 2018/417. Although there is no known attack against it, the security of 2-round MuSig does not appear to be provable under standard assumptions with current techniques. The revised version of this paper, dated May 20, 2018, contains a security proof (under the DL assumption) for a 3-round variant of MuSig.