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
next prev parent 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 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$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=lloyd.fourn@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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