MuSig-DN Promises a Faster, Smaller, Cheaper Option for Secure Multisig
A persistent problem in cryptography is that of insufficiently random numbers.
Not-random-enough might sound like a contradiction in terms, but the issue has led to known attacks and real losses. On Thursday, the Blockstream research team introduced MuSig-DN, a proposal to overcome the vulnerabilities introduced by bad random number generators when using multisignature schemes.
Random number generators are used to create nonces, which are required as inputs when signing a message with a Schnorr or ECDSA signature. If a user signs multiple messages using nonces from a biased random number generator, that could potentially give an attacker enough information to extract the private key used to sign those messages.
Even worse is the problem of nonce reuse. This vulnerability recently appeared in the Wasabi wallet, where multiple users were given the same nonce to register for a CoinJoin.
The best-practice solution to the key leakage problem, used by most bitcoin software today, is to generate the nonce using a hash of some secret information, such as a combination of the private key and message to be signed. This is called a deterministic nonce.
The hash function preserves the randomness and incalculability of the nonce as long as the private key is secret. The clever part of deterministic nonces is it solves nonce-reuse statelessly. If you accidentally sign the same message twice, you will reuse the nonce, but only on the same message. This is harmless as it produces the same signature.
Deterministic nonces protect against biased random number generators and nonce reuse, but the key leakage problem returns in the case of multisignature schemes. An honest user may generate a deterministic nonce, while a malicious multisig co-signer selects an arbitrary nonce.
The attacker can then request another multisignature on the same message, while signing with a maliciously chosen nonce. The aggregate signatures appear as though the victim has signed two different messages using the same nonce. As with single signature nonce reuse, the victim's private key can then be exfiltrated from the signatures.
MuSig-DN is a potential solution that prevents a malicious co-signer from selecting arbitrary nonce values to trick other participants in a multisig signing session. The novelty of the MuSig-DN scheme is that signers send their public nonces along with a zero-knowledge proof to demonstrate that the nonce was in fact generated deterministically. A zero-knowledge proof is a cryptographic protocol that proves the participant has some information, without revealing the information itself. This enables deterministic 2-round multisignatures, matching the usability of the deterministic single signature widely used today.
Zero-knowledge proofs are computationally expensive. Many privacy coins offer zero-knowledge proofs for shielded transactions alongside an unshielded option, and end up with the vast majority of transactions in clear text, negating any privacy benefits. MuSig-DN provides a function called Purify that can be used efficiently with lightweight zero-knowledge proof frameworks such as Bulletproofs, which require roughly 2% of the computational power of using a zero-knowledge proof of the IETF standard algorithm for deterministic nonces.
Speaking to the BTC Times, Blockstream CEO Dr. Adam Back said, “the MuSig-DN design makes possible robust and secure 2-round multisig, which is important for usability by reducing the number of times a user has to manually interact where for security wallets maybe in a safe and need to be fetched twice with MuSig, vs only once with MuSig-DM."
Still, it may be some time before Bitcoin users experience these improvements. MuSig requires Schnorr signature support, which is currently proposed as part of the “Taproot” soft fork.