public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
To: Lloyd Fournier <lloyd.fourn@gmail.com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Composable MuSig
Date: Sun, 08 Dec 2019 01:15:51 +0000	[thread overview]
Message-ID: <5JbfLKwbVsIev2M33s366qbyuAGqz-ydB4gZ2KTFR_nCWbgZ0vWMm5UOU19jNVeMfYD3A0GPTpbuuYINwOv_F6fJS3NdxuPgMm8hGUnjbB0=@protonmail.com> (raw)
In-Reply-To: <CAH5Bsr07ZxxneRngGO=C56qODxu7FQ3r1c7NmcXYY3BZ2VEokA@mail.gmail.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



  reply	other threads:[~2019-12-08  1:16 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-11-25 11:00 [bitcoin-dev] Composable MuSig ZmnSCPxj
2019-11-29  5:50 ` Lloyd Fournier
2019-12-02  2:05   ` ZmnSCPxj
2019-12-02  3:30     ` Lloyd Fournier
2019-12-08  1:15       ` ZmnSCPxj [this message]
2019-12-08  6:10         ` Lloyd Fournier
2020-02-23  7:27 ` Erik Aronesty
2020-02-24 11:16   ` Tim Ruffing
2020-02-24 15:30     ` Erik Aronesty
2020-02-24 16:56       ` Tim Ruffing

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='5JbfLKwbVsIev2M33s366qbyuAGqz-ydB4gZ2KTFR_nCWbgZ0vWMm5UOU19jNVeMfYD3A0GPTpbuuYINwOv_F6fJS3NdxuPgMm8hGUnjbB0=@protonmail.com' \
    --to=zmnscpxj@protonmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=lloyd.fourn@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox