1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id 755B6C077D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Dec 2019 01:16:03 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by fraxinus.osuosl.org (Postfix) with ESMTP id 6AC20862A9
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Dec 2019 01:16:03 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from fraxinus.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id rTBKSnSvz0Jg
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Dec 2019 01:16:01 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail2.protonmail.ch (mail2.protonmail.ch [185.70.40.22])
by fraxinus.osuosl.org (Postfix) with ESMTPS id 8131086283
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Dec 2019 01:16:01 +0000 (UTC)
Date: Sun, 08 Dec 2019 01:15:51 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=default; t=1575767752;
bh=pbgJCB50F2gY1vzpQ5oDjYh9zBRUiqqsmiCRr5oadPw=;
h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:
Feedback-ID:From;
b=lcRtlFSR1hLIFc3K4rushkZB6AbHpG7Jwv1QHq/7RH9chOYBEEw9pgOKBzEU9qqQD
uprQNqR5spS/5bMjmiog6aLzxucLbYuNc1wqdZdJj/NRlhM+lO9LIxGpseT3nx/3Dv
HUStsYozBN5TBxSyJj8/xnvfCebEhIWUt20b2YNQ=
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sun, 08 Dec 2019 01:16:03 -0000
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
|
