Date: Sun, 08 Dec 2019 01:15:51 +0000
To: Lloyd Fournier <lloyd.fourn@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <5JbfLKwbVsIev2M33s366qbyuAGqz-ydB4gZ2KTFR_nCWbgZ0vWMm5UOU19jNVeMfYD3A0GPTpbuuYINwOv_F6fJS3NdxuPgMm8hGUnjbB0=@protonmail.com>
In-Reply-To: <CAH5Bsr07ZxxneRngGO=C56qODxu7FQ3r1c7NmcXYY3BZ2VEokA@mail.gmail.com>
References: <u1IeyK5A7zyklXzl26UpCliJrFEsDp5SXUGbtXGBCrEWw6Wi7vNcoy4HNv2WXUTG_SBuMURDLhvh3YCwL2r53rL0Yj19TZpumYFD5WqmYL8=@protonmail.com>
 <CAH5Bsr2rsiU9gV6VsGH3ZCWGRoTz=g5hXNq37P3P6HB+MmxUAA@mail.gmail.com>
 <tvK5ZI4GmQzBkGfcYFOaUI4kgLBv7N615LV-yvyUOeYU49Ig2krXbyPOrTSwiiYNZpPYNv6GtLrSRTQf_MRwqmYeXY1VTLzinq93wNW9ex8=@protonmail.com>
 <CAH5Bsr07ZxxneRngGO=C56qODxu7FQ3r1c7NmcXYY3BZ2VEokA@mail.gmail.com>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Composable MuSig
Precedence: list

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 comm=
itment 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 comm=
itment 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 functio=
n.
* `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]) =3D=3D c[B]`.

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

-----

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

To create a commitment `c[A]` on the point A, such that `A =3D 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] =3D=3D s * G`.

Now, we know that signatures can be composed in such a way that points (pub=
lic keys) cannot be cancelled, i.e. preventing the creation of a `NegateCom=
mitment()` operation.
Thus, a signature can be used as a composable commitment in composable MuSi=
g 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 fram=
ework.

Regards,
ZmnSCPxj