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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 7AF2284B
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 23 May 2018 06:15:10 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-1857040130.protonmail.ch (mail-1857040130.protonmail.ch
[185.70.40.130])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6C555180
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 23 May 2018 06:15:09 +0000 (UTC)
Date: Wed, 23 May 2018 02:15:03 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=default; t=1527056107;
bh=jPXRp/BNrqpd2kjBvr5BykANNsflUnwyG3UREyyv6BY=;
h=Date:To:From:Reply-To:Subject:In-Reply-To:References:Feedback-ID:
From;
b=PQjjz1LPbdSYw1kaxnFyVxxADYMzyqxF8EEgu6Sa6YP9OPT4Mqxkhd4Map2eRM3gf
qriFfSEB2XcY9YGZdVHuztkH4qwVDKkQWGmAY4DmW25/vSELCJ9br/Tj4jB/nkGKZO
TbduTwpmQzTilQROmMqwNDHAs3sNS4NoOYfP/m58=
To: Pieter Wuille <pieter.wuille@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <D3Cs5IbxxGQ_EvtMsOnbyOJGiGScqJN-fWeT82tGoOTN5zcLGZOvpMLZAoSwgQzOEUgEyUcSvHkWw26FiAqAUJGtMST9BmEkZC8nYsrnyPI=@protonmail.com>
In-Reply-To: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@mail.gmail.com>
References: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@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
X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, FROM_LOCAL_NOVOWEL,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 23 May 2018 12:21:32 +0000
Subject: Re: [bitcoin-dev] Should Graftroot be optional?
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Wed, 23 May 2018 06:15:10 -0000
Good morning Pieter and list,
It seems to me, naively, that it would be better to make Graftroot optional=
, and to somehow combine Taproot and Graftroot.
So I propose that the Taproot equation be modified to the below:
Q =3D P + H(P, g, S) * G
Where `g` is the "Graftroot flag", i.e. 0 if disable Graftroot, and 1 if en=
able Graftroot.
A Graftroot spend would need to reveal P and the Taproot script S, then sig=
n the Graftroot script using P (rather than Q).
If an output wants to use Graftroot but not Taproot, then it uses Q =3D P +=
H(P, 1, {OP_FALSE}) * G, meaning the Taproot script can never succeed. Th=
en Graftroot scripts need to be signed using P.
A simple wallet software (or hardware) that only cares about spending using=
keys `Q =3D q * G` it controls does not have to worry about accidentally s=
igning a Graftroot script, since Q is not used to sign Graftroot scripts an=
d it would be "impossible" to derive a P + H(P, 1, S) * G from Q (using the=
same argument that it is "impossible" to derive a P + H(P, S) * G from Q i=
n Taproot).
In a multisignature setting, it would not be possible (I think) to generate=
a single private key p1 + H(P1 + P2, 1, {<p1*G> OP_CHECKSIG}) that can be =
used to kick out P2, since that would be signature cancellation attack by a=
nother path.
This increases the cost of Graftroot by one point P and a Taproot script (w=
hich could be just `OP_FALSE` if Taproot is not desired). In addition, if =
both Taproot and Graftroot are used, then using any Graftroot branch will r=
eveal the existence of a Taproot script. Similarly, using the Taproot bran=
ch reveals whether or not we also had some (hidden) Graftroot branch.
--
Now the above has the massive privacy loss where using Taproot reveals whet=
her or not you intended to use Graftroot too, and using Graftroot reveals w=
hether or not you intended to use Taproot.
So now let us consider the equation below instead:
Q =3D P + H(P, H(sign(P, g)), H(S)) * G
A Taproot spend reveals P, H(sign(P,g)), and S, and the witness that makes =
S succeed.
A Graftroot spend reveals P, sign(P, 1), H(S), and sign(P, Sg), and the wit=
ness that makes Sg succeed.
If we want to use Graftroot but not Taproot, then we can agree on the scrip=
t S =3D `push(random 256-bit) OP_FALSE`, which can never be made to succeed=
. On spending using Taproot, we reveal H(S) but not the S. Nobody can now=
distinguish between this and a Graftroot+Taproot spent using Graftroot. W=
e only need to store H(S), not the original S (but we do need to verify tha=
t the original S follows the correct template above).
If we want to use Taproot but not Graftroot, then we can agree to do a `sig=
n(P, 0)`, which definitely cannot be used to perform a Graftroot spend. Th=
e act of signing requires a random nonce to be generated, hence making the =
signature itself random. On spending using Graftroot, we reveal H(sign(P, =
0)) but not the signature itself. Nobody can now distinguish between this =
and a Graftroot+Taproot spent using Taproot. We only need to store H(sign(=
P, 0)), not the original signature (but we do need to verify(P, sign(P, 0))=
). Some other way of obfuscating the flag can be done, such as H(g, random=
), with the parties to the contract agreeing on the random obfuscation (but=
I am unsure of the safety of that).
In effect, instead of the Taproot contract S, we use as contract a one-leve=
l Merkle tree, with one branch being an enable/disable of Graftroot and the=
other branch being an ordinary Script.
Note that even if we are fooled into signing a message sign(P, 1), as long =
as we made sure that the output paid to a Q =3D P + H(P, H(sign(p, 0)), H(S=
)) * G in the first place, it cannot be used after-the-fact to make a non-G=
raftroot output a Graftroot output.
Simple wallets that use Q =3D q * G need not worry whether signing arbitrar=
y messages with that key might suddenly make their outputs spendable as Gra=
ftroot.
This increases Taproot spends by a hash.
This increases Graftroot spends by a point, a signature, and a hash.
--
I am not a mathematician and the above could be complete bunk.
--
The above also does not actually answer the question.
Many users of Bitcoin have been depending on the ability to sign arbitrary =
messages using a public key that is also used to protect funds. The use is=
common enough that people are asking for it for SegWit addresses: https://=
lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015818.html
Now it might be possible that a valid Script can be shown as an ordinary AS=
CII text file containing some benign-looking message. For example a messag=
e starting with "L" is OP_PUSHDATA1 (76), the next character encodes a leng=
th. So "LA" means 65 bytes of data, and the succeeding 65 bytes can be an =
arbitrary message (e.g. "LARGE AMOUNTS OF WEALTH ARE SAFE TO STORE IN BITCO=
IN, DONCHA KNOW?\n"). Someone might challenge some fund owner to prove the=
ir control of some UTXO by signing such a message. Unbeknownst to the sign=
er, the message is actually also a valid Script (`OP_PUSHDATA1(65 random by=
tes)`) that lets the challenger trivially acquire access to the funds via G=
raftroot.
Thus I think this is a valid concern and we should indeed make Graftroot be=
optional, and also ensure that the simple-signing case will not be a vulne=
rability for ordinary wallets, while keeping the property that use of Tapro=
ot and Graftroot is invisible if the onchain spend does not involve Taproot=
/Graftroot.
Regards,
ZmnSCPxj
|
