Re: [bitcoin-dev] Composable MuSig

[ZmnSCPxj <ZmnSCPxj@protonmail.com>]

Good morning Lloyd,

> The real
> question is what properties does the commitment scheme need to be
> appropriate for MuSig R coin tossing?

It seems to me that what is needed for a composable MuSig is to have a commitment scheme which is composable.

Let me define a composable commitment scheme:

Given:

* `A` and `B`, two points to be committed to.
* `c[A]` and `c[B]`, commitments to the above points respectively.
* `r[A]` and `r[B]`, openings of the above commitments respectively.

Then a composable commitment scheme must have these operations:

* `ComposeCommitments(c[A], c[B])`, which returns a commitment to the point `A + B`.
* `ComposeOpenings(r[A], r[B])`, which returns an opening of the above commitment to the point `A + B`.

My multi-`R` proposal is a composable commitment scheme:

* A commitment `c[A]` is the list `{h(A)}` where `h()` is some hash function.
* `ComposeCommitments(c[A], c[B])` is the concatenation on lists of hashes of points.
* An opening `r[A]` is the list `{A}`.
* `ComposeOpenings(r[A], r[B])` is the concatenation on lists of points.

The property we want to have, is that:

* There must not exist some operation `NegateCommitment(c[A])`, such that:
  * `ComposeCommitments(ComposeCommitments(c[B], NegateCommitment(c[A])), c[A]) == c[B]`.

My multi-`R` proposal works as a composable commitment scheme appropriate for composable MuSig because there is no way to create an input to a concatenation operation such that the concatenation operation becomes a "search and delete" operation.
Pedersen and ElGamal commitments, I think, cannot work here, because commitments in those schemes are negatable in such a way that composing the commitments allows a commitment to be cancelled.

-----

Let us now turn to signature schemes.
I conjecture that the Schnorr and ECDSA signature schemes are also commitment schemes on points.

To create a commitment `c[A]` on the point A, such that `A = a * G`, the committer:

* Generates random scalars `r` and `m`.
* Computes `R` as `r * G`.
* Computes `s` as `r + h(R | m) * a`.
* Gives `c[A]` as the tuple `(R, s)`.

The opening `r[A]` of the above is then the tuple `(m, A)`.
The verifier then validates that the commitment was indeed to the point `A` by doing the below:

* Computes `S[validator]` as `R + h(R | m) * A`.
* Validates that `S[validator] == s * G`.

Now, we know that signatures can be composed in such a way that points (public keys) cannot be cancelled, i.e. preventing the creation of a `NegateCommitment()` operation.
Thus, a signature can be used as a composable commitment in composable MuSig scheme.

In summary, I conjecture that:

* We need a composable commitment scheme that does not allow cancellation, and any such commitment scheme can be "slotted" into the 3-phase MuSig framework.

Regards,
ZmnSCPxj