MuSig in Wasabi coinjoin protocol

[lontivero]

Notes about MuSig in Wasabi coinjoin protocol

Disclaimer: This is a very preliminar document where we can discuss the topic. My current understanding of the scheme is very incomplete and the implementation in the bitcoin protocol is still unknown (we don't know where the signature will be or how the transaction hash for signing will looks like (are we going to have a new transaction id version? IDK). In summary, take this notes as preliminary understanding about the system.

---

It seems that MuSig is the multi-signature scheme that will be used by the bitcoin protocol, this is a schnorr-based scheme that allows key aggregation, what means that a signature produced by multiple
signers looks as the same length that one produced by only one signer.

This new multi-signature scheme can be used for improving the bitcoin protocol mainly in two ways: providing a better multisig script and allowing to have just one signature for the entire transaction instead of having one signature per input. In case the highlighted part is really implemented, it could be very important for Wallet because it could make the coinjoin transactions smaller (cheaper), which in turn
would allow us to implement some "crazy" ideas as sending anonymously "by free" (see the quotation marks)

Wasabi coinjoin protocol changes

A common misunderstanding in the team had being that given the signatures aggregation is a 3-rounds interactive process it cannot be used Wasabi coinjoin transactions. However, Wasabi coinjoin protocol is also interactive and the new signing process can be built on Wasabi.
Lets see how the Wasabi protocol could be modified to take advantage for the one signature for the entire transaction part.

At inputs registration phase

Each participant has to send the input pubkey (Xi) to the server. Wasabi doesn't need to change because those pubkeys are already available at input registration and are being extracted from the compact signatures in the input proof message.

Additionally each participant generates a new private key ri and derivates its public key Ri. The commitment ti is ti = H(Ri). The participant has to submit this commitment in the input registration message.

At confirmation phase

The coordinator shares all participants' public keys with the all the participants. With that, they can compute L as the hash of the multiplication of all the public keys: L = H(X1 * X2 +.....Xn).

Each participant computes all the values ai = H(L || Xi). And finally the aggregated public key AK = a1*X1 * a2*X2 *.....* an*Xn.

The coordinator also shares the all participants commitments ti with the all the participants. Once the commitments set is received each participant reveals its Ri to the coordinator. The coordinator verifies that each Ri received ti=H(Ri). In case it detects an error here the coordinator bans the participant and restart.

Once all the Ri were recived, the coordinator shares all the Ri with all the participants and they verify all the ti=H(Ri) as the coordinator does. Participants should not sign if that verification fails. Both coordinator and participants compute R = R1*R2*....+Rn.

At signing phase

Each participant receive the unsigned transaction and computes the signature as follow:

c= H(AK || R || m)
si=(ri + c*ai*xi) % p

Note 1 I am not sure what m represents here because participants have to sign their inputs so, the message m could be different for each one. I need to read more about this point.
Note II this will be implemented by NBitcoin by sure.

Next they send their signatures si to the coordinator who computes the final signature s as s=s1+s2+.......+sn

[nopara73]

This is awesome! I don't claim I understand all the math, but if we can make this work, then it can make Schnorr aggregation integration seamless.

I just drop it here, that maybe we could do signature aggregation even today: https://eprint.iacr.org/2017/552.pdf

[lontivero]

We can this make work. I am sure about that. Here is the document that I am reading https://eprint.iacr.org/2018/068.pdf.

Btw, I've read the paper you shared above and it is about how to create a ECDSA signature with more than one signer, that means we can have multisignature transactions that look like a simple P2[W]PKH, transaction, i mean, with this we wouldn't need OP_CHECKMULTISIG for example, or P2SH for multisignature transactions, etc. great! However it seems Bitcoin Core team is going to go for Schnorr and implement cross-inputs signature and one single signature for the complete transaction + taproot what will make this new ECDSA key aggregation obsolete to fast.

[lontivero]

In code: https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/src/modules/musig/example.c

[lontivero]

Note 1:

At confirmation time I read it was L = H(X1 * X2 *.....Xn) but in the code I see L = H(X1 || X2 ||.....Xn) where || means byte array concatenation.

// Combining public keys...  L=H(x1, x2,...,xn)
var pubkeys = alices.Select(a=>a.PubKey);
var ell = SHA256(Concat(pubkeys));

[harding]

I saw this being mentioned on Twitter and I wanted to note that cross-input signature aggregation is not something I believe is being worked on by @sipa and others for an initial implementation of schnorr and taproot in Bitcoin. As Wuille said:

With the emergence of so many ideas for improvements to Bitcoin’s script execution (MAST, Taproot, Graftroot, new sighash modes, multisignature schemes, …) there is simply too much to do everything at once. Since aggregation really interacts with all other things, it seems like the better choice to pursue later. (source, 6 July 2018)

For details, here's one of the concerning interactions.

[nopara73]

@harding Can I get a quick fact-check on my knowledge on sigaggregation?

To my understanding we will have to make 100 peers sign the same transaction, but each signature have to come on top of another one. Compared to now when we can just give out the unsigned transaction and let the signatures come in in parallel. Is that correct?

If that's true, then I'm kind of pleased to hear that sig aggregation is being pushed back a bit so there may be more chance to fix this issue (or the Tor network develops to the point where this issue wouldn't be a problem anymore.)

[harding]

@nopara73 I'm not an expert (pinging @jonasnick, who is) but my understanding is that the MuSig protocol is parallelizable, although it's multi-round unlike currently single-round coinjoin signing. Signers generate commitments to nonces and send those to all other signers (in Wasabi, this would be through the coordinator). Signers then verify all of the other commitments are valid and produce their partial signature, which can be collected and combined (again, in Wasabi through the coordinator). Assuming Wasabi's timeouts stay the same, I think this would only take a small multiple longer than the current protocol (e.g. 2x longer for the two rounds described above; I've read that maybe one of those rounds could be eliminated using some ZK fanciness).

For details, you can see an implementation here. The API is clearly documented.

A question I don't know the answer to would be how resistant the protocol would be to sabotage. E.g. can Mallory generate a nonce or partial signature that will cause the combined signature to be invalid in a way that it can't be detected that Mallory is at fault?

Finally, what MuSig does may not be the best guide to how cross-input signature aggregation (sigagg) would work because we don't know what restrictions there might be on sigagg to prevent unwanted interactions between it and other protocol features.

[jonasnick]

Thanks for the ping.

my understanding is

correct. MuSig is usually "parallelized" that way. The nonce can be likely attached to an earlier protocol message like the transaction submission to save a round.

how resistant the protocol would be to sabotage

Both key and signature aggregation work in a way such that the individual partial signatures alone can be checked for correctness, so it's trivial to find out who is dishonest.

[nopara73]

This is huge! Thanks guys!