Subject: Re: [bitcoin-dev] Composable MuSig

From: ZmnSCPxj <[email-masked]>
Date: Mon, 02 Dec 2019 02:05:01 +0000

Good morning Lloyd, and list,

> Just a quick note: I think there is a way to commit to a point properly with Pedersen commitments. Consider the following:
> COM(X) = (y*G + z*H, y*G + X)  where y and z are random and the opening is (y,z,X).  This seems to be a  unconditionally hiding and computationally binding homomorphic commitment scheme to a point based on the DL problem rather than DDH.

So the Pedersen commitment commits to a tweak on `X`, which is revealed later so we can un-tweak `X`.
Am I correct in assuming that you propose to use `X` for the contribution to `R` for a participant?
How is it different from using ElGamal commitments?

-------

Some number of people have noted, including at least one MuSig author, that in the ElGamal case it would be possible to prove your knowledge of the `q` behind `q * G`, and thus prevent the cancellation attack shown.
We already have a general proof-of-knowledge-of-secret-key, the Schnorr signature signing algorithm itself.

Thus, together with `q * G` in the ElGamal commitment, we could include a Schnorr signature using `q * G`, either of the target message itself, or any constant string.

This seems highly appropriate, yo dawg, I heard you like MuSig, so I put an aggregate in your aggregate, so you could sign (singly) while you sign (multiply).

In terms of a *composable* MuSig, e.g. MuSig(MuSig(A, B), C), both A and B will select `q[a]` and `q[b]` and will generate a shared `q[ab] * G` as the MuSig of `q[a] * G` and `q[b] * G`.
Since they know the corresponding `q[a]` and `q[b]` they will also known the contributions they each will need to generate `q[ab] * H`, but note that there is no proof of this until they reveal `q[a]` and `q[b]`, which may lead to further attacks, this time on `q[ab] * H` instead.
So at least for `q` it seems not to be a good idea, though I have not put much thought into this.

Indeed, it seems to me that signatures using the contributions `R[a]` and `R[b]` as public keys seems to be another way to commit to `R` while ensuring that your own `R` cannot have cancelled the other participant `R`.
You would have to exchange the (single) signatures of `R[a]` and `R[b]` first, however, otherwise a Wagner attack may be possible if you exchange `R[a]` and `R[b]` first (i.e. the signatures replace the `R` commitment phase of 3-phase MuSig).

The complexity of either sign-while-you-sign idea, however, is much greater.
Your signing algorithm now requires delegating to another signing algorithm, which while at least fair in that you are now signing while you sign because you aggregated while you aggregated, is more complicated to implement practically.

Regards,
ZmnSCPxj