10

2 Questions:

  • Why is Musig signing always interactive?
  • Let's say I have a Musig wallet where keys are stored in secure locations with no internet access. What are some methods to sign from these secure, offline locations given Musig interactivity constraints?
12

MuSig is interactive because each signer needs to provide a signature nonce (effectively randomness) before signing. This is not specific to MuSig, but applies to any discrete logarithm-based multisignature scheme as far as I know.

Now to understand why multiple communication rounds are necessary let's look at what happens at each of them, starting from the last, the third round:

  • Round 3 Every participant creates a partial signature with their secret key. The sum of the partial signatures is the final signature. In order to compute the sum the signers must send their partial signatures. That's one communication round.
  • Round 2 In order to create a partial signature, the signers have to compute the hash of the combined public nonce R. This is the sum of the individual signer's nonces R_i. The nonces are somewhat similar to public keys in that they are random points whose discrete logarithm is unknown to everyone else Broadcasting R_i is another round.
  • Round 1 The reason for the first round is the most difficult to understand. If the signature hash would just consist of the sum of R_i's then an attacker would have control over the outcome of the hash function. For example, the attacker could first collect every other signers R_i and then choose his R_j such that the hash output is odd. This specific example would not be helpful to the attacker, but what he can also do in a similar way is to mount a Wagner's attack which results in signature forgery. This is why in the first round, the signers send a commitment (for example SHA256(R_i)) of their nonces. Therefore they have to choose their nonce before seeing the other nonces, because they will only be revealed at round 2.

While this is a relatively intricate dance where quite a few things can go wrong, our implementation in libsecp256k1-zkp should be misuse resistant provided that you

  1. Never reuse a session id. The id can be the output of a cryptographic random number generator or an atomic counter.
  2. Never copy a signing session state. Otherwise, nonces will be reused which results in a direct leak of a secret key. Also, it allows active attacks, such as Wagner's attack.

Now it should be easy to see that offline signing is difficult with MuSig. Before shutting down the signing device you need to store active MuSig sessions on a persistent medium. That's effectively a copy of the state and very dangerous. You need to be sure that you load the correct session state when powering up again and not a corrupted or old or wrong session. For that reason, the libsecp256k1-zkp implementation does not support serializing the session state right now. However, there are some ideas for how to design a serialization format that is maximally misuse resistant.

Another aspect is that nonce commitments can be safely "pre-shared" before a message is known. That means that when setting up your offline signing devices, you start multiple sessions in parallel and exchange the nonce commitments. Then, when you want to sign a transaction, you only need to go there twice, first to get the actual nonce and then to get a partial signature. If you have only one device at a remote location you can make it so that you only go there once (by having all other decommitted nonces ready when you go there). It's important to note that as opposed to nonce commitments, nonces can not be pre-shared because that would allow yet another Wagner's attack.

There is research in progress to effectively remove the nonce commitment round and the whole session state with zero knowledge proofs. This is exciting for the offline signing case, but of course also brings increased implementation and computational complexity.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.